旅行商问题遗传算法代码并注释

旅行商问题（Traveling Salesman Problem, TSP）是一个经典的组合优化问题，它涉及到一个旅行者需要访问一定数量的城市，找到一条最短路径来完成整个旅程然后返回起点。遗传算法是一种模拟自然选择过程的计算搜索技术，常用于解决这类复杂问题。

下面是一个简单的Python遗传算法求解TSP问题的示例代码，包括初始化、交叉、变异和选择步骤，并附有基本注释：

import random
# 遗传算法参数设置
pop_size = 50      # 种群大小
gene_length = 10   # 城市数，基因长度代表城市数量
mutation_rate = 0.01  # 变异概率
crossover_rate = 0.9  # 交叉概率

# 定义城市列表 (这里假设每个城市都是一个整数)
cities = [i for i in range(1, gene_length + 1)]

def create_population(pop_size):
    """生成初始种群"""
    return [[random.randint(0, len(cities) - 1) for _ in range(gene_length)] for _ in range(pop_size)]

def fitness(route):
    """计算路线的总距离"""
    dist_matrix = [[abs(city1 - city2) for city2 in cities] for city1 in cities]
    total_distance = sum(dist_matrix[route[i]][route[i+1]] for i in range(len(route) - 1)) + dist_matrix[route[-1]][route[0]]
    return total_distance, total_distance

def selection(population, fitness_values):
    """按适应度值选择父母"""
    return [population[i] for i in sorted(range(len(fitness_values)), key=lambda k: fitness_values[k][0], reverse=True)[:pop_size // 2]]

def crossover(parents):
    """二点交叉"""
    offspring = []
    for _ in range(pop_size // 2):
        parent1, parent2 = random.sample(parents, 2)
        cut_point = random.randint(1, len(parent1) - 1)
        child = parent1[:cut_point] + parent2[cut_point:]
        offspring.append(child)
    return offspring

def mutation(offspring):
    """插入随机突变操作"""
    mutated_offspring = []
    for child in offspring:
        if random.random() < mutation_rate:
            swap_index = random.randint(0, len(child) - 1)
            child[swap_index], child[random.randint(swap_index + 1, len(child) - 1)] = child[random.randint(swap_index + 1, len(child) - 1)], child[swap_index]
        mutated_offspring.append(child)
    return mutated_offspring

def main():
    population = create_population(pop_size)
    best_fitness = None
    best_route = []

    for generation in range(100):  # 进行多次迭代
        fitness_values = [(fitness(route)[0], route) for route in population]
        selected = selection(population, fitness_values)

        offspring = crossover(selected)
        offspring = mutation(offspring)

        population = selected + offspring

        # 记录最佳解决方案
        if not best_fitness or fitness(population[0])[0] < best_fitness[0]:
            best_fitness = fitness(population[0])
            best_route = population[0]

    print("Best Route: ", best_route)
    print("Best Fitness: ", best_fitness[0])

if __name__ == "__main__":
    main()

在这个代码中，`create_population`函数生成随机的初始种群，`fitness`函数计算每条路线的总距离，`selection`函数按照适应度值选择优胜者，`crossover`和`mutation`分别负责交叉和变异操作。通过不断迭代，算法逐渐接近最优解。