2.2 进化算法
作为复杂性研究的方法，自然现象本身又是我们解决各种问题时获取灵感的源泉，在复杂优化问题中也是如此。近十余年来，遗传算法（Genetic Algorithm，GA）、进化策略（Evolutionary strategy，ES）、进化规划（Evolutionary Programming，EP）等进化类算法在理论和应用两方面发展迅速，并且效果显著，逐渐融合形成了一种新颖的模拟进化的计算理论，统称为进化计算（Evolutionary Compulation，EC）。进化计算的具体实现方法与形式被称为进化算法（Evolutionary Algontbm，EA）。进化算法是一种受生物进化论和遗传学等理论启发而形成的求解优化问题的随机算法，虽然出现了多个具有代表性的重要分支，但它们各自代表了进化计算的不同侧面，各具特点。
2.2.1 遗传算法
遗传算法（Genetic Algorithm，GA）是由J.Holland于1975年受生物进化论的启发而提出的。GA是基于“适者生存”的一种高度并行、随机和自适应的优化算法，它将问题的求解表示成染色体的适者生存过程，通过染色体群一代代的不断进化，包括复制、交叉和变异等操作，最终收敛到最适应环境的个体，从而求得问题的最优解或满意解。GA是一种通用的优化算法，其编码技术和遗传比较简单，优化不受限制性条件的约束，而其中两个最显著特点则是隐含并行性和全局解空间搜索。
遗传算法是一类随机优化算法，但它不是简单的随机比较搜索，而是通过染色体的评价和对染色体中基因的作用，有效地利用已有信息来指导搜索，有希望改善优化质量的状态。标准遗传算法的优化框图如图2.1所示。
算法的主要步骤可描述为如下几步。
（1）随机产生一组初始个体构成初始种群，并评价每一个体的适配值（Fitness Value，也称为适应度）。
（2）判断算法收敛准则是否满足。若满足，则输出搜索结果，否则执行以下步骤。
（3）根据适配值大小以一定方式执行复制操作。
（4）按交叉概率Pc执行交叉操作。
（5）按变异概率Pm执行变异操作。
（6）返回步骤（2）。
图2.1 标准遗传算法的优化框图
上述算法中，适应度是对染色体（个体）进行评价的一种指标，是GA进行优化所用的主要信息，它与个体的目标值存在一种对应关系。复制操作通常采用比例复制，即复制概率正比于个体的适应度，如此意味着适应度高的个体在下一代中复制自身的概率大，从而提高了种群的平均适应度；交叉操作通过交换两父代个体的部分信息构成后代个体，使后代可以继承父代的有效模式，从而有助于产生优良个体；变异操作通过随机改变个体中某些基因而产生新个体，有助于增加种群的多样性，避免早熟收敛。
有关遗传算法的研究成果已相当丰富，包括编码方案、遗传算子的设计及操作概率的自适应性控制策略等。各种各样的改进算法层出不穷，其应用范围几乎涉及优化问题的所有领域，有关遗传算法方面的专著国内外也已有很多。
2.2.2 进化策略
进化策略是由德国数学家I.Rechenberg和H.P.Schwefel等人于二十世纪六十年代提出的一类数值优化算法。进化策略缘于生物进化中的自然突变和自然选择思想，强调的是个体层次上的改变。Rechenberg提出的原始进化策略，（1+1）策略，它采用的是一种简单的变异选择机制，即每一代通过高斯分布变异算子作用在一个个体上产生一个子代。由于（1+1）策略难以收敛到最优解，且搜索效率相对较低，因此其改进的方法就是增加种群内个体的数量，即（μ+1）进化策略。此时种群内含有μ个个体，随机抽取一个个体进行变异，然后取代群体中最差的个体。为了进一步提高搜索效率，H.P.Schwefel随后推广了Rechenberg的原始进化策略，建立了所谓（μ+λ）和（μ，λ）进化策略，其中，μ表示当前种群的规模，λ表示由当前种群通过杂交和变异而产生的中间种群的规模。（μ+λ）是从两个种群的并集中选择μ个最好的个体作为下一代种群，而（μ，λ）是从包含λ个个体的中间种群中选择μ（1≤μ≤λ）个最好的个体作为下一代种群，（μ+λ）和（μ，λ）这两种方式在进化策略中均占据着重要地位。
2.2.3 进化规划
进化规划方法最初是由美国科学家L.J.Fogel等人在二十世纪六十年代提出的。它在求解连续参数优化问题时与进化策略的区别很小，进化规划仅使用变异与选择算子，而绝对不使用任何重组算子。其变异算子与进化策略的变异类似，也是对父代个体采用基于正态分布的操作进行变异，生成相同数量的子代个体，即μ个父代个体总共产生μ个子代个体。进化规划采用一种随机竞争选择方法，从父代和子代的并集中选择出μ个个体构成下一代群体。其选择过程为：对于由父代个体和子代个体组成的大小为2μ的临时群体中的每一个个体，从其他（2μ-1）个个体中随机等概率地选取出q个个体与其进行比较。在每次比较中，若该个体的适应值不小于与之比较的个体的适应值，则称该个体获得一次胜利。从2μ个个体中选择获胜次数最多的μ个个体作为下一代群体。
2.2.4 遗传算法、进化规划和进化策略之间的异同点
以遗传算法为代表的三种进化算法在本质上是相同的，但它们又有区别。其中，进化策略与遗体算法相比，主要不同之处在于遗传算法是将原问题的解空间映射到位串空间上，然后再进行遗传操作，它强调的是个体基因结构的变化对其适应度的影响；而进化策略则是直接在解空间上进行遗传操作，它强调的是父代到子代行为的自适应性和多样性。
进化规划与遗传算法的区别主要表现在以下三个方面。
（1）在对待求问题的表示方面，进化规划因为其变异操作不依赖于线性编码，所以可以根据待求问题的具体情况而采取一种较为灵活的组织方式；典型的遗传算法则通常要把问题的解编码成为一串表达符号，即基因组的形式。前者的这种特点有些类似于神经网络对问题的表达方法。
（2）在后代个体的产生方面，进化规划侧重于群体中个体行为的变化。与遗传算法所不同的是，进化规划没有利用个体之间的信息交换，所以也就省去了交叉和插入算子，而只保留了变异操作。因此，在不考虑搜索效率的前提下，在应用方面，进化规划更易于掌握，也更便于实现。
（3）在竞争与选择方面，进化规划允许父代与子代一起参与竞争，正因为如此，进化规划可以保证以概率1收敛的全局最优解；而典型遗传算法若不强制保留父代最佳解，则算法是不收敛的。
进化规划与进化策略的区别主要体现在以下两个方面。
（1）在编码结构方面，进化规划是将种群类比为编码结构，而进化策略则是把个体类比为编码结构。所以，前者无须再通过选择操作来产生新的候选解，而后者还要进行这一操作。
（2）在竞争与选择方面，进化规划需要通过适当的选择机制，从父代和当前子代中选取优胜者组成下一代群体；而进化策略则是通过一种确定性选择，根据适应值的大小，直接将当前优秀个体和父代最佳个体保留到下一代中。