绪论

在图书馆“逛街”的时候偶然看到了这本书，发现写的真心不错，主笔之一的焦院士也凭借“进化计算理论、方法及其应用”获得了2008年的陕西省科学技术奖一等奖，于是想结合我个人的理解，截取一些重点，把本书内容分享给大家，供大家讨论指正，也当作我对进化算法的更进一步了解的见证。

本人不是生态学和数学专业学生，仅仅作为抛砖引玉，还望多多海涵。当然还是希望大家能够借一本或买一本原书，以便了解到书中内容的全貌。

1. 1 生物进化与优化

1.1.1 繁殖

生命的持续是通过繁殖作用实现的。在大部分情况下，繁殖能够使生物量增长。

最初出现的是无性（孤雌）繁殖，但在无性繁殖中上代和下代只有信息的复制，而没有不同信息的交流。这样无法促成进化现象，也就是一般来说有性繁殖带有DNA上的信息交换，无性繁殖是没有的。到了有性繁殖这里，不仅有了DNA的分割和交换，还增加了对于基因/表现空间的探测速率，特别是在变化的环境下。

1.1.2 变异

变异指的是同种生物世代之间或同代不同个体之间的差异，我们感兴趣的是能遗传的变异，因为只有遗传变异才能作为进化的材料。在细胞核分子水平上，遗传变异主要表现为突变，突变又分为三种：

1. 基因突变
2. 染色体突变
3. 基因重组

1.1.3 竞争

生存竞争是指生物与环境所发生的关系，这种关系包括：种内斗争、种间斗争、生物与自然环境斗争三个方面。

产生生存斗争的重要原因在于生物的高度繁殖力。反过来说，如果多个种群有高度繁殖力就很可能导致生存斗争的产生。资源有限，则必定引起竞争。同种之间，生存竞争最为激烈。由于他们对于食物和空间等的生存条件最为相似，生活资源又有限，同种斗争比不同种斗争更激烈，也会产生淘汰。

我个人理解就是内卷卷死同类，外卷并没有那么消耗......

1.1.4 选择

自然选择学说是达尔文进化论的核心，自然选择是指适合于环境的生物被保留，不适合的生物被淘汰。自然选择通过微小的有利变异的积累而促使生物进化。

选择作用集中表现在对群体中基因频率的影响，但是自然选择并不直接作用在基因型上，而是直接作用在表现型上。选择压力是指在两个基因频率之间一个比另一个更能生存下来的优势。选择压力增大，环境剧烈变化，生存斗争加剧，严重冲击生物的正常生活，导致物种大量死亡，同时出现少量新的突变类型。

繁殖是所有生命的共同特征；变异保证了任何生命系统能在正熵世界中连续繁殖自己，对于限制在有限区域中的不断膨胀的种群来说，竞争和选择不可避免。进化，就是这四个相互作用的随机过程一代一代地作用在种群上的结果。

个体和物种的区别：它们的遗传编码和遗传编码所表现出来的行为特性。

个体的遗传编码通常被称为基因型（genotype），而表现出来的行为被称为表现型（phenotype）。

基因型：为进化过程中所获信息的存储提供了一种机制。多效性和多基因性导致了遗传结果不可预料。

表现型：它的变化实际上是基本遗传结构和现有的环境条件之间相互作用的一个复杂非线性函数。

多效性：一个单一基因可以同时对多个表现型特征产生作用 多基因性：单一的表现型特征可能由多个基因共同的相互作用所确定

生物进化显然是一种求解优化问题的过程，给定了初始条件和环境约束，通过选择可以得到与最优解尽可能接近的表现型。但是环境持续变化，物种跟在环境变化的后面，不断地向一个新的最优解进化。这就是进化算法的思想源泉。

1.2 进化计算

进化计算是一类模拟生物进化过程与机制来求解问题的自适应人工智能技术。它的核心思想基于：从简单到复杂、从低级到高级的生物进化过程本身是一个自然的、并行发生的、稳健的优化过程，这一过程的目标是对环境的适应性，生物种群通过“优胜劣汰”及遗传变异来进化。

进化算法（evolutionary algorithm, EA）就是基于这种认识的一种随机搜索技术。它们模拟由个体组成的群体的学习过程，其中每个个体表示给定问题搜索空间的一点。

进化算法从选定的初始解出发，通过不断迭代的进化过程逐步改进当前解，直至最后搜索到最优解或满意解为止。在进化过程中，算法在一组解上，采用类似于自然选择和有性繁殖的方式，在继承原有优良基因的基础上，生成具有更好性能指标的下一代解的群体。

进化算法求解的一般步骤：

1. 随机给定一组初始解。
2. 评价当前这组解的性能。
3. 若当前解满足要求或进化过程达到一定代数，计算结束。
4. 根据（2）的评价结果，从当前解中选择一定数量的解作为基因操作对象。
5. 对所选择的解进行基因操作（如交叉、变异等），得到一组新解，转到（2）。

在搜索方法里，进化算法属于枚举法、解析法和随机法里的随机法。在多个步骤里，比如说初始解生成以及选择、交叉与变异等遗传操作过程中，均是随机处理。

进化算法相比传统搜索算法有以下不同：

1. 进化算法不直接作用在解空间上，而是利用解的某种编码表示；
2. 进化算法从一个群体即多个点而不是一个点开始搜索，帮助进化算法用较大的概率找到整体最优解；
3. 进化算法只使用解的适应性信息（目标函数值），并在增加收益和减少开销之间权衡。传统搜索算法可能还要用到导数；
4. 进化算法使用随机处理方法而不是确定性的转移规则。

智能性：进化算法的智能性包括自组织、自适应和自学习等。确定编码方案、适应值函数和遗传算子后，利用信息自发组织搜索。

本质并行性：进化算法本身非常适合大规模并行，而且因为它采用种群的方式组织搜索，因而可以搜到解空间的多个区域，相互交流信息，这是它的内涵并行性。

1.2.1 进化计算的主要分支

1. 遗传算法（Genetic Algorithm, GA）
2. 进化规划（Evolutionary Programming, EP）
3. 进化策略（Evolutionary Strategy, ES）
4. 遗传编程（Genetic Programming, GP）

1.2.2 进化计算的数学基础

Holland和Goldberg为解释进化算法的功效建立了基于模式分析的模式定理、隐含并行性定理以及积木块假设。

1.2.2.1 模式定理

定义1.1 设遗传算法中的个体$p∈\{0,1\}^l$，则记集合$S=\{0,1,*\}^l$为一个模式（schemata）。其中$*$为通配符。（𝑙 通常表示个体的长度，也就是个体的基因序列中基因（位元）的数量。）

意思是个体 𝑝 是一个长度为 𝑙 的二进制字符串，其中每个位置的值可以是 0 或 1。

定义1.2 若一个个体$p$的每一位与模式$s$相匹配，则称$p$是$s$的一个表示。 定义1.3 一个模式$s$的阶就是出现在模式中的"0"和"1"的数目，记为$o(s)$。 定义1.4 一个模式$s$的长度就是模式中第一个确定位置和最后一个确定位置间的距离，记为$\delta(s)$。

假定在给定的时间步$t$，一个特定的模式$s$在种群$P(t)$中包含有$m$个字符串，记为$m=m(s,t)$。经过交叉、变异和选择操作后，则在种群$P(t+1)$中，模式$s$的代表串的数量的期望值为

$E[m(s,t+1)]=m(s,t)\frac{\overline{f(s)}}{\overline{f}}[1-p_c\frac{\delta(s)}{l-1}-o(s)p_m] (1.1)$

其中，$\overline{f(s)}$表示模式$s$在$t$时刻的所有代表串的适应值的均值，称为模式$s$的适应值；$\overline{f}$表示种群$P(t)$中所有个体的适应值的平均值；$p_c$和$p_m$分别表示交叉和变异概率。

由（1.1）式有： 定理1.1 即模式定理。适应值在种群平均适应值之上的、长度较短的、低阶的模式在遗传算法的迭代过程中将按指数增长率被采样。

遗传算法根据模式的适应值、长度和阶次来为模式分配搜索次数，为那些适应值较高、长度较短、阶次较低的模式分配的搜索次数按照指数率增长，反之则衰减。

1.2.2.2 隐含并行性定理

在长度为$l$，规模为$n$的群体中，包含了$2^{l}$~$(n\times2^l)$个不同的模式。所以每进行一次迭代所处理的模式数目往往远远大于个体数目。Holland教授将遗传算法的这个特性称为隐含并行性。

定理1.2 即隐含并行性定理。设$\varepsilon∈(0,1)$是一个很小的数，$l_s<[(l-1)\cdot\varepsilon]+1$，群体规模为$N=2^{l_s/2}$，则遗传算法在一次迭代中所处理的“存活率”大于$(1-\varepsilon)$的模式数约为$O(N^3)$，其中，符号“[ ]”表示向上取整。

隐含并行性定理反映出遗传算法对空间的搜索效率是非常高的，它对种群进行一次处理就处理了$O(N^3)$个模式，同时，隐含并行性定理反映出遗传算法存储空间信息的能力也是很强的，每个种群中存储了$O(N^3)$个模式的信息。

1.2.2.3 积木块假设

定义1.5 具有高适应度、长度短、低阶的模式被称为积木块（building block）。

就像搭积木块一样，“好”的模式在遗传操作下相互拼搭、结合，产生适应值较高的串，从而找到更优的可行解。

1.2.2.4 小结

模式定理保证了较优的样本数呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在着寻找到全局最优解的可能性。

积木块假设则指出，遗传算法具有寻找到全局最优解的能力，即积木块假设在遗传算子的作用下，能生成高于瓶颈适应值的、长的、高阶的模式，最终生成全局最优解。

1.2.3 进化算法的收敛性理论

收敛性的定义：

定义1.6 设$Z_t$为$t$时刻种群中所包含个体的适应值的最大值，$f^{*}$为适应值函数$f(x)$在所有可能的个体所组成的集合$X$中所取得的最大值。若$Z_t$满足

$\lim_{t \to +\infty}P\{Z_t=f^*\}=1$

则称算法收敛到最优解。

1.2.3.1 基于压缩映射原理的收敛性分析

定义1.7 设X为一个非空集合，若$d$是一个$X \times X$到$R$的映射，并且对于$\forall x,y,z∈X$满足以下条件，则称$d$为$X$上的度量或距离函数，称$(X,d)$为度量空间。

1. $d(x,y)\ge0$，并且$d(x,y)=0$，当且仅当$x=y$。
2. $d(x,y)=d(y,x)$。
3. $d(x,y)\le d(x,z)+d(z,y)$