python 旅行商问题遗传算法

旅行商问题是一个经典的组合优化问题，它要求找到一条路径，使得旅行商能够按照最短的距离依次访问一系列城市并回到起点。遗传算法是一种启发式搜索算法，可以用来解决这个问题。

在使用遗传算法解决旅行商问题时，一般会将每个可能的路径表示为一个染色体，并使用染色体的适应度来衡量路径的优劣。遗传算法主要包括选择、交叉、变异等操作，通过不断迭代优化染色体，最终找到最优解。

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

import random

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

# 定义遗传算法参数
population_size = 50
mutation_rate = 0.01
num_generations = 100

# 初始化种群
def initialize_population():
    population = []
    cities = list(city_coords.keys())
    for _ in range(population_size):
        chromosome = random.sample(cities, len(cities))
        population.append(chromosome)
    return population

# 计算路径长度
def calculate_distance(chromosome):
    distance = 0
    for i in range(len(chromosome) - 1):
        city1 = chromosome[i]
        city2 = chromosome[i + 1]
        coord1 = city_coords[city1]
        coord2 = city_coords[city2]
        distance += ((coord1[0] - coord2[0]) ** 2 + (coord1[1] - coord2[1]) ** 2) ** 0.5
    return distance

# 计算适应度
def calculate_fitness(chromosome):
    distance = calculate_distance(chromosome)
    return 1 / distance

# 选择操作
def selection(population):
    fitness_scores = [calculate_fitness(chromosome) for chromosome in population]
    total_fitness = sum(fitness_scores)
    probabilities = [fitness / total_fitness for fitness in fitness_scores]
    selected_indices = random.choices(range(population_size), weights=probabilities, k=population_size)
    selected_population = [population[i] for i in selected_indices]
    return selected_population

# 交叉操作
def crossover(parent1, parent2):
    point1 = random.randint(0, len(parent1) - 1)
    point2 = random.randint(point1 + 1, len(parent1))
    child1 = parent1[:point1] + parent2[point1:point2] + parent1[point2:]
    child2 = parent2[:point1] + parent1[point1:point2] + parent2[point2:]
    return child1, child2

# 变异操作
def mutation(chromosome):
    if random.random() < mutation_rate:
        point1 = random.randint(0, len(chromosome) - 1)
        point2 = random.randint(0, len(chromosome) - 1)
        chromosome[point1], chromosome[point2] = chromosome[point2], chromosome[point1]
    return chromosome

# 遗传算法主循环
def genetic_algorithm():
    population = initialize_population()
    best_distance = float('inf')
    best_chromosome = None
    for _ in range(num_generations):
        population = selection(population)
        new_population = []
        while len(new_population) < population_size:
            parent1 = random.choice(population)
            parent2 = random.choice(population)
            child1, child2 = crossover(parent1, parent2)
            child1 = mutation(child1)
            child2 = mutation(child2)
            new_population.append(child1)
            new_population.append(child2)
        population = new_population
        best_chromosome = max(population, key=calculate_fitness)
        best_distance = calculate_distance(best_chromosome)
    return best_distance, best_chromosome

# 运行遗传算法
best_distance, best_chromosome = genetic_algorithm()
print('最短路径:', best_chromosome)
print('最短距离:', best_distance)

这是一个简单的示例，实际上旅行商问题的规模可能会更大，对遗传算法的参数和优化过程进行更细致的调整可以得到更好的结果。希望这个示例能帮助到你！