tsp问题Python代码

TSP（Traveling Salesman Problem）问题是一个经典的组合优化问题，目标是最小化旅行商完成所有城市访问一次并返回起点所需的总距离。这里是一个简单的 Python 代码示例，使用了遗传算法（Genetic Algorithm）作为求解策略，因为 TSP 的精确解决方案通常很复杂：

import random
from deap import base, creator, tools

# 定义问题数据结构
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)

def distance(city1, city2):
    # 这里假设city1和city2都是二维坐标列表
    return sum((a - b) ** 2 for a, b in zip(city1, city2))

def evalTSP(individual):
    total_distance = 0
    n = len(individual)
    for i in range(n):
        total_distance += distance(individual[i], individual[(i + 1) % n])
    return (total_distance,)

toolbox = base.Toolbox()
toolbox.register("attr_city", random.randint, 0, n-1)
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_city, n)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

toolbox.register("evaluate", evalTSP)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)

def main():
    pop = toolbox.population(n=50)
    hof = tools.HallOfFame(1)
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", numpy.mean)
    stats.register("std", numpy.std)
    stats.register("min", numpy.min)
    stats.register("max", numpy.max)

    pop, logbook = algorithms.eaSimple(pop, toolbox, cxpb=0.8, mutpb=0.2, ngen=500, verbose=True,
                                       halloffame=hof, stats=stats)

    print(f"Best solution found: {hof[0]}, Fitness: {hof[0].fitness.values[0]}")

if __name__ == "__main__":
    main()