摘要：將量子進化算法與蟻群算法思想相融合，提出一種求解機器人聯(lián)盟問題的量子蟻群算法。為了避免搜索陷入局部最優(yōu)，采用多種群并行搜索及量子交叉策略，以改善種群信息結(jié)構(gòu)；算法中還設(shè)計了一種新的信息素表示方式。仿真實驗結(jié)果表明，該算法具有較快的收斂速度和全局尋優(yōu)能力。

關(guān)鍵詞：機器人；聯(lián)盟；蟻群算法；量子蟻群算法

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2013）15-3596-03

在多機器人系統(tǒng)中，單個機器人個體的資源、能力與智能都是有限的，往往不能獨自完成特定的任務(wù)。為了完成任務(wù)，機器人之間就必須相互協(xié)作，通過結(jié)成聯(lián)盟來提高求解問題的能力[1]。因此聯(lián)盟是多機器人系統(tǒng)的重要合作方式，而機器人聯(lián)盟生成問題（Multi-Robot Coalition Formation）則成為多機器人系統(tǒng)研究中一個關(guān)鍵的基礎(chǔ)性問題，主要研究如何在多機器人系統(tǒng)中動態(tài)生成面向任務(wù)的最優(yōu)機器人聯(lián)盟。從1993年提出聯(lián)盟方法以來，國內(nèi)外學者對面向任務(wù)的聯(lián)盟生成進行了大量的研究工作，其中智能進化算法由于具有全局尋優(yōu)能力強、收斂速度快等優(yōu)點，在近年來更是被廣泛地應(yīng)用到機器人聯(lián)盟問題的求解中，如蔣建國、夏娜、李杰等[2-4]基于粒子群和蟻群算法、許波等人[5-6]基于量子粒子群算法，這些方法在可接受時間內(nèi)獲得的解的質(zhì)量有所提高，仿真實驗也驗證了智能算法的高效性。

1 機器人聯(lián)盟問題描述

機器人聯(lián)盟C是一組相互合作、能共同完成某一任務(wù)的一個或多個機器人集合。若系統(tǒng)中有n個機器人集合[R={R1，R2，…，Rn}]，則一個聯(lián)盟C就是R的一個非空子集。在多機器人系統(tǒng)中，每個機器人[Ri]都具有一個能力向量[Bi=b1i，b2i，…，bri]， [bji≥0，（1≤i≤n，1≤j≤n）]，用于定量描述24Qb6So0x7YgIViSLCsb+X/6gv3zse8yw/VlUBikWi0=[Ri]執(zhí)行某種特定動作的能力大小，若[bji]=0，則表示[Ri]不具備能力[bji]。任務(wù)t具有一定的能力需求[Bt=b1t，b2t，…，brt]。聯(lián)盟C具有一個能力向量[BC=b1C，b2C，…，brC]，BC是聯(lián)盟中所有機器人能力向量的總和，即[BC=Ri∈CBi]，聯(lián)盟C能完成任務(wù)t的必要條件是：[BC≥Bt]。

任何一個聯(lián)盟C都有聯(lián)盟代價CostC、聯(lián)盟收益ProfitC和聯(lián)盟值ValueC，若聯(lián)盟C不能完成任務(wù)，則聯(lián)盟值ValueC為0，否則，ValueC為一正數(shù)，并且隨著ProfitC值的遞增而遞增，隨著CostC的遞增而遞減。因此在本文中我們將聯(lián)盟值定義為：ValueC=ProfitC /CostC（當聯(lián)盟C不能完成任務(wù)時，ProfitC=0）。機器人聯(lián)盟問題就是要求出能完成任務(wù)的并擁有最大ValueC值的最優(yōu)聯(lián)盟。

2 量子蟻群算法（QACA）

2.1編碼方式

2.2 量子信息素

量子螞蟻[QAtk]的量子信息素值[Qτtk]的具體表示如下：

[Qτtk=βt112βt122…βt1n2βt212βt222…βt212??βtij2?βtn12βtn12…βtnn2] （2）

通過上面公式可以發(fā)現(xiàn)，量子信息素量直接通過相應(yīng)的量子螞蟻就可獲得，采用這種量子信息素表示方式使得信息素的更新操作變得非常簡單，不需要任何參數(shù)，對于各路徑上信息素的揮發(fā)和增強完全可以通過對量子螞蟻的更新來完成，例如：若螞蟻在機器人 i 上選擇了機器人 j 作為盟友，并成為較優(yōu)的聯(lián)盟組合，則機器人 i 到機器人 j 就是用來更新量子螞蟻的較優(yōu)路徑中的一條邊，通過更新量子螞蟻，會使得其概率幅[βtij]的值增加，從而[βtij2]也增加，即使得機器人 i 到 機器人 j 路徑上的信息素得以增強；反之，該路徑上的信息素會有所揮發(fā)。

2.3 多種群并行搜索及量子交叉

為了避免算法陷入局部最優(yōu)，我們采用多種群并行搜索策略，得到解空間中不同區(qū)域的最優(yōu)值。在進化初期，以各種群最優(yōu)值為進化目標引導搜索方向。每進化一定代數(shù)后，比較各種群的最優(yōu)值，保留全局最優(yōu)個體，并以該最優(yōu)個體取代各種群中最差個體。若某種群連續(xù)若干代仍沒有找到更優(yōu)個體時，則利用量子信息的糾纏和干涉特性執(zhí)行一種量子交叉策略，以促進種群內(nèi)部的信息交流，增強種群多樣性。量子交叉的具體做法如下：

2.4 算法流程

求解機器人聯(lián)盟問題的量子蟻群算法（QACA）具體操作步驟如下：

1） 初始化N組量子蟻群；

2） 分別計算各組種群的量子信息素[Qτ（t）=Qτtk，k=1，2，…m]；

3） 構(gòu)建路徑，計算適應(yīng)度；

4） 判斷是否滿足終止條件，若滿足，則算法終止，否則執(zhí)行下一步；

5） 采用量子旋轉(zhuǎn)門[7]更新量子蟻群[QA（t）]；

6） 進化每間隔D代，記錄所有種群中全局最優(yōu)個體，并以全局最優(yōu)個體取代各種群中最差個體。若某種群連續(xù)D代沒有找到更優(yōu)個體，則執(zhí)行量子交叉操作；

7） t=t+1，算法轉(zhuǎn)到（2）繼續(xù)執(zhí)行，直到算法結(jié)束。

3 仿真實驗

為了驗證算法的有效性，將QACA與文獻[3]中基本蟻群算法（BACA）和文獻[8]中的量子遺傳算法（QGA）進行比較。實驗中機器人個數(shù)、能力向量及任務(wù)等相關(guān)參數(shù)選用文獻[5]中給定的實驗數(shù)據(jù)，其它參數(shù)設(shè)定為：種群規(guī)模100，進化代數(shù)1000，[α]=1，[β]=2，D=10。針對給定的聯(lián)盟問題，分別采用QGA、BACA和QACA三種算法進行50次獨立實驗，并記錄下50次實驗中各算法找到的最優(yōu)聯(lián)盟值、最差聯(lián)盟值、平均聯(lián)盟值，及最快搜索到最優(yōu)解的迭代次數(shù)和50次實驗平均搜索到最優(yōu)解的迭代次數(shù)。通過考察這幾個參數(shù)指標，可以實現(xiàn)對算法全局尋優(yōu)性能及收斂性能的比較，其對比實驗結(jié)果見表1。

從表1的統(tǒng)計結(jié)果可以看出， QACA算法無論在最好情況、最差情況還是平均情況下都要明顯優(yōu)于QGA和BACA算法。這表明在相同的迭代條件下QACA算法能夠搜索到較高質(zhì)量的解，具有較好的全局尋優(yōu)能力。而通過搜索到最優(yōu)解的迭代次數(shù)，可以表明QACA算法的收斂速度較快，且收斂穩(wěn)定性較高。

4 結(jié)束語

將蟻群算法與量子進化算法思想相結(jié)合，提出了一種求解機器人聯(lián)盟問題的量子蟻群算法（QACA）。算法中根據(jù)量子編碼的多樣性特性，設(shè)計了一種新的信息素表示及更新方式；為了避免搜索陷入局部最優(yōu)，設(shè)計了一種多種群并行搜索和量子交叉策略。最后將QACA與BACA和QGA進行仿真實驗比較，測試結(jié)果也表明了算法具有一定的優(yōu)勢。在QACA基礎(chǔ)上的多任務(wù)聯(lián)盟問題求解將是我們下一步研究工作的重點。

參考文獻：

[1] Lovekech V， Julie A. Multi-robot coalition formation[J]. IEEE Transactions on Robotics， 2006， 22（4）： 637–649.

[2] 蔣建國，張國富，齊美彬，等.基于離散粒子群求解復雜聯(lián)盟的并行生成[J].電子與信息學報， 2009， 31（30）： 519-522.

[3] 夏娜，蔣建國，魏星，等.改進型蟻群算法求解單任務(wù)agent聯(lián)盟[J].計算機研究與發(fā)展，2005，42（5） ：734-739.

[4] 李杰，王愛民，于金剛，等.一種非線性動態(tài)自適應(yīng)的Agent聯(lián)盟生產(chǎn)算法[J].小型微型計算機系統(tǒng)， 2012， 33（8）： 1792-1794.

[5] 許波，余建平.基于QPSO 的單任務(wù)Agent 聯(lián)盟形成[J].計算機工程， 2010， 36（19）： 168-170.

[6] 許波，彭志平，余建平，等. 基于量子多目標進化算法的多任務(wù)Agent 聯(lián)盟生成[J] .系統(tǒng)工程理論與實踐， 2012， 32（10）： 2254-2261.

[7] 李絮，劉爭艷，譚拂曉.求解TSP的新量子蟻群算法[J].計算機工程與應(yīng)用，2011， 47（32）： 42-44.

[8] 張葛祥，金煒東.量子遺傳算法改進及其應(yīng)用研究[J].西南交通大學學報，2003，38（6）：718-722.