别再死记硬背了！用Python实战遗传算法中的轮盘赌选择（附完整代码）

用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"个体{i+1}: {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'个体{i+1}' 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, startangle=90, counterclock=False) # 模拟指针旋转 for angle in np.linspace(0, 360, 30): ax.clear() wedges, texts = ax.pie(sizes, startangle=90-angle, counterclock=False) 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, startangle=90-stop_angle, counterclock=False) 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]}', xy=wedges[i].center, xytext=(10, 10), textcoords='offset points', bbox=dict(boxstyle="round", fc="yellow")) break cumulative += size/total plt.legend(wedges, labels, title="个体适应度", loc="center left", bbox_to_anchor=(1, 0, 0.5, 1)) plt.tight_layout() plt.show() # 使用考试数据可视化 visualize_roulette_wheel(fitness_values)

这个可视化会展示：

1. 轮盘根据适应度分配的区域大小
2. 模拟指针旋转过程
3. 最终根据随机数停在某个个体区域
4. 高亮显示被选中的个体

5. 从选择到进化：完整的遗传算法流程

轮盘赌选择只是遗传算法的一个环节。完整的遗传算法还包括：

1. 初始化：随机生成初始种群
2. 评估：计算每个个体的适应度
3. 选择：使用轮盘赌等方法选择父代
4. 交叉：通过基因重组产生后代
5. 变异：随机改变某些基因位
6. 替换：用新种群替代旧种群
7. 终止：满足条件时停止迭代

让我们实现一个简单的完整遗传算法，求解一个实际问题：找到二进制数各位全为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"第{generation+1}代, 最佳适应度: {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 i+1 >= len(parents): break parent1, parent2 = parents[i], parents[i+1] 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_size=10, chrom_length=5, max_generations=50, mutation_rate=0.1)

6. 轮盘赌的变体与选择压力调节

标准轮盘赌选择有时会导致过早收敛——某个高适应度个体迅速主导种群。为了避免这个问题，我们可以调整选择压力：

1. 线性尺度变换

def linear_scaling(fitness_values, alpha=1.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, k=3): 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), key=lambda 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) )

选择方法对比表：

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[(i+1)%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, replace=False)) # 初始化后代 child1 = [None]*size child2 = [None]*size # 复制中间段 child1[cx1:cx2+1] = parent1[cx1:cx2+1] child2[cx1:cx2+1] = parent2[cx1:cx2+1] # 填充剩余位置 def fill_child(child, parent): ptr = (cx2 + 1) % size for gene in parent[cx2+1:] + parent[:cx2+1]: if gene not in child[cx1:cx2+1]: 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(f"Generation {generation+1}: 最短距离 = {current_best:.2f}") # 选择 parents = roulette_wheel_selection(population, fitness_values, pop_size//2) # 交叉与变异 offspring = [] for i in range(0, len(parents), 2): if i+1 >= len(parents): break parent1, parent2 = parents[i], parents[i+1] child1, child2 = ox_crossover(parent1, parent2) # 变异：交换两个城市 if np.random.random() < 0.1: swap_pos = np.random.choice(num_cities, 2, replace=False) 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, replace=False) 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_cities=5, pop_size=50, max_generations=100)