基于IPSO算法的多Agent聯(lián)盟形成研究

摘? 要：考慮單個(gè)Agent資源有限，多個(gè)Agent時(shí)常需形成聯(lián)盟來(lái)完成任務(wù)或提高聯(lián)盟整體能力，如何形成一組針對(duì)某個(gè)任務(wù)的最佳聯(lián)盟是MAS中一個(gè)緊迫而又關(guān)鍵性的問(wèn)題。基于此，文中提出一種改進(jìn)的IPSO算法來(lái)解決該問(wèn)題，同時(shí)為克服粒子過(guò)早收斂和局部?jī)?yōu)化，在改進(jìn)的慣性權(quán)重上引入一種柯西變異的擾動(dòng)算子，最后與PSO算法及ACO算法做對(duì)比，結(jié)果表明該IPSO算法的全局搜索能力較強(qiáng)，成功避免了粒子過(guò)早收斂，資源浪費(fèi)等問(wèn)題。

關(guān)鍵詞：多Agent聯(lián)盟;PSO算法;ACO算法;IPSO算法

中圖分類號(hào)：TP18? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2019）09-0005-03

0? 引? 言

Agents聯(lián)盟形成是分布式人工智能中一種重要的協(xié)作方法。一個(gè)聯(lián)盟可以定義為一組Agents為完成一個(gè)共同任務(wù)或達(dá)到一個(gè)共同目標(biāo)而進(jìn)行的合作，Agent加入一個(gè)聯(lián)盟可加強(qiáng)聯(lián)盟完成任務(wù)的能力和最大化個(gè)人收益，甚至在有些情況下，聯(lián)盟形成是完成任務(wù)唯一或最有效的方法[1-3]。目前，在MAS中，聯(lián)盟形成的基本理論是N人合作對(duì)策理論，主要考慮如何在聯(lián)盟內(nèi)Agent間劃分聯(lián)盟的額外效用，使Agent在決策時(shí)愿意形成全局最優(yōu)聯(lián)盟。

3.3? 粒子適應(yīng)值的計(jì)算

如果該粒子當(dāng)前適應(yīng)值等于個(gè)體歷史最優(yōu)值或粒子當(dāng)前適應(yīng)值等于全局粒子最優(yōu)值，則隨機(jī)選擇粒子位置;如果該粒子當(dāng)前適應(yīng)值優(yōu)于個(gè)體歷史最優(yōu)值或粒子當(dāng)前適應(yīng)值優(yōu)于全局粒子最優(yōu)，則將歷史最優(yōu)值或全局最優(yōu)值替換當(dāng)前粒子的位置。

3.4? 算法步驟

Step1 初始化種群，設(shè)粒子數(shù)為n、學(xué)習(xí)因子c1，c2及慣性權(quán)重ω初始值、最大迭代次數(shù)的值，并隨機(jī)產(chǎn)生n個(gè)初始位置及初始速度;

Step2 根據(jù)適應(yīng)度函數(shù)對(duì)每個(gè)粒子位置進(jìn)行更新;

Step3 根據(jù)式（6）對(duì)ω的值進(jìn)行更新，同時(shí)由式（3）和式（4）計(jì)算下一刻粒子位置和速度，并運(yùn)用式（8）和式（9）對(duì)粒子位置進(jìn)行擾動(dòng)，同時(shí)記下每個(gè)粒子的當(dāng)前值;

Step4 若粒子當(dāng)前值優(yōu)于個(gè)體歷史最優(yōu)值，則將當(dāng)前個(gè)體最優(yōu)值替換個(gè)體歷史最優(yōu)值，否則不替換;

Step5 粒子當(dāng)前值優(yōu)于群體歷史最優(yōu)值，則將當(dāng)前個(gè)體最優(yōu)值替換群體歷史最優(yōu)值，否則不替換;

Step6 若達(dá)到最高迭代次數(shù)或找到最優(yōu)解，則輸出搜索結(jié)果，否則轉(zhuǎn)入Step2。

4? 實(shí)驗(yàn)環(huán)境設(shè)置及結(jié)果分析

為驗(yàn)證算法性能，文中以ACO[3]、PSO[4]及本文的IPSO三種算法進(jìn)行實(shí)驗(yàn)設(shè)計(jì)。隨機(jī)選取任務(wù)量分別為4、12和30，具體算法參數(shù)假設(shè)如下：粒子數(shù)n=30，c1=c2=2，ω初始值為0.9。每個(gè)Agent能力向量為，Ai完成任務(wù)需要的聯(lián)盟代價(jià)值為 ;任務(wù)需求能力向量為，完成任務(wù)需要的聯(lián)盟值為。

4.1? 實(shí)驗(yàn)環(huán)境設(shè)置

（1）當(dāng)時(shí)，因Agent能力不足，聯(lián)盟失敗，故任務(wù)均不能被完成;

（2）當(dāng)時(shí)，符合聯(lián)盟生成條件，圖1、圖2、圖3給出了在Agents數(shù)量不斷增加的情況下，前500次迭代在1000次實(shí)驗(yàn)中聯(lián)盟值的變化情況。

4.2? 實(shí)驗(yàn)分析

從圖1、圖2、圖3可看出，不同算法下，在隨機(jī)選取的三種任務(wù)下IPS0算法比PSO算法曲線坡度更陡且位于PSO算法及ACO算法曲線的上方，這意味著IPSO算法在解決Agents聯(lián)盟生成問(wèn)題時(shí)，最終收斂的聯(lián)盟值更有效，從坡度上可看出收斂速度也更快。

同時(shí)表1也給出了當(dāng)?shù)螖?shù)為500時(shí)三種算法在完成不同任務(wù)時(shí)找到最優(yōu)聯(lián)盟值時(shí)程序運(yùn)行時(shí)間之比，具體如表1所示，從表中可得出IPSO算法運(yùn)行時(shí)間相比于其它兩種算法時(shí)間都是最少的。

綜上可知，本文提出的IPSO算法無(wú)論在聯(lián)盟值大小、收斂性還是運(yùn)行時(shí)間上均優(yōu)于PSO算法和ACO算法。

5? 結(jié)? 論

多Agent聯(lián)盟是MAS中的一個(gè)緊迫性問(wèn)題，基于此，文中提出一種改進(jìn)的IPSO算法來(lái)解決該問(wèn)題，同時(shí)為克服粒子過(guò)早收斂和局部?jī)?yōu)化，在改進(jìn)的慣性權(quán)重基礎(chǔ)上引入一種柯西變異的擾動(dòng)算子，經(jīng)驗(yàn)證該IPSO算法的全局搜索能力較高，有效地避免了粒子過(guò)早收斂，資源浪費(fèi)等問(wèn)題。

參考文獻(xiàn)：

[1] 黃麗麗.基于多Agent的智能生存空間異構(gòu)協(xié)作研究 [D].北京：北京交通大學(xué)，2014.

[2] 李天文.面向多Agent系統(tǒng)的博弈聯(lián)盟形成與分配問(wèn)題研究 [D].昆明：云南大學(xué)，2013.

[3] 吳慶洪，張穎，馬宗民.蟻群算法綜述 [J].微計(jì)算機(jī)信息，2011，27（3）：1-2+5.

[4] 蔣建國(guó)，夏娜，齊美彬，等.一種基于蟻群算法的多任務(wù)聯(lián)盟串行生成算法 [J].電子學(xué)報(bào)，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] 傅小利，顧紅兵，陳國(guó)呈，等.基于柯西變異粒子群算法的永磁同步電機(jī)參數(shù)辨識(shí) [J].電工技術(shù)學(xué)報(bào)，2014，29（5）：127-131.

作者簡(jiǎn)介：陳寧霞（1986-），女，漢族，河南周口人，專任教師，助教，Web前端在線課程開(kāi)發(fā)者之一，碩士，研究方向：分布式人工智能、軟件開(kāi)發(fā)等。