用Python实战遗传算法从头歌平台玩转TSP问题第一次接触遗传算法时我被那些生物学术语绕得头晕——染色体、基因、交叉、变异...直到在头歌平台用Python真正实现了一个求解旅行商问题(TSP)的遗传算法才恍然大悟原来这些概念在代码里如此直观本文将带你跳出理论迷雾用不到200行Python代码构建完整的遗传算法框架并在头歌实验环境中验证效果。我们会重点拆解三个关键环节如何用列表表示染色体、为什么适应度函数要取倒数、以及交叉变异操作的实际编码技巧。1. 环境准备与问题定义1.1 配置头歌实验环境头歌平台的Python3编程环境已经预装了numpy等科学计算库这对我们实现遗传算法非常有利。首先创建一个新实验项目建议命名为GA_TSP_solver。平台提供的可视化结果展示功能能让我们直观看到算法收敛过程。需要特别注意的是平台对计算资源有限制单次运行时间不超过60秒内存使用不超过512MB禁止使用多进程等并行计算这些限制实际上帮助我们优化算法效率。以下是基础环境检查代码import platform import numpy as np print(Python版本:, platform.python_version()) print(NumPy版本:, np.__version__) # 测试平台计算速度 %timeit sum(range(10**6))1.2 TSP问题建模假设我们要解决一个5个城市的对称TSP问题可以用距离矩阵表示城市间关系。在头歌平台中我们可以直接使用平台提供的城市坐标数据也可以手动定义测试数据# 示例距离矩阵 (5个城市) distance_matrix np.array([ [0, 10, 15, 20, 25], [10, 0, 35, 25, 30], [15, 35, 0, 30, 40], [20, 25, 30, 0, 50], [25, 30, 40, 50, 0] ]) num_cities len(distance_matrix) print(f城市数量: {num_cities})提示对称TSP指城市A到B的距离等于B到A的距离这种情况距离矩阵是对称的。非对称TSP需要调整交叉变异策略。2. 遗传算法核心组件实现2.1 染色体编码与种群初始化在TSP问题中染色体就是城市的访问顺序。我们用列表存储这个顺序例如[0,3,1,2,4]表示城市访问路径。种群则是多个这样的排列组合。def initialize_population(pop_size, num_cities): 生成初始种群 population [] for _ in range(pop_size): chromosome np.random.permutation(num_cities).tolist() population.append(chromosome) return population # 参数设置 POP_SIZE 50 MAX_GENERATIONS 100 CROSSOVER_RATE 0.8 MUTATION_RATE 0.1 population initialize_population(POP_SIZE, num_cities) print(初始种群示例:, population[:2])2.2 适应度函数设计适应度函数是遗传算法的导航系统。对于TSP问题路径越短适应度应该越高。常见做法是取路径长度的倒数def calculate_fitness(population, distance_matrix): 计算种群中每个个体的适应度 fitness [] for chromosome in population: total_distance 0 for i in range(len(chromosome)-1): from_city chromosome[i] to_city chromosome[i1] total_distance distance_matrix[from_city][to_city] # 回到起点 total_distance distance_matrix[chromosome[-1]][chromosome[0]] fitness.append(1 / total_distance) return fitness fitness_values calculate_fitness(population, distance_matrix) print(适应度示例:, fitness_values[:5])为什么用倒数而不是直接取负距离因为保证适应度始终为正数路径越短适应度增长越快便于后续的概率计算3. 遗传操作实现细节3.1 选择算子轮盘赌策略轮盘赌选择根据适应度比例分配选择概率。numpy的random.choice函数可以优雅实现def selection(population, fitness_values): 轮盘赌选择 probs np.array(fitness_values) / sum(fitness_values) selected_indices np.random.choice( len(population), sizelen(population), pprobs, replaceTrue ) return [population[i] for i in selected_indices] selected_population selection(population, fitness_values) print(选择后种群大小:, len(selected_population))3.2 交叉算子有序交叉(OX)TSP问题的交叉需要特殊处理因为简单交叉会产生非法解重复或缺失城市。有序交叉(Ordered Crossover)能保留父代序列特征def ordered_crossover(parent1, parent2): 有序交叉 size len(parent1) child1, child2 [-1]*size, [-1]*size # 随机选择交叉区间 start, end sorted(np.random.choice(range(size), 2, replaceFalse)) # 复制中间段 child1[start:end1] parent1[start:end1] child2[start:end1] parent2[start:end1] # 填充剩余位置 def fill_child(child, parent): pointer 0 for gene in parent: if gene not in child: while child[pointer] ! -1: pointer 1 child[pointer] gene return child child1 fill_child(child1, parent2) child2 fill_child(child2, parent1) return child1, child2 # 测试交叉 parent_a [0,1,2,3,4] parent_b [4,3,2,1,0] child_x, child_y ordered_crossover(parent_a, parent_b) print(f父代A: {parent_a} 父代B: {parent_b}) print(f子代X: {child_x} 子代Y: {child_y})3.3 变异算子交换突变变异操作通过随机交换两个城市位置引入多样性def swap_mutation(chromosome, mutation_rate): 交换突变 if np.random.random() mutation_rate: idx1, idx2 np.random.choice(len(chromosome), 2, replaceFalse) chromosome[idx1], chromosome[idx2] chromosome[idx2], chromosome[idx1] return chromosome # 测试变异 original [0,1,2,3,4] mutated swap_mutation(original.copy(), 1.0) # 强制变异 print(f原始: {original} - 变异后: {mutated})4. 算法整合与性能优化4.1 主循环实现将各个组件整合成完整算法def genetic_algorithm(distance_matrix, generations100): # 初始化 population initialize_population(POP_SIZE, len(distance_matrix)) best_chromosome None best_fitness 0 history [] for gen in range(generations): # 评估 fitness calculate_fitness(population, distance_matrix) # 记录最佳个体 current_best max(fitness) if current_best best_fitness: best_idx np.argmax(fitness) best_chromosome population[best_idx] best_fitness current_best history.append(1 / best_fitness) # 记录最佳路径长度 # 选择 selected selection(population, fitness) # 交叉 next_population [] for i in range(0, len(selected), 2): if i1 len(selected): next_population.extend(selected[i:i1]) break parent1, parent2 selected[i], selected[i1] if np.random.random() CROSSOVER_RATE: child1, child2 ordered_crossover(parent1, parent2) next_population.extend([child1, child2]) else: next_population.extend([parent1.copy(), parent2.copy()]) # 变异 population [swap_mutation(chromo, MUTATION_RATE) for chromo in next_population] return best_chromosome, 1/best_fitness, history # 运行算法 best_route, best_distance, history genetic_algorithm(distance_matrix) print(f最优路径: {best_route} 距离: {best_distance})4.2 参数调优技巧在头歌平台实验时我发现这些参数组合效果较好参数推荐范围影响效果种群大小50-200越大搜索空间越广但计算越慢交叉率0.7-0.9控制新个体生成速度变异率0.05-0.2防止早熟收敛的关键最大代数100-500根据问题复杂度调整调试时常见问题过早收敛增加变异率或种群多样性收敛速度慢适当提高交叉率结果不稳定增加种群大小或运行代数4.3 可视化收敛过程头歌平台支持matplotlib绘图我们可以观察算法收敛情况import matplotlib.pyplot as plt plt.plot(history, b-) plt.xlabel(Generation) plt.ylabel(Best Distance) plt.title(GA Convergence) plt.grid(True) plt.show()典型收敛曲线会呈现快速下降后逐渐平稳的趋势。如果曲线波动剧烈可能需要调整参数。