基于生物入侵思想的自适应遗传算法优化

简静芳

(漳州职业技术学院 计算机工程系, 福建 漳州 363000)

美国密歇根大学J.H.Holland提出的遗传算法(Genetic Algorithm，GA)是借鉴生物进化论，模拟生物界自然选择和遗传变异机制来求解复杂问题的随机化搜索和优化算法[1]，具有自适应寻优、智能搜索且收敛性好等特点，能有效解决组卷中的约束优化问题，被广泛应用于智能组卷过程中[2-3]。

标准遗传算法(SGA)采用固定的交叉和变异概率，在搜索更优解的过程中将使种群的多样性降低，从而导致算法停滞不前，使得算法只能搜索到局部最优解，因此造成算法早收敛现象及收敛速度慢等问题[4]。

为了解决早收敛问题，目前许多学者进行深入研究，大体上提出3种改进方法：小生境技术、自适应遗传算法和混合遗传算法[5]。小生境技术注重保持种群多样性，但并没有产生群体多样性，虽然对算法有一定地改进，但不能从根本上解决早收敛问题。混合遗传算法在算法复杂度和计算量方面耗费较大，所以也非优选算法。此外Srinvas等人[6]提出自适应遗传算法(Adaptive GA，AGA),有效地提高了遗传算法的收敛速度，在一定程度上预防了早收敛现象，但是由于该算法对较优个体进行保护，易使算法陷入局部最优，依然不能有效解决早收敛问题[7]。

在这里我们将生物入侵思想引入自适应遗传算法优化中，提出基于生物入侵思想的自适应遗传算法(Improved Adaptive Genetic Algorithm based on biological Invasion，IIAGA)，在较大程度上能比较好地解决早收敛现象。

1 早收敛现象分析及应对

1.1 早收敛现象分析

早收敛现象是指算法在搜索到最优解之前便收敛于局部最优解，即出现早熟现象，最终的最优个体适应度小于实际最优个体适应度。

由于现实条件制约，种群规模有限且一般保持一定，遗传算法的选择操作会保护优秀个体，使种群多样性降低，而种群多样性越小，则越不可能产生更优子代，将导致算法停滞，因此可能只搜索到局部最优解，从而引起早收敛现象。由此可见，算法的早收敛与种群的多样性有直接的关系，要解决早收敛现象，就是尽可能保证种群的多样性[5]。

1.2 早收敛现象的应对

遗传算法存在一个比较矛盾的问题:为保证能全局收敛、避免早收敛，必须要保证种群个体的多样性；然而，为了使算法拥有较快的收敛速度，又必须保证种群中的个体尽快靠近最优解，因而不可避免地在一定程度上降低种群多样性。因此想要有效地解决早收敛现象就要考虑保持群体多样性与收敛速度的平衡，只有综合考虑这两个方面提出的应对早收敛措施，才能起到真正的优化作用[8]。

本文提出的IIAGA，就是综合考虑了多样性和收敛速度的平衡，尽可能从根本上解决早收敛现象，保证收敛速度，优化提高遗传算法的性能[9]。

2 基于生物入侵思想的自适应遗传算法

IIAGA主要通过两个方面解决多样性和收敛速度平衡问题：首先，根据种群的实际情况对AGA交叉和变异概率进行非线性化调整，有效地保证种群的多样性；其次，利用生物入侵思想，用新生个体替换较差个体，并通过控制入侵概率，以保证算法的收敛速度。

2.1 非线性化调整AGA交叉和变异概率

遗传算法中控制参数的设置直接影响系统性能，这些参数主要包括交叉概率Pc、变异概率Pm及种群规模。当Pc、Pm增大，算法新空间搜索能力增强，越能探测到优良个体,但容易破坏较优个体，影响收敛速度；Pc、Pm减小，算法的开发能力增强，保持较优个体能力增强，但是种群的多样性降低，易出现早收敛，因此选择合适的Pc、Pm值直接影响遗传算法的收敛性[10]。在SGA中，一般取0.4≤Pc≤0.99，0.001≤Pm≤0.1。 固定的Pc、Pm容易引起早收敛，为获得算法更好的性能，一般根据算法的实际情况动态地调整Pc、Pm参数。

2.1.1 传统 AGA中交叉和变异概率

在Srinvas等人的传统AGA中，对Pc、Pm进行线性自适应调整，使Pc、Pm能根据适应度值的变化动态调整，如公式(1)和公式(2)所示。k1、k2、k3、k4∈(0，1)，fmax为最大适应度值，f′为要交叉的两个体中取值较大的适应度值，favg为平均适应度值，f为要变异个体适应度值[11]：

(1)

(2)

在遗传算法中，我们一般用适应度分布的离散程度来衡量种群中个体的多样性程度，当种群的个体适应度值趋于一致或局部最优时，为避免早收敛，跳出局部最优，要增加种群的多样性，从公式(1)、(2)中可见，此时favg靠近fmax，fmax-favg取值较小，会自适应调整Pc、Pm值变大，达到预期效果；而当种群个体的适应度值比较分散时，需要使种群中的个体尽快靠近最优解，以便加快收敛速度，此时fmax-favg取值较大，将调整Pc、Pm值变小。从理论上可见，这种改进方法在一定程序上解决了多样性和收敛速度平衡问题，但它们存在一些突出的缺限。

首先，在进化初期，fmax并没有达到全局最优解，而如果此时f或f′达到fmax时，fmax-f′=0和fmax-f=0，因此Pc、Pm均为0，此时算法对最优个体进行保护，较优个体基本上处于不变化的状态，算法停滞，使算法陷入局部最优，从而使算法出现早收敛现象。此外，算法进化过程中，Pc、Pm值直接是由个体适应度值f或f′进行调整的，缺乏全局性，因此当算法陷入局部最优时，很难跳出，使算法直接陷入早收敛。

2.1.2 IAGA(改进的AGA算法)中交叉和变异概率

IAGA将favg-fmax作为评价种群早收敛程度的重要指标，直接用favg-fmax值对Pc、Pm进行非线性自适应调节，如公式(3)、公式(4)所示，式中k1、k2均大于0，且根据算法需要进行取值：

(3)

(4)

在算法进化过程中，favg-fmax≤0，所以Pc∈[0.5，1],Pm∈[0，0.5], 当种群的个体适应度值趋于一致或局部最优时，favg靠近fmax，favg-fmax取值较大，Pc将变小，Pm将变大，在一定程度上增强种群的多样性，避免早收敛现象；而当种群个体的适应度值比较分散时，favg-fmax取值较小，Pc将变大，Pm变小，在一定程度上增强生成优良个体的能力，加快收敛速度。

在实际算法的进化过程中，早收敛现象主要表现在种群内适应度值暂时最大的那些个体的趋同程度，所以在算法中要考虑计算favg-fmax时一些较差个体将直接影响favg值，从而影响favg-fmax值，因此可以排除这些较差个体的影响，用favg′来替代favg，favg′表示将个体适应度值大于favg的先求和后再取平均值，这样能更好表现适应度较优的个体间的趋同程度，准确地体现个体的早收敛程度，因此IAGA由公式(5)、(6)调整Pc、Pm值：

(5)

(6)

2.2 生物入侵优化算法

在生物界，生物入侵是一种常见现象，即外来生物在人为因素或自然因素作用下，迁徙到异地，当该物种适应当地环境并生长繁殖时，将对当地的生物或环境产生影响。我们在优化算法时，将生物入侵的思想引入遗传算法中，目的就是使新生个体代替原来适应度较差的个体，为种群注入新的个体，增加种群的多样性，使得在很大程度上预防早收敛现象。但是，也不能无限制地增加新生个体数量。我们引入入入侵率Pr，即入侵的新个体数量占种群规模的比例。入侵率越大，表明更新的染色体基因越多，将导致较优个体被破坏，影响收敛速度。入侵率越低，表明种群中新生个体越少，越易导致早收敛的发生[12]。我们围绕保持群体多样性与收敛速度的平衡这一问题进行算法改进，在此表现为合理地控制入侵率Pr,如公式(7)所示，以保证算法的平衡：

(7)

其中k3>0,favg′-fmax≤0，所以Pr∈[0，0.5]。当种群适应度值趋于早收敛时，要增加种群的多样性，favg′-fmax取值较大，Pr变大，即入侵率变大，防止早收敛；当种群适应度值趋于离散时，favg′-fmax取值较小，Pr变小，将会保持优良个体，保证收敛速度。可见，引入Pr能有效地平衡保持群体多样性与收敛速度这两个方面，很大程度上改善遗传算法的性能。

3 仿真验证

为了验证IIAGA全局收敛性和收敛速度等方面的性能，我们用一个多峰值测试函数f(x)=xsin(10πx)+2.0,x∈[-1，2]在MATLAB中进行仿真验证，并与SGA、AGA、IAGA等仿真曲线进行对比，验证算法的性能优劣。函数f(x)全局收敛于3.850 3，我们对4种遗传算法均选用二进制编码，种群规模设定为40，编码长度为10，选用比例选择操作，同时采用单点交叉和单点变异，并设置最大进化代数200作为算法的结束条件。此外SGA中交叉概率Pc为0.7，变异概率Pm为0.1，在AGA中选择k1=k2=0.7,k3=k4=0.1,IAGA中设置k1=0.5,k2=1,IIAGA中取k1=0.5,k2=1,k3=1，在MATLAB中进行算法仿真，仿真结果如图1—5所示。

图1 IIAGA最佳和平均适应度曲线 图2 SGA和IIAGA平均适应度曲线

图3 AGA和IIAGA平均适应度曲线 图4 IAGA和IIAGA平均适应度曲线

图5 SGA、AGA、IAGA和IIAGA最佳适应度曲线

其中图1为IIAGA在进化过程中的最佳适应度曲线和平均适应度曲线。可以看出，两曲线相互趋同，且收敛于极大值处，表明算法收敛得很顺利，并没有陷入早收敛状态，保证种群的多样性，同时收敛速度也比较快，说明算法能满足我们既定的要求。

接着对另外几种算法进行比较，图2是SGA与IIAGA平均适应度曲线比较。从曲线中可以看出IIAGA的平均适应度值明显较高，说明IIAGA的种群个体优于SGA，同时IIAGA在稳定性方面及收敛速度方面明显优于SGA。

图3为AGA与IIAGA平均适应度曲线比较。AGA在曲线上的表现优于图2中的SGA，虽然在收敛速度上和IIAGA相差不多，但是AGA的平均适应度值总体低于IIAGA曲线，即IIAGA拥有更优秀的个体。

图4所示为IAGA与IIAGA平均适应度曲线比较。IAGA平均适应度值大体与IIAGA趋同，但稳定性方面较差，同时收敛速度上也差于IIAGA，由此可见IIAGA在性能上相较于其它遗传算法都有所改善，显示IIAGA的可行性。

图5为SGA、AGA、IAGA和IIAGA最佳适应度曲线。从图中可以看出，AGA和SGA在算法开始时，陷入局部最大适应度值，在曲线上表现为出现一定时间上的停滞，进化多代后才最终收敛于全局最大适应度值，即两者均出现不同程度的早收敛现象，其中SGA情况比AGA来得严重些，AGA的收敛速度优于SGA。IIAGA和IAGA最佳适应度曲线明显优于SGA、AGA，尤其表现在收敛性方面，IIAGA和IAGA能较快地收敛于全局最大适应度值。但从图中也可以发现IAGA在曲线稳定性方面不如IIAGA，在算法开始的一小段时间内，出现小幅度的振荡，且并非在全局极大值处，即出现早收敛倾向，虽然最后还是收敛于全局极大值处，但在收敛速度方面受一定的影响，由此也可以验证出IIAGA的优势，它能有效地保证种群的多样性，即防止出现早收敛，同时还能保证收敛速度，且具有较好的稳定性。

4 结 语

从上述结果可以看出，改进的IIAGA在平衡种群多样及收敛速度上有明显的效果，有效地防止早收敛现象，可以进一步应用于智能组卷过程中，同时可以通过对k1、k2、k3进行进一步的选择，使算法具有更好的性能。

[参考文献]

[1] 耿辉，武妍.基于动态入侵的自适应遗传算法研究[J].计算机工程与应用，2011,47(7):40-42.

[2] 薛清龙，李郴.自动组卷策略中遗传算法的优化[J].电脑编程技巧与维护,2010(6):50-52.

[3] 李军.基于遗传算法的智能组卷系统研究[D].天津:天津大学，2008.

[4] 张宇，郭晶，周激流.动态变异遗传算法[J].电子科技大学学报，2002,31(3):234-239.

[5] 赵苓.基于遗传算法的智能组卷策略的研究[D].哈尔滨:哈尔滨工程大学，2012.

[6] SRINVAS M ,PATNAIK L M.Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms[J].IEEE Transactions on Systems,Man and Cybernetics,1994,24(4):656-667.

[7] 金晶，苏勇.一种改进的自适应遗传算法[J].计算机工程与应用,2005(18):65-69.

[8] 吴浩扬，朱长纯，常炳国，等.基于种群过早收敛程度定量分析的改进自适应遗传算法[J].西安交通大学学报，1999,33(11):27-30.

[9] 王淑佩.基于改进的遗传算法组卷系统应用研究[D].湖南:湖南大学，2005.

[10] 刘怀兰，牛辉，王佳.基于改进遗传算法的智能组卷模型优化[J].华中科技大学学报：自然科学版，2013,41(5):82-85.

[11] 张开便，李喜艳，董振华.一种自适应遗传算法在自动组卷中的应用[J].福建电脑，2013(4):119-121.

[12] 潘晓辉.在线考试系统中组卷技术的研究[J].价值工程，2010(14):159-161.