演化算法 (Evolutionary Algorithm,简称EA,或称进化算法)是演化计算的子集,是一种基于群体的元启发式(Meta Heuristic)最优化算法.演化算法使用了各种模拟生物演化机制的操作,比如繁衍、变异、重组、选择等.

PS. 群体和种群基本是一样的

元启发式算法是相对于最优化算法提出来的,一个问题的最优化算法可以求得该问题的最优解,而元启发式算法是一个基于直观或经验构造的算法,它可以在可接受的花费(指计算时间和空间)下给出问题的一个可行解,并且该可行解与最优解的偏离程度不一定可以事先预计.

在种群中每一个个体(不同形式下有不同叫法)都是问题的备选解,而适应度函数(fitness function) 用于计算出每一个解的质量（也就是个体对于环境的适应度）.演化就是在不断在种群中进行变异、交叉、选择这些操作进而找出最优解的过程.演化算法之所以在各种优化问题上都经常逼近最优解,是因为它不会对适应度的范围作出预先假设.

在大多数演化算法的应用中,计算复杂度都是最大障碍.事实上,这种**计算复杂度来源于适应度函数.简化适应度函数,从而计算近似的适应度,是克服这一障碍的方法之一.**由于看似简单的演化算法常常可以解决复杂的优化问题,因此,算法复杂度应该与问题的复杂性之间,可能没有直接关系.

一般性的算法流程:

1. 初始化规模为N的解(solution)的集合,称为种群(population),当前进化代数Generation=0

2. 通过适应度函数评估各个解的适应度(fitness),保存最好的值best

3. 从当前种群中**选择(selection)**N次染色体,产生规模同样为N的种群

4. 基于选择后的种群,通过**变异(mutation)和交叉(crossover/recombination)**产生一些新解(子代解)

   子代解替代父代解进入新种群

5. 重新计算新种群的各适应度,如果最好的值大于上次的best值,就替代

6. 当前进化代数+1,如果进化代数超出规定值或者best满足要求,就退出算法,否则返回3.

变异算子:随机修改一个解产生新解

交叉算子:混合多个解产生新解

选择算子:按照一定规则选择解

PS.规模为N的种群意味着有N个不同的方案,而不是有N个参数

第3步可能会重复选某个解,但没关系,后面可以通过交叉/变异变得不同

具体类型以及衍生算法

演化算法的具体技术可以按照遗传信息表达(编码)方式、实现细节、以及特定问题的特定处理分类：

• 遗传算法 Genetic algorithm：这是演化算法中最常用的类型.这种技术应用于求解最优解是一组数字的问题.
• 遗传编程 Genetic programming ：这种技术用于生成一段计算机程序,其适应度是这些计算机程序解决某计算问题的能力.
• 演化编程 Evolutionary programming ：与遗传编程类似,但其求解的计算机程序的结构是固定的,可以演化的是一些数值参数.
• 演化策略 Evolution strategy ：这种技术以实数向量作为个体,而且使用了自适应的变异率.
• 差分进化 Differential evolution ：这种算法以向量的差为基础,因此特别适合数值最优化问题.

鸟群、鱼群的迁徙、觅食等行为属于群体智能(swarm intelligence)行为,本身是一个最优化的过程.通过模拟这些群体智能行为,并融入一些个体认知/社会的概念,就有了群算法(Swarm algorithms)

与演化算法相关的集群算法包括：

• 蚁群优化算法(Ant Colony Optimization, ACO)：这种技术以蚂蚁觅食和通过信息素沟通寻路为基础,最早应用于组化优化和图相关问题.
• 人工蜂群算法(Artificial bee colony algorithm)：根据蜜蜂觅食行为设计,最初为数值优化提出,后来扩展至解决组合、受约束的多目标最优化问题.
• 粒子群算法(Particle Swarm Optimization, PSO)：是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法,主要适合用于解决数值优化问题.

解的形式(编码方式)

一般来说,一个**个体(individual)**就是一个有效解

但在遗传算法中,有效解也会称为**染色体(chromosome) **或 串.

染色体的具体形式是一个使用特定编码方式生成的串,串中每个编码单元称为基因(gene)

解/染色体有一下具体形式:

布尔向量/二进制编码

遗传算法常用布尔向量(二进制串/序列)来表示个体/染色体/解,用一个bit表示1或0. 比如[0,1,1,0] (简写成0110),并采用基于位的变异/交叉来产生新解

向量的长度通常取决于具体问题,比如问题的解空间为64(等效于有6个独立的bool参数),长度6位就够了

解空间也叫做搜索空间(search space),决策空间(decision space).布尔向量也被叫做决策变量(decision variable)

一般来说是定长的,但也有变长的方式

模式(schema)定理:证明了以该形式的GA寻求全局最优是有可能的

浮点数编码

虽然二进制编码简单粗暴,但是精度差,表示范围小.换成浮点会好得多,浮点数的范围取决于问题中变量的范围

树状结构

若干函数(比如运算符+-*/)构成的集合F和若干终止符(比如变量)构成的集合T,树的内部节点表示F,叶子节点表示T

基于节点的变异:随机使用替换/插入/删除操作

替换:叶节点换个其他的T 插入:插一个F 删除:删除叶节点的兄弟和父节点

遗传编程通常将解表示成树状结构,并采用基于节点的变异/交叉算子

当问题的解具有复杂结构时(比如电路设计,符号回归),用结构化的表示方式更自然且更高效,也就是用遗传编程更好,但是遗传编程的演化过程十分复杂

其他形态

进化多任务 EMT/MTO

多年来,EA已被成功应用于解决科学、运筹学（OR）和工程领域的各种优化问题.这些问题一般可分为两类：

1. 单目标优化(Simple Objective Optimization, SOO),其中搜索空间的每一点都映射到一个标量目标值
2. 多目标优化(Mutiobjective Optimization, MOO),其中搜索空间的每一点都映射到一个矢量值的目标函数

在论文Multifactorial Evolution: Toward Evolutionary Multitasking中,引入了第三类问题:多因子优化(Multifactorial Optimization, MFO),其特点是多个搜索空间同时存在,对应于不同的任务（也可能不是相互依赖的）

之后也把MFO叫做进化多任务(EMT)/多任务优化(MTO),与MOO最大不同就是MTO不要求任务之间约束要一致,MTO也可以用于单目标优化

遗传算法 GA

一种随机的自适应全局搜索算法,算法流程就是上面提到的

基本做法

种群初始化

一般是随机初始化的,但必须注意初始化的染色体是否是有效解

也有在一开始寻求一个比较好的初始解的方法,具体不谈

种群大小一般在20-100

适应度评价

在遗传算法中,规定适应值越大的染色体越优.因此对于一些求解最大值的数值优化问题,我们可以直接套用问题定义的函数表达式.但是对于其他优化问题,问题定义的目标函数表达式必须经过一定的变换.例如,应用遗传算法求解某个函数的最小值,可对问题定义的目标函数f(X)进行以下变换,得到算法的评估函数:Eval(C)=-f(X)
其中X表示一个有效解,C表示X对应的染色体

为了更好地提高选择的效能,可以对评估函数做出一定的修正.目前主要的评估函数修正方法有：线性变换,乘幂变换,指数变换等

选择算子

种群的选择操作使用轮盘赌选择算法(roulette wheel selection).轮盘赌选择算法是遗传算法最经常使用的选择算法,其基本思想是基于概率的随机选择

轮盘赌选择算法首先计算群体所有染色体的适应值总和,并分别计算每个染色体适应值与总和的占比P_i;然后弄一个具有N个扇区的轮盘,每个扇区对应群体中的一个染色体,扇区的大小与对应染色体的P_i.

每转动一次轮盘,轮盘转动停止时指针停留的扇区对应的染色体即被选中进入种群.依次进行N次选择即可得到规模同样为N的种群.

实际在进行轮盘赌选择时个体的选择往往不是依据个体的选择概率,而是根据“累积概率”来进行选择:

//P[i]表示第i个个体被选中的概率
m =0;
r =Random(0,1); //r为0至1的随机数
for(i=1;i<=N;i++) {
	m = m + P[i];
	if(r<=m) //产生的随机数如果小于m+P[i]则认为选中了i,i被选中的概率是P[i]
        return i;
	}

累积概率？
上一步计算得到每个个体被选择的概率时,可容易看出,各个个体被选择概率的总概率和为1（相当于根据适应度进行归一化处理）.现在需要把这N个体按比例放入0~1范围的线段里,每个个体应该占用多长的线段呢？用线段的长度代表被选择概率.

代码中,我们生成一个[0,1]中的随机数,落在0~1线段上的哪段位置上的概率就是各个个体被选择的概率

为什么要累积概率?

因为选择过程需要选N个染色体,选择前后数量一样,这就意味有一些染色体被忽略,有些染色体被多次选择,用累积概率容易实现

交叉算子

在交叉阶段,每个染色体能否交叉取决于交叉概率(一般0.4-0.99)

每两个染色体被选出来后,交叉操作是随机生成一个有效的位置,两个染色体交换在该位置之后的所有基因

比如: 1号 010101 2号 101010 随机出来的位置是4(假设索引从1开始), 则交换后 1号 010110 2号 101001

交叉操作后也要注意生成的是不是有效解

变异算子

染色体中每一位基因都有变异概率(0.001-0.01),如果是浮点数编码就随机数生成一个来替换

终止条件

最大进化代数一般为100-1000,或者best值满足条件

其他形态

混合GA

传统GA局部搜索能力较弱,可以与其他搜索方法结合,如爬山法,模拟退火...

对于解产生的策略,除了交叉变异,还可以有:粒子群,协方差矩阵自适应,差分进化...

对于选择解的策略,除了轮盘赌,可以有:联赛选择,非支配排序,代理模型...

并行GA

GA有并行的潜力,比如各个染色体的交叉/变异.用SIMD实现

应用

主要是关于优化与调度

大量实际工程系统的设计和优化问题可以转换为函数优化问题进行解决.函数优化问题是一类通过对函数变量进行数值的设置优化以达到函数优化目标的问题.函数优化是遗传算法的传统应用领域,随着对遗传算法的不断改进,遗传算法应用于解决函数优化问题已经越来越成熟.
实际生产生活中存在许多调度和规划问题,这类问题属于组合优化问题,通常涉及比函数优化更为复杂的优化目标,例如作业调度问题、旅行商问题、布局问题等.到目前为止,遗传算法已经成功地在许多调度和规划问题上给出了令人满意的解决结果.

涉及全局搜索的地方都可以用用,比如机器学习/数据挖掘的参数

其他算子

tournament selection 联赛选择算法

每次从种群中取出k个个体,然后选择其中适应性最好的一个进入子代种群.几元竞赛就是一次性在总体中取出几个个体

算法避免了轮盘赌算法的缺点:选择个体的概率与目标函数的形状有很大关系;选择个体的概率与目标函数的偏移有很大关系

粒子群算法 PSO

是一个全局搜索算法,结合了动物的群体行为以及人类社会的认知特性

基本思想

在群体觅食的过程中,每个个体都会受益于所有成员在觅食过程中所发现和累计的经验

如鸟群觅食,在粒子群优化算法中,鸟群中的每个小鸟被称为一个“粒子”,通过随机产生一定规模的粒子作为问题搜索空间的有效解.和小鸟一样,每个粒子都具有速度和位置,可以由问题定义的适应度函数确定粒子的适应值,然后不断进行迭代,由粒子本身的历史最优解和群体的全局最优解来影响粒子的速度和位置,让粒子在搜索空间中探索和开发,最终找到全局最优解.

基本流程

每个个体(粒子)在进化过程中需要维护两个向量:

速度向量v_i=[v_i¹,v_i²,...,v_i^D]和位置向量x_i=[x_i¹,x_i²,...,x_i^D],i表示粒子的编号,D是解空间的维数.

粒子的速度决定了运动的方向和速率;位置体现了粒子所代表的解在解空间的位置,是评估该解质量的基础

每个粒子还要维护一个自身历史最优位置向量pBest;而群体要维护一个全局最优向量gBest,代表所有pBest中最优的那个

与GA相比,PSO没有选择/交叉/变异算子,而是仅通过速度和位置更新公式来进化

对于第i个粒子的第d维

速度更新公式:$\boldsymbol{v}_{i}^{d}=\omega \times \boldsymbol{v}_{i}^{d}+c_{1} \times \operatorname{rand}_{1}^{d} \times\left(\boldsymbol{pBest} _{i}^{d}-\boldsymbol{x}_{i}^{d}\right)+c_{2} \times \operatorname{rand}_{2}^{d} \times\left(\boldsymbol{gBest}^{d}-\boldsymbol{x}_{i}^{d}\right)$

ω是惯性权重(inertia weight),取值[0,1]区间,控制前一速度对当前速度的影响.一般初始化为0.9,然后随着进化过程线性降低至0.4

c1和c2是加速系数/学习因子,代表向pBest/gBest推进的权重.一般取2

rand是[0,1]区间的随机数

位置更新公式:$\boldsymbol{x}_{i}^{d}=x_{i}^{d}+v_{i}^{d}$ 就是位置+速度

步骤

1. 初始化粒子(速度和位置),并把pBest设为当前位置,最优pBest作为gBest
2. 在每一代的进化中计算各粒子的适应度
3. 如果粒子当前的适应度比历史最优还好,就更新pBest,如果比全局最优更好,gBest也更新
4. 通过速度和位置更新公式来进化
5. 如果还没达到终止条件,就回到2.

注意事项

进化过程中,还需要设定一个速度最大值V_max(其每一维V_max^d可以取相应维的取值范围的10%-20%),决定粒子最大移动能力

还要注意位置更新必须是有效解,不然要么重新随机要么限制边界

种群规模不用太大效果也不错,一般20-40

拓扑结构/社会结构

就是个体如何进行互相作用的问题

PSO的拓扑结构是由互相重叠的邻域构成的,粒子在这些邻域内互相影响.不同的拓扑结构将影响粒子间的交流方式和速度,从而影响算法性能

基础版本的PSO中,粒子都受到gBest的影响,可以认为所有粒子的邻域就是全局且重叠的

如果限定一个范围的邻域,由gBest变成lBest,就变成局部版本的PSO了,局部版本虽然慢一点,但是不易陷入局部最优

还有其他花样,就不谈了

其他形态

基础PSO只适合连续问题,离散问题需要不同的编码方式,比如整数编码,二进制编码...

应用

和GA差不多,函数优化,调度和规划

涉及全局搜索的地方都可以用用

差分进化 DE

Differential evolution,一种强大的连续优化算法,由Storn和Price在1997年提出.为了解决一个特定的问题,DE中种群的个体可以用一个浮点数的向量来表示,被称为目标向量,可以表示为:

$X_{i}=\left[x_{i, 1}, x_{i, 2}, \cdots, x_{i, n}\right]$

其中i是群体中的第i个个体,n是问题的维度

DE的基本思想是通过利用当前群体的个体差异来组成一个临时群体.变异和交叉是DE的两个关键组成部分,这两个算子根据两个随机选择的种群个体之间的加权差产生新的候选解分量,并添加到第三个个体上。这导致了相对于整个种群扩散的种群个体的扰动。

1. 每个x_i,j的初始化为: $x_{i, j}=\operatorname{Rand}\left(L B_{j}, U B_{j}\right)$,其中LB_j和UB_j是第j个变量的下限和上限,Rand(a,b)返回一个在a和b之间均匀分布的随机数

2. 对每个目标向量进行**变异(mutate)**运算,创建一个变异向量(以DE/rand/1为例):$Y_{i}=X_{r 1}+F \cdot\left(X_{r 2}-X_{r 3}\right)$

   其中,i表示每个向量中的第i个变量,F是控制差分向量的幅度比例因子,r1,r2,r3是三个不同的随机数,范围[1,种群大小],代表在种群中随机选3个个体的索引.

   之后,每个目标向量(Xi)与它的变异向量(Yi)交叉,形成一个试验向量(Ui),可表示为$u_{i, j}=\left\{\begin{array}{ll}y_{i, j}, & \text { if } \operatorname{rand}(0,1)<C R \text { or } j=k \\ x_{i, j}, & \text { otherwise }\end{array}\right.$ 其中,u_i,j,x_i,j和y_i,j分别是Ui,Xi和Yi的第j个分量,CR∈[0,1]是交叉率,k是1到d(维度)之间的随机整数

3. 目标向量和试验向量之间较好的一个将成为下一代的新目标向量,可表示为:$X_{i}=\left\{\begin{array}{ll}U_{i}, & \text { if } f\left(U_{i}\right) \leq f\left(X_{i}\right) \\ X_{i}, & \text { otherwise }\end{array}\right.$

第二和第三步之间有一个重复,直到满足终止条件

DE中常用的五种变异策略如下:

$\begin{gathered} D E / r a n d / 1: \mathbf{v}_i^g=\mathbf{x}_{r 1}^g+F \times\left(\mathbf{x}_{r 2}^g-\mathbf{x}_{r 3}^g\right) \\ D E / \text { best } / 1: \mathbf{v}_i^g=\mathbf{x}_{\text {best }}^g+F \times\left(\mathbf{x}_{r 1}^g-\mathbf{x}_{r 2}^g\right) \\ D E / \text { current-best } / 2: \mathbf{v}_i^g=x_i^g+F \times\left(\mathbf{x}_{\text {best }}^g-\mathbf{x}_i^g+\mathbf{x}_{r 2}^g-\mathbf{x}_{r 3}^g\right) \\ D E / \text { best } / 2: \mathbf{v}_i^g=\mathbf{x}_{\text {best }}^g+F \times\left(\mathbf{x}_{r 1}^g-\mathbf{x}_{r 2}^g+\mathbf{x}_{r 3}^g-\mathbf{x}_{r 4}^g\right) \\ D E / \text { rand } / 2: \mathbf{v}_i^g=x_{r 1}^g+F \times\left(\mathbf{x}_{r 2}^g-\mathbf{x}_{r 3}^g+\mathbf{x}_{r 4}^g-\mathbf{x}_{r 5}^g\right) \end{gathered}$

$\mathbf{v}_i^g$表示个体i在第g代的变异向量. x^g_best就是第g代中最好的解

DE与GA

GA 更适合离散优化,PSO 和 DE 更适合连续优化

GA可用于组合优化问题,如调度.但DE不太行

其他基于种群的元启发式方法

高斯适应 Gaussian adaptation ：一种基于信息论的方法, 用于最大化成品率、平均适应度、平均信息量等.参考热力学和信息论中的熵.

模因算法 Memetic Algorithm

类似于遗传学中的基因,模因(文化基因 meme)可以被描述为可复制和可传播的文化知识的构建块.这是一种混合方法,通常采用基于群体的算法形式,再加上能够执行局部优化的个体学习过程.这种方法强调利用每个问题自身的特性,并调和局部搜索和全局搜索.

它的本质可以理解为：Memetic = GA + 局部搜索

即memetic算法实质上为遗传算法加上一个局部搜索（Local Search）算子.局部搜索算子可以根据不同的策略进行设计,比如常用的爬山机制、模拟退火、贪婪机制、禁忌搜索等.