Page 157 - 大数据技术及安全研究

第四章 大数据时代演化算法与进化算法的有关分析

也可以用目标函数变换的方式来定义。在协同演化（Coevolution）时，适应值通
常由某一对策与群体中相左的对策进行抗衡的获利来确定。个体在种群中的存活
量和繁殖量也可以作为适应值的一种度量，这种度量方式常在人工生命的研究中
使用。目前，我们在设计演化算法时，群体规模一般在几十到几百之间，与实际

物种的规模相差甚远。因此，个体繁殖数量的调节在演化计算中比较重要。如果
群体中出现了超级个体，即该个体的适应值大大超过群体的平均适应值，则按适
应值比例进行选择时，该个体很快会在群体中占有绝对的比例，从而导致算法较
早地收敛到一个局部最优点，这种现象称为过早收敛。又如在搜索过程的后期，

虽然群体中存在足够的多样性，但群体的平均适应值可能会接近群体的最优适应
值。在这种情况下，群体中实际上已不存在竞争，因而搜索目标难以得到改善，
这种现象称为停滞现象。基于上述原因，改变算法性能的方法之一，就是对适应
值进行调节，即通过变换来改变原适应值间的比例关系。常用的比例变换有线性

变换及指数函数变换等。
（四）选择策略
选择策略对算法性能有举足轻重的影响作用。不同的选择策略将导致不同的
选择压力，即下一代中父代个体的复制数目的分配关系不同。较大的选择压力使

最优个体具有较高的复制数目，从而使算法收敛速度较快，但也容易出现过早收
敛现象。相对地，较小的选择压力一般能使群体保持足够的多样性，从而增大了
算法收敛到全局最优的概率，但算法的收敛速度一般较慢。
按选择机制的不同，常用的选择策略可分为基于适应值比例的选择、基于排

名的选择和基于局部竞争机制的选择。基于适应值比例的选择包括繁殖池选择、
轮盘式选择、Boltzmann 选择等。基于排名的选择主要包括基于线性排名和基于
非线性排名的选择。基于局部竞争机制的选择主要包括锦标赛选择、（μ，λ）
和（μ+λ）选择、Boltzmann 锦标赛选择等。

（五）遗传算子的设计
遗传算子的设计是演化计算中最富有特色和创造性的部分。基本的演化算
法只使用再生、杂交和变异三种操作。编码策略的不同造成了遗传操作的多样
性。对二进制编码，杂交算子有点式杂交和均匀杂交方式，且点式杂交算子又分

为单点式杂交和多点式杂交。其它编码方式的杂交算子和变异算子更是丰富多
彩。自然界的遗传操作按操作对象的不同可分为基因级、个体级和群体级三个层

·145·