The travelling salesperson problem (TSP) asks for the shortest possible route that visits every location exactly once and returns to the starting location. It is a combinatorial optimization problem used in IB Computer Science HL to illustrate how a genetic algorithm can search for an approximate solution.
Each location is represented as a vertex in a weighted graph, while each connection is an edge whose weight may represent distance, time, or cost. A valid route must include every vertex once before returning to its starting vertex.
The main difficulty is the enormous number of possible routes. For a symmetric problem with locations, where travel costs are identical in both directions, the number of distinct routes is:
For 10 locations, this gives routes. As increases, checking every route using brute force quickly becomes impractical. TSP is therefore classified as NP-hard: no known algorithm can find the optimal route efficiently for every large instance.
A genetic algorithm can produce a good, although not necessarily optimal, route:
| Genetic algorithm stage | Application to TSP |
|---|---|
| Encoding | Each chromosome stores one possible ordering of locations. |
| Fitness evaluation | Shorter routes receive higher fitness scores. |
| Selection | Fitter routes are more likely to become parents. |
| Crossover | Sections of two parent routes are combined without duplicating locations. |
| Mutation | Locations are swapped or reordered to introduce variation. |
| Termination | The process stops after a set number of generations or when improvement becomes negligible. |
A common misconception is that a genetic algorithm guarantees the shortest route. It is a heuristic approach, so it usually finds a near-optimal solution but cannot prove that the solution is globally optimal.
Exam technique: Define the route constraints, explain why factorial growth makes exhaustive search inefficient, and apply each genetic algorithm stage specifically to TSP. Distinguish clearly between an exact optimal solution and an approximate solution.
