基于遗传算法的旅行商问题Python实现与优化

旅行商问题（Travelling Salesman Problem, TSP）是组合优化领域的经典难题，其目标是在给定城市集合和距离矩阵的条件下，找到一条访问所有城市且总距离最短的闭合路径。作为NP难问题，传统精确算法在规模较大时难以高效求解，而启发式算法如遗传算法（Genetic Algorithm, GA）因其全局搜索能力和并行性，成为解决TSP的常用方法。本文将通过Python实现遗传算法求解TSP，提供完整源码并深入解析关键步骤。

一、遗传算法核心原理

遗传算法模拟自然选择与遗传机制，通过迭代优化种群中的个体（即路径）来逼近最优解。其核心流程包括：

1. 初始化种群：随机生成若干条路径作为初始解。
2. 适应度评估：计算每条路径的总距离，距离越短适应度越高。
3. 选择操作：根据适应度选择优秀个体进入下一代，常用方法有轮盘赌选择、锦标赛选择等。
4. 交叉操作：交换两个父代个体的部分基因（路径片段），生成新个体，常用方法包括顺序交叉（OX）、部分匹配交叉（PMX）等。
5. 变异操作：随机改变个体中的部分基因（如交换两个城市位置），以增强种群多样性。
6. 终止条件：达到最大迭代次数或适应度收敛时停止。

二、Python实现步骤

1. 环境准备与数据定义

首先导入必要的库，并定义城市坐标和距离矩阵。这里以随机生成的20个城市为例：

import numpy as np
import random
import matplotlib.pyplot as plt
# 生成随机城市坐标
num_cities = 20
cities = np.random.rand(num_cities, 2) * 100  # 坐标范围[0,100]
# 计算距离矩阵
def calc_distance(cities):
    num = len(cities)
    dist_matrix = np.zeros((num, num))
    for i in range(num):
        for j in range(num):
            dist_matrix[i][j] = np.linalg.norm(cities[i] - cities[j])
    return dist_matrix
dist_matrix = calc_distance(cities)

2. 初始化种群

种群中的每个个体代表一条路径，通过随机排列城市索引生成：

def init_population(pop_size, num_cities):
    population = []
    for _ in range(pop_size):
        path = list(range(num_cities))
        random.shuffle(path)
        population.append(path)
    return population
pop_size = 100  # 种群规模
population = init_population(pop_size, num_cities)

3. 适应度计算

适应度定义为路径总距离的倒数（距离越短，适应度越高）：

def calc_fitness(population, dist_matrix):
    fitness = []
    for path in population:
        total_dist = 0
        for i in range(len(path)-1):
            total_dist += dist_matrix[path[i]][path[i+1]]
        total_dist += dist_matrix[path[-1]][path[0]]  # 闭合路径
        fitness.append(1 / total_dist)  # 适应度为距离的倒数
    return fitness

4. 选择操作

采用轮盘赌选择，根据适应度概率选择父代个体：

def select_parents(population, fitness):
    fitness_sum = sum(fitness)
    prob = [f/fitness_sum for f in fitness]
    parents_idx = np.random.choice(len(population), size=2, p=prob)
    return [population[i] for i in parents_idx]

5. 交叉操作

使用顺序交叉（OX）方法生成子代：

def order_crossover(parent1, parent2):
    size = len(parent1)
    child1, child2 = [None]*size, [None]*size
    # 随机选择交叉点
    start, end = sorted(random.sample(range(size), 2))
    # 复制父代片段到子代
    child1[start:end+1] = parent1[start:end+1]
    child2[start:end+1] = parent2[start:end+1]
    # 填充剩余位置
    def fill_child(child, parent):
        current_pos = (end + 1) % size
        parent_pos = (end + 1) % size
        while None in child:
            if parent[parent_pos] not in child1:
                child[current_pos] = parent[parent_pos]
                current_pos = (current_pos + 1) % size
            parent_pos = (parent_pos + 1) % size
        return child
    child1 = fill_child(child1, parent2)
    child2 = fill_child(child2, parent1)
    return child1, child2

6. 变异操作

随机交换路径中的两个城市位置：

def swap_mutation(path, mutation_rate=0.1):
    if random.random() < mutation_rate:
        i, j = random.sample(range(len(path)), 2)
        path[i], path[j] = path[j], path[i]
    return path

7. 主算法流程

整合上述步骤，迭代优化种群：

def genetic_algorithm(cities, pop_size=100, generations=500, mutation_rate=0.1):
    dist_matrix = calc_distance(cities)
    population = init_population(pop_size, len(cities))
    best_dist = float('inf')
    best_path = None
    for gen in range(generations):
        fitness = calc_fitness(population, dist_matrix)
        # 记录当前最优解
        current_best_dist = 1 / max(fitness)
        if current_best_dist < best_dist:
            best_dist = current_best_dist
            best_path = population[np.argmax(fitness)]
        # 生成新一代种群
        new_population = []
        for _ in range(pop_size//2):
            parent1, parent2 = select_parents(population, fitness)
            child1, child2 = order_crossover(parent1, parent2)
            child1 = swap_mutation(child1, mutation_rate)
            child2 = swap_mutation(child2, mutation_rate)
            new_population.extend([child1, child2])
        population = new_population[:pop_size]  # 保持种群规模
        # 打印进度
        if gen % 50 == 0:
            print(f"Generation {gen}, Best Distance: {best_dist:.2f}")
    return best_path, best_dist
best_path, best_dist = genetic_algorithm(cities)
print(f"Optimal Path: {best_path}, Shortest Distance: {best_dist:.2f}")

三、性能优化与注意事项

1. 种群规模与迭代次数：种群规模过小会导致早熟收敛，过大则增加计算量。建议初始种群规模为50-200，迭代次数根据问题规模调整（如20城市问题可设为200-500代）。
2. 选择策略优化：轮盘赌选择可能因适应度差异过大导致过早收敛，可结合锦标赛选择（每次随机选择k个个体，保留最优者）增强多样性。
3. 交叉与变异平衡：交叉概率通常设为0.8-1.0，变异概率设为0.01-0.1。高变异率可能破坏优质解，低变异率则导致种群停滞。
4. 精英保留策略：在每一代中保留最优个体直接进入下一代，避免优质解丢失。
5. 并行化加速：遗传算法的适应度计算和种群进化过程可并行化，利用多核CPU或GPU加速（如使用multiprocessing库）。

四、可视化与结果分析

通过Matplotlib绘制最优路径和适应度变化曲线：

# 绘制最优路径
def plot_path(cities, path):
    plt.figure(figsize=(10, 6))
    x = [cities[i][0] for i in path] + [cities[path[0]][0]]
    y = [cities[i][1] for i in path] + [cities[path[0]][1]]
    plt.plot(x, y, 'o-', markersize=8)
    plt.title("Optimal TSP Path")
    plt.xlabel("X Coordinate")
    plt.ylabel("Y Coordinate")
    plt.grid(True)
    plt.show()
plot_path(cities, best_path)

五、总结与扩展

本文通过Python实现了基于遗传算法的TSP求解，核心步骤包括种群初始化、适应度计算、选择、交叉与变异。实验表明，遗传算法能有效找到近似最优解，尤其适用于大规模问题。未来可探索以下方向：

1. 结合局部搜索算法（如2-opt）进一步优化路径。
2. 使用更复杂的交叉算子（如循环交叉、基于位置的交叉）。
3. 动态调整遗传参数（如自适应变异率）。

完整源码已提供，开发者可根据实际需求调整参数或扩展功能，例如读取真实城市坐标、添加可视化交互界面等。遗传算法的灵活性和并行性使其成为解决组合优化问题的有力工具。