用Python实战遗传算法中的轮盘赌选择从理论到代码的逆向学习期中考试那道关于轮盘赌算法的题目让我栽了跟头——课堂上老师只是简单提了一句教材上更是只字未提。这种知道它存在却不知道它如何工作的感觉实在太糟糕了。于是我决定换种学习方式用代码实现它直到彻底理解每个数字如何跳动、每次选择为何发生。这就是本文的由来——一个考试失利者的代码反击战。1. 遗传算法与轮盘赌动态系统的生存法则遗传算法模拟的是自然界优胜劣汰的进化过程。想象你有一群候选解称为个体每个解都有自己的适应度fitness——就像生物的生存能力。轮盘赌选择就是决定哪些个体能够繁殖的关键机制它确保适应度高的个体有更大几率被选中同时也不完全排除适应度低的个体。为什么叫轮盘赌因为这个选择过程就像赌场里的轮盘每个个体占据轮盘的一块区域区域大小与其适应度成正比。转动轮盘时指针停在哪块区域就选中对应的个体。这种随机性保证了种群的多样性避免算法过早收敛到局部最优解。关键概念速览种群Population一组候选解的集合适应度Fitness衡量解优劣的函数值选择压力Selection Pressure高适应度个体被选中的概率优势程度2. 构建遗传算法的Python实验室让我们从零开始搭建这个数字生态系统。首先需要创建初始种群——一组随机生成的二进制串每个串代表一个潜在解。import numpy as np def initialize_population(pop_size, chromosome_length): 初始化二进制编码的种群 return np.random.randint(2, size(pop_size, chromosome_length)) # 示例创建4个个体每个个体有5位基因 population initialize_population(4, 5) print(初始种群:\n, population)接下来定义适应度函数。在考试题目中给出的是f(x)x²我们需要先将二进制串转换为十进制值def binary_to_decimal(binary_array): 将二进制数组转换为十进制数值 return binary_array.dot(2**np.arange(binary_array.size)[::-1]) def fitness_function(binary_array): 计算个体的适应度 x binary_to_decimal(binary_array) return x**2 # 题目要求的f(x)x² # 测试适应度计算 for i, individual in enumerate(population): print(f个体{i1}: {individual}, 十进制值: {binary_to_decimal(individual)}, 适应度: {fitness_function(individual)})3. 轮盘赌算法的核心实现现在来到关键部分——实现轮盘赌选择。这个算法的精妙之处在于它用累积概率分布将随机数的选择映射到具体的个体。def roulette_wheel_selection(population, fitness_values, num_parents): 轮盘赌选择实现 total_fitness sum(fitness_values) # 计算每个个体的选择概率 probabilities [f/total_fitness for f in fitness_values] # 计算累积概率分布 cumulative_probabilities np.cumsum(probabilities) selected_parents [] for _ in range(num_parents): # 生成随机数 r np.random.random() # 找到第一个累积概率大于随机数的个体 for i, cp in enumerate(cumulative_probabilities): if r cp: selected_parents.append(population[i]) break return np.array(selected_parents)为了验证我们的实现是否正确让我们用考试题目中的数据进行测试# 考试题目数据 exam_population np.array([ [1,0,1,1,0], # 个体1: 10110 [0,1,1,0,0], # 个体2: 01100 [0,1,0,0,1], # 个体3: 01001 [1,1,0,1,1] # 个体4: 11011 ]) # 计算适应度 fitness_values [fitness_function(ind) for ind in exam_population] # 使用题目给定的随机数序列进行确定性测试 def deterministic_roulette_selection(population, fitness_values, random_numbers): total_fitness sum(fitness_values) probabilities [f/total_fitness for f in fitness_values] cumulative_probabilities np.cumsum(probabilities) selected_parents [] for r in random_numbers: for i, cp in enumerate(cumulative_probabilities): if r cp: selected_parents.append(population[i]) break return np.array(selected_parents) # 题目给定的随机数序列 random_numbers [0.42, 0.16, 0.89, 0.71] selected deterministic_roulette_selection(exam_population, fitness_values, random_numbers) print(选择结果:\n, selected)提示在真实应用中我们会直接使用随机数。这里为了复现考试结果特意实现了接受预设随机数序列的版本。4. 可视化轮盘赌过程看见不可见的概率理解轮盘赌最好的方式就是可视化它的工作过程。让我们用matplotlib创建一个动态的轮盘赌演示import matplotlib.pyplot as plt def visualize_roulette_wheel(fitness_values): labels [f个体{i1} for i in range(len(fitness_values))] sizes fitness_values total sum(sizes) fig, ax plt.subplots(figsize(8, 8)) ax.set_title(轮盘赌选择可视化 (区域大小适应度)) # 绘制饼图表示轮盘 wedges, texts ax.pie(sizes, startangle90, counterclockFalse) # 模拟指针旋转 for angle in np.linspace(0, 360, 30): ax.clear() wedges, texts ax.pie(sizes, startangle90-angle, counterclockFalse) ax.set_title(f轮盘旋转中... ({angle:.0f}°)) plt.pause(0.05) # 最终停止位置使用第一个随机数 r random_numbers[0] stop_angle 360 * r ax.clear() wedges, texts ax.pie(sizes, startangle90-stop_angle, counterclockFalse) ax.set_title(f选择结果: 随机数{r:.2f}) # 标记被选中的扇形 cumulative 0 for i, size in enumerate(sizes): if r (cumulative size/total): wedges[i].set_hatch(//) ax.annotate(f选中 {labels[i]}, xywedges[i].center, xytext(10, 10), textcoordsoffset points, bboxdict(boxstyleround, fcyellow)) break cumulative size/total plt.legend(wedges, labels, title个体适应度, loccenter left, bbox_to_anchor(1, 0, 0.5, 1)) plt.tight_layout() plt.show() # 使用考试数据可视化 visualize_roulette_wheel(fitness_values)这个可视化会展示轮盘根据适应度分配的区域大小模拟指针旋转过程最终根据随机数停在某个个体区域高亮显示被选中的个体5. 从选择到进化完整的遗传算法流程轮盘赌选择只是遗传算法的一个环节。完整的遗传算法还包括初始化随机生成初始种群评估计算每个个体的适应度选择使用轮盘赌等方法选择父代交叉通过基因重组产生后代变异随机改变某些基因位替换用新种群替代旧种群终止满足条件时停止迭代让我们实现一个简单的完整遗传算法求解一个实际问题找到二进制数各位全为1的解。def genetic_algorithm(pop_size, chrom_length, max_generations, mutation_rate): # 1. 初始化 population initialize_population(pop_size, chrom_length) best_fitness [] for generation in range(max_generations): # 2. 评估 fitness_values [fitness_function(ind) for ind in population] current_best max(fitness_values) best_fitness.append(current_best) print(f第{generation1}代, 最佳适应度: {current_best}) # 检查是否找到完美解 if current_best (2**chrom_length - 1)**2: print(找到最优解!) break # 3. 选择 parents roulette_wheel_selection(population, fitness_values, pop_size//2) # 4. 交叉 (单点交叉) offspring [] for i in range(0, len(parents), 2): if i1 len(parents): break parent1, parent2 parents[i], parents[i1] crossover_point np.random.randint(1, chrom_length) child1 np.concatenate([parent1[:crossover_point], parent2[crossover_point:]]) child2 np.concatenate([parent2[:crossover_point], parent1[crossover_point:]]) offspring.extend([child1, child2]) # 5. 变异 for child in offspring: for i in range(chrom_length): if np.random.random() mutation_rate: child[i] 1 - child[i] # 翻转该位 # 6. 替换 (精英保留策略) population[:len(offspring)] offspring # 绘制适应度进化曲线 plt.plot(best_fitness) plt.xlabel(Generation) plt.ylabel(Best Fitness) plt.title(遗传算法进化过程) plt.show() return population # 运行遗传算法 final_pop genetic_algorithm(pop_size10, chrom_length5, max_generations50, mutation_rate0.1)6. 轮盘赌的变体与选择压力调节标准轮盘赌选择有时会导致过早收敛——某个高适应度个体迅速主导种群。为了避免这个问题我们可以调整选择压力1. 线性尺度变换def linear_scaling(fitness_values, alpha1.2): avg np.mean(fitness_values) return [max(f * alpha - (alpha-1)*avg, 0) for f in fitness_values]2. 锦标赛选择def tournament_selection(population, fitness_values, k3): selected [] for _ in range(len(population)): # 随机选择k个个体进行比赛 contestants np.random.choice(range(len(population)), k) # 选择适应度最高的 winner contestants[np.argmax([fitness_values[i] for i in contestants])] selected.append(population[winner]) return np.array(selected)3. 排序选择def rank_selection(population, fitness_values): # 根据适应度排序个体 ranked sorted(zip(population, fitness_values), keylambda x: x[1]) # 分配基于排名的选择概率 ranks np.arange(1, len(population)1) probabilities ranks / sum(ranks) return roulette_wheel_selection( [ind for ind, _ in ranked], probabilities, len(population) )选择方法对比表方法优点缺点适用场景轮盘赌实现简单符合概率原理高适应度个体可能过快主导适应度差异适中的问题锦标赛选择压力可调(k值控制)需要额外参数k需要平衡探索与利用排序选择避免超级个体主导忽略实际适应度绝对值适应度尺度不稳定的问题线性尺度变换保持种群多样性需要调整alpha参数适应度差异过大的情况7. 遗传算法实战优化旅行商问题让我们用遗传算法解决一个经典问题——旅行商问题(TSP)。假设有5个城市需要找到最短的环游路线。首先定义城市坐标和距离计算# 5个城市的坐标 cities { 0: (2, 5), 1: (8, 3), 2: (6, 9), 3: (4, 7), 4: (1, 2) } def calculate_distance(route): 计算路线总距离 total 0 for i in range(len(route)): x1, y1 cities[route[i]] x2, y2 cities[route[(i1)%len(route)]] total np.sqrt((x2-x1)**2 (y2-y1)**2) return total def tsp_fitness(route): 适应度函数距离的倒数 return 1 / calculate_distance(route)实现TSP专用的交叉操作(有序交叉OX)def ox_crossover(parent1, parent2): 有序交叉(OX) size len(parent1) # 选择交叉点 cx1, cx2 sorted(np.random.choice(range(size), 2, replaceFalse)) # 初始化后代 child1 [None]*size child2 [None]*size # 复制中间段 child1[cx1:cx21] parent1[cx1:cx21] child2[cx1:cx21] parent2[cx1:cx21] # 填充剩余位置 def fill_child(child, parent): ptr (cx2 1) % size for gene in parent[cx21:] parent[:cx21]: if gene not in child[cx1:cx21]: child[ptr] gene ptr (ptr 1) % size return child child1 fill_child(child1, parent2) child2 fill_child(child2, parent1) return child1, child2完整的TSP遗传算法实现def tsp_genetic_algorithm(num_cities, pop_size, max_generations): # 初始化种群随机排列 population [np.random.permutation(num_cities) for _ in range(pop_size)] best_distance float(inf) best_route None history [] for generation in range(max_generations): # 评估 fitness_values [tsp_fitness(route) for route in population] distances [calculate_distance(route) for route in population] current_best min(distances) if current_best best_distance: best_distance current_best best_route population[np.argmin(distances)] history.append(current_best) print(fGeneration {generation1}: 最短距离 {current_best:.2f}) # 选择 parents roulette_wheel_selection(population, fitness_values, pop_size//2) # 交叉与变异 offspring [] for i in range(0, len(parents), 2): if i1 len(parents): break parent1, parent2 parents[i], parents[i1] child1, child2 ox_crossover(parent1, parent2) # 变异交换两个城市 if np.random.random() 0.1: swap_pos np.random.choice(num_cities, 2, replaceFalse) child1[swap_pos[0]], child1[swap_pos[1]] child1[swap_pos[1]], child1[swap_pos[0]] if np.random.random() 0.1: swap_pos np.random.choice(num_cities, 2, replaceFalse) child2[swap_pos[0]], child2[swap_pos[1]] child2[swap_pos[1]], child2[swap_pos[0]] offspring.extend([child1, child2]) # 替换 population[:len(offspring)] offspring # 可视化结果 plt.figure(figsize(12, 5)) plt.subplot(1, 2, 1) plt.plot(history) plt.xlabel(Generation) plt.ylabel(Best Distance) plt.title(进化过程) plt.subplot(1, 2, 2) x [cities[i][0] for i in best_route] [cities[best_route[0]][0]] y [cities[i][1] for i in best_route] [cities[best_route[0]][1]] plt.plot(x, y, o-) for i, (xi, yi) in enumerate(zip(x[:-1], y[:-1])): plt.text(xi, yi, str(best_route[i])) plt.title(f最佳路线 (距离{best_distance:.2f})) plt.tight_layout() plt.show() return best_route, best_distance # 运行TSP遗传算法 best_route, best_distance tsp_genetic_algorithm(num_cities5, pop_size50, max_generations100)