The traveling salesman problem asks for the best order in which to visit several cities, visiting each exactly once and returning to the start. “Best” may mean shortest, cheapest, or most scenic. The difficulty grows rapidly as more locations create a combinatorial explosion of possible routes. section 2.5
A genetic algorithm approaches the problem by:
- Creating an initial population of possible routes, either randomly or with heuristics. section 2.5
- Scoring each route with a fitness function, such as total distance. section 2.5
- Selecting stronger routes and combining portions of routes to produce new candidates. section 2.5
Why exhaustive search fails
The number of routes rises from 24 for four locations to 2,432,902,008,176,640,000 for twenty, making a list-and-check strategy impractical. section 2.5
Figure 2.2 Flowchart of a genetic algorithm
Use the flowchart to follow the genetic algorithm’s route-generation, evaluation, selection, and crossover cycle. section 2.5
