用python写一个程序，用遗传算法解决旅行商问题

在Python中，我们可以利用遗传算法（Genetic Algorithm，GA）来解决旅行商问题（Traveling Salesman Problem，TSP）。这是一个经典的组合优化问题，目标是找到从一系列城市出发、访问每个城市一次并返回起点的最短路径。

下面是一个简单的遗传算法实现旅行商问题的例子：

import random
from deap import base, creator, tools

# 初始化问题数据
def create_city_list(num_cities):
    cities = [(i, i * 5 + random.randint(0, 100)) for i in range(num_cities)]
    return cities

# 计算两个城市的距离
def distance(city1, city2):
    x1, y1 = city1
    x2, y2 = city2
    return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5

# 遗传算法核心部分
def genetic_algorithm(cities, pop_size=50, gen_num=100, mutation_rate=0.01):
    # 定义染色体（解空间）
    creator.create("FitnessMax", base.Fitness, weights=(1.0,))
    creator.create("Individual", list, fitness=creator.FitnessMax)

    toolbox = base.Toolbox()
    toolbox.register("individual", tools.initCycle, creator.Individual,
                     lambda: [random.choice(cities) for _ in range(len(cities)-1)],
                     n=pop_size)
    toolbox.register("population", tools.initRepeat, list, toolbox.individual)

    toolbox.register("evaluate", evaluate_tsp, cities=cities)
    toolbox.register("mate", tools.cxTwoPoint)
    toolbox.register("mutate", tools.mutShuffleIndexes, indpb=mutation_rate)
    toolbox.register("select", tools.selTournament, tournsize=3)

    population = toolbox.population()
    fitnesses = map(toolbox.evaluate, population)
    for ind, fit in zip(population, fitnesses):
        ind.fitness.values = fit

    for g in range(gen_num):
        offspring = toolbox.select(population, len(population))
        offspring = [toolbox.clone(ind) for ind in offspring]

        for child1, child2 in zip(offspring[::2], offspring[1::2]):
            if random.random() < 0.7:
                toolbox.mate(child1, child2)
                del child1.fitness.values
                del child2.fitness.values

        invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
        fitnesses = map(toolbox.evaluate, invalid_ind)
        for ind, fit in zip(invalid_ind, fitnesses):
            ind.fitness.values = fit

        population[:] = offspring

    best_solution = min(population, key=lambda individual: individual.fitness.values)
    return best_solution, best_solution.fitness.values[0]

# 评估函数，计算解决方案的成本
def evaluate_tsp(individual, cities):
    total_distance = sum(distance(cities[i], cities[i+1]) for i in range(len(individual)))
    total_distance += distance(cities[-1], cities[0])
    return total_distance,

# 示例使用
num_cities = 10
cities = create_city_list(num_cities)
solution, cost = genetic_algorithm(cities)
print(f"最优解：{solution}，总成本：{cost}")