从考试题到实战：用Python手把手实现轮盘赌算法（附遗传算法完整代码）

第一次在遗传算法考题中遇到轮盘赌选择时，那种手足无措的感觉我至今记忆犹新。试卷上冷冰冰的四个随机数要求我们预测选择结果，而课本上对这个关键算法却只字未提。正是这次挫败让我意识到，真正掌握算法不能只靠死记硬背，必须亲手实现它——这就是我们今天要用Python完整实现遗传算法核心组件的初衷。

1. 轮盘赌算法的数学本质

轮盘赌选择（Roulette Wheel Selection）之所以得名，是因为它的运作机制酷似赌场里的轮盘。想象一个被划分成不同扇区的圆形轮盘，每个扇区的大小与其对应个体的适应度成正比。当我们旋转这个虚拟轮盘时，指针停在哪块区域，就选择哪个个体进入下一代。

这个过程的数学核心是 概率分配 和 累积概率计算 。假设种群中有N个个体，每个个体的适应度为f_i，那么它被选中的概率p_i可以表示为：

p_i = f_i / sum(f_j for j in range(N))

实际操作中，我们会预先计算每个个体的累积概率区间。例如第一个个体的区间是[0, p₁)，第二个是[p₁, p₁+p₂)，依此类推。当随机数落入某个区间时，就选择对应的个体。

为什么这种方法有效？ 它确保了高适应度个体有更大生存机会，同时低适应度个体也有一定概率保留——这正是自然选择的精髓。不过在实际编码时，我们会遇到几个关键细节：

1. 适应度缩放 ：当某些个体适应度远高于平均值时，它们可能过早主导种群。常见的解决方法是进行适应度缩放（如窗口缩放或线性缩放）
2. 选择压力 ：通过调整适应度值的转换方式（如指数变换），可以控制选择压力的强度
3. 随机数精度 ：在Python中要特别注意浮点数精度问题，累积概率的总和应该严格等于1.0

2. Python实现轮盘赌选择

让我们从零开始构建这个选择机制。首先定义测试数据——假设我们有4个个体，其适应度分别为[15, 7, 2, 6]：

import numpy as np

def roulette_wheel_selection(fitness_values, num_parents):
    total_fitness = sum(fitness_values)
    probs = [f/total_fitness for f in fitness_values]
    cum_probs = np.cumsum(probs)
    
    selected_indices = []
    for _ in range(num_parents):
        r = np.random.random()
        for i, cp in enumerate(cum_probs):
            if r <= cp:
                selected_indices.append(i)
                break
    return selected_indices

# 测试用例
fitness = [15, 7, 2, 6]
print(roulette_wheel_selection(fitness, 4))

这个基础版本已经能完成选择任务，但存在几个可以优化的地方：

• 向量化操作 ：使用NumPy的 searchsorted 可以避免显式循环
• 稳定性处理 ：当所有个体适应度相同时需要特殊处理
• 批量生成随机数 ：一次性生成所有随机数效率更高

优化后的版本如下：

def enhanced_roulette_selection(fitness_values, num_parents):
    probs = np.array(fitness_values) / sum(fitness_values)
    cum_probs = np.cumsum(probs)
    rand_values = np.random.random(num_parents)
    return np.searchsorted(cum_probs, rand_values)

注意：实际遗传算法中，通常会保留当前最优个体（精英保留策略），避免优质基因在随机选择中丢失。

3. 完整遗传算法框架实现

现在我们将轮盘赌选择整合到完整的遗传算法流程中。以下是一个求解函数最大值的示例：

import random

class GeneticAlgorithm:
    def __init__(self, population_size, chromosome_length, fitness_func):
        self.pop_size = population_size
        self.chromo_len = chromosome_length
        self.fitness_func = fitness_func
        self.population = self._init_population()
        
    def _init_population(self):
        return [''.join(random.choice('01') for _ in range(self.chromo_len)) 
                for _ in range(self.pop_size)]
    
    def _calculate_fitness(self):
        return [self.fitness_func(int(ind, 2)) for ind in self.population]
    
    def _select_parents(self, fitness_values):
        return enhanced_roulette_selection(fitness_values, self.pop_size)
    
    def _crossover(self, parent1, parent2):
        pt = random.randint(1, self.chromo_len-2)
        return parent1[:pt] + parent2[pt:], parent2[:pt] + parent1[pt:]
    
    def _mutate(self, individual, mutation_rate=0.01):
        return ''.join(
            bit if random.random() > mutation_rate else '1' if bit == '0' else '0'
            for bit in individual
        )
    
    def evolve(self, generations):
        for _ in range(generations):
            fitness = self._calculate_fitness()
            parents_indices = self._select_parents(fitness)
            new_population = []
            
            for i in range(0, self.pop_size, 2):
                p1 = self.population[parents_indices[i]]
                p2 = self.population[parents_indices[i+1]]
                child1, child2 = self._crossover(p1, p2)
                new_population.extend([
                    self._mutate(child1),
                    self._mutate(child2)
                ])
            
            self.population = new_population
            print(f"Generation {_+1}, Best fitness: {max(fitness)}")

使用示例——寻找函数f(x)=x²在[0,31]区间的最大值：

def fitness_func(x):
    return x**2

ga = GeneticAlgorithm(
    population_size=10,
    chromosome_length=5,  # 因为2^5=32足以表示0-31
    fitness_func=fitness_func
)
ga.evolve(20)

4. 选择策略对比与可视化

轮盘赌选择并非唯一的选择机制，让我们对比几种常见策略的表现：

为了直观展示不同选择策略的效果，我们可以使用Matplotlib进行可视化：

import matplotlib.pyplot as plt

def compare_selection_strategies():
    strategies = {
        'Roulette': roulette_wheel_selection,
        'Tournament': tournament_selection,
        'Rank': rank_selection
    }
    
    results = {name: [] for name in strategies}
    for name, strategy in strategies.items():
        ga = GeneticAlgorithm(20, 5, fitness_func)
        ga._select_parents = lambda f: strategy(f, 20)
        for gen in range(50):
            fitness = ga._calculate_fitness()
            results[name].append(max(fitness))
    
    plt.figure(figsize=(10,6))
    for name, values in results.items():
        plt.plot(values, label=name)
    plt.legend()
    plt.show()

在实现可视化时，有几个关键观察点：

1. 收敛速度 ：锦标赛选择通常收敛最快
2. 最终解质量 ：轮盘赌选择可能找到更好的全局最优解
3. 种群多样性 ：排序选择能最好地维持多样性

实际项目中，我经常采用混合策略——前期使用轮盘赌保持多样性，后期切换为锦标赛选择加速���敛。这种动态调整策略的方法往往能取得最佳效果。