H-Break

Here is my android game that I made for fun. I used Unity3D for development.

https://play.google.com/store/apps/details?id=com.diwsi.hbreak

Genetic Algorithm vs Travelling Salesman Problem

 Download demo source code HERE.

Travelling salesman problem (TSP) a NP-hard problem. A salesman must visit a certain number of cities only for once and return to start position. What is the shortest route? It is a popular problem on mathematical optimisations and computer science. Genetic algorithm is a metaheuristic method to resolve problems that inspired by biological evolution process. I tried to resolve TSP by genetic algorithm. I used pure javascript and html. Here its steps and how I applied them to the TSP.

1.Initialization
First, we need to create population. Each individual of the population is random route. To mimic biological processes, each individual must have a gene. Chromosome base on solution of problem and on TSP situation a gene is an array of city list.

2.Selection

Nature has an elimination system called 'Natural Selection'. Stronger members of the population survive and breed. Genetic algorithm uses a function called 'Fitness Function' to find out strongest individuals. The fitness function is not a generic function. It is determined by the developer based on the problem. In TSP case my fitness function measures the length of the route. Individuals with lower length route are stronger. I select top individuals, keep and breed them and replace with weaker ones. 

Here is my fitness function.

3.Genetic Operations
Chromosomal crossover is an exchange of genetic material. Nature creates better genes by using stronger parts of two different chromosomes.

 In the genetic algorithm approach I sorted population by fitness (length of the route) and apply crossover to create shorter route:

1. Select a pair of solution (route). Each solution is an index  array of city points.
   Mate 1:
   
   Mate 2: 
   
2.  Select a random point and slice Mate 1:
   
3. Fill rest of the sliced Mate 1 array by using Mate 2:
   
4. Here is the new solution (child):
   

New children populeted this way probably will have better finess result.

4.Mutation
Some mutations create crippled creatures, but some mutations are next jump in evaluation tree. Mutation adds dynamism to the population and breaks, repeating crossover loops. I added mutation if genes in pair of solution are same. Just swapped two random indices.

Mutates to

The working implemantation is down below. Also here is he github page.

Point Count:

Population Count:

---