一种基于相异因子的最优保存策略*

张 雷 ，常敏慧

(1.运城学院 公共计算机教学部，山西 运城 044000；2.运城学院 应用数学系，山西 运城 044000)

遗传算法(GA)是根据生物进化理论和遗传变异理论提出的一种基于种群搜索的优化算法，其思想是通过选择复制和遗传算子的共同作用使种群不断进化，最终收敛到优化解[1]。在机器人控制、函数优化、参数辨别等方面得到了广泛的应用，但简单的遗传算法(SGA)具有一些固有的弊端，如局部收敛性、早熟等。参考文献[2]对交换和变异操作进行了改进，提出一种防止近亲繁殖的交换策略，有效地避免了基因缺失。但由于海明距离下限不随进化代数和本代平均海明距离变化，因而不利于产生种群多样性。参考文献[3]利用构造新选择算子，通过按亲缘关系放弃一个解而获得另一个解来保证算法在最优解的领域内的有效搜索，提高全局最优解的搜索能力和收敛速度。参考文献[4]采用混沌变异算子的进化算法，并提出“尺度收缩”的变异策略，从一定程度上提高了收敛速度。但由于采用线性交叉算子，在进行交叉之前不进行近亲判断和回避，因此交叉操作的效率不高。此外，许多文献还对遗传算法中的最优个体保存策略进行了研究[5～8]，其中最优保存遗传算法(ESGA)直接将最优个体保存到下一代，具有全局收敛性，但是使得下一代中的某些个体缺乏活力，协作能力差。本文提出一种基于相异因子的最优保存策略，用于最优个体相异因子较大，但目标值相近的个体，依次将种群中与最劣个体相似因子较大且目标值相近的个体替换。既可以通过新添加的个体来保证种群多样性，又可以保证全局收敛性。从而加快收敛速度，提高收敛性能。

1 相关定义

为了方便描述，引入以下定义：

定义 2 假设 n维空间的任意两个个体 M1=(x1，x2，…，xn)，M2=(y1，y2，…，yn)，每个分量的编码长度不同，其中编码采用m进制编码， 即xi=(xi1xi2…xij…xili)，yi=(yi1yi2… yij…yili)， 将第i个分量中对应位置相同的位数记为Ci(i=1，2，…，n)，则定义这两个个体间的相似因子为：

定义 3 假设 n维空间的任意两个个体 M1=(x1，x2，…，xn)，M2=(y1，y2，…，yn)，每个分量的编码长度不同，其中编码采用m进制编码， 即xi=(xi1xi2…xij…xili)，yi=(yi1yi2… yij… yili)，定义这两个个体间的相异因子为[8]：

2 基于相异因子的最优保存策略

在遗传操作过程中，首先从种群中找出最优个体ChromMaxHao和最劣个体ChromMaxBad，产生一个与最优个体相异因子μ较大的个体ChromFan，为了既能够保证种群多样性，又能加快收敛速度，再随机产生一个新个体ChromNew，比较ChromFan和ChromNew的目标值，找出与ChromMaxHao最接近的个体并记为ChromFind。依次计算种群中的个体与最劣个体ChromMaxBad之间的相似因子v。当v较大时，比较当前个体与ChromFind的目标值，如果当前个体的目标值小于ChromFind的目标值，则用ChromFind替换当前个体，这样不仅保证了种群的多样性，而且将种群中的最劣个体以及与其极其相似的个体都用较好的个体进行替换，加快了收敛速度。

采用基于相异因子的最优保存策略的遗传算法(DESGA)描述如下：

(1)设置遗传算法的基本参数，采用二进制编码，随机产生初始种群Chrom；

(2)计算Chrom中各个体适应度值FitnV；

(3)根据计算出的适应度值FitnV将种群Chrom依次进行选择、交叉和变异操作，得到种群SelCh；

(4)在种群SelCh中找出最优个体ChromMaxHao和最劣个体ChromMaxBad，根据相异因子μ计算得到ChromFind；

(5)根据相似因子依次用ChromFind替换与ChromMaxBad相似的个体；

(6)将 Chrom和 SelCh合并，得到新的Chrom；

(7)gen=：gen+1，若 gen小于最大代数，则转到(2)继续执行，否则循环结束。输出最优值。

3 仿真实验

为了验证本文提出的基于相异因子的最优保存策略的遗传算法(DESGA)的有效性，将该策略和算法分别应用到多个典型优化测试函数中，分别与最优保存遗传算法(ESGA)和简单遗传算法(SGA)进行分析和比较。其中，测试的基本参数设置如表1所示。染色体编码采用二进制编码。

表1 测试基本参数设置

本文所用测试函数F1、F2、F3选择参考文献[9]中的典型测试函数。

F1：一元多峰函数

maxf(x)=xsin(10π·x)+2.0，x∈[-1，2]，该函数具有多个极值点，全局最大值为：x=1.850 5，f(x)=3.850 3

F2：多元单峰函数

F3：多元多峰函数-10≤x1，x2≤10，该函数具有多个极值点，全局最小值为(x1，x2)=(-1.434 2，-0.800 3)，f(x1，x2)=-186.730 9

分别利用DESGA、ESGA和SGA对上述三个函数进行优化测试，测试结果如表2所示。

表2 测试结果比较

从表2可以看出，ESGA只是简单地将每一代产生的最优个体直接保留，有可能使得下一代中的某些个体缺乏活力，协作能力差，DESGA利用相异因子产生与最优个体目标值相近的个体，并且利用该个体将种群中与最劣个体相似因子较大且目标值相近的个体依次替换，这样不仅可以保证种群多样性，而且可以大大提高收敛速度。

本文提出了一种基于相异因子的最优个体保存策略的遗传算法(DESGA)，该算法相对于最优保存遗传算法(ESGA)和简单遗传算法(SGA)有更好的全局收敛性能。

[1]HOLLAND J H.Adaptation in natural and artificial systems[M].The University of Michigan Press，1975.

[2]边润强，陈增强，袁著祉.一种改进的遗传算法及其在系统辨识中的应用[J].控制与决策，2000，15(5)：623-625.

[3]杨世达，单志勇，李庆华.基于亲缘选择的遗传算法[J].计算机工程，2009，35(15)：10-12.

[4]骆晨钟，邵惠鹤.采用混沌变异的进化算法[J].控制与决策，2000，15(5)：557-560.

[5]孔春海，张志涌.基于最优保存并行混合遗传算法的直接盲信号检测[J].西安邮电学院学报，2007，12(1)：71-75.

[6]王秀坤，赫然，张晓峰.一种改进的最优保存遗传算法[J].小型微型计算机系统，2005，26(5)：833-835.

[7]尉宇，孙德宝.自适应最优保存的模拟退火遗传算法及应用[J].华中科技大学学报，2001，29(9)：46-47.

[8]毕惟红，任红民，吴庆标.一种新的遗传算法最优保存策略[J].浙江大学学报(理学版)，2006，33(1)：32-35.

[9]雷英杰，张善文，李续武，等.MATLAB遗传算法工具箱及应用[M].西安：西安电子科技大学出版社，2005.