python旅行商问题代码

Python中的旅行商问题（Traveling Salesman Problem, TSP）是一个经典的组合优化问题，它涉及到如何找到访问一系列城市的一条最短路径，以便在完成所有访问后返回起点，每个城市仅访问一次。由于其复杂性（NP完全），一般采用启发式算法或近似算法来求解，如遗传算法、模拟退火、蚁群优化等。

以下是一个简单的使用遗传算法来解决TSP问题的Python代码示例，利用了`deap`库（一个用于研究和应用进化计算的Python库）：

# 导入所需库
from deap import algorithms, base, creator, tools

# 假设我们有一个表示城市及其之间的距离矩阵
cities = [(0, 0), (1, 1), (2, 2)]  # 用元组表示坐标
distances = [ + [euclidean(city1, city2) for city2 in cities] for city1 in cities]

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

def distance(city1, city2):
    # 使用实际的计算方法（这里用简单的欧氏距离作为示例）
    return ((city1[0] - city2) ** 2 + (city1 - city2) ** 2) ** 0.5

def tour_distance(tour):
    return sum(distance(tour[i], tour[i + 1]) for i in range(len(tour) - 1)) + distance(tour[-1], tour)

def eval_tour(individual):
    return -tour_distance(individual),

toolbox = base.Toolbox()
toolbox.register("individual", tools.initCycle, creator.Individual, cities, n=2)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
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=100)
    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=1000, stats=stats, halloffame=hof, verbose=True)

    best_solution = hof
    print(f"Best solution found: {best_solution} with distance: {tour_distance(best_solution)}")

if __name__ == "__main__":
    main()