演化算法是一个大类，是根据模拟自然界生物进化过程而发展起来的一种通用问题求解方法，而非具体算法。
打个比方，“蛋糕”是一类食物的统称，而“黑森林蛋糕”、“抹茶奶油蛋糕”才是具体的蛋糕品种；同理，“演化算法”就是一类算法的统称，而“遗传算法”、“遗传规划”等才是具体的算法。
本章节就像是一张面向新手的食谱，先不细说如何制作“黑森林蛋糕”等具体繁琐的内容，而是先从整体上介绍所有“蛋糕”的统一特点，即主要从整体上介绍演化类算法的起源和发展，以及它们共同的设计思路。
下一篇介绍的遗传算法才是具体算法。
一、演化计算
(一) 生物进化
演化计算：模拟自然界生物进化过程而发展起来的一种通用问题求解方法。
什么是生物进化？
生物进化是生物与其生存环境之间的相互作用的变化所导致的部分或整个生物种群遗传组成的一系列不可逆的改变。我们认为生物进化是生物与其生存环境互相作用过程中，其遗传系统随时间发生一系列不可逆的改变，从而导致生物总体对其生存环境的相对适应。
生物的进化可以看作是一个优化过程，而优化的结果是能够很好地适应环境的生物体。生物的进化过程也可以看作是在众多可能性中搜索“解”的一种方法。现在地球上的种类繁多、结构复杂的生物都是通过漫长的由简单到复杂、由低级到高级的进化过程而得到的优化结果。在生物中，众多可能性的集合是可能遗传序列的集合，而所要求的“解”则是能够适应环境的生物体。
(二) 演化计算的概念
演化计算的概念：是在达尔文进化论和孟德尔的遗传变异理论的基础上产生的一种在基因和种群层次上模拟自然界生物进化过程与机制，进行问题求解的自组织、自适应的随机搜索技术。
它以达尔文进化论的“物竟天择、适者生存”作为算法的进化规则，并结合孟德尔的遗传变异理论，在算法中引入了生物进化过程中的繁殖、变异、竞争和选择等机制。
生物进化与问题求解术语之间的联系：
生物进化术语问题求解术语环境问题个体可能解适应度质量
二、演化算法
(一) 演化算法求解问题
目前，用演化计算表示用模拟生物进化过程来求解问题的整个研究领域，而遗传算法、遗传规划、演化策略和演化规划是演化计算研究领域的四个主要研究方向。
演化计算所涉及的算法称为演化算法。有许多不同类型的演化算法，但所有演化算法的一个共同特点是求解问题的过程也就是模拟大自然生物进化的过程。
演化算法在求解问题的过程中怎么做？
保持一个个体的种群，每个个体表示问题的一个可能解个体适应环境的程度用一个适应函数判断，每个个体按照适应函数来度量该个体作为问题解的好坏的程度，而度量值称为该个体的适应值。基于个体的适应值，某些较好的个体被选择，通过重组、变异等算子的作用，产生一些新的个体，这些个体与种群中原来的个体竞争，形成下一代种群，继续这个过程，直到终止条件被满足。
生物系统优化问题生物个体问题的一个解（多个变量组成的向量）染色体携带遗传信息二进制编码表示解的信息基因（染色体的片段）二进制编码中的一个或多个位一定数量的个体组成生物种群一定数量的二进制编码组成解的群体个体能否生存由其适应性决定解的“好坏”用适应度函数确定自然选择（适者生存）适应度值大的解被留住的可能性大基因的混合与重组由交叉概率控制，对二进制串进行交叉基因的变异由变异概率控制，对二进制串的某些位进行变异
演化算法（也称“进化算法”）的三大分支：https://zhuanlan.zhihu.com/p/479552083
(二) 演化算法求解过程
演化算法流程图：
该流程用伪代码表示就是：
Procedure Evolutionary_Algorithm
Begin
t=0;
initialize(P(t)); evaluate(P(t));
while(not termination condition) do
P'(t) = parent_select(P(t));
P''(t) = recombine(P'(t));
P'''(t) = mutate(P''(t));
evaluate(P'''(t));
P(t+1) = survivor_select(P(t)∪P'''(t));
t = t+1;
end while
return the best solution;
End
t 表示演化代数，其初始值为 0； 表示第 t 代种群；演化算法首先产生一个初始种群，其中 N 是一个常数，称为种群规模； 通常是随机产生的初始种群，但也可以用其他启发式算法得到。 初始种群中的每个个体 x 表示所求解问题的一个可能解。 产生初始种群 ； 对种群 中每个个体的进行适应值度量。个体的适应值度量可以是简单地计算一个适应函数，也可以是个复杂的模拟过程； 根据种群 中个体的适应值选择出一些个体作为父体。适应值较大的个体被选择的概率较大，所选择的个体形成一个中间种群 : 对中间种群 中的个体以一定的概率进行重组，其目的是期望通过对适应值较大的个体进行重组得到适应值更大的个体，重组后得到中间种群 : 对中间种群 中的个体以一定的概率进行变异，其目的是引进新的个体，以保持种群的多样性； 确定 中的哪些个体存活下来，以形成下一代种群； 从初始种群 开始，演化算法通过选择、重组、变异、存活选择等过程得到后代种群，然后再对后代种群重复上述过程，直到某种终止条件满足。当算法终止后，将所得到的适应值最大的个体作为问题的解。
三、演化算法设计
设计演化算法需要详细指明以下构成成分：
个体编码适应函数父体选择策略变化算子存活选择策略参数设置种群初始化终止条件
(一) 个体编码
个体（问题的解）的编码的目的是为了能够有效地执行遗传操作。如，若一个优化问题的解空间由整数构成，那么一种编码方式是采用整数的二进制编码：整数18编码为10010。
解的编码通常也称为染色体，或基因型，或个体。
编码空间也称为基因型空间或搜索空间，演化算法对个体的遗传操作是在基因型空间中完成的。
一个染色体解码后所对应的解称为该染色体的表现型。
解空间也称为表现型空间，演化算法对个体的评估和选择是在表现型空间中完成的。
(二) 适应函数
适者生存：同自然天气、地理条件、异种个体和同种个体进行斗争时，适应能力强的群体和个体能够生存下来，适应能力弱的个体被淘汰。
适应函数是区别种群中个体好坏的唯一方法，是进行选择的依据，直接影响到演化算法的收敛速度和效率。适应函数的作用是对基因空间中的每个染色体指定一个实数，称之为适应值，使得我们可以区分染色体的好坏。一般来说，一个染色体的适应值越大，表明该染色体越好。反之亦然。概念上讲，一个适应函数是从编码空间到实数域的一个函数。
例如：
该问题的一个解为一个 n 维向量
两个适应函数
一种选择是直接用目标函数 作为适应函数，显然向量 中 1 的个数越多，该向量就越接近最优解，其适应值也就越大，最优解 的适应值最大。另一方面，如果取 作为目标函数，这时最优解的适应值还是最大，但除了最优解 外，其他所有解的适应值均为 0。第一个适应函数允许逐步改进解的质量，第二个适应函数则无此作用。
在技术上，适应函数通常是一个从解空间到实数域的函数。 （比如某个函数f(x)，输入的x为二进制编码110110101，输出的适应度值为实数0.987）
（因为我们评估一个解的好坏，肯定是看一个实数指标值比较直观，例如小明考了99分，小刚考了64分，那么明显小明在这一轮考试中更优秀；而没有人愿意通过看一串二进制数来评估好坏，比如小明的适应度是10010111，小刚是10100101）
按如下过程对基因型空间的一个染色体进行评估：
先将该染色体解码为其对应的解，即表现型 然后用适应函数对表现型进行评估，并将评估值作为该染色体的适应值。
在许多情况下，演化算法求解的问题是一个优化问题，这时适应函数可以直接从目标函数得到或简单地由目标函数变换而成。
(三) 父体选择策略
演化算法通过从当前代种群产生下一代种群的方式，使得种群不断演化，从而逐步逼近问题的最优解。类似于生物，产生下一代个体的一个重要手段是对当前代中的个体进行重组。而父体的选择是重组的基础。父体选择的目的是期望较好个体的重组能够得到更好的后代。若一个个体被选择通过重组产生新的个体，那么该个体称为一个父体。并不是最好的一些个体总是被选择为父体。这是因为选择压力过大，搜索会过早终止，算法容易收敛到局部最优。当然，若选择压力过小，虽然可以保持种群的多样性，增加算法收敛到全局最优的概率，但算法的收敛的速度缓慢。有许多不同的父体选择策略，通常父体的选择是随机的，使得具有较高适应值的个体被选择作为父体的概率较大，具有较低适应值的个体被选择作为父体的概率较小。
(四) 变化算子
变化算子的作用是从已有的染色体中产生新的染色体，在解空间中产生新的解，包括重组算子和变异算子。
重组算子：
重组算子将两个或多个父体的信息进行组合，得到一个或多个后代染色体，期望通过重组较好父体的信息得到更好的后代染色体。重组算子是一个随机算子，在重组父体的信息时，每个父体的哪一部分信息被重组，以何种方式重组是随机的。
变异算子：
变异算子改变一个染色体的信息，得到一个新的染色体。其目的是通过引入新的染色体来增加种群的多样性，扩大搜索空间，从而避免演化算法陷入局部最优。变异算子是一个随机算子，通常假定变异算子引起染色体的一个随机、无偏的变化。
在不同的演化算法中，变化算子所起的作用有所不同：
在遗传算法中，重组算子是一个主要的变化算子，变异算子起辅助性的作用。在演化策略中，变异算子是一种主要的遗传算子，重组算子起辅助性的作用。在演化规划中，只使用变异算子，根本不使用重组算子。
变化算子的设计与所选择的编码方案有密切的关系，不同的编码方案，其相应的变化算子也有所不同。
(五) 存活选择策略
存活选择的作用是从当前代种群和由父体所产生的后代个体中选择出个体以形成下一代种群。
父体选择是随机的，而存活选择倾向于适应值较高的个体。譬如说，按照当前代种群中的个体和所有后代个体按照适应值排序，然后选择出最好的一些个体形成下一代种群。
(六) 参数设置
不同的演化算法有不同的参数：
演化策略中的变异步长遗传算法的种群规模、杂交概率和变异概率遗传程序设计中的树的深度等
参数设置有以下两种主要方法：
参数调整：
参数调整是算法设计中的一个典型方法，也是实际中用的最多的方法之一。参数调整是指通过选取不同的参数值，进行一系列实验（运行演化算法），比较实验结果，然后挑出使结果最好的参数，在算法运行过程中，参数保持不变。
参数控制：
参数控制是预先给定初始参数值，在算法的运行过程中，对参数进行动态地变更。有多种参数控制策略，如将参数p作为演化代数t的一个函数p(t)，随着演化代数的变化，参数p(t)动态地改变，因为参数的选取本身也是一个优化问题，所以也可以用另一个演化算法来优化参数，还可以只用一个演化算法在求解问题的同时对参数进行优化。
(七) 种群初始化
一个种群是编码表示的一个多重集。种群构成演化的单位。在演化算法中，种群是动态的、变化的。演化算法正是通过种群的演化而得到问题的最优解或近似最优解。种群的规模（即种群中个体的数目）通常是一个常数，在演化搜索中保持不变。
随机地产生初始种群：随机产生的目的是使初始种群中的个体均匀地分布在搜索空间中。
使用某种启发式算法产生初始种群：该法可使初始种群中包含较好的解，这可能使算法能更快地发现问题的最好解。然而该法产生的初始种群中个体不是均匀分布在编码空间中，这可能会导致算法过早收敛到局部最优解。
(八) 终止条件
若已知问题的最优适应值，当最好个体的适应值与最优适应值之差的绝对值小于给定的精度Ɛ>0时，可终止算法。然而，由于演化算法是随机算法，不能确保算法收敛到最优解，故上述条件有可能无法满足。
为确保算法终止，通常有以下终止条件：
算法的运行时间达到预先指定的最大运行时间算法计算个体适应值的总数达到预先指定的最大次数算法的演化代数达到预先指定的最大代数在连续若干代以后，个体适应值没有明显的改进种群的多样性降低到某个预先指定的阈值
算法的实际终止条件可能是上述若干条件的析取。最常用的是预先制定一个最大演化代数。
💡 关键要点
演化算法是一个大类，是根据模拟自然界生物进化过程而发展起来的一种通用问题求解方法，而非具体算法。 打个比方，“蛋糕”是一类食物的