跳到正文
DEV Community· Josep Oriol Carné·· 13 天前AI 評分34

旅行推銷員問題:從 19 世紀謎題到遺傳算法

The Traveling Salesman Problem: From 19th Century Puzzles to Genetic Algorithms

AI 導讀

旅行推銷員問題(TSP)要求每座城市只到訪一次並返回起點,同時將總路程縮至最短;其解法研究由 19 世紀的數學謎題發展至遺傳算法。遺傳算法透過選擇、交叉和變異改進候選路線,但不保證找到最優解,適合用於精確解法難以處理的大型問題。文章並示範使用 DEAP 以 Python 求解 20 個城市的 TSP。

正文

A salesman must visit a set of cities exactly once and return home, minimizing total travel distance. This deceptively simple puzzle—the Traveling Salesman Problem (TSP)—has haunted mathematicians, computer scientists, and logistics planners for nearly two centuries. It remains one of the most studied problems in computational optimization.

Historical Origins

The TSP's roots trace to the 1830s, when Irish mathematician William Rowan Hamilton and British mathematician Thomas Kirkman studied related mathematical problems involving traversing graph vertices. Hamilton created the "Icosian Game" in 1857, a puzzle requiring players to find paths visiting each vertex of a dodecahedron exactly once.

The problem as we know it crystallized in the 1930s. Karl Menger studied the "messenger problem" in Vienna, and Hassler Whitney at Princeton coined the name "Traveling Salesman Problem." The 1940s brought the first serious computational attacks when mathematicians at RAND Corporation, including George Dantzig and Delbert Ray Fulkerson, began developing solution methods.

In 1954, Dantzig, Fulkerson, and Selmer Johnson solved a 49-city instance optimally—a remarkable achievement for the era. Their cutting-plane method laid groundwork for integer programming. By the 1970s, the TSP had become the canonical example of NP-hard problems, meaning no known algorithm can solve all instances efficiently.

Why It Matters

The TSP's significance extends far beyond academic curiosity:

Logistics and Transportation: Delivery companies, from postal services to Amazon, solve TSP variants daily. FedEx and UPS route thousands of vehicles through millions of potential paths. Even small improvements translate to massive fuel savings.

Manufacturing: Circuit board drilling, where a machine must visit thousands of holes in optimal order, is a direct TSP application. Chip fabrication uses similar routing for wire placement.

DNA Sequencing: Genome assembly involves finding optimal orderings of DNA fragments—structurally identical to TSP.

Telescope Scheduling: Astronomical surveys must observe targets across the sky efficiently, minimizing slew time between observations.

The TSP belongs to the NP-hard complexity class. For n cities, there are (n-1)!/2 possible routes. Ten cities yield 181,440 routes—tractable by brute force. Twenty cities produce over 60 quadrillion routes. Fifty cities exceed the number of atoms in the observable universe.

This exponential explosion means exact solutions become impractical beyond a few dozen cities. Real-world applications with thousands of locations require approximation methods.

Genetic Algorithms: Evolution as Optimizer

Genetic algorithms (GAs) apply biological evolution principles to optimization. A population of candidate solutions evolves through selection, crossover, and mutation, gradually improving over generations.

For TSP:

  • Individual: A sequence of cities representing a tour
  • Fitness: Total tour distance (lower is better)
  • Selection: Better solutions reproduce more frequently
  • Crossover: Combine routes from two parent solutions
  • Mutation: Randomly swap cities within a route

GAs don't guarantee optimal solutions but often find excellent approximations quickly—making them practical for large instances where exact methods fail.

Solving TSP with Python and DEAP

DEAP (Distributed Evolutionary Algorithms in Python) provides a flexible framework for implementing genetic algorithms. The library includes an official TSP example that demonstrates the core concepts. Here's an adapted version solving a 20-city TSP:

import random
import numpy as np
from deap import algorithms, base, creator, tools

# Generate 20 random cities as (x, y) coordinates
NUM_CITIES = 20
random.seed(42)
CITIES = [(random.uniform(0, 100), random.uniform(0, 100)) for _ in range(NUM_CITIES)]

def distance(city1, city2):
    """Euclidean distance between two cities."""
    return np.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)

# Precompute distance matrix
DISTANCE_MATRIX = [[distance(CITIES[i], CITIES[j])
                    for j in range(NUM_CITIES)]
                   for i in range(NUM_CITIES)]

def evaluate(individual):
    """Calculate total tour distance."""
    total = DISTANCE_MATRIX[individual[-1]][individual[0]]  # Return to start
    for i in range(len(individual) - 1):
        total += DISTANCE_MATRIX[individual[i]][individual[i + 1]]
    return (total,)  # Must return tuple

# DEAP setup
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))  # Minimize
creator.create("Individual", list, fitness=creator.FitnessMin)

toolbox = base.Toolbox()

# Individual: random permutation of city indices
toolbox.register("indices", random.sample, range(NUM_CITIES), NUM_CITIES)
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.indices)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

# Genetic operators
toolbox.register("evaluate", evaluate)
toolbox.register("mate", tools.cxOrdered)  # Order crossover preserves city visits
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)

def main():
    random.seed(42)

    # Create population
    pop = toolbox.population(n=300)

    # Track best solution
    hof = tools.HallOfFame(1)

    # Statistics
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("min", np.min)
    stats.register("avg", np.mean)

    # Run evolution
    pop, log = algorithms.eaSimple(
        pop, toolbox,
        cxpb=0.7,      # Crossover probability
        mutpb=0.2,     # Mutation probability
        ngen=100,      # Generations
        stats=stats,
        halloffame=hof,
        verbose=True
    )

    best = hof[0]
    print(f"\nBest tour distance: {evaluate(best)[0]:.2f}")
    print(f"Best route: {best}")

    return pop, log, hof

if __name__ == "__main__":
    main()

Key Implementation Details

Order Crossover (cxOrdered): Standard crossover would produce invalid tours with duplicate or missing cities. Order crossover preserves visit sequences from parents while maintaining valid permutations.

Shuffle Mutation (mutShuffleIndexes): Swaps cities within a tour with probability 0.05 per position. This local modification explores neighboring solutions.

Tournament Selection: Randomly samples three individuals and picks the fittest. Balances selection pressure with diversity.

Running this code typically converges to within 5-10% of optimal for 20 cities within seconds. Larger instances may require parameter tuning or advanced techniques like island models or local search hybridization.

Beyond Basic GAs

Modern TSP solvers combine multiple techniques:

  • Lin-Kernighan heuristic: Local search that swaps edge sequences
  • Ant Colony Optimization: Probabilistic technique inspired by ant pheromone trails
  • Simulated Annealing: Accepts worse solutions with decreasing probability
  • Branch and Bound: Exact method pruning infeasible regions

The current record for proven optimal TSP solution stands at 85,900 cities, achieved in 2006 after years of computation. Practical applications typically use heuristics that find solutions within 1-2% of optimal.

Conclusion

The Traveling Salesman Problem bridges pure mathematics and practical engineering. Its simple statement belies profound computational complexity. While we can't efficiently solve it exactly for large instances, approximation methods like genetic algorithms provide useful solutions for real-world applications.

The TSP reminds us that some problems resist elegant solutions. Progress comes not from breakthroughs but from accumulating clever techniques—each shaving percentages off tour lengths, each saving fuel, time, and resources at scale.

For logistics companies routing millions of packages, those percentages translate to billions of dollars. The salesman's ancient puzzle remains urgently relevant.

來源:DEV Community · dev.to