python遗传算法实现tsp问题

以下是Python实现TSP问题的遗传算法的步骤：

1.定义城市坐标和距离矩阵

import numpy as np

# 城市坐标
city_pos = np.array([[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]])

# 计算距离矩阵
def calc_dist_matrix(city_pos):
    n = city_pos.shape[0]
    dist_matrix = np.zeros((n, n))
    for i in range(n):
        for j in range(i+1, n):
            dist_matrix[i][j] = dist_matrix[j][i] = np.linalg.norm(city_pos[i] - city_pos[j])
    return dist_matrix

dist_matrix = calc_dist_matrix(city_pos)

2.定义遗传算法的参数

POP_SIZE = 50 # 种群大小
CROSS_RATE = 0.8 # 交叉概率
MUTATION_RATE = 0.02 # 变异概率
N_GENERATIONS = 500 # 迭代次数

3.定义遗传算法的主要函数

def select(pop, fitness):
    idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True, p=fitness/fitness.sum())
    return pop[idx]

def crossover(parent, pop):
    if np.random.rand() < CROSS_RATE:
        i_ = np.random.randint(0, POP_SIZE, size=1)
        cross_points = np.random.randint(0, 2, size=len(parent)).astype(np.bool)
        parent[cross_points] = pop[i_, cross_points]
    return parent

def mutate(child):
    for point in range(len(child)):
        if np.random.rand() < MUTATION_RATE:
            swap_point = np.random.randint(0, len(child))
            child[point], child[swap_point] = child[swap_point], child[point]
    return child

def translateDNA(pop):
    # 将二进制编码转换为路径
    paths = np.zeros((len(pop), dist_matrix.shape[0]), dtype=np.int)
    for i, dna in enumerate(pop):
        paths[i] = np.argsort(np.argsort(dna))
    return paths

def get_fitness(paths):
    # 计算路径的总距离
    distances = np.zeros(len(paths))
    for i, path in enumerate(paths):
        distances[i] = dist_matrix[path[-1]][path[0]]
        for j in range(1, len(path)):
            distances[i] += dist_matrix[path[j-1]][path[j]]
    fitness = np.exp(distances.max() - distances)
    return fitness / fitness.sum()

def evolve(pop):
    paths = translateDNA(pop)
    fitness = get_fitness(paths)
    pop = select(pop, fitness)
    pop_copy = pop.copy()
    for parent in pop:
        child = crossover(parent, pop_copy)
        child = mutate(child)
        parent[:] = child
    return pop

4.定义主函数并运行遗传算法

pop = np.random.randint(0, 2, size=(POP_SIZE, dist_matrix.shape[0]))
for i in range(N_GENERATIONS):
    pop = evolve(pop)

best_idx = np.argmax(get_fitness(translateDNA(pop)))
best_path = translateDNA(pop)[best_idx]
best_distance = get_fitness(translateDNA(pop))[best_idx]

print('最短路径：', best_path)
print('最短距离：', best_distance)