企业官网建设流程全解析

用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[i+1] 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])

为什么用倒数而不是直接取负距离？因为：

1. 保证适应度始终为正数
2. 路径越短适应度增长越快
3. 便于后续的概率计算

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), size=len(population), p=probs, replace=True ) 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, replace=False)) # 复制中间段 child1[start:end+1] = parent1[start:end+1] child2[start:end+1] = parent2[start:end+1] # 填充剩余位置 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, replace=False) 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, generations=100): # 初始化 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 i+1 >= len(selected): next_population.extend(selected[i:i+1]) break parent1, parent2 = selected[i], selected[i+1] 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 参数调优技巧

在头歌平台实验时，我发现这些参数组合效果较好：

调试时常见问题：

1. 过早收敛：增加变异率或种群多样性
2. 收敛速度慢：适当提高交叉率
3. 结果不稳定：增加种群大小或运行代数

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()

典型收敛曲线会呈现快速下降后逐渐平稳的趋势。如果曲线波动剧烈，可能需要调整参数。