基于量子遺傳算法的多任務(wù)聯(lián)盟并行生成算法

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

關(guān)鍵詞:多任務(wù)聯(lián)盟; 量子遺傳算法; 多agent系統(tǒng); agent聯(lián)盟; 組合優(yōu)化

中圖分類號:TP393;TP301.6文獻(xiàn)標(biāo)志碼: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間通過組成聯(lián)盟可以提高求解問題的能力，因此agent聯(lián)盟問題引起了研究人員廣泛的關(guān)注。自1993年提出聯(lián)盟方法以來，聯(lián)盟生成已成為多agent系統(tǒng)研究的一個重要方面并取得了一定的進(jìn)展。傳統(tǒng)的方法是利用n人合作對策論，但是計算復(fù)雜度過高;Shehory等人[1]通過限制聯(lián)盟規(guī)模使算法在多項式時間內(nèi)收斂，但減少了系統(tǒng)的收益;徐晉暉等人[2]提出基于任務(wù)等價的聯(lián)盟演化機(jī)制，但匹配要求很嚴(yán)格。

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

1 相關(guān)概念

1.1 多任務(wù)聯(lián)盟問題

當(dāng)多agent系統(tǒng)同時存在多個待求解的任務(wù)時，需要針對每個任務(wù)同時生成相應(yīng)的聯(lián)盟予以求解，這類問題稱為多任務(wù)聯(lián)盟的并行生成問題。

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

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)。

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

1.2 量子遺傳算法

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

2 基于量子遺傳算法的多任務(wù)聯(lián)盟并行生成算法

2.1 量子編碼

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

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

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

2.2 適應(yīng)度函數(shù)設(shè)計

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

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

2.3 量子門更新策略

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

3 實(shí)驗(yàn)結(jié)果與分析

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

環(huán)境1 Ball=∑ni=1BAi

環(huán)境2 Ball=∑ni=1BAi≥Bl，任務(wù)復(fù)雜，資源不充裕。在此環(huán)境下任務(wù)間激烈爭奪agent資源，合理的agent聯(lián)盟結(jié)構(gòu)對完成相應(yīng)任務(wù)獲得最大收益有重大的影響，該環(huán)境是實(shí)際agent系統(tǒng)中最為常見的情形。

環(huán)境3 Ball=∑ni=1BAi>>Bl，此時系統(tǒng)資源充足，各任務(wù)均能獲得充分資源，任務(wù)agent聯(lián)盟結(jié)構(gòu)對任務(wù)求解影響較小。

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

表1 三種算法的最優(yōu)結(jié)果比較(100次統(tǒng)計平均值)

環(huán)境任務(wù)數(shù)

最大聯(lián)盟值

本文算法文獻(xiàn)[15]算法文獻(xiàn)[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 結(jié)束語

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

參考文獻(xiàn):

[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]徐晉暉，石純一. 一種基于等價的聯(lián)盟演化機(jī)制[J].計算機(jī)研究與發(fā)展，1999，36(5):513-517.

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

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

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

[6]許波，李智勇，王永.改進(jìn)型量子遺傳算法求解機(jī)器人聯(lián)盟問題[J].計算機(jī)工程與應(yīng)用，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]尹翔，蔣建國，夏娜，等.多任務(wù)多聯(lián)盟并行生成:模型與求解[J].系統(tǒng)工程理論與實(shí)踐，2008，28(4):90-95.

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

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

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

[12]駱正虎.移動agent系統(tǒng)若干關(guān)鍵技術(shù)問題研究[D].合肥:合肥工業(yè)大學(xué)研究生院，2002:81-98.

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

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

[15]郝志峰，蔡瑞初.并行多任務(wù)環(huán)境下agent聯(lián)盟的快速生成算法[J].華南理工大學(xué)學(xué)報:自然科學(xué)版，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.