Python 遗传算法求解TSP问题代码

遗传算法是一种基于生物进化原理的优化算法，用于求解最优化问题。TSP（Traveling Salesman Problem）问题是一个经典的组合优化问题，目标是找到一条最短路径，使得旅行商依次访问所有城市并回到起始城市。

下面是一个使用Python实现遗传算法求解TSP问题的代码示例：

import random

# 定义城市坐标
cities = {
    'A': (0, 0),
    'B': (1, 5),
    'C': (5, 2),
    'D': (3, 6),
    'E': (8, 3)
}

# 遗传算法参数设置
population_size = 50  # 种群大小
elite_size = 10  # 精英个体数量
mutation_rate = 0.01  # 变异率
generations = 100  # 迭代次数

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

# 创建初始种群
def create_individual():
    cities_list = list(cities.keys())
    random.shuffle(cities_list)
    return cities_list

# 计算个体的适应度（路径长度）
def fitness(individual):
    total_distance = 0
    for i in range(len(individual) - 1):
        total_distance += distance(individual[i], individual[i+1])
    total_distance += distance(individual[-1], individual[0])
    return total_distance

# 选择精英个体
def select_elite(population):
    population_fitness = [(individual, fitness(individual)) for individual in population]
    population_fitness.sort(key=lambda x: x[1])
    return [individual for individual, _ in population_fitness[:elite_size]]

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

# 变异操作
def mutate(individual):
    if random.random() < mutation_rate:
        index1 = random.randint(0, len(individual) - 1)
        index2 = random.randint(0, len(individual) - 1)
        individual[index1], individual[index2] = individual[index2], individual[index1]
    return individual

# 遗传算法主函数
def genetic_algorithm():
    population = [create_individual() for _ in range(population_size)]
    for _ in range(generations):
        elite = select_elite(population)
        offspring = elite[:]
        while len(offspring) < population_size:
            parent1 = random.choice(elite)
            parent2 = random.choice(elite)
            child = crossover(parent1, parent2)
            child = mutate(child)
            offspring.append(child)
        population = offspring
    best_individual = min(population, key=fitness)
    return best_individual

# 执行遗传算法
best_path = genetic_algorithm()
best_distance = fitness(best_path)

print("最短路径：", best_path)
print("最短路径长度：", best_distance)

这段代码实现了一个简单的遗传算法来求解TSP问题。它首先定义了城市坐标和遗传算法的参数，然后实现了计算两个城市之间距离、创建初始种群、计算个体适应度、选择精英个体、交叉操作、变异操作等函数。最后，在遗传算法主函数中执行遗传算法，并输出最优路径和最优路径长度。