解排列优化的整数编码多智能体进化算法

摘要：为解排列优化问题，在多智能体进化算法的基础上，提出一种整数编码的多智能体进化算法。重新定义了竞争算子和自学习算子。在网格内，智能体与周围的8个智能体构成竞争域，优胜智能体将编码段植入失败智能体，只有优胜者能获得自学习机会，自学习算子中智能体通过两种编码段换位方式来提升能量。使用本算法在旅行商问题典型数据上进行测试，与现有文献比较，表明该算法具有更好的全局寻优能力而且收敛稳定性更好。

关键词：排列优化；多智能体进化算法；旅行商问题；进化算法；整数规划

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

Number Coding Multi-Agent Evolutionary Algorithm for Deployment Optimization

YUAN Zhi

(South-China Institute of Software Engineering, Guangzhou University, Guangzhou 510990, China)

Abstract: For deployment optimization, Number Coding MAEA named as NC-MAEA is proposed based on Multi-agent Evolutionary Algorithm, the competition operator and learning operator are redefined. In grids, a agent and 8 agents around constitute a competing area, the winner plants it’s codes fragment into failure’s codes series, only winner obtains learning chance, in learning process it swap code fragments in two ways to improve energy. Simulated with the typical test data of in traveling salesman problems, compared with other related literatures, it has been proved that NC-MAEA has better global optimization ability and convergence stability.

Key Words: deployment optimization; Multi-Agent Evolutionary Algorithm; traveling salesman problem; Evolution Algorithm; integer programming

1.引言

排列优化问题广泛应用在生产调度、工程规划等方面。不失一般性，排列优化问题可以转换为一个整数规划下的函数极值问题,描述为：

minZ =F(x1, x2, …, xn) (xi∈N；1≤xi≤n；若i≠j,xi≠xj)minZ =F(x1, x2, …, xn)

旅行商问题是排列优化问题的典型代表。旅行商问题是个NP完全问题，传统算法中用分支定界法来求解，但当数据规模过大时，会出现“组合爆炸”问题，目前多用智能算法求解[1]。文献[2][3][4]使用0-1编码，通过遗传算法和二进制粒子群算法求解旅行商问题，文献[5]使用整数编码，通过模拟退火粒子群算法来求解旅行商问题，文献[6]使用混合蚂蚁算法来求解旅行商问题。通过分析以上文献的计算结果，发现它们的全局寻优能力和收敛稳定性都有待提高。

多智能体进化算法(Multi-Agent Evolutionary Algorithm，MAEA)用智能体网格构造进化环境，每个智能体依据目标自我学习以提升能量，并在邻域中参与竞争，竞争失败便被邻域中能量最大的智能体淘汰，不需要全局消息，更接近于自然界进化模式[7]。文献[8]提出了组合优化多智能体进化算法，证明了算法的全局收敛性。但以该算法求解排列优化问题时存在明显不足：采用0-1编码产生大量重复编码段属于非法解，导致大量无效计算；0-1编码使解空间编码规模庞大，迭代运算时间长；以逻辑运算为基础的淘汰算子和学习算子在排列优化问题中难以赋予清晰的自然语义。

本文提出整数编码的多智能体进化算法(NC-MAEA)，在原算法的基础上重新设计竞争算子和自学习算子。在旅行商问题的典型测试数据上进行仿真，实验表明，它的全局寻优能力和收敛稳定性更好。

2．整数编码的多智能体进化算法

2.1 智能体网格初始化

设排列的规模为n,构造一个规模为m×m的智能体网格,每个网格中放置一个的智能体，智能体包含一个学习状态LearnMethod和[1~n]的全排列。LearnMethod有两种取值，初始状态下为1。

2.2竞争算子

网格中的每个智能体与其邻域中的智能体竞争。将网格看作一个球面，智能体的竞争域是所有与它距离不超过1的8个智能体。从竞争域中寻找能量最大的智能体Amax,如果Energy(Amax)>Energy(Aij)，则执行淘汰算子，用Amax去感染Aij。方法如下：

从Amax的随机位置取一段随机长度的编码D,插入到Aij的相应位置。删除Aij中与D相同的编码，然后重新排序,保持插入段的位置不变，并将当前智能体的学习状态赋值为1.例如：智能体A1(6 5 |3 2 1| 4 )淘汰A2(2 1 5 6 4 3), |表示随机产生的分割位置，首先将A1中的|3 2 1|放入A2的相应位置，得到（2 1 |3 2 1| 5 6 4 3），删除重复的3,2,1，重新整理编码位置(5 6 3 2 1 4 )。

2.3自学习算子

一个竞争域中，只有能量最大的智能体获得学习机会。学习行为通过编码段的移位来试图提升能量。智能体有两种学习方法，当LearnMothod为1时，采用第一种学习方法，当LearnMethod为2时，采用第二种学习方法。只有当第一种学习无法获得更高的能量时，才会转入第二种学习方法。

第一种学习方法使用遍历的方法来交换两位编码，一旦发现交换后能量得到提高，即终止学习。如果遍历之后仍然无法提升量，则将LearnMethod置为2。

第二种学习方法的过程：（1）产生一个随机的[1到n]排列P，k置为1；（2）从智能体的P(k)位置开始，选择一段随机长度的编码，将其移动到随机的位置，得到一个新的智能体newAw；（3）如果Energy(newA)>Energy(Aij),则Aij替换为newAw,转步骤4；否则k加1,转到步骤2；（4）LearnMothod置为1，学习结束。

2.4算法流程

（1）设定进化代数和网格规模，构造智能体网格；（2）一次群体进化，智能体竞争，如果竞争失败则被优胜智能体感染，优胜的智能体执行学习算子；（3）达到优化目标或进化代数，则输出最优解，结束。

NC-MAEA算法的基本框架与MAEA相同，可基于文献[7]、[8]，证明其时间复杂度为O(na),全局收敛的概率为1。

3.仿真实验

在2G主频2G内存的微机上，用MATLAB7.1编程，使用NC-MAEA算法进行仿真。

3.1 在实数排序问题上的实验

为了验证算法的收敛性稳定性，用整数排序来实验。对100个随机整数降序排列，易知优化目标为：minF=∑(k*ak)。为了让算法在找到完全降序排列的时候停止，引入函数G=∑ek（当ak

100个整数有100！个排列组合，如果用遍历的方法逐个比较F值，其计算量将大于10100，采用NC-MAEA算法，用40*40的网格规模，取200组不同的随即数据，实验结果全部在180秒之内得到G=0，即得到最优解。

3.2 在旅行商典型数据机上的实验

在Burma14上，用5×5的智能体网格，运算30次，运算结果与文献[3]的比较如表1。

4.总结

整数编码的多智能体进化算法继承了多智能体进化算法的全局寻优能力，针对排列优化问题进行专门设计，大幅提高了运算速度。它的执行参数简单，只需要设定智能体网格的规模和进化代数，因此方便应用。在旅行商问题上仿真，表明其全局寻优能力和收敛稳定性比现有启发算法有明显提升。

参考文献：

[1]贵超,黎明,韦雪洁.旅行商问题的几种求解方法[J].计算机仿真,2006,23(8):153-157.

[2]胡玉兰.基于遗传算法的旅行商问题的仿真实现[J].控制工程,2002,9(6):79-81.

[3]刘勤明,吕文元.旅行商问题的改进粒子群算法[J].计算机应用,2007,27(12):185-187.

[4]刘松兵,李智勇,王永,等．一种新的计划粒子群算法及其在TSP中的应用[J]．计算机工程与应用，2008，44(28):62-64.

[5]曹平,陈盼,刘世华.改进的粒子群算法在旅行商问题中的应用[J].计算机工程,2008,34(6):217-331.

[6]陈星宇,肖伟,全惠云,等.应用LK算法求解旅行商问题的混合蚂蚁算法[J].计算机工程,2008,(4):228-

230.

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

[8]钟伟才,刘静,刘芳焦.组合优化多智能体进化算法[J].计算机学报,2004,27（10）:1341-1353.

作者简介：袁志（1971- ），男，汉族，湖北黄冈，硕士，高级工程师，主要研究方向为网络与信息系统。