At the beginning of the year I finished reading Swarm intelligent, amazing book. First part of the book is more about human mind, how we think and social aspects of it, second half focuses more about evolutionary algorithm implementation and problems that can be solved using them, one of them TSP (traveling salesman problem). I decided to write my custom TSP solver, it’s not perfect and it’s not trying to be, just my playground. Genetic algorithm is much simpler than I thought before trying to implement it, there are only three steps: initialization, crossover and mutation.

Looking at evolutionary algorithm variables from TSP perspective:

  1. Initialization – random path between cities.
  2. Crossover – take random city from fittest salesman and add it to other salesman.
  3. Mutation – take random city and replace it with other random city.

Fitness – length of the path between all cities.

Fittest salesman – salesman with shortest path.

Evolution – number of times crossover and mutation had occurred.

Cheating – traveling against the rules: skipping city or visiting it more then once.

Initialize once, then repeat crossover and mutation until certain condition is met.

I started with completely random initialization, crossover and mutation and then moved to more complex one, I won’t discuss it here because implementation changes quite often as I come up with new ideas. If you want to play with it yourself, source code can be found here.

image

Source with demo

Source code contains initialization, crossover and mutation functions which might look complex, but most of the code is to make sure that salesmans can’t cheat.

Comments


Comments are closed