改进遗传算法及性能测试

尚宇晴，左钱，王腾，李亦民，夏津

(上海机电工程研究所，上海 201100)

0 引言

遗传算法(genetic algorithm, GA)是由自然界生物遗传进化准则“物竞天择、适者生存”得到的启发而进行的计算机模拟研究。由美国Michigan大学的HOLLAND教授创造的一种基于Mendel生物遗传与Darwin进化机制的能解算复杂体系最优解的优化技术[1-2]。1967年，BAGLEY率先在论文中使用“遗传算法”这一概念[3]。20世纪70年代，DE Jong运用遗传算法理论进行数值函数最优值的求解尝试。20世纪80年代GOLDBERG概括总结得出遗传算法的基本结构布局。遗传算法是借用生物遗传学的观点[4]，从待解决的问题中可能存在解的一个种群开始，通过选择、交叉、变异等遗传操作提高个体的适应度，进化种群，从而得出最佳个体。其中每个个体表现性是由各自携带的基因类型而决定的。多个个体组成一个种群，而各个体的最佳程度通过适应度来评价，并将其适应度作为后续遗传操作的依据。标准遗传算法采用赌轮选择机理，每个个体被选择的概率与其各自适应度的大小有关，适应度越高被选中的几率越大，以便后续采用固定数值的交叉、变异概率算子进化种群。

由于标准遗传算法采用赌轮选择及固定交叉、变异算子使得种群易于出现早熟现象及稳定性差现象。早熟现象即为算法在寻找最优解的过程中过早陷入系统的局部最优中，且很难跳出局部困局寻找到全局最优解。故本文对标准的遗传算法进行改进，在选择操作时，将部分较优个体直接复制留下，剩余个体随机选择且只留下随机选择的两个个体中适应度较好的个体；对于交叉变异操作，采用了动态自适应的交叉、变异概率。交叉、变异概率的大小与种群适应度的大小有关。最后，利用权威检测函数对改进前后的遗传算法进行对比，通过实验结果显示，改进后的遗传算法收敛性及稳定性大大高于标准遗传算法，且改进后的遗传算法不会出现早熟现象。

1 改进遗传算法具体方案

1.1 改进选择算子

采用常规的轮盘赌选择法，每个个体被选中的概率与其适应度高低成正比。适应度越高的个体被选中的机会越大，但由于选择操作过程中的随机性，可能导致最优个体未被选择，而适应度较差的个体可能多次被选中，无法实现遗传算法的优胜劣汰的原则，而且在种群进化一定代数后，因种群中的个体适应度很相近，若再采用轮盘赌选择种群时会导致种群进化停滞。故现改进种群的选择操作，在进行选择个体时，先将种群个体按照适应度的大小进行排序[5]，取位于优势位置前1/4的个体直接选择复制于下一代，新种群剩余3/4的个体进行随机选择。具体方式为随机选择两个个体，比较其适应度大小，选择两者中较优个体。这样操作大大提高了适应度，较高个体占据了种群的比例且不失种群的多样性，使得遗传算法更高效实用。

1.2 改进交叉与变异算子

遗传算法中的交叉概率Pc和变异概率Pm对算法的收敛性有很大的影响[6-7]。Pc、Pm值较大易于产生新的个体，但过大使得个体的基因易于破坏，可能会改变适应度较高个体的基因，从而使得原本适应度较高的个体适应度变差，不易于种群的进化；而Pc、Pm过小不易产生新的个体，可能无法保证种群的多样性。根据种群进化的特点，在进化的初期，种群平均适应度普遍偏低，需要产生较多的新个体以便快速地寻找到最佳个体。在进化的后期，种群平均适应度普遍偏高，个体很接近于最佳个体，若再采用较大的交叉、变异概率会使得适应度高的个体特征被破坏。故采用固定的交叉、变异概率不利于根据种群的实际情况而进行进化种群。

现对标准遗传算法中固定的交叉、变异概率进行改进，采用动态自适应的交叉、变异概率值进行进化[8-9]。在进化的前期，种群的差异性很大，即种群适应度的方差较大，故可通过增大交叉概率Pc保证种群的多样性，而此时种群在进化过程无需变异概率Pm很高，以保证种群在进化过程的高效性；在进化的后期，种群差异较小，种群适应度很接近，即种群适应度的方差较小，为了找到全局最优解、避免种群寻优陷入局部最值中，应使得种群的变异概率Pm提高，以便获得不同的个体，而此时由于个体很接近，种群进化的交叉概率Pc无需过高。故可根据种群在进化过程适应度的变化特点，利用方差来满足种群进化过程前后期对交叉、变异概率值的不同要求。现引入了S型增长曲线sigmoid函数，函数图形如图1所示，从图中可以明显看出该函数的非线性，其表达式如式(1)所示。

(1)

图1 sigmoid函数曲线

sigmoid函数当自变量>0时，值域为[0.5,1)。当自变量为0时，函数值为0.5；当自变量趋于10时，该函数值趋于1，且该函数呈现明显的非线性：在自变量>0的情况下，自变量较小时，斜率较大；随着自变量增加，函数斜率减小。故可利用sigmoid函数的非线性，结合遗传算法进化特点与sigmoid函数值域情况，编制进化过程中的交叉概率公式如式(2)，变异概率公式如式(3)所示。

(2)

(3)

其中：Pc、Pm为需要进行交叉、变异操作个体的交叉、变异概率；Pc max、Pm max为该个体所在种群最大交叉、变异概率；Pc min、Pm min为该个体所在种群最小交叉、变异概率；k2的取值根据sigmoid函数的特点可选为10，k1的取值可根据需要解决的实际问题自行定义，用于修饰种群的方差。交叉概率Pc和变异概率Pm根据种群适应度方差的改变而作动态的自适应调整。在进化初期，种群个体差异性较大即种群适应度的方差较大，故交叉概率Pc较大、变异概率Pm较小，种群通过较大的交叉概率增加种群的多样性；在进化后期，种群个体差异性较小即种群适应度的方差较小，故交叉概率Pc较小、变异概率Pm较大，种群通过较高的变异概率产生新个体。

从公式中可以看出，不同代个体的交叉、变异的概率并不相同，它们的交叉、变异概率与种群适应度紧密相关。个体的交叉、变异概率根据种群适应度的变化作动态的自适应调节。

2 算法的收敛性(精英保留)

在遗传算法中，通过交叉、变异操作产生新的个体，随着群体的进化会产生越来越多的优良个体，但由于选择、交叉及变异操作的随机性会使得当前最优个体有可能被破坏，而这种情况对进化是不利的，影响算法的运行效率与收敛性。故为了确保种群在进化过程的收敛性，DE Jong博士针对遗传算法提出精英选择(elitist selection or elitism)策略，也称精英保留(elitist preservation)策略[10-11]。该策略的思想是迄今出现的最优个体，且不进行交叉、变异操作直接复制到下一代中。精英个体是迄今为止所有个体中适应度最高的个体，该个体所代表的特征就是解决问题的最优解，而采用精英保留策略可以很大程度上改善算法的收敛性，能够确保最优个体的特征在进化的过程中不会被破坏。RUDOLPH已经从理论上证明了采用精英保留策略可以保证算法的全局收敛性。其中，遗传算法流程图如图2所示。

图2 遗传算法流程图

3 性能测试

3.1 常见的测试函数

常见的测试函数很多[4,12]，本文通过Rastrigin函数、shubert函数及schaffer函数这3个典型测试函数对改进后的遗传算法进行检测。从函数的三维图可以看出这3个函数都存在很多的局部最值，若算法存在早熟现象的话，很容易收敛于这些局部最值中且停止进化。故可以通过此3个函数对改进后的遗传算法与标准遗传算法的收敛性及稳定性进行比较并测试改进后的遗传算法的性能。3个测试函数的表达式如表1所示。

表1 测试函数表达式

1) Rastrigin函数

Rastrigin函数有许多局部最小值，但该函数只有1个全局最小值在(0，0)点处取得，其对应最小函数值为0，对于其他异于点(0，0)的Rastrigin函数值均>0。Rastrigin函数的三维图如图3所示。

图3 Rastrigin函数三维图

2) shubert函数

shubert函数为复杂函数，存在760个局部极小值，只有在点(-1.42513，-0.80032)处取得全局最小值为-186.34。shubert函数的三维示意图如图4所示。

图4 shubert函数三维图

3) schaffer函数

schaffer函数有无数个极大值点，只有在点(0，0)处取得全局最大值，其最大值为1。且函数在最大值周围存在一圆脊，它们的取值均为0.990283，故很容易陷入此局部极小值中。schaffer函数的三维示意图如图5所示。

图5 schaffer函数三维图

3.2 测试结果

对于标准遗传算法采用轮盘赌进行选择、0.9的交叉概率和0.3的变异概率进行编程。对于改进后的遗传算法交叉概率范围为0.9～0.5，其中Pc max=0.9、Pc min=0.5；变异概率范围为0.2～0.001，其中Pm max=0.2、Pm min=0.001；用改进后的遗传算法与标准遗传分别对Rastrigin函数、shubert函数及schaffer函数3个函数寻找最值。为了使实验具有说服力，每种算法分别对每个函数实验15次，每次实验均随机产生50个种群个体进化40代，得出每代最佳个体的适应值随进化代数的变化曲线图，其中个体的适应度即为每个个体对应的函数值，从而通过实验结果比较改进前后遗传算法的差距并得出改进后遗传算法的性能。

1) Rastrigin函数测试结果

标准算法与改进后的算法均随机产生50个种群个体进化40代，每代最佳个体的适应值随进化代数的变化曲线如图6、图7所示。图6为标准遗传算法的进化过程，图7为改进后的遗传算法的进化过程。改进前后算法均仿真15次，观察15次算法寻优过程。

图6 标准遗传算法的进化过程

图7 改进后遗传算法的进化过程

从Rastrigin函数的三维图可以看出，函数在最优值附近有很多小峰值且最优值很接近于全局最优值，若算法不具备很好的收敛性，会在最优解附近停滞，极易收敛于局部最优值中。从实验仿真结果可以看出，虽然标准遗传算法寻找到的最优值很接近于全局最优值，但根据此函数的特点可以看出该算法非收敛该函数的全局最优值，而是寻找到Rastrigin函数最优值附近小峰值的局部最优值。而改进后的算法寻找最优值均为0与该函数最优值一致，且多次仿真均在进化20代时趋于稳定，说明改进后的遗传算法具有很好的全局收敛性且收敛速度较快，而且具有很好的稳定性。

2) shubert函数

两种算法均循环15次，每次循环随机产生的50个种群个体进化40代，其中每代最佳个体的适应值随进化代数的变化曲线图如图8、图9所示，图中每条曲线代表一次算法的寻优过程。图8为标准遗传算法的进化过程，图9为改进后的遗传算法的进化过程。

图8 标准遗传算法的进化过程

图9 改进后遗传算法的进化过程

从shubert函数的三维图可以看出，该函数有无数个极小值，且每个最小值都是很高的峰值，对于检测算法是否具有全局收敛性具有很好的权威性，若算法的进化不能实现全局搜索，进化过程中个体易陷入局部最值中。通过实验最佳个体适应度值随进化代数的曲线图可以看出，标准遗传算法15次的进化结果，寻找到的最优解并不收敛，结果停滞在不同的值，而改进后的遗传算法15次的仿真最终结果均收敛于shubert函数的全局最优解值-186.34，且均在进化35代左右趋于稳定。结果表明标准遗传算法存在早熟现象，对于复杂问题并不能很好地寻找到全局最优，而改进后的遗传算法具有很好的收敛性，不会陷入局部最优。

3) schaffer函数

改进前后两种算法均循环15次，每次循环随机产生50个种群个体然后进化40代，其中每代最佳个体的适应值随进化代数的变化曲线图如图10、图11所示。图中每条曲线代表一次算法的寻优过程。图10为标准遗传算法的进化过程，图11为改进后的遗传算法的进化过程。

图10 标准遗传算法的进化过程

图11 改进后遗传算法的进化过程

从schaffer函数的三维图可以看出，该函数有无数个极大值，且存在于最优点(0，0)周围一圈，无论算法从任何方向进行进化至最优值均会通过此圆脊，若函数进化能力有限会很容易收敛至局部最值0.990283而停止进化至全局最优值1。从实验结果可以看出，标准遗传算法多次进化收敛于局部最值0.990283，说明标准遗传算法存在早熟现象。而改进后的遗传算法在进化>35代之后均收敛于全局最优值1。

从3个权威检测函数可以看出标准遗传算法[13-14]对于处理复杂问题存在很大的局限性，而改进后的遗传算法均能快速准确地寻找到全局最优值，能够很好地处理求解复杂问题。

4 结语

本文通过改变遗传算法中选择、交叉、变异3个算子对标准遗传算法进行改进，并利用Rastrigin函数、shubert函数及shaffer函数3个典型测试函数对改进的遗传算法与标准遗传算法进行比较，实验结果表明，标准算法对于处理较复杂问题存在很大的局限性，而改进后的遗传算法具有更快的收敛速度和更好的稳定性，比标准遗传算法更易快速寻找全局最优解而且不易陷入局部最优中。