群体智能与仿生计算：Matlab技术实现最新章节_杨淑莹著

2.4 进化策略算法仿生计算

2.4.1 进化策略算法

1.基本原理

20世纪60年代，德国柏林工业大学的I.Rechenberg和H.P.Schwefel等在进行风洞实验时，由于设计中描述物体形状的参数难以用传统方法进行优化，因而利用生物变异的思想来随机改变参数值，获得了较好的结果。随后，他们对这种方法进行了深入的研究和发展，形成了一种新的进化计算方法——进化策略。

进化策略算法的基本流程如下：

种群初始化（随机分布个体）→重组（更新个体）→变异（更新个体）→适应度计算（评价个体）→选择（群体更新）。

进化策略算法采用重组算子、高斯变异算子实现个体更新。在进化策略的早期研究中种群里只包含一个个体，并且只使用变异操作。在每一代中，变异后的个体与其父代进行比较，并选择较好的一个，这种选择策略被称为（1+1）策略。这种进化策略虽然可以渐近地收敛到全局最优点，但由于点到点搜索的脆弱本质使得程序在局部极值附近容易受停滞的影响。

1981年，Schwefel在早期研究的基础上，使用多个亲本和子代，后来分别构成( μ + λ )-ES和( μ , λ )-ES两种进化策略算法。在( μ + λ )-ES中，由 μ 个父代通过重组和变异，生成 λ 个子代，并且父代与子代个体均参加生存竞争，选出最好的 μ 个作为下一代种群；在( μ , λ )-ES中，由 μ 个父代生成 λ 个子代后，只有 λ ( λ ＞ μ )个子代参加生存竞争，选择最好的 μ 个作为下一代种群，代替原来的 μ 个父代个体。

进化策略（Evolution Strategies，ES）是专门为求解参数优化问题而设计的，而且在进化策略算法中引进了自适应机制。进化策略是一种自适应能力很好的优化算法，因此更多地被应用于实数搜索空间。进化策略在确定了编码方案、适应度函数及遗传算子以后，算法将根据“适者生存，不适者淘汰”的策略，利用进化过程中获得的信息自行组织搜索，从而不断地向最佳解方向逼近。隐含并行性和群体全局搜索性是它的两个显著特征，而且具有较强的鲁棒性，对于一些复杂的非线性系统求解具有独特的优越性能。因此研究这一算法的原理、算法步骤，以及它的优、缺点，对于在各领域解决实际问题和进一步完善算法，都有很大的益处。目前，这种算法已广泛应用于各种优化问题的处理，如神经网络的训练与设计、系统识别、机器人控制和机器学习等领域。

2.基本流程

进化策略的基本流程如下。

① 初始化种群，假设其种群规模为 μ 。

② 进入迭代操作。

③ 产生新个体：

通过重组算子，生成 λ 个新个体。

通过高斯变异算子，令这 λ 个新个体进一步改变。

④ 计算父代与子代个体的适应度值。

⑤ 选择算子：

对于( μ + λ )-ES进化策略，令 μ 个父代与 λ 个子代个体一同参加选择，确定性地选择 μ 个最好个体，组成下一代的种群。

对于( μ , λ )-ES进化策略，从子代（ λ 个）个体中，确定性地选择 μ 个最好个体，组成下一代的种群。

⑥ 记录种群中的最优解。

⑦ 判断是否满足停止条件，如果是，则输出最优解，并退出；反之，则跳转到步骤③，继续迭代。

进化策略算法的流程图如图2-18所示。

图2-18 进化策略算法流程图

3.进化策略算法的构成要素

由图2-18可以看到，进化策略的基本构成包含几个部分：染色体种群的构造，适应度计算，重组算子，变异算子，选择和终止条件。其中适应度计算、终止条件与前面遗传算法等算法大体相同，这里不再赘述。下面将对进化策略其他特有的要素进行详细说明。

1）染色体构造

与遗传算法通常使用的二进制编码不同，进化策略采用传统的十进制实型数表达问题。为了与算法中高斯变异算子配合使用，染色体一般用二元表达方式构造。

其形式如下：

( X , σ )=(( x ₁ , x ₂ ,…, x _L ),( σ ₁ , σ ₂ ,…, σ _L ))

X 为染色体个体的目标变量， σ 为高斯变异的标准差。每个 X 有 L 个分量，即染色体的 L 个基因位。每个 σ 有对应的 L 个分量，即染色体每个基因位的方差。

2）重组算子

重组（Recombination）是将参与重组的父代染色体上的基因进行交换，形成下一代的染色体的过程。

目前，常应用的重组算子有离散重组、中间重组、混杂重组。下面的部分将介绍几种重组算子。

（1）离散重组

离散重组是随机选择两个父代个体来进行重组产生新的子代个体，子代上的基因随机从其中一个父代个体上复制。

然后将其分量进行随机交换，构成子代新个体的各个分量，从而得出如下新个体：

（2）中间重组

中间重组则是通过对随机两个父代对应的基因进行求平均值，从而得到子代对应基因的方法，进行重组产生子代个体。

这时，新个体的各个分量兼容两个父代个体信息，而在离散重组中则只含有某一个父代个体的因子。

（3）混杂（Panmictic）重组

混杂重组方式的特点在于父代个体的选择上。混杂重组时先随机选择一个固定的父代个体，然后针对子代个体每个分量再从父代群体中随机选择第二个父代个体。也就是说，第二个父代个体是经常变化的。至于父代两个个体的组合方式，既可以采用离散方式，也可以采用中值方式，甚至可以把中值重组中的1/2改为[0，1]之间的任一权值。

3）变异算子

变异（Mutation）的实质是在搜索空间中随机搜索，从而找到可能存在于搜索空间中的优良解，经过多次尝试，从而找到全局的最优解。若变异概率过大，则使搜索个体在搜索空间内大范围跳跃，算法的启发式和定向性作用就不明显，随机性增强，算法接近于完全的随机搜索；但若变异概率过小，则搜索个体仅在很小的邻域范围内跳动，发现新基因的可能性下降，优化效率很难提高。

进化策略的变异是在旧个体的基础上添加一个正态分布的随机数，从而产生新个体。

X 为染色体个体的目标变量， σ 为高斯变异的标准差。每部分都有 L 个分量，即染色体的 L 个基因位。 X 和 σ 之间的关系是：

即

式中( x _i ( t )， σ _i ( t ))——父代个体的第 i 个分量；

( x _i ( t +1)， σ _i ( t +1))——子代新个体的第 i 个分量；

N (0,1)——服从标准正态分布的随机数；

N _i (0,1)——针对第 i 个分量重新产生一次符合标准正态分布的随机数；

τ′ 和 τ ——全局系数和局部系数，通常都取1。

上式表明，新个体是在旧个体基础上添加一个独立的随机变量 N (0, σ ( t ))变化而来的。二元表达方式简单易行，得到广泛的应用。

4）选择算子

选择机制（Selection）为进化规定了方向：只有那些具有高适应度的个体才有机会进行繁殖。在进化策略里，选择过程是确定性的。

在不同的进化策略中，选择机制也有所不同。

( μ + λ )-ES，在原有 μ 个父代个体及新产生的 λ 个新子代个体（共 μ + λ 个个体）中，再择优选择 μ 个个体作为下一代群体，也被称为精英机制。

( μ , λ )-ES，这种选择机制是依赖于出生过剩的基础上的，因此要求 λ ＞ μ 。在新产生的 λ 个新子代个体中择优选择 μ 个个体作为下一代父代群体。无论父代的适应度和子代相比是好是坏，在下一次迭代时都被遗弃。

在( μ + λ )-ES选择机制中，上一代的父代和子代都可以加入下一代父代的选择中， μ = λ 或 μ ＞ λ 都是可能的，这种选择机制对子代数量没有限制，这样就最大程度地保留了那些具有最佳适应度的个体。但是它可能会增加计算量，降低收敛速度。

在(μ,λ)-ES选择机制中，只有最新产生的子代才能加入选择机制中。从 λ 中选择出最好的 μ 个个体，作为下一代的父代，而适应度较低的 λ-μ 个个体被放弃。

4.进化策略算法群体智能搜索策略分析

进化策略和遗传算法及进化规划都是进化计算的一种，是通过模拟生物界自然选择和自然遗传机制的随机化搜索算法。它们都遵循达尔文的生物进化理论“物竞天择、优胜劣汰”，且求解过程相同，即从随机产生的初始可行解出发，经过进化择优，逐渐逼近最优解。三者都是渐进式搜索寻优，经过多次的反复迭代，不断扩展搜索范围，最终找出全局最优解。这三者的进化计算都采用群体的概念。尽管早期的进化策略中存在(l+1)-ES，及( μ +1)-ES是基于单个个体的，但最后也发展为( μ + λ )-ES或( μ , λ )-ES，可以同时驱动多个搜索点，体现并行算法的特点。此外，它们在自适应搜索、有指导的搜索及全局寻优等方面都具有很多相似之处。

1）个体行为及个体之间信息交互方法分析

从产生子代的过程来看，遗传算法使用交叉算子和变异算子，进化规划只使用变异算子，而进化策略使用了重组算子和变异算子。但是重组算子只是起到辅助作用，就如变异算子在遗传算法中的作用一样。

重组算子采用对群体中的个体两两进行基因位随机组合，产生具有两个父代个体部分基因的子代个体。通过这种方式，可以使一些优良个体的基因与其他个体进行优化组合，产生新的个体，保持种群的多样性。进化策略的重组算子，不仅可以继承不同父代个体的部分信息，还可以通过中值计算或加权的方法产生新的信息。而遗传算法的交叉算子，仅仅是交换父代个体的部分基因，不能产生新的基因。

进化策略的变异算子是最主要的进化方法，是每一个个体必需的；遗传算法是对旧个体的某个基因做补运算；而进化策略的变异算子与进化规划类似，也采用了高斯变异算子。它是在旧个体的基础上添加一个正态分布的随机数，从而产生新个体。与进化规划一节中介绍的高斯变异算子不同的是，它不以适应度信息作为高斯变异的方差，而是通过加上服从高斯分布的随机值实现方差的改变，再以符合这个改变后的方差的高斯随机数实现基因值的改变。由于符合高斯分布的随机数取得均值附近的值的概率较大，因此变异幅度并不会很大，这符合自然界中细微变异远多于巨大变异的进化规律，使得个体通过渐变，逐渐趋向全局最优。

2）群体更新机制

选择作为进化计算中的重要操作算子，起到了引导群体进化方向的作用，通过确定性地或依据概率从种群中选择出优良个体，形成新的种群，从而使得种群整体趋向更优。在前面介绍的两种进化计算中，遗传算法的选择对象只有子代个体群体，并且是依据个体的适应度值进行轮盘赌选择算子，由于每个个体都是依据选择概率被选出，因此，即使较差的个体也有机会被选中。进化规划的选择也是一种概率性的选择，选择对象是父子两代种群，通过选择一部分个体，与种群中每个个体进行适应度的比较，并以比较结果作为依据，进行择优选择。这种选择方法受比较个体的数目和优劣程度影响较大，当数目较小或它们的适应度值偏低时，这种选择的随机性将变大；反之，当数目较大或适应度值较高时，这种选择偏向于确定性选择。

进化策略的选择则是完全确定的选择，它只依据适应度值对种群中的个体进行由高到低的排名，并选择较好的一部分个体，作为下一代的种群。选择对象可以是父子两代种群，也可以单是子代种群。依据选择对象可分为两种选择方式，从 λ 个个体或 μ + λ 个个体中挑选 μ 个个体组成新群体。( μ + λ )-ES与进化规划算法类似，选择的对象是父子两代的个体。而( μ , λ )-ES则是只从新生成的子代个体进行选择。

粗略地看，似乎（ μ + λ ）选择最好，它可以保证最优个体存活，使群体的进化过程呈单调上升趋势。但是，( μ + λ )选择保留旧个体，有可能会是过时的可行解，妨碍算法向最优方向发展；也有可能是局部最优解，从而误导进化策略收敛于次优解而不是最优解。( μ , λ )选择全部舍弃旧个体，使算法始终从新的基础上全方位进化，容易进化至全局最优解。( μ + λ )选择在保留旧个体的同时，也将进化参数 σ 保留下来，不利于进化策略中的自适应调整机制。( μ , λ )选择则恰恰相反，可促进自适应调整机制。实践证明，( μ , λ )-ES优于( μ + λ )-ES，成为当前进化策略的主流。

2.4.2 进化策略算法仿生计算在聚类分析中的应用

1.构造个体

例如，一个待聚类样品图如图2-19所示，编号在每个样品的右上角，不同的样品编号不同，而且编号始终固定。

图2-19 待聚类样品图

采用符号编码，位串长度 L 取12位，基因代表样品所属的类号（1～4），基因位的序号代表样品的编号，基因位的序号是固定的，也就是说某个样品在染色体中的位置是固定的，而每个样品所属的类别随时在变化。如果基因位为 n ，则其对应第 n 个样品，而第 n 个基因位所指向的基因值代表第 n 个样品的归属类号。

每个个体包含一种分类方案。假设初始某个个体的染色体编码为（4，1，2，1，4，4，2，3，4，3，2，3），其含义为：第3、7、11个样品被分到第2类；第8、10和12个样品被分到第3类；第2、4个样品被分到第1类；第1、5、6、9个样品属于第4类。这时还处于假设分类情况，不是最优解，如表2-5所示。

表2-5 初始某个个体的染色体编码