采用遗传算法用python写出TSP问题的代码

以下是一个使用遗传算法解决TSP问题的Python代码示例：

import random

# TSP问题的城市坐标
cities = [(60, 200), (180, 200), (80, 180), (140, 180), (20, 160),
          (100, 160), (200, 160), (140, 140), (40, 120), (100, 120),
          (180, 100), (60, 80), (120, 80), (180, 60), (20, 40), (100, 40),
          (200, 40), (20, 20), (60, 20), (160, 20)]

# 遗传算法参数
POPULATION_SIZE = 50
ELITE_SIZE = 10
MUTATION_RATE = 0.01
GENERATIONS = 100

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

# 计算一条路径的总距离
def path_distance(path):
    return sum(distance(cities[path[i]], cities[path[i+1]]) for i in range(len(path)-1))

# 初始化种群
def init_population():
    return [random.sample(range(len(cities)), len(cities)) for _ in range(POPULATION_SIZE)]

# 选择精英个体
def select_elites(population):
    return sorted(population, key=path_distance)[:ELITE_SIZE]

# 交叉操作
def crossover(parent1, parent2):
    start = random.randint(0, len(parent1)-2)
    end = random.randint(start+1, len(parent1)-1)
    child = [-1] * len(parent1)
    for i in range(start, end+1):
        child[i] = parent1[i]
    j = 0
    for i in range(len(parent2)):
        if parent2[i] not in child:
            while child[j] != -1:
                j += 1
            child[j] = parent2[i]
    return child

# 变异操作
def mutate(path):
    if random.random() < MUTATION_RATE:
        i = random.randint(0, len(path)-1)
        j = random.randint(0, len(path)-1)
        path[i], path[j] = path[j], path[i]

# 遗传算法主函数
def genetic_algorithm():
    population = init_population()
    elites = select_elites(population)
    for generation in range(GENERATIONS):
        new_population = elites[:]
        while len(new_population) < POPULATION_SIZE:
            parent1, parent2 = random.sample(elites, 2)
            child = crossover(parent1, parent2)
            mutate(child)
            new_population.append(child)
        elites = select_elites(new_population)
    return elites[0]

# 运行遗传算法并输出结果
best_path = genetic_algorithm()
print("最短路径：", best_path)
print("总距离：", path_distance(best_path))

注意：这只是一个简单的示例代码，实际应用中可能需要更复杂的遗传算法实现和更高效的优化方法。