The Traveling Salesman problem (TSP) asks for a route that visits every destination once, returns home, and minimizes total distance. As destinations grow, the search becomes NP-hard: computational cost rises exponentially rather than linearly. That makes the TSP a useful optimization target for estimation methods such as genetic algorithms. section 3.3
A practical model uses randomly placed map points and represents each candidate route as an ordered list of destination indexes. Each index is a gene; together, the sequence is an individual. Route fitness is the summed Euclidean distance between consecutive points plus the final leg back to the start, so shorter paths are preferred. section 3.3.1
A genetic TSP solver can be assembled in a few direct steps:
- Generate destination coordinates, then create and plot an initial index-ordered path. section 3.3.1
- Evaluate every route by accumulating point-to-point distance and the return distance. section 3.3.1
- Register sampled destination indexes as DEAP individuals and build a population. section 3.3.1
- Run evolution while tracking population statistics and retaining the best route in a Hall of Fame. section 3.3.1
Evolving a 22-destination route
With 22 destinations including home, a DEAP population of 300 routes is evolved with crossover probability 0.7, mutation probability 0.3, and up to 200 generations. A plotted result shows a TSP solution reached in 52 generations. section 3.3 section 3.3.1
Operator choice changes how route populations evolve. A simplified TSP experiment compares selection operators and crossover behavior through population-diversity and genealogy visualizations. Mutation remains specialized to swapping route indexes, preserving the route-style representation while altering its order. section 3.4
Listing 3.15 EDL_3_3_TSP.ipynb: Evaluating the path
def evaluate_path(path):
prev_pt = None
distance = 0
for i in path: #1
pt = map[i]
if prev_pt is not None: #2
distance += math.sqrt((prev_pt[0]-pt[0]) ** 2 + (prev_pt[1]-pt[1]) ** 2)
else:
start_pt = pt
prev_pt = pt
distance += math.sqrt((start_pt[0]-pt[0]) ** 2 + (start_pt[1]-pt[1]) ** 2)
return distance, #3
evaluate_path(path)
Inspect the fitness function that closes the route and calculates its total Euclidean distance. section 3.3.1
