基于遗传算法求解TSP：Python相关库、代码及实现步骤咨询

一、可用的Python库 #

• deap：专注于进化算法的工具库，内置丰富的遗传操作组件，适合自定义TSP的进化逻辑
• gaft：轻量级遗传算法框架，支持快速定义适应度函数与遗传算子
• pygad：API友好的入门级遗传算法库，能快速实现基础TSP求解

二、示例代码（基于deap） #

import random
from deap import base, creator, tools, algorithms

# 1. 初始化问题参数：生成10个随机坐标的城市
CITIES = [(random.randint(0, 100), random.randint(0, 100)) for _ in range(10)]
IND_SIZE = len(CITIES)

# 2. 定义适应度函数：计算路径总距离，取负值适配deap的最大化逻辑
def evalTSP(individual):
    total_distance = 0
    city_count = len(individual)
    for i in range(city_count):
        current_city = CITIES[individual[i]]
        next_city = CITIES[individual[(i+1) % city_count]]
        total_distance += ((current_city[0]-next_city[0])**2 + (current_city[1]-next_city[1])**2)**0.5
    return (-total_distance,)

# 3. 配置遗传算法核心组件
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)

toolbox = base.Toolbox()
# 生成个体：随机生成城市索引的全排列
toolbox.register("indices", random.sample, range(IND_SIZE), IND_SIZE)
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.indices)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

# 遗传操作：交叉用部分映射交叉（避免无效路径），变异用洗牌变异
toolbox.register("mate", tools.cxPartialyMatched)
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("evaluate", evalTSP)

# 4. 运行遗传算法
def main():
    random.seed(42)
    pop = toolbox.population(n=300)
    hof = tools.HallOfFame(1)  # 保存迭代过程中的最优个体
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", lambda x: sum(x)/len(x))
    stats.register("min", min)
    stats.register("max", max)

    pop, log = algorithms.eaSimple(pop, toolbox, cxpb=0.7, mutpb=0.2, ngen=100, 
                                   stats=stats, halloffame=hof, verbose=True)
    
    # 输出最优结果
    best_ind = hof[0]
    best_distance = -evalTSP(best_ind)[0]
    print("\n最优路径:", best_ind)
    print("最短距离:", round(best_distance, 2))

if __name__ == "__main__":
    main()

三、求解步骤与提示 #

核心步骤 #

1. 问题建模：确定城市坐标或预计算距离矩阵，明确目标为路径总距离最小
2. 遗传编码：用城市索引的全排列作为个体编码，确保每个城市仅出现一次
3. 适应度函数：计算个体对应的路径总距离，由于遗传算法默认最大化适应度，通常取负距离作为适应度值
4. 遗传算子配置：
   • 交叉：优先选择部分映射交叉（PMX）或顺序交叉（OX），避免产生包含重复城市的无效路径
   • 变异：使用逆转变异或交换变异，保证变异后仍为合法的城市排列
5. 种群初始化：生成足够数量的随机城市排列作为初始种群
6. 迭代优化：重复执行选择、交叉、变异操作，直到达到迭代次数或适应度收敛

关键提示 #

• 避免无效个体：TSP的个体必须是城市的全排列，禁止使用普通二进制交叉/变异操作
• 参数调优：种群规模建议设为城市数量的20-30倍；交叉概率（cxpb）通常取0.6-0.8，变异概率（mutpb）取0.1-0.3；迭代次数根据问题规模调整
• 结果验证：遗传算法得到的是近似最优解，小规模TSP可与动态规划等精确算法的结果对比验证
• 效率优化：城市数量较多时，提前预计算距离矩阵，避免每次适应度计算重复计算城市间距离

内容的提问来源于stack exchange，提问作者Jack