遗传算法解决TSP问题代码

以下是遗传算法解决TSP问题的Python代码：

import random

# TSP问题中城市的数量
city_num = 20

# 种群数量
pop_size = 100

# 迭代次数
iter_num = 500

# 交叉概率
crossover_rate = 0.8

# 变异概率
mutation_rate = 0.2

# 城市坐标
city_pos = []
for i in range(city_num):
    city_pos.append((random.randint(0, 100), random.randint(0, 100)))

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

# 计算路径长度
def path_length(path):
    length = 0
    for i in range(city_num - 1):
        length += distance(city_pos[path[i]], city_pos[path[i+1]])
    length += distance(city_pos[path[0]], city_pos[path[-1]])
    return length

# 初始化种群
population = []
for i in range(pop_size):
    population.append(list(range(city_num)))
    random.shuffle(population[-1])

# 进化
for i in range(iter_num):
    # 选择
    fitness = []
    for j in range(pop_size):
        fitness.append(1 / path_length(population[j]))
    total_fitness = sum(fitness)
    selection_prob = [f / total_fitness for f in fitness]
    selected = random.choices(population, weights=selection_prob, k=pop_size)

    # 交叉
    offspring = []
    for j in range(0, pop_size, 2):
        if random.random() < crossover_rate:
            x = selected[j]
            y = selected[j+1]
            cxpoint1 = random.randint(1, city_num - 1)
            cxpoint2 = random.randint(1, city_num - 1)
            if cxpoint2 < cxpoint1:
                cxpoint1, cxpoint2 = cxpoint2, cxpoint1
            child1 = [0] * city_num
            child2 = [0] * city_num
            for k in range(cxpoint1, cxpoint2+1):
                child1[k] = y[k]
                child2[k] = x[k]
            index1 = cxpoint2+1
            index2 = cxpoint2+1
            while 0 in child1:
                if x[index1] not in child1:
                    child1[child1.index(0)] = x[index1]
                index1 = (index1 + 1) % city_num
            while 0 in child2:
                if y[index2] not in child2:
                    child2[child2.index(0)] = y[index2]
                index2 = (index2 + 1) % city_num
            offspring.append(child1)
            offspring.append(child2)
        else:
            offspring.append(selected[j])
            offspring.append(selected[j+1])

    # 变异
    for j in range(pop_size):
        if random.random() < mutation_rate:
            x = offspring[j]
            mut_point1 = random.randint(0, city_num - 1)
            mut_point2 = random.randint(0, city_num - 1)
            x[mut_point1], x[mut_point2] = x[mut_point2], x[mut_point1]

    # 更新种群
    population = offspring

# 打印最优解和路径长度
best_path = min(population, key=path_length)
print(f'Best path: {best_path}')
print(f'Path length: {path_length(best_path)}')

其中，`city_num`、`pop_size`、`iter_num`、`crossover_rate`、`mutation_rate`等参数可以根据具体问题进行调整。