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.

Check out my other projects
Active forks newsletter
Get a glimpse on open source active forks. Weekly newsletter with selection of repositories and their active forks.

Comments


Comments are closed