进化算法的收敛速度的影响.doc

进化算法的收敛速度的影响
进化算法的收敛速度的影响
张彩虹
（数学与信息学院数学与应用数学00级5班）
摘 要

在进化过程中，可能会出现过早收敛现象，这主要是因为种群中出现了超级个体，按照一定的选择策略，该个体很快会在种群中占据绝对优势，从而使算法过早的收敛于一个局部的最优解，现在解决的方法有对超级个体的适应函数进行调整，从而控制该个体的选择概率，或增加个体的变异率来增加种群的多样性。同时，不同的群体规模和选择策略对算法性能的影响起到举足轻重作用。
关键词：进化算法；过早收敛；适应函数；变异率；选择策略

1引言
进化算法的思想来源于达尔文的“适者生存”的理论，其最大特点是群体搜索和群体中个体之间的信息交换，从而表现出以下优越性：进化算法在搜索过程中不易陷入局部最优，即使所定义的函数不连续、不规则或有噪声时，仍能以很大概率得到全局最优解；进化算法具有内在的并行性；再者，进化算法采用自然进化机制来表现复杂现象，能快速可靠地解决非常困难的问题；易介入到已有模型中且易于同别的技术混合等。因此，进化算法，目前在很多领域得到了广泛应用。
现在对进化算法的一些基本概念进行一下简单介绍[2]。进化计算在求解问题时是从初始给定的多个解开始搜索的，这些初始解的集合称为一个种群。适应值函数是种群中各个个体对各自适应环境的程度的一种量度，它通常是用户所提供的目标函数的一个合理的数学变换，而目标函数用能反映个体在种群中优劣程度的数学表达式表示。选择是决定以一定的概率从种群中选取若干对个体的操作。变异是指让遗传因子以一定的概率变化的操作。在通常的二进制编码方式下，变异操作只是简单的将因子之值取反，即将“0”变为“1”，将“1”变为“0”。
进化算法是一种基于自然选择和遗传变异等生物进化机制的全局性概率搜索方法。它从选定的初始解出发，通过不断迭代逐步改进当前解，直至最后搜索到最优解或满意解。
优化问题采用进化计算求解的一般过程包括以下几步：
1)随机给定一组初始解;
2)评价当前这组解的性能；
3)根据第二步的评价结果，从当前解中选择一定数量的解作为基因操作的对象；
4)对所选择的解进行基因操作例如交叉或变异，得到一组新的解；
5)返回到第二步，对该组新的解进行评价；
6)若当前解满足要求或进化过程达到一定代数，计算结束，否则转向第三步继续循环。
遗传算法自从诞生以后，已经在各个领域中得到了广泛的应用，但是遗传算法在应用过程中，也暴露出了许多缺点。在进化过程中，可能会出现过早收敛问题，当通过染色体的交叉和变异，种群已经很难产生优于亲本的子代个体时，就会发生早熟收敛。在均匀种群中经常发生这种情况，所有标准形式的交叉简单地重复产生当前的亲本。进一步优化将完全依赖于位变异而且可能非常慢。在遗传算法中，经常会遇到早熟收敛，因伴随着交叉和选择的作用，观察到的最优个体就会以指数速度繁殖，该个体很快占据种群的大部分。
对于早熟的原因，大至可以归结如下类型[1]：
2群体规模
群体规模与很多因素有关，当群体规模太小时，造成有效等位基因先天缺乏，即使采用较大概率的变异算子，生成具有竞争力的高阶模式的可能性极小，况且大概率变异算子对已有模式的破坏作用显著增大。同时，由于遗传算子存在随机误差（模式采样误差），妨碍小群体中有效模式的正确传播，使得群体进化不能按模式定理产生所预测的期望数量。根据模式理论和隐并行性，群体规模越大，遗传算子所处理的模式就越多，生成有意义的建筑模块并逐渐进化为最优解的机会就越高，同时，群体规模越大，群体中个体的多样性越好，算法陷入局部解的危险就越小，但是，群体规模增大，个体适应值计算与评估计算次数增加，计算量也随着增加，算法效率会降低。因此，为防止过早收敛，应该选择合适的群体规模，在计算量许可的情况下，尽量选择较大规模的群体，保证群体的多样性及其进化能力，如果采用可变规模群体，初始阶段应将群体规模保持在一个较大数值。
3 适应值函数[2]
在我们设计的进化算法中，物种规模一般都在几十到几百之间，与实际物种规模相比是很小的，一方面，如果个体繁殖量调节得不好，很容易出现超级个体，即该个体的适应值大大超过群体的平均适应值，这样很容易导致算法过早收敛于一个局部最优点；另一方面，在搜索的后期，群体的平均适应值，可能会接近群体的最优适应值，这样群体中实际上已不存在竞争，使搜索目标难以得到改善，出现停滞现象。这些现象和结果不利于优化，可能导致一些异常个体在群体中占据很大的比例，这是我们所不期望的现象，因为这样可能导致未成熟的收敛现象。因为如果这些异常个体竞争力太突出，那么会控制选择过程，从而影响算法的全局优化性能。
在算法运行的初始阶段，群体中可能存在少数适应值很高的个体，若使用基于适应值的概率选择方法，这些个体就会被大量繁殖，从而在群体中占有很大的比重。而适应值很低的个体在群体中过早地被淘汰，造成群体多样性急剧下降。这样可导致群体前收敛，或者将搜索引向局部极值点。在后期阶段，在采用一定的变异概率的变异算子的作用下，群体保持了相对稳定的多样性，对于最优解附近变化比较平缓的适应值差异变得比较小，个体被选中的概率几乎相同，选择渐近为随机过程，群体性能在很长的代数内得不到显著改进。
因此，有必要对适应函数进行针对性的调整，或者减少个体选择概率的差异即降低选择压力，或者增大个体选择概率的差异，即提高选择压力，统称为适应值标度变换。适应值调整可以保持群体中个体间存在一定程度的竞争，从而促进所期望的群体进化过程。适应值调整的方法以有以下几种：
3.1 线性变换[1]
线性适应值标度变换的一般公式为：

其中，为适应函数值，为变换后适应函数值，为系数。一般要求满足，即变换前后群体的平均适应值相等。
在实际应用中，噪声变换后当前群体中最佳个体的适应值设为-2.0(经验值),则由联合求解得出:
,
对于适应值比较低的个体，若，则取，那么变换后的个体选择概率：

若取，则个体选择概率保持不变，另外，Forrest 推出了采用当前群体适应值标准方差进行变换的方法[3]：

其中，根据经验确定，使得，为群体适应值标准方差。
3.2 幂函数变换[1]
幂函数变换的公式为：

其中，依赖于具体问题性质和遗传算法性能控制选择变换后个体的选择概率：

显然，，即当前群体最佳个体的选择概率是增大。
3.3 指函数变换[1]
指函数变换的公式为：

其中，依赖于具体问题性质和遗传算法性能控制选择，当前群体最佳个体的选择概率随着变化而变化。对于具体的适应函数，当比较小时，当前群体最佳个体的选择概率减少；当比较大时，当前群体最佳个体的选择概率增大。
4. 选择算子[2]
选择策略对算法性能的影响起举足轻重的作用，不同的选择策略将导致不同的选择压力，即下一代中父代个体的复制数目的不同分配关系。较大的选择压力使最优个体具有较高的复制数目，从而使得算法的收敛速度较快，但容易出现过早收敛现象。相对而言，较小的选择压力一般能使群体保持足够的多样性，从而增加了算法收敛到全局最优的概率，但算法的收敛速度较慢。所以为了防止出现早熟收敛的现象，需要选择一种适当的选择策略。
下面是几种常用的选择策略：
4.1 基于适应值比例的选择
适应度比例法又称旋轮线模型或蒙特卡罗模型,这个模型是利用比例于各个个体适应度的概率决定其子孙的遗留可能性。若某个个体I,以各自的选择被选取的概率已表示为:

其中,为个体的适应度.
表1给出用适应度比例法表示和选择概率的例子。表中,表示原适应度,,表示调整后的适应度,采用表示选择概率,表中采用的比率。当选择的概率约定后，产生0-1区间的随机数，以决定哪些个体要进行交配。一般地，选择概率大的个体希望多次参加交配，它的遗传因子就会在群体中扩大。

表1 适应度比例法表示和选择概率的示例

个体

1
2.5
6.25
0.18
2
1.0
1.00
0.03
3
3.0
10.00
0.26
4
1.2
1.44
0.04
5
2.1
4.41
0.13
6
0.8
0.64
0.02
7
2.5
6.25
0.18
8
1.3
1.69
0.05
9
0.9
0.81
0.02
10
1.8
3.24
0.09

适应度比例法的一种最典型且使用最多的方法是转盘式选择,实施该策略的步骤是:
a. 计算个体的相对适应值；
b. 根据选择概率把一个圆盘分式N份，其中第扇形的半分角为；
c. 针对个体计算从1到第个个体的累计相对适应值；
d. 产生[0，1]内的随机数，满足，则选择个体；
转盘式选择使得种群中各个体都有机会根据其相对适应值被选中。
4.2 基于排名的选择
使用基于适应值比例的选择常常会出现过早收敛现象或停滞现象.避免这种现象的方法之一是使用基于排名的选择策略.这种方法的基本思想是:
I 首先根据个体的相对适应值在种群中的排名来分配其选择概率.这种“分配”是基于数学方法的。
II然后再根据这个概率使用轮盘策略，这样个体的绝对适应值并不直接影响后代的数量，人们可以使用各种不同的数学“分配”方法来调节个体选择概率，以达到防止或减少过早收敛和停滞的现象。
表2给出了基于排名的选择策略中适应值和选择概率的关系的一个例子。由此表可见，所有个体按适应度大小排序，因而选择概率和适应度无直接关系，而仅与序号有关。这种方法的不足之外在于选择概率和序号的关系须事先确定。此外，它和适应度比例方法一样都是一种基于概率的选择，所以仍有统计误差。

表2 基于排序的选择方法的示例

序号
个体

1
3
3.0
10.00
0.35
2
1
2.5
6.25
0.20
3
7
2.5
6.25
0.15
4
5
2.1
4.41
0.10
5
10
1.8
3.24
0.06
6
8
1.3
1.69
0.05
7
4
1.2
1.44
0.04
8
2
1.0
1.00
0.03
9
9
0.9
0.81
0.02
10
6
0.8
0.64
0.001

基于排名选择策略的优点:一是可以避免出现过早收敛现象或停滞现象;二是无论对极小化和极大化的问题,它都不需要进行适应值的标准化和调整,可以直接使用原始适应值进行排名选择。
4.3 基于局部竞争机制的选择。
基于这种思想的典型选择方法是锦标赛选择，其基本做法是：在选择时先随机的在
种群中选择个个体进行锦标赛式的比较，从中选出适应值最好的个体进入下一代，
复用这种方法进行直到下一代个体数为种群规模时为止。这种方法也使得适应值好的个体在下一代具有较大的“生存”机会，同时它只能使用适应值的相对值作为选择的标准，而与适应值的数值大小不成直接比例，所以，它能较好的避免超级个体的影响，一定程度的避免过早收敛现象和停滞现象。
4.4 精华保存法
上述3种选择法都是基于概率的选择，概率选择法的优点在于对适应度低的个体也给予选择的机会，能维持群体的多样性。另一方面，即使适应度高的个体也有被淘汰的可能，这是概率选择的缺点。
为弥补概率选择法上述不足，常常采用精华保存法。这种方法，在现世代适应度大的个体不是受交叉和突然变异的影响，而是无条件留给下一代，这种方法常被用于最优化问题。在选择算子后保留当前最好解的SGA能认概率收敛到全局最优解。
Michalewicz[4] 在拥挤因子模型的基础上提出了一种新的选择算子。这种算子在进行选择时需要有两个步骤：
第一步，先从种群中选择个个体作为父代个体（不要求数目一定是个，可以小于个），然后再从种群中选择个个体（要求数目一定是个），将这个个体从种群中剔除。选择基于个体的适应值：适应值越大的个体被选择作为父代个体的概率越大，适应值越小的个体被选择从种群中剔除的概率越大。在进行完第一步后，各群的个体被分三类：
（1）个（不严格）作为父代的个体；
（2）个（严格）被剔除的个体；
（3）剩余的个体，称为“中性”个体。
第二步，生成下一代个体。下一代个体由两部分组成，一部分是个原有的个体（上一代个体除去个被剔除的个体），另一部分是由父代个体新生成的个个体。Michalewicz把使用这种选择算子的算法称为modGA，图3给出modGA的算法流程。
Begin
；
初始化
计算的适应值；
While（不满足终止条件时）
Begin
;
从中选择父代个体；
从中选择被剔除的个体；
生成；
计算的适应值；
end
end

图3 modGA的算法流程

从上面的描述中可以发现，这种选择方法存在一个病态问题：个（不严格）作为父代的个体集合和个（严格）被剔除的个体集合有可能出现相重叠的情况。也就是说，个体有可能既被选作父代个体，又被选作剔除的个体。显然，我们希望具有较高适应值的个体被剔除的概率很小，那么，我们就可以通过修改的生成方法来解决这个问题：
第一步：从中选择个（不严格）父代个体，每个被选择的个体被标记为可以用于某一种固定的遗传算子；
第二步：从中选择个（严格）个体，将它们复制到中；
第三步：从个（不严格）父代个体中成生个（严格）后代；
第四步：将新生成的个（严格）后代插入到。
第一步和第二步中的选择是根据个体的适应值进行的。
ModGA中的选择方法与前面所介绍的其他一些选择方法存在一些重要的不同之处。首先，父代个体和子代个体都有可能出现在后一代中。在第一步和第二步的选择中，一个个体既有可能被选择成为个（不严格）父代个体之一，又有可能被选择成为下一代个体之一，其次，所有算子都直接作用于个体上。在第一步中，一些个体被标记为“变异”，一些个体被标记为“交叉”。在第四步中对标记为“变异”的个体进行变异，对标记为“交叉”的个体进行交叉。Michalewicz证明了这种选择方案使得模式定理仍然成立。ModGA的优点在于它能够更有效地利用存储空间：这种算法减少了适应值高的个体产生多个相同后代的概率。在ModGA中，一个适应值高的个体可能会有多个后代，但每个后代都不完全相同，GA正是由于适应值高的个体容易产生多个相同的后代才导致了早熟收敛，所以这种方法可以降低早熟收敛的概率。
5. 变异概率
当变异概率比较小时,群体多样性下降太快,容易导致有效基因的迅速丢失且难以恢复;当变异概率比较大时,尽管群体的多样性可以保持在较高水平,但是高阶模式被破坏的概率也随之增大.
5.1自适应变异率的设计
在简单遗传算法中,变异率是个常数。通常，对于变异率是一常量的情况，经过多次迭代后，群体的素质会趋于一致，这样就形成了“近亲繁殖”，但近亲繁殖对后代的质量不利。同样，如果双亲的染色体非常接近，其后代对于双亲素质提高也极少。因此，群体基因的多样性变差不仅会减慢进化历程，而且可能导致进化停滞，过早收敛于非最优解。这里提出一种与父串间相对距离成反比、随迭代率（迭代次数与最大迭代次数的比值）指数下降的自适应变化的方式。具体公式设计如下：

式中：、分别为最大和最小变异率；分别为迭代次数和最大迭代次数；分别为父串间的欧式距离和最大欧式距离。
这种方法在群体中各个个体过分趋于一致时，会使变异的可能性增加，从而提高群体的多样性，增强算法维持搜索的能力；而在群体的多样性已经很强时，则减小变异率，以免破坏优良个体。这种方法同样能够保证在迭代初期，对劣质个体赋予较大的变异率，以造成足够的扰动，扩大解空间，而随着迭代次数的增加，该变异率逐步减少至一常量，从而保证平滑收敛。这是符合优胜劣汰规律的；同时，为了防止发生局部收敛和出现随机搜索，在整个迭代过程中，将变异率控制在0.01-0.45之间，即选取。
6 结束语
本文通过研究影响进化算法收敛速度的因素,从群体规模，适应值函数，选择算子以及变异概率等方面找出了影响过早收敛的原因,并在此基础上根据各个因素找到了一些解决过早收敛的方法，为将来进一步研究奠定了基础。
参考文献
[1] 李敏强.林丹等.遗传算法的基本理论与应用.科学出版社，2002.3
[2] 李陶深.人工智能. 重庆大学出版社 2002.4
[3] 王正志,薄涛.进化算法.国防科技大学出版社，2000.11
[4] Michalewicz,Z., Genetic Algorithms + Data Structure = Evolutionary programs, Springer-Verlag, Berlin, Heideberg, 2nd Edition,1994.

The influence on the convergence speed of evolutionary algorithms
Zhang caihong
(Class 5, Grade 2000, School of Math.& Information)
Abstract
In the course of evolution, there may be premature convergence. It is mainly because the super individual has appeared in the population, according to a certain selection strategy, this individual will occupy the absolute predominance in the population soon, and this makes the algorithm to converge exploitation too early. Now the solution about this question is to adjust the fitness function of the super individual to control it selection probability, or to increase the mutation probability of the individual to increase the diversity of the population. Meanwhile, different population scale and selection strategy play a very important role in the algorithm function.
Keywords: Evolutionary algorithms; Premature convergence; Fitness function; Mutation probability; selection strategy.

9