基于IPSO算法的多Agent联盟形成研究

摘  要：考虑单个Agent资源有限，多个Agent时常需形成联盟来完成任务或提高联盟整体能力，如何形成一组针对某个任务的最佳联盟是MAS中一个紧迫而又关键性的问题。基于此，文中提出一种改进的IPSO算法来解决该问题，同时为克服粒子过早收敛和局部优化，在改进的惯性权重上引入一种柯西变异的扰动算子，最后与PSO算法及ACO算法做对比，结果表明该IPSO算法的全局搜索能力较强，成功避免了粒子过早收敛，资源浪费等问题。

关键词：多Agent联盟;PSO算法;ACO算法;IPSO算法

中图分类号：TP18       文献标识码：A 文章编号：2096-4706（2019）09-0005-03

0  引  言

Agents联盟形成是分布式人工智能中一种重要的协作方法。一个联盟可以定义为一组Agents为完成一个共同任务或达到一个共同目标而进行的合作，Agent加入一个联盟可加强联盟完成任务的能力和最大化个人收益，甚至在有些情况下，联盟形成是完成任务唯一或最有效的方法[1-3]。目前，在MAS中，联盟形成的基本理论是N人合作对策理论，主要考虑如何在联盟内Agent间划分联盟的额外效用，使Agent在决策时愿意形成全局最优联盟。

3.3  粒子适应值的计算

如果该粒子当前适应值等于个体历史最优值或粒子当前适应值等于全局粒子最优值，则随机选择粒子位置;如果该粒子当前适应值优于个体历史最优值或粒子当前适应值优于全局粒子最优，则将历史最优值或全局最优值替换当前粒子的位置。

3.4  算法步骤

Step1 初始化种群，设粒子数为n、学习因子c1，c2及惯性权重ω初始值、最大迭代次数的值，并随机产生n个初始位置及初始速度;

Step2 根据适应度函数对每个粒子位置进行更新;

Step3 根据式（6）对ω的值进行更新，同时由式（3）和式（4）计算下一刻粒子位置和速度，并运用式（8）和式（9）对粒子位置进行扰动，同时记下每个粒子的当前值;

Step4 若粒子当前值优于个体历史最优值，则将当前个体最优值替换个体历史最优值，否则不替换;

Step5 粒子当前值优于群体历史最优值，则将当前个体最优值替换群体历史最优值，否则不替换;

Step6 若达到最高迭代次数或找到最优解，则输出搜索结果，否则转入Step2。

4  实验环境设置及结果分析

为验证算法性能，文中以ACO[3]、PSO[4]及本文的IPSO三种算法进行实验设计。随机选取任务量分别为4、12和30，具体算法参数假设如下：粒子数n=30，c1=c2=2，ω初始值为0.9。每个Agent能力向量为，Ai完成任务需要的联盟代价值为 ;任务需求能力向量为，完成任务需要的联盟值为。

4.1  实验环境设置

（1）当时，因Agent能力不足，联盟失败，故任务均不能被完成;

（2）当时，符合联盟生成条件，图1、图2、图3给出了在Agents数量不断增加的情况下，前500次迭代在1000次实验中联盟值的变化情况。

4.2  实验分析

从图1、图2、图3可看出，不同算法下，在随机选取的三种任务下IPS0算法比PSO算法曲线坡度更陡且位于PSO算法及ACO算法曲线的上方，这意味着IPSO算法在解决Agents联盟生成问题时，最终收敛的联盟值更有效，从坡度上可看出收敛速度也更快。

同时表1也给出了当迭代次数为500时三种算法在完成不同任务时找到最优联盟值时程序运行时间之比，具体如表1所示，从表中可得出IPSO算法运行时间相比于其它两种算法时间都是最少的。

综上可知，本文提出的IPSO算法无论在联盟值大小、收敛性还是运行时间上均优于PSO算法和ACO算法。

5  结  论

多Agent联盟是MAS中的一个紧迫性问题，基于此，文中提出一种改进的IPSO算法来解决该问题，同时为克服粒子过早收敛和局部优化，在改进的惯性权重基础上引入一种柯西变异的扰动算子，经验证该IPSO算法的全局搜索能力较高，有效地避免了粒子过早收敛，资源浪费等问题。

参考文献：

[1] 黄丽丽.基于多Agent的智能生存空间异构协作研究 [D].北京：北京交通大学，2014.

[2] 李天文.面向多Agent系统的博弈联盟形成与分配问题研究 [D].昆明：云南大学，2013.

[3] 吴庆洪，张颖，马宗民.蚁群算法综述 [J].微计算机信息，2011，27（3）：1-2+5.

[4] 蒋建国，夏娜，齐美彬，等.一种基于蚁群算法的多任务联盟串行生成算法 [J].电子学报，2005（12）：2178-2182.

[5] Kennedy J ，Eberhart R C . A discrete binary version of the particle swarm algorithm [C]// 1997 IEEE International Conference on Systems，Man，and Cybernetics. Computational Cybernetics and Simulation. IEEE，1997.

[6] 傅小利，顧红兵，陈国呈，等.基于柯西变异粒子群算法的永磁同步电机参数辨识 [J].电工技术学报，2014，29（5）：127-131.

作者简介：陈宁霞（1986-），女，汉族，河南周口人，专任教师，助教，Web前端在线课程开发者之一，硕士，研究方向：分布式人工智能、软件开发等。