一种多目标混合进化算法的研究

梁国伟　王社伟　赵雪森

摘 要：针对遗传算法的不足，提出将禁忌搜索方法、免疫算法、遗传算法融和的多目标混合进化算法。该算法引入禁忌搜索法，避免了传统遗传算法早熟现象的发生；引入基于浓度的自适应变异操作，克服算法由于变异概率不变导致的求解过程长，解的多样性差的缺陷；引入外部精英集，避免最优解的丢失，通过ZDT系列测试函数的仿真实验并与NSGA-Ⅱ算法进行比较，验证了算法的有效性。

关键词：多目标优化；遗传算法；多目标混合进化算法；ZDT测试函数

中图分类号：TP18 文献标识码：A

Abstract：A multiobjective hybrid evolutionary algorithm （MHEA） was put forward aiming at the shortcomings of the traditional genetic algorithm， which combines taboo search algorithm， immune algorithm and genetic algorithm. This algorithm avoids the premature phenomenon of the traditional genetic algorithm through importing the taboo search algorithm. The operator of adaptive mutation based on the density overcomes the problem of long solving process caused by the constant mutation probability and bad diversity of the solution. Then external elite set was introduced to avoid the loss of the optimal solution. Finally the simulation of ZDT series test functions and the comparison with NSGA-Ⅱ algorithm verifies the effectiveness of the algorithm.

Key words：Multiobjective optimization；genetic algorithm； MHEA； ZDT test functions

2.3 算法简介

遗传算法[4，5]因其高度的并行处理能力、强鲁棒性和全局搜索能力而被广泛地应用于诸多领域。理论上遗传算法依“概率1”收敛于问题的最优解，然而实践应用中，遗传算法会表现出早熟现象、局部寻优能力较差等不足，所以一些常规遗传算法并不一定是针对某一问题的最佳求解方法。

禁忌搜索法[6]具有灵活的记忆功能和藐视原则，并且在搜索过程中可以接受劣解，因而具有较强的爬山能力，搜索时能够跳出局部最优解，从而增强获得更好的全局最优解的概率。但其搜索性能完全依赖于邻域结构和初始解。

免疫算法[7]可以通过细胞的分裂和分化作用，对抗体的产生进行促进或者抑制，体现了自我调节功能，保证了个体的多样性。

由于遗传算法、禁忌搜索法、免疫算法各有优缺点，因此将三种算法相结合，互相取长补短，则可能设计出性能优良的新的全局搜索算法，可以加快算法的收敛性同时提高算法的多样性。

3 多目标混合进化算法（MHEA）

本文引入禁忌搜索法[8]，避免早熟现象的发生，提高了局部搜索能力；采用基于浓度的自适应变异操作，克服了算法由于变异概率不变导致的求解过程长，解的多样性差的缺陷；引入外部精英集，避免了最优解的丢失，下面介绍算法的实现：

3.1 算法的设计

1）将部分精英集中的个体加入到种群POP0中并进行选择操作，可以提高种群的收敛速度。

2）交叉操作：

由于交叉算子在搜索最优解的进程中是一个破坏性同时也是产生新解的过程，因此遗传算法常常很快收敛到比较好的解，但是往往不能收敛到最优解，本文采用单点交叉算子。

3）禁忌搜索法：利用遗传算法与禁忌搜索法相结合，克服遗传算法早熟和收敛慢的缺点，具体步骤如下：

（1）对选择操作产生的新种群的个体进行禁忌搜索；

（2）查找禁忌表中是否有此个体记录；

（3）如果有，再看是否满足特赦准则；

（4）如果满足特赦准则，再看是否满足收敛准则；

（5）满足收敛准则，继续进行交叉操作，产生新种群，然后转到1）；

（6）如果不满足特赦准则，禁忌表中也没有此个体记录，则放人禁忌表；

（7）继续查看是否满足收敛准则，满足后输出结果，否则进行上述的交叉操作。

4）基于浓度的自适应变异算子

相比变异概率不变情况下，自适应变异更加符合生物遗传规律，有利于提高种群多样性。借用免疫算法中对抗体产生进行促进或者抑制，可以自我调节，从而保证个体多样性的思想，本文提出了一种基于浓度的自适应变异算子。

3.2 外部精英集

由图1可知，最初的精英集由初始群体中适应度最高的个体填充，随后由交叉和变异操作产生的最优个体对精英集进行更新，如果个体的数量超过档案规模，则依据适应度值大小对精英集进行修剪。在种群外设置一个精英集合用于保存种群进化每一步搜索到的非支配解。精英集合的使用将有效防止算法在搜索过程中由于随机因素而丢失最优解，并且能加快算法收敛速度。

3.3 多目标混合进化算法的步骤

（如图1）可描述为：

1）初始化算法的参数（包括种群规模POP、禁忌表及其长度、迭代次数等），随机产生初始群体POP0。

2）计算种群中每个个体的适应度值，并将适应度最高的个体存入精英集1中。

3）将精英集中的部分个体加入到种群中，进行选择操作得到种群POP1。

4）对POP1进行禁忌搜索同时进行交叉操作得到种群POP2，将POP2中适应度最高的个体存入精英集2中。

5）对POP2进行基于浓度的自适应变异操作得到种群POP3，将POP3中适应度最高的个体存入精英集3中。

6）更新精英集，如果个体数量超过档案规模，则对精英集进行修剪。

7）如果满足终止条件，执行步骤8，否则，转到步骤3。

8）输出最优解。

4 仿真实验

4.1 仿真测试

为了验证MHEA算法解决多目标优化问题的性能优劣，将该算法与目前解决多目标问题较好的NSGA-Ⅱ[10]算法进行比较分析。本文选取一组具有不同特征的benchmark问题ZDT1、ZDT3和ZDT6作为测试函数，其中ZDT1具有Pareto最优前沿，ZDT3具有非连续Pareto最优前沿，ZDT6具有非凸性且非均匀Pareto最优前沿。

测试过程中，MHEA算法和NSGA-Ⅱ算法均采用实数编码，浓度阈值γ=0.7，交叉概率pm=0.9，变异概率pc=1/n（n为变量个数），种群规模M=200，迭代次数gen=300。在同一台计算机上分别独立运行20次，从中选取最优结果进行比较，试验结果如图所示。

4.3 实验结果分析

由表1可知，所提算法MHEA在优化测试函数ZDT中的收敛性能、分布性能及多样性均优于算法NSGA-Ⅱ，说明算法引用禁忌搜索法及基于浓度的自适应变异算子是可行有效的，它能够提高收敛性，增加群体的多样性，但MHEA的平均运行时间却较长，这是它在提高算法搜索性能的同时所付出的代价。

5 结 论

本文有效的结合了遗传算法、禁忌搜索法和免疫算法的优点，提出了一种多目标混合进化算法，提高了收敛性，同时保证了多样性。通过仿真实验验证了算法的有效性。

参考文献

[1] 雷德明，严新平.多目标智能优化算法及其应用[M].北京：科学出版社，2009：31-33.

[2] 张勇德，黄莎白.多目标优化问题的蚁群算法研究[J].控制与决策，2005，20（2）：170-173.

[3] COELLO COELLO C A，PULIDO G T.Handing multiple objectives with particle swarm optimization[J].IEEE Transactions on Evolutionary Computation， 2004， 8（3）： 256-279.

[4] GOLDBERG D E.Genetic Algorithm in Search， Optimization and Machine Learning[J].NJ： Addtion Wesley，1989.

[5] 王娜，向凤红，毛剑琳.改进的自适应遗传算法求解0/1背包问题[J].计算机应用，2012，32（6）：1682-1684.

[6] 张文化，刘素华，侯惠芳.一种用于特征选择的禁忌搜索算法[J].计算机应用于软件，2010，27（5）：125-127.

[7] 崔逊学.基于免疫原理的多目标进化算法群体多样性研究[J].模式识别与人工智能，2001，14（3）：291-296.

[8] B T G TAN，S M LIM.Automated Parameter Optimization for Double Frequency Modulation Synthesis Using the Genetic Annealing Algorithm[J].J Audio Eng Soc.1996，44（1）.

[9] 王洁，高家全.一种新的的免疫遗传算法及应用[J].计算机应用与软件，2010，27（12）：89-91

[10]Deb K，Prata A，Agarwal S，Meyarivan T.A fast and elitist multiobjective geneticalgorithm： NSGAⅡ[C].IEEE Transactions on Evolutionary Computation， 2002， 6 （2）：182-197.

[11]郑金华.多目标进化算法及其应用[M].北京：科学出版社，2007.

[12]王璇.遗传算法的改进及其应用研究.[R].保定：华北电力大学，2012.