遗传算法与多Agent遗传算法操作与性能比较

摘要：该文主要介绍遗传算法及其改进的混合算法多Agent遗传算法在操作和性能上的差异，分析并证明了了遗传算法求解高维函数优化问题的局限性。通过实验证明了多Agent遗传算法的执行性能上较遗传算法具有很大的优越性，特别是在求解不高于400维的优化问题时。

关键词：遗传算法；多Agent遗传算法；高维函数优化

中图分类号：TP301文献标识码：A文章编号：1009-3044(2011)16-3893-03

遗传算法（Genetic algorithm，简称GA）是进化计算的一个主要分支，是二十世纪六十年代初由美国Michigan大学的J.H.Holland教授所提出的[1]。GA是一类随机搜索技术，它模拟由个体组成的群体的学习过程，其中的每个个体都代表了给定的搜索空间中的一个可能解。从最初的点（即可能解）出发，通过不断的迭代，逐步改进当前解，直至搜索到最优解或满意解为止。目前GA已经在人工智能、知识发现、模式识别、图象处理、决策分析、产品工艺设计、资源调度、股市分析等仍然不断增加的领域中发挥出了显著的作用。

多Agent遗传算法（Multi-Agent Genetic Algorithm，简称MAGA）是GA与多Agent技术相结合的一种混合算法，是由焦李成教授所提出的[2]。MAGA与GA的实现机制与操作流程有很大不同，主要体现在个体之间的交互、协作和自学习上。另外从算法执行性能上讲，MAGA作为一种改进的混合GA在收敛时间、优化结果上往往较传统GA有着很大的提升，特别是在处理超大规模、高维、复杂、动态优化问题时MAGA算法存在着明显的优势。

1 遗传算法

1.1 遗传算法的原理与实现机制

GA是二十世纪六十年代初，由美国Michigan大学的J. H. Holland教授借鉴达尔文的生物进化论和孟德尔的遗传定律的基本思想，并从中提取、简化与抽象而提出的第一个进化计算算法。其中，“遗传”与“算法”的结合充分体现了生物科学与计算机科学的相互渗透，相互融合[4]。它借鉴生物界的进化思想，通过计算机来模拟物种繁殖过程中父代遗传基因的重组与“优胜劣汰”的自然选择机制，以解决科学与工程中的复杂问题。

GA启迪于达尔文的“优胜劣汰”的自然选择机制和孟德尔的遗传学说。其算法实质上是一个不断循环迭代优化的过程，标准GA的主要执行步骤如图1所示，主要包括编码、群体初始化、确定适应度函数、选择、交叉、变异、评价和终止判定八步。

1.2 遗传算法的局限性

GA在解决优化问题过程中有如下不足之处：

1) GA在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优，故适应度函数的选取对于算法的速度和效果至关重要。

2) 对于任何一个具体的优化问题，选择、交叉和变异概率因子对于全局收敛的作用较大。若选择不当，很可能造成未成熟收敛或过收敛现象。

3) 对于高维函数，GA的收敛速度很慢，甚至不能收敛。

4) GA不能解决那些“大海捞针”的问题。

下面通过一组函数优化实验来测试GA的性能，优化函数为：

(1)

GA参数设置：群体规模设置为20，交叉率0.75，变异率0.1，由于128

算法执行中的选择采用赌轮选择法，交叉采用两点交叉法。最大迭代代数都为10000，迭代阈值为0.0001，分别取维数为2、4、6、8，即分别进行4组实验，每组实验执行20次，每次记录迭代至最优解时的代数，取20次执行的平均迭代次数、最小迭代次数以及最大迭代次数分别加以分析。

图2为实验运行迭代代数，在图中，当维数为2时，GA执行优化过程所用的平均迭代次数8.65，最小迭代次数为3，最大迭代次数为17；当维数为4时，平均迭代次数为78.6，最小迭代次数为7，最大迭代次数为167；维数为6时，平均迭代次数为1959.8，最小迭代次数为107，最大迭代次数为4966；维数为8时，在10000代以内大部分情况下都无法迭代至最优解，20次中只有三次在10000代以内迭代至最优解，其中最小的一次迭代次数为1899。

从图2可以看出，在维数大于等于8时，使用传统的GA来解决优化问题往往会变得比较困难。由于问题求解空间指数级的增长，造成了GA执行的迭代次数的急剧增加，而且很难收敛至最优解，优化过程中经常会停留在某个接近最优解的位置上，而无法向更优目标进行搜索。

2 多Agent遗传算法

从Agent的角度出发，把GA中的个体作为一个具有局部感知、竞争协作和自学习能力的Agent，通过Agent与环境以及Agent间的相互作用达到全局优化的目的，这就是MAGA的思想[2]。MAGA的实现机制与GA有很大不同，主要体现在个体之间的交互、协作和自学习上。一些学者已经通过实验证明了MAGA有很快的收敛速度，能够很好的应用于解决高维函数优化问题。

MAGA把每个个体都视为一个Agent，所有的Agent均生活在Agent网格环境中，这是MAGA与GA的不同点之一。两者相同的是MAGA中的Agent与GA中的个体都是解空间中的一个可行解。MAGA中的遗传算子主要包括：邻域竞争算子、邻域正交交叉算子、变异算子和自学习算子四个算子。其中邻域竞争算子实现了各Agent之间的竞争操作；邻域正交交叉算子实现了各Agent之间的协作行为；变异算子和自学习算子实现了Agent利用自身知识的行为。MAGA的实现流程如图3所示。

3 遗传算法与多Agent遗传算法操作对比

MAGA与GA在操作上的不同之处如表1所示。

4 遗传算法与多Agent遗传算法性能对比

以函数优化为例，对MAGA与GA的性能做出比较。

(2)

(3)

分别取n=20。

MAGA参数设置：Agent网格大小或种群规模Lsize=5，邻域竞争算子占据策略P0=0.2，邻域正交交叉算子执行概率Pc=0.1，变异算子执行概率Pm=0.1，自学习中的群体规模sLsize=3，自学习中的搜索半径sR=0.2，自学习中的变异率sPm=0.05，自学习迭代代数sGen=10。

GA参数设置：群体规模设置为25，交叉概率0.75，变异概率0.1，式2取个体每维长度为8，式3取个体每维长度为10。

设置阈值为0.0001；设置迭代最大代数为3000。对两种算法执行10次的结果进行对比显示如图4和5所示。

由图4与4可以看出，在20维函数优化时，MAGA无论从优化结果还是稳定性方面都远远胜于GA。GA在求解函数优化时随着维数的增加，其收敛速度会变得很慢，即便是增加迭代次数，GA也难以收敛至最优解。而MAGA在每次执行过程中都能够很快速的向最优值靠近。

下面对MAGA的性能做出分析：

对于式2，将维数分别设置为20、100、200、400和1000，分别采用MAGA进行优化，记录每次迭代次数，并计算20次平均优化迭代次数，每维的平均迭代优化次数比较结果如图6所示。

通过图6可以看出，MAGA在解决400维以下的函数优化问题时，其收敛速度都比较快。因此，我们在解决400维以下问题时使用MAGA是可行且有效的。

5 总结

该文主要介绍了GA及MAGA的算法执行流程和两者操作上不同之处，并通过一组实验结果分析证明了GA解决高维优化问题时的局限性。另外通过两个20维测试函数来对MAGA与GA的性能进行分析，通过对比实验结果分析可知MAGA由于引入了竞争、自学习等操作，其在解决函数优化问题，特别是解决高维函数优化问题时，无论从收敛速度上还是收敛精度上都远远超过传统的GA，因此MAGA具有比GA更好的性能。但是实验结果仍展示出在函数维数大于400后，MAGA算法的性能也会迅速下降，故由此可知，在求解不高于400维的函数优化问题，采用MAGA算法是可行并有效的。

参考文献：

[1] 夏定纯, 徐涛. 计算智能[M]. 北京：科学出版社, 2008.

[2] 焦李成, 刘静, 钟伟才. 协同进化计算与多智能体系统[M]. 北京: 科学出版社, 2006.

[3] Deb K, Beyer H G. Self-adaptive genetiv algorithms with simulated binary crossover. Evolutionary Computation. 2001,9(2):137-221.

[4] 樊重俊, 王浣尘. 遗传算法的改进与应用[J]. 上海交通大学学报, 1998(12).

[5] Holland d, H, Adaptation in Natural and Artificial Systems[M]. University of Michigan Press, Ann Arbor MI, 1975.

[6] 王小平, 曹立明. 遗传算法理论应用与软件实现[M]. 西安:西安交通大学出版社, 2002.

[7] Baowen Xu, Yu Guan, Zhenqiang Chen, et al. Parallel Genetic Algorithms with Schema Migration, 26th Annual International Computer Software and Applications Conference August 26-29, 2002.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文