The goal of this application is to use a genetic algorithm to find solutions to several problems, primarily the travelling salesman problem.
Genetic Algorithms work by creating a population of randomly generated possible solutions to a problem. Each individual competes against others to see who will reproduce based on a fitness which is determined by how close an individual is to the best solution. Two individuals are selected, and their genetic material (pieces of the possible answer) are combined randomly. As each generation passes, the solutions evolve closer to the ideal answer. The "correct" answer may never be found, but a "close enough" answer usually is.
The solutions to the problems found on this page are of fixed size. For example, the solution to Simple Max has exactly 10 genes. Some problems allow the number of genes to increase without bounds.
Once the optimal solution is found, the algorithm continues to search, because it doesn't know if it has found the best answer yet. In order to avoid searching forever, we limit the number of generations before stopping the search.
One Max seeks to maximize the number of 1's. A gene can be either a 1 or a 0. The best solution is one where all genes are a 1 as this would give the highest number of 1's.
Simple Max seeks to maximize the value of (x1*x2*x3*x4*x5)/(x6*x7*x8*x9*x10). Each xn is a gene which can have a value of 1 to 10. The best solution is (10*10*10*10*10)/(1*1*1*1*1).
The Travelling Salesman Problem seeks to find the shortest (or least expensive) path that will allow a salesman to visit each city and return home. The optimal answer for the Square, Circle and Random maps is found quickly. The Berlin52 map takes significantly longer, since there are so many possibilities.