python 遗传算法 TSP

遗传算法是一种用于解决优化问题的启发式算法，可以用于解决旅行商问题（TSP）。在TSP中，旅行商需要找到一条最短路径，经过所有城市且每个城市只经过一次。

下面是一个简单的Python代码示例，演示如何使用遗传算法解决TSP问题：

import random

# 初始化种群
def initial_population(num_cities, pop_size):
    population = []
    for _ in range(pop_size):
        # 随机生成一个城市序列
        cities = list(range(num_cities))
        random.shuffle(cities)
        population.append(cities)
    return population

# 计算路径长度
def calculate_distance(cities, dist_matrix):
    distance = 0
    for i in range(len(cities) - 1):
        distance += dist_matrix[cities[i]][cities[i+1]]
    distance += dist_matrix[cities[-1]][cities[0]]  # 回到起点
    return distance

# 选择父代
def selection(population, dist_matrix):
    fitnesses = [1 / calculate_distance(cities, dist_matrix) for cities in population]
    total_fitness = sum(fitnesses)
    probabilities = [fitness / total_fitness for fitness in fitnesses]
    parents = random.choices(population, probabilities, k=2)
    return parents

# 交叉操作
def crossover(parents):
    parent1, parent2 = parents
    child = [None] * len(parent1)

    start_idx = random.randint(0, len(parent1) - 1)
    end_idx = random.randint(start_idx, len(parent1) - 1)

    child[start_idx:end_idx+1] = parent1[start_idx:end_idx+1]

    remaining_cities = [city for city in parent2 if city not in child]
    idx = end_idx + 1
    for city in remaining_cities:
        if child[idx] is None:
            child[idx] = city
            idx = (idx + 1) % len(child)

    return child

# 变异操作
def mutation(child):
    idx1, idx2 = random.sample(range(len(child)), 2)
    child[idx1], child[idx2] = child[idx2], child[idx1]
    return child

# 遗传算法主循环
def genetic_algorithm(num_cities, dist_matrix, pop_size, num_generations):
    population = initial_population(num_cities, pop_size)

    for _ in range(num_generations):
        new_population = []

        for _ in range(pop_size // 2):
            parents = selection(population, dist_matrix)
            child = crossover(parents)
            if random.random() < mutation_rate:
                child = mutation(child)
            new_population.append(child)

        population = new_population

    best_solution = min(population, key=lambda cities: calculate_distance(cities, dist_matrix))
    best_distance = calculate_distance(best_solution, dist_matrix)

    return best_solution, best_distance

# 示例用法
dist_matrix = [
    [0, 2, 9, 10],
    [1, 0, 6, 4],
    [15, 7, 0, 8],
    [6, 3, 12, 0]
]
num_cities = len(dist_matrix)
pop_size = 100
num_generations = 100
mutation_rate = 0.1

best_solution, best_distance = genetic_algorithm(num_cities, dist_matrix, pop_size, num_generations)
print("Best solution:", best_solution)
print("Best distance:", best_distance)

请注意，这只是一个简单的示例，实际上你可能需要更复杂的交叉和变异操作，以及更复杂的适应度函数来适应不同问题的需求。