Traveling Salesman Problem - Java Genetic Algorithm Solution

Binary/Source/SVN/Documentation available.

Application features

• Implementation and comparison of different genetic algorithms

- unisex random mutation - crossover algorithm - 2opt heuristics + unisex random mutation - 2opt heuristics + crossover algorithm

• Open source multi platform Java application with well commented source code
• Console and GUI application mode
• Parametrized configuration
• Multi threading computation engine
• Application thread priority settings
• Simple map file formats, exporting existing maps, using external maps

- map of 192 real cities from CZ, coordinates in S-JTSK, distances in meters - fractal maps (circle, triangle, square, spiral, ... )

• Descriptive XML and PDF reports, converting XML reports to PDF
• Web support

General genetic algorithm problems

• Code the problem
• Define fitness function
• Select genetic algorithm engine (population and mutation handling, multithreading)
• Use good mutation algorithm to create offspring
• Implement random mutations
• Think about using heuristics
• Apply the right initial parameters (population size, mutation ratio, population growth)
• Initialize population
• Run the computation on proper hardware

Links

• Definition and research of Traveling Salesman Problem

http://www.tsp.gatech.edu/

• Basic description of genetic algorithms

http://en.wikipedia.org/wiki/Genetic_algorithm

• Suggested and probably best way for solving TSP using genetic algorithm and 2opt heuristic optimization described by Hiroaki Sengoku and Ikuo Yoshihara

http://www.gcd.org/sengoku/docs/arob98.pdf