告别交叉变异：一文读懂基于群体的增量学习算法 (PBIL)——python实现

一、前言一种不同的“进化”思路在优化算法的大家庭里遗传算法Genetic Algorithm, GA无疑是明星成员。它通过模拟生物界的“优胜劣汰、交叉变异”来寻找最优解。但你是否想过我们一定要维护一个庞大的“种群”吗今天介绍的基于群体的增量学习算法Population-Based Incremental Learning, PBIL就给出了一个全新的答案。它属于分布估计算法Estimation of Distribution Algorithms, EDA的一种其核心思想是不再进化具体的“个体”而是进化生成优秀个体的“概率模型”。二、PBIL的核心思想从操作个体到学习蓝图为了更好地理解我们来做一个对比遗传算法 (GA)维护一个由多个解个体组成的种群。通过选择、交叉、变异等算子直接对这些个体进行操作希望好的基因能够代代相传。PBIL算法它不维护种群而是维护一个概率向量Probability Vector, PV。这个向量可以看作是生成优秀解的“蓝图”或“模板”。假设我们要解决一个解为n位二进制串的问题。PBIL的概率向量PV就是一个n维的浮点数数组其中PV[i]代表了在最终解的第i个位置上值为1的概率。算法的目标就是通过不断从这个概率模型生成样本并从样本中学习持续优化这个概率向量使其最终能够以极高的概率直接生成问题的最优解。三、算法步骤与核心公式PBIL的流程非常简洁优雅主要分为以下几步1. 初始化 (Initialization)创建一个概率向量PV。在没有任何先验知识的情况下我们通常将其所有元素初始化为0.5。PV [0.5, 0.5, 0.5, ...]这表示在每个位置上生成0和1的概率是均等的。2. 生成样本 (Sampling)根据当前的概率向量PV随机生成N个候选解个体。例如要生成一个个体的第i位如果PV[i]是0.8那么该位有80%的概率是120%的概率是0。3. 评估 (Evaluation)计算这N个新生成的候选解的适应度值即它们有多好。4. 学习与更新 (Learning Updating)这是PBIL的灵魂所在。首先从N个解中找到适应度最高的那个解我们称之为best_individual。然后使用这个最好的解来更新概率向量PV使其“朝着”这个最好解的方向移动一点。更新公式如下PVnew[i](1−LR)⋅PVold[i]LR⋅best_individual[i] PV_{new}[i] (1 - LR) \cdot PV_{old}[i] LR \cdot \text{best\_individual}[i]PVnew​[i](1−LR)⋅PVold​[i]LR⋅best_individual[i]其中LR是学习率 (Learning Rate)一个介于0和1之间的小数如0.1控制着每次更新的幅度。best_individual[i]是最优解的第i位值为0或1。这个公式的本质是一个加权平均它把概率向量向当前找到的最优解的方向“拉”了一把。5. 变异 (Mutation) (可选)为了防止概率向量过早收敛即某些值过分接近0或1导致多样性丧失可以引入一个小的变异步骤对概率向量进行轻微的随机扰动。if (random() mutation_prob): PV[i](1−mutation_shift)⋅PV[i]mutation_shift⋅random_bit \text{if (random() mutation\_prob): } PV[i] (1 - \text{mutation\_shift}) \cdot PV[i] \text{mutation\_shift} \cdot \text{random\_bit}if (random() mutation_prob):PV[i](1−mutation_shift)⋅PV[i]mutation_shift⋅random_bit这相当于给概率向量一个机会去探索那些当前看起来不是最优的方向。6. 终止重复步骤2到5直到满足终止条件如达到最大迭代次数或概率向量已收敛。四、经典应用One-Max问题One-Max问题是最简单的测试函数之一其目标是找到一个二进制串使其包含的1的数量最多。对于长度为n的串最优解就是全1串适应度为n。使用PBIL解决此问题时初始PV全为0.5。生成的样本中1越多的个体适应度越高。在更新步骤中best_individual中1的位置会使得PV对应位置的概率值增加。经过多次迭代PV的所有元素都会趋近于1.0从而稳定地生成最优解。完整python代码importnumpyasnpimportmatplotlib.pyplotasplt# 设置matplotlib支持中文显示plt.rcParams[font.sans-serif][SimHei]# 设置中文字体为黑体plt.rcParams[axes.unicode_minus]False# 设置正常显示负号以防坐标轴负数出错# --- 1. 参数定义 ---ONE_MAX_LENGTH50# 问题规模二进制串的长度POPULATION_SIZE100# 种群大小每代生成的个体数量LEARNING_RATE0.05# 学习率控制概率向量更新的步长MUTATION_PROB0.02# 变异概率对概率向量进行扰动的概率MUTATION_SHIFT0.05# 变异幅度扰动的大小MAX_GENERATIONS100# 最大迭代次数# --- 2. 适应度函数 (One-Max问题) ---defevaluate_fitness(individual):计算个体的适应度即二进制串中1的数量。returnnp.sum(individual)# --- 3. PBIL算法实现 ---# 初始化概率向量 (PV)# 开始时每个位置为1的概率都是0.5prob_vectornp.full(ONE_MAX_LENGTH,0.5)# 用于记录每代的最优适应度以便可视化best_fitness_history[]avg_fitness_history[]print(--- PBIL算法开始运行 ---)# 开始迭代forgenerationinrange(MAX_GENERATIONS):# --- 步骤1: 根据概率向量生成种群 ---# population是一个 (POPULATION_SIZE, ONE_MAX_LENGTH) 的矩阵# np.random.rand(...) prob_vector 利用了NumPy的广播机制# 生成一个随机数矩阵然后与概率向量逐行比较得到布尔矩阵再转为整数0或1population(np.random.rand(POPULATION_SIZE,ONE_MAX_LENGTH)prob_vector).astype(int)# --- 步骤2: 评估种群中每个个体的适应度 ---fitness_scoresnp.array([evaluate_fitness(ind)forindinpopulation])# --- 步骤3: 找到当前种群中的最优个体 ---best_individual_indexnp.argmax(fitness_scores)best_individualpopulation[best_individual_index]best_fitnessfitness_scores[best_individual_index]# 计算平均适应度avg_fitnessnp.mean(fitness_scores)# 记录历史数据best_fitness_history.append(best_fitness)avg_fitness_history.append(avg_fitness)# --- 步骤4: 更新概率向量 ---# 公式: PV_new (1 - LR) * PV_old LR * best_individualprob_vector(1-LEARNING_RATE)*prob_vectorLEARNING_RATE*best_individual# --- 步骤5: 对概率向量进行变异 ---foriinrange(ONE_MAX_LENGTH):ifnp.random.rand()MUTATION_PROB:# 公式: PV_mutated (1 - MS) * PV MS * random_bitrandom_bitnp.random.randint(0,2)# 随机选择0或1prob_vector[i](1-MUTATION_SHIFT)*prob_vector[i]MUTATION_SHIFT*random_bit# 打印当前代的信息if(generation1)%100:print(f第{generation1:3d}代: 最优适应度 {best_fitness:2.0f}/{ONE_MAX_LENGTH}, 平均适应度 {avg_fitness:5.2f})# --- 4. 结果展示 ---print(\n--- 算法运行结束 ---)print(f最终概率向量 (部分):{np.round(prob_vector[:10],2)}...)# 根据最终的概率向量生成最终的推荐解final_solution(prob_vector0.5).astype(int)final_fitnessevaluate_fitness(final_solution)print(f最终解的适应度:{final_fitness}/{ONE_MAX_LENGTH})print(f最终解 (部分):{final_solution[:20]}...)# --- 5. 可视化 ---plt.figure(figsize(10,6))plt.plot(best_fitness_history,label每代最优适应度)plt.plot(avg_fitness_history,label每代平均适应度,linestyle--)plt.axhline(yONE_MAX_LENGTH,colorr,linestyle-,labelf理论最优值 ({ONE_MAX_LENGTH}))plt.title(PBIL算法求解One-Max问题收敛曲线)plt.xlabel(迭代次数)plt.ylabel(适应度)plt.legend()plt.grid(True)plt.show()五、优缺点分析优点概念简单相比GA复杂的算子PBIL的更新规则非常直观。计算高效省去了维护和操作庞大种群的开销。全局信息利用概率向量是对历史所有优秀解的统计抽象隐式地利用了全局信息。缺点变量无关性假设基本PBIL假设变量基因位间相互独立难以捕捉变量间的复杂关联例如x[1]和x[5]必须同时为1。主要用于离散空间基本形式主要针对二进制编码问题解决连续问题需要对概率模型进行扩展如使用高斯分布。六、总结PBIL算法为我们提供了一种“上帝视角”的优化思路它不关心种群中个体的“爱恨情仇”交叉而是通过统计和学习直接去描绘最优解的“样貌”概率分布。这种从操作实例到学习模型的思想转变正是分布估计算法的魅力所在也为解决复杂优化问题开辟了新的道路。