机器学习中四类进化算法的详解（遗传算法、差分进化算法、协同进化算法、分布估计算法）

1、遗传算法（Genetic Algorithm，GA）

GA算法原理

首先我们来介绍进化算法的先驱遗传算法，遗传算法（Genetic Algorithm，简称GA）是一种最基本的进化算法，它是模拟达尔文生物进化理论的一种优化模型，最早由J.Holland教授于1975年提出。遗传算法中种群分每个个体都是解空间上的一个可行解，通过模拟生物的进化过程，进行遗传、变异、交叉、复制从而在解空间内搜索最优解。

GA算法步骤

Step 1 种群初始化：根据问题特性设计合适的初始化操作（初始化操作应尽量简单，时间复杂度不易过高）对种群中的N个个体进行初始化操作；

Step 2 个体评价：根据优化的目标函数计算种群中个体的适应值（fitness value）；

Step 3 迭代设置：设置种群最大迭代次数，并令当前迭代次数 =1 ；

Step 4 个体选择：设计合适的选择算子来对种群 P(g) 个体进行选择，被选择的个体将进入交配池中组成父代种群 FP(g) ，用于交叉变换以产生新的个体。选择策略要基于个体适应值来进行，假如要优化的问题为最小化问题，那么具有较小适应值的个体被选择的概率相应应该大一些。常用的选择策略有轮盘赌选择，锦标赛选择等。

Step 5 交叉算子：根据交叉概率 pm （预先指定，一般为0.9）来判断父代个体是否需要进行交叉操作。交叉算子要根据被优化问题的特性来设计，它是整个遗传算法的核心，它被设计的好坏将直接决定整个算法性能的优劣。

Step 6 变异算子：根据变异概率 pc （预先指定，一般为0.1）来判断父代个体是否需要进行变异操作。变异算子的主要作用是保持种群的多样性，防止种群陷入局部最优，所以其一般被设计为一种随机变换。

通过交叉变异操作以后父代种群生成了新的子代种群，令种群迭代次数+1 ，进行下一轮的迭代操作（跳转到Step 4），直至迭代次数达到最大的迭代次数。

通过交叉操作，原始的两个个体组合生成了两个新的个体组合，这就相当于在解空间进行搜索，每个个体都是解空间的一个可行解。

在进行完一轮「遗传变异」之后，我们用适应度函数对这些新的后代进行验证，如果函数判定它们适应度足够，那么就会用它们从总体中替代掉那些适应度不够的染色体。

当达到如下几个条件，则终止循环 1. 在进行 X 次迭代之后，总体没有什么太大改变。 2. 我们事先为算法定义好了进化的次数。 3. 当我们的适应度函数已经达到了预先定义的值。

2、差分进化算法（Differential Evolution，DE）

DE算法原理

差分进化算法（Differential Evolution，DE)于1997年由Rainer Storn和Kenneth Price在遗传算法等进化思想的基础上提出的，本质是一种多目标（连续变量）优化算法（MOEAs），用于求解多维空间中整体最优解。DE算法也属于智能优化算法，与启发式算法，如ABC，PSO等类似，都属于启发式的优化算法。差分进化思想来源即是早期提出的遗传算法（GeneticAlgorithm，GA），模拟遗传学中的杂交(crossover)、变异(mutation)、复制(reproduction)来设计遗传算子。

差分进化算法相对于遗传算法而言，相同点都是通过随机生成初始种群，以种群中每个个体的适应度值为选择标准，主要过程也都包括变异、交叉和选择三个步骤。不同之处在于遗传算法是根据适应度值来控制父代杂交，变异后产生的子代被选择的概率值，在最大化问题中适应值大的个体被选择的概率相应也会大一些。而差分进化算法变异向量是由父代差分向量生成，并与父代个体向量交叉生成新个体向量，直接与其父代个体进行选择【也就是变异和选择操作与差分向量有关系，而差分向量是与随机选择的三个个体有关系】。显然差分进化算法相对遗传算法的逼近效果更加显著。

DE算法步骤

看详解：差分向量（Differential Vector）【差分进化算法】_HealthScience的博客-CSDN博客

DE的群体由突变和选择过程驱动。突变过程，包括突变和交叉操作，这两步操作被设计用于利用或探索搜索空间，而选择过程被用于确保有希望的个体的信息可以进一步利用。

3、合作协同进化算法（Cooperative Co-Evolution Algorithm，CCEAs）

“合作协同进化算法”思想来自于“协同进化”：两方在不断影响和发展的过程

分组思想 和小生境共享（Niche Sharing）有异曲同工之妙（【IEEE CIM 2023】基于多目标进化算法的抗菌肽设计方法_HealthScience的博客-CSDN博客）

分组中的多个个体合作 与“6、共同进化：在合作与竞争中共同成长”是一样的思想（【NMI 2021】从生物学角度看进化计算（6个生物进化特征）_HealthScience的博客-CSDN博客）

CCEAs算法原理

CCEAs（合作协同进化算法）是一个求解大规模优化问题的算法，该算法采取“分而治之”的策略。对于一个优化问题，依变量分解成若干组问题，分组优化，且各分组间进行合作协同，共同完成整个问题的优化。该算法是一种在传统遗传算法基础上，对其进行改进优化，提出的保留优异群体的协同进化遗传算法。

复杂问题分解为子问题，子问题在进化的子种群中解决，个体的评估依赖于子种群间的合作，由各子种群的代表性个体组合而得完整的解决方案。个体在子种群的适应度由其在完整解决方案的参与来评估。

CCEAs的优点：

问题分解后可通过并行计算提速，提高优化效率；
子问题在子种群独立解决，方法多样；
分解成子模块，增加对模块错误的鲁棒性；
正确的分解能够减缓决策变量的迅速增加。

CCEAs算法步骤：

初始化：随机生成ｎ个初始父代子群体，并创建一个空的外部集合Ａ ,把各子群体随机组合产生的解中的非支配解（人工智能中的一些术语_HealthScience的博客-CSDN博客）加入Ａ；设Ａ的最大容量=Ｍ,子群体规模=Ｎ,交叉概率 =Ｐc,变异概率 =Ｐｍ；
繁殖操作：依次对每个父代子群体进行交叉和变异操作，生成ｎ个子代子群体；
子群体间的合作：依次让子代子群体中的每个个体与父代子群体合作生成一个完整解,计算目标向量,并判断该解是否应对外部集合Ａ进行更新或是舍弃,直至处理完所有子代子群体中的所有个体；
外部集合的裁减：若 |Ａ|>Ｍ(|·|表示集合中元素的个数 ),则对Ａ进行裁减操作,移除那些具有最近邻居的解,使得Ａ的大小变为Ｍ,否则,若 |Ａ|≤ Ｍ,则进入第 5 步；
新一代父代子群体的生成：若 |Ａ|≤ Ｎ,则分别从每个子代子群体中随机选取Ｎ -|Ａ|个个体,把其与Ａ中所有解的相应分量合并构成下一代的父代子群体,否则,若 |Ａ |>Ｎ,则从Ａ中随机挑选Ｎ个解,把其各分量合并作为下一代父代子群体；
终止判断：若满足终止条件，则把外部集合Ａ作为最终求得的非支配解集 (近似 Pareto 最优解集 )输出,算法终止,否则, 转至第 2 步进入新一代的进化。

4、分布估计算法（Estimation of Distribution Algorithm，EDA）

EDA算法原理

遗传算法是对于个体进行遗传操作（交叉、变异等），“微观”层面模拟生物的进化。

分布估计算法是对于整个群体的分布建立一个概率模型，通过这个概率模型来描述进化的方向，是“宏观”层面的模拟。
在这里插入图片描述

分布估计算法的概念最初在1996年由H. Muhlenbein提出，主要思想就是把自然进化算法和构造性数学分析方法相结合，以指导对问题空间的有效搜索。

分布估计算法本质上是一种基于概率模型的新型进化算法，遗传算法与统计学习相结合，是自然计算的又一典型实现模式。它通过对当前找到的较优个体集合建立概率模型来引导算法下一步的搜索范围，并从所获得的较优解的概率分布函数中抽样产生出新的个体。打个比方，我每天不知到吃啥，第一周我在后街随便吃了10家店，觉得ABCD这四家店很好吃，那么第二周的时候我更可能选择ABCD这四家店及其旁边的店，这这周发现ABE这几家好吃，然后下周我更可能去这几家店及其旁边的店，周而复返最后得出B家最好吃。