基于量子遺傳算法的多任務聯盟并行生成算法

摘 要:提出一種基于量子遺傳算法的多任務聯盟并行生成算法，運用量子編碼映射的方式將任務分配與資源組合合并為一個過程，使多任務聯盟問題的復雜性得到降低。實驗表明，該算法在面向多任務的領域中可以快速、有效地并行形成多個任務求解聯盟;與遺傳算法和蟻群算法的對比實驗表明，該算法是正確、有效、可行的，在運行時間和解的性能上都優于前兩種算法。

關鍵詞:多任務聯盟; 量子遺傳算法; 多agent系統; agent聯盟; 組合優化

中圖分類號:TP393;TP301.6文獻標志碼:A

文章編號:1001-3695(2010)06-2100-03

doi:10.3969/j.issn.1001-3695.2010.06.030

Multi-task coalition parallel generation algorithm based on quantum genetic algorithm

XU Bo1， YU Jian-ping2

(1.Dept. of Computer Science Technology， Maoming College， Maoming Guangdong 525000， China; 2.College of Mathematics Computer Science， Hunan Normal University， Changsha 410081， China)

Abstract:This paper presented multi-task coalition parallel generation algorithm based on quantum genetic algorithm， using the quantum encoding map， combined the mix of resources and distribution of tasks into one process， reduced the complexity of the multi-task coalition problem. Experiments show that the algorithm-oriented areas of multi-tasking can be quickly and effectively to solve multiple tasks in parallel to form coalitions. Ant colony algorithm and genetic algorithm and comparison of experiments show that the algorithm is correct， effective and feasible and in the run-time performance of reconciliation are better than the first two algorithms.

Key words:multi-task coalition; quantum genetic algorithm; multi-agent system; agent coalition; combinatorial optimization

Agent間通過組成聯盟可以提高求解問題的能力，因此agent聯盟問題引起了研究人員廣泛的關注。自1993年提出聯盟方法以來，聯盟生成已成為多agent系統研究的一個重要方面并取得了一定的進展。傳統的方法是利用n人合作對策論，但是計算復雜度過高;Shehory等人[1]通過限制聯盟規模使算法在多項式時間內收斂，但減少了系統的收益;徐晉暉等人[2]提出基于任務等價的聯盟演化機制，但匹配要求很嚴格。

智能算法近年來被廣泛地應用于聯盟生成問題，如鄭金華等人[3]基于遺傳算法、蔣建國等人[4]基于粒子群算法、夏娜等人[5]基于改進蟻群算法、許波等人[6，7]基于改進量子遺傳算法等方法，這些方法在可接受時間內解的質量有所提高，但都是針對單任務單聯盟的生成問題。在現實世界中，系統在某一時刻可能同時存在多個任務，需要分別針對每個任務形成各自的聯盟，使得系統的總收益最大，這類問題稱為多任務多聯盟生成問題[8]。蔣建國、許金友等人[9，10]將多任務聯盟生成串行進行，其實質還是單聯盟生成問題;蘇射雄等人[11]對基于聯盟結構的方法進行了比較深入的探討，但是并沒有針對具體的任務生成聯盟，難以應用于實際;駱正虎[12]提出一種二維二進制遺傳算法來實現多聯盟的并行形成;蘇兆品等人[13]采用的免疫算法對多任務聯盟并行進行研究。林超峰 、郝志峰等人[14，15]分別采用螞蟻群算法對并行多任務環境下agent聯盟進行了研究。但是，這些多任務聯盟并行算法存在計算量大、收斂速度慢、全局尋優能力不強等問題。本文在前人研究的基礎上提出一種基于量子遺傳算法的多任務聯盟并行生成算法，降低了多任務聯盟問題的復雜性。

1 相關概念

1.1 多任務聯盟問題

當多agent系統同時存在多個待求解的任務時，需要針對每個任務同時生成相應的聯盟予以求解，這類問題稱為多任務聯盟的并行生成問題。

多任務多聯盟問題可描述為:設所要執行的任務為T={t1，t2，…，tm}，每個任務ti所需的能力向量為Bi=〈b1i，b2i，b3i，…，bri〉。假設任何一個聯盟組合CS都包含m(m為任務T所包含的任務個數)個聯盟，即CS={C0，C1，…，Cm};聯盟組合CS中的每一個聯盟Ci都對應于一個任務ti(C0除外，C0中的成員不屬于任何子任務)，若對應于任務ti的聯盟Ci不存在，則聯盟Ci不包括任何成員。每個聯盟Ci有一個聯盟代價costCj，該聯盟若能完成任務ti，則會獲得一個正的利益profitCi;若該聯盟不能完成任務ti，則profitCi=0。對于任務ti，每個聯盟Ci都有一個聯盟值valueCi，該值由聯盟代價costCi和聯盟完成任務所得的利益profitCi決定。多任務聯盟問題的數學模型為

a)集合N={A1，A2，A3，…，An};

b)對Ai∈N，有Bl=〈b1l，b2l，b3l，…，brl〉，1≤i≤n;

c)集合T={t1，t2，…，tm};

d)對ti∈T，有Bi=〈b1i，b2i，b3i，…，bri〉，1≤i≤m;

e)集合CS={C0，C1，…，Cm}，UCi∈CSCi=N;若i≠j，有Ci∩Cj=;

f)valueCS=∑mi=1valueCi=∑mi=1F(profitCi，costCi)。

本文的目的是要求一個最佳的聯盟組合CS，使得valueCS最大。

1.2 量子遺傳算法

量子遺傳算法[16](quantum genetic algorithm)是一種基于量子計算原理的概率優化方法。它以量子計算的一些概念和理論為基礎，采用量子比特編碼方式來表示染色體。這樣一條染色體能夠同時表達多個態的疊加，而傳統的編碼方式只能表示一個具體的狀態， 所以量子遺傳算法比其他傳統遺傳算法更容易保持種群的多樣性。量子遺傳算法用量子門作用和量子門更新來完成進化搜索，從而實現對目標問題的優化求解，具有種群規模小而不影響算法性能、同時兼有“開采”“勘探”的能力、全局尋優能力強以及收斂速度快的特點。利用量子遺傳算法簡單、通用、魯棒性強、并行搜索、群體尋優等特點來提高算法的搜索效率，構造量子染色體、構造初始種群，使資源組合和任務分配同時進行。經過量子遺傳算法優化后，根據適應度值確定下一輪迭代，并構成新的方案，染色體隨即延伸、演化，直至找到最優聯盟組合。

2 基于量子遺傳算法的多任務聯盟并行生成算法

2.1 量子編碼

編碼是應用進化算法時要解決的首要問題，因此也是應用量子遺傳算法時的首要問題。編碼的好壞直接決定了如何進行群體的進化和進化運算的效率。與單任務聯盟問題不同，考慮到多任務聯盟問題的復雜性，采用量子比特編碼來形成染色體:

p′i=α′11β′11α′12β′12……α′1lβ′1lα′21β′21……α′2lβ′2l……α′m1β′m1α′m2β′m2……α′mlβ′ml(1)

其中:m為染色體基因個數，對應于現實中任務的個數;k為編碼每個基因的量子比特數，如果可以執行該任務的agent數目為n，則k=log2 n」，」表示向上取整。對于一個用概率幅編碼的染色體進行測量獲得的一個確定的由二進制表示的解，該確定解對應一種分配方案如式(2)所示，即每個任務具體由哪個聯盟執行。在本文的編碼及其映射意義上，對于任務配置，選擇的是系統所有可能的資源集合，所以一個確定解準確地說代表了一種任務分配和資源組合方案，這種量子編碼方法同時完成了資源組合和任務分配步驟。

2.2 適應度函數設計

設一個多任務聯盟組合CS有聯盟代價costCS。對于每個多任務聯盟組合CS和任務集合T={t1，t2，…，tm}，對于任務t對應的利益為profitt，CS由m個聯盟組成，每一個聯盟Ci對應于任務ti，并且每個聯盟Ci包括幾個或零個agent。如果Ci沒有包括一個agent，那么ti將不被選中，若CS不能完成ti，則聯盟的值valueCS為0，否則聯盟值為一正數，并且代價越大，聯盟值越小，當聯盟CS不能完成任務t時，profitCS=0。本文將適應度函數定義為

F(CS)=valueCS=∑mi=1value(Ci)=∑mi=0profitti/∑mi=0costti(3)

2.3 量子門更新策略

量子門的構造是量子遺傳算法設計的關鍵問題，它直接關系到量子遺傳算法的性能好壞。在傳統量子遺傳算法中主要采用量子旋轉門，即U=cosθ-sinθsinθcosθ。其中θ為旋轉角。旋轉門是實現演化操作的最終執行機構， 這是由于個體的調整是通過量子旋轉門來實現的。傳統的旋轉門操作由于不改變相應基因位的值收斂為1或0的情況，經過傳統的旋轉門操作使此幾率幅值更趨近于1或0，因此易于產生早熟現象。為了改善這種現象，有的研究者設計了量子交叉操作，但這種方法在進化后期對種群的多樣化程度提高不太明顯。鑒于筆者前期的研究工作中采用進化方程自動調整量子門在解決單任務聯盟時得到的良好效果[6]，本文設計針對多任務多聯盟問題的量子遺傳算法也采用這種量子門更新策略。

3 實驗結果與分析

為了驗證本文算法的有效性，實驗參數如下:設機器人具有四種不同的能力，Ai=〈b1i，b2i，b3i，b4i〉，Ai完成任務所花費的代價為costAi=1×b1i+2×b2i+3×b3i+4×b4i;任務l需要四種不同的能力Bl=〈b1l，b2l，b3l，b4l〉，任務l的利益profitl=1×b1l+2×b2l+3×b3l+4×b4l。本文算法采用種群規模設為50，概率幅旋轉角度θ=0.002π;最大迭代次數為1 000;量子變異概率為0.05;實驗中設機器人個數n=200，其中每個agent的能力向量和各個任務的能力需求根據三種典型的環境隨機產生。然后在三種典型環境下分別應用本文算法、文獻[12]中的遺傳算法、文獻[15]中的蟻群算法求解相同的多任務聯盟問題，并對所得結果進行了比較。

環境1 Ball=∑ni=1BAi

環境2 Ball=∑ni=1BAi≥Bl，任務復雜，資源不充裕。在此環境下任務間激烈爭奪agent資源，合理的agent聯盟結構對完成相應任務獲得最大收益有重大的影響，該環境是實際agent系統中最為常見的情形。

環境3 Ball=∑ni=1BAi>>Bl，此時系統資源充足，各任務均能獲得充分資源，任務agent聯盟結構對任務求解影響較小。

表1給出了在三種環境下各種算法求解多任務聯盟的實驗結果統計比較;圖1給出了三種算法在環境3中求解30個任務時的進化過程曲線。從表1可以看出，在環境1下三種算法都無法生成任務求解聯盟;環境2下三種方法都可以生成任務求解聯盟，但結果的質量有差異，本文算法生成的聯盟其聯盟值總和最大、結果最優;環境3下文獻[12]和文獻[15]的算法因其極大的資源浪費，聯盟值甚小，而本文算法所得結果的優勢更明顯。從圖1可以看出，本文算法不易陷入局部極小，收斂速度快、收斂穩定性較高，且能很快收斂到最優解附近。由以上統計結果表明，在三種典型環境下本文算法可以及時、高效地生成多任務多個聯盟，并且解的質量明顯優于前兩種算法，特別是對于任務多、需要搜索時間較長、計算量較大的環境，能更好地體現本文算法的特點，避免了聯盟死鎖和資源浪費。

表1 三種算法的最優結果比較(100次統計平均值)

環境任務數

最大聯盟值

本文算法文獻[15]算法文獻[12]算法

1410300.00.00.00.00.00.00.00.00.0

2410300.989 70.978 80.968 90.949 80.947 70.936 60.834 90.802 20.783 4

3410300.982 20.975 60.968 10.943 20.934 50.930 30.801 20.792 40.774 3

4 結束語

在MAS中，聯盟是主要的合作方式。本文提出一種基于量子遺傳算法的多任務聯盟并行生成算法，運用量子編碼映射的方式將任務分配與資源組合合并為一個過程，使多任務聯盟問題的復雜性得到降低。

參考文獻:

[1]SHEHORY O，KRAUS S.Feasible formation of coalition among autono-mous agents in non-super-additive environments[J]. Computational Intelligence，1999，15(3):218-251.

[2]徐晉暉，石純一. 一種基于等價的聯盟演化機制[J].計算機研究與發展，1999，36(5):513-517.

[3]鄭金華，陳振洲，蔡自興. 用遺傳算法實現多智能體聯盟的形成[J].計算機工程與科學，2004，26(6):58-61.

[4]蔣建國，吳瓊，夏娜.自適應粒子群算法求解agent聯盟[J].智能系統學報，2007，2(2):69-73.

[5]夏娜，蔣建國，魏星，等.改進型蟻群算法求解單任務agent聯盟[J]. 計算機研究與發展，2005，42(5):734-739.

[6]許波，李智勇，王永.改進型量子遺傳算法求解機器人聯盟問題[J].計算機工程與應用，2009，45(4):38-41.

[7]LI Zhi-yong， XU Bo， YANG Lei， et al. Quantum evolutionary algorithm for multi-robot coalition formation[C]//Proc of the 1st ACM/SIGEVO Summit on Genetic and Evolutionary Computation.New York:ACM Press，2009:295-302.

[8]尹翔，蔣建國，夏娜，等.多任務多聯盟并行生成:模型與求解[J].系統工程理論與實踐，2008，28(4):90-95.

[9]蔣建國，夏娜，齊美彬，等.一種基于蟻群算法的串行多任務聯盟生成算法[J].電子學報，2005，33(12):2178-2182.

[10]許金友，李文立.基于自適應PSO和類別分解的多任務串行聯盟生成[J].計算機應用研究，2009，26(4):1338-1341.

[11]蘇射雄，胡山立，鄭盛福，等.基于勢結構的任一時間聯盟結構生成算法[J].計算機研究與發展，2008，45(10):1756-1762.

[12]駱正虎.移動agent系統若干關鍵技術問題研究[D].合肥:合肥工業大學研究生院，2002:81-98.

[13]蘇兆品，蔣建國，夏娜，等，基于維數劃分策略和免疫的多任務聯盟并行生成算法[J].系統工程理論與實踐，2008，28(1):118-123.

[14]林超峰，胡山立，鄭盛福，等.基于改進型蟻群算法的多任務聯盟形成算法[J].計算機研究與發展，2006，43(1):176-181.

[15]郝志峰，蔡瑞初.并行多任務環境下agent聯盟的快速生成算法[J].華南理工大學學報:自然科學版，2008，36(9):11-14，30.

[16]HAN K H， KIM J H. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization[J].IEEE Trans on Evolutionary Computation，2002，6(6):580-593.