一、 本課題設(shè)計(jì)（研究）的目的：
多機(jī)器人系統(tǒng)聯(lián)盟是多機(jī)器人協(xié)作的重要方法，聯(lián)盟的優(yōu)化問題是解決如何有效，快速的把系統(tǒng)中各個(gè)機(jī)器人組織起來結(jié)成任務(wù)聯(lián)盟，使系統(tǒng)能靈活、高效的完成某個(gè)任務(wù)，避免任務(wù)的死鎖問題和資源的浪費(fèi)問題，充分發(fā)揮系統(tǒng)的優(yōu)勢(shì)，降低任務(wù)成本，提高工作效率。[10]
現(xiàn)在，聯(lián)盟形成己經(jīng)成為多機(jī)器人系統(tǒng)研究的一個(gè)重要方面。基于生物學(xué)自然遺傳進(jìn)化的遺傳算法，是目前一種較成熟的進(jìn)化算法;是一種新的全局優(yōu)化搜索算法;是解決復(fù)雜問題的有效方法。遺傳算法具有很好的魯棒性，這是其他普通的優(yōu)化搜索算法所無法比擬的。它采用了許多獨(dú)特的方法和技術(shù)，利用選擇、交叉和變異等遺傳算子構(gòu)成的隨機(jī)技術(shù)來指導(dǎo)對(duì)搜索空間進(jìn)行高效搜索，被認(rèn)為是目前最好的搜索算法之一。近些年來，隨著計(jì)算機(jī)硬件技術(shù)的不斷提高以及對(duì)遺傳算法的研究的深入，遺傳算法的并行實(shí)現(xiàn)研究取得了許多成果。鑒于多智能體系統(tǒng) (特別是大規(guī)模智能體系統(tǒng))中聯(lián)盟形成的解空間的復(fù)雜性、多智能體系統(tǒng)的分布并行性以及遺傳算法的特性，研究運(yùn)用遺傳算法來實(shí)現(xiàn)聯(lián)盟形成和解決聯(lián)盟優(yōu)化問題具有重要的意義。
基本要求：
（1） 選擇合適的編碼方式如 0-1編碼或?qū)崝?shù)編碼；
（2） 使問題空間中的解能采用遺傳算法中的染色體來描述；
（3） 對(duì)遺傳算法中的相關(guān)部分 (如編碼、交叉、變異等)進(jìn)行設(shè)計(jì)，提出新的聯(lián)盟優(yōu)化算法；
（4） 針對(duì)某一具體聯(lián)盟問題，并給出模擬實(shí)驗(yàn)結(jié)果，說明改進(jìn)算法的優(yōu)點(diǎn)與特點(diǎn)。
二、 設(shè)計(jì)（研究）現(xiàn)狀和發(fā)展趨勢(shì)：
研究現(xiàn)狀：
1) 在聯(lián)盟形成方面：
聯(lián)盟是多Agent系統(tǒng)(MAS)的重要合作方法。Agent間通過組成聯(lián)盟可以提高求解問題的能力，獲得更多的利益。
目前在MAS中，聯(lián)盟形成的基本理論是N 人合作對(duì)策論理論，如Shapley值、核、核心等．N 人合作對(duì)策主要考慮如何劃分聯(lián)盟值，檢查劃分的穩(wěn)定性和公平性，使Agent在決策時(shí)愿意形成全局最優(yōu)聯(lián)盟；它沒有考慮算法，只考慮解的存在性，也不考慮計(jì)算資源、通信開銷和計(jì)算分布等要求．
隨著MAS的發(fā)展，研究人員從計(jì)算可實(shí)現(xiàn)的角度研究聯(lián)盟生成，并提出了一些相關(guān)算法Sandholm[11(4,5)]、 胡山立[11(6)]徐晉暉[11(7)]基于“聯(lián)盟結(jié)構(gòu)”求解多任務(wù)的Agent聯(lián)盟，聯(lián)盟的生成過程就是在聯(lián)盟結(jié)構(gòu)圖中進(jìn)行搜索．這些算法大多通過約束條件來裁剪搜索樹，減少搜索空間，在降低了算法復(fù)雜度的同時(shí)也犧牲了對(duì)最優(yōu)解的求解．Sen[11(8)] 、駱正虎[11(9)]基于遺傳算法求解Agent聯(lián)盟，在可接受的時(shí)間內(nèi)求解的質(zhì)量有所提高. 。陳振洲[13]等的工作主要討論非高一附加的多智能體環(huán)境，為多個(gè)智能體提供一個(gè)明顯的聯(lián)盟形成機(jī)制,在他們的研究中，聯(lián)盟值取決于聯(lián)盟資源的耗費(fèi)和完成任務(wù)所得的利益。
此外， Shehory和Kraus[13（2）]提出了一種合作的聯(lián)盟結(jié)構(gòu)產(chǎn)生算法——最大化整體的利益，即Agents都是非自私的。在這種Agents中，收益分配問題不需要討論。該分布算法形成不相交的聯(lián)盟，并將任務(wù)分配給聯(lián)盟，且每個(gè)聯(lián)盟每次只能執(zhí)行一個(gè)任務(wù)。Klusch和Shehory[13(4, 8)]對(duì)功利的聯(lián)盟形成進(jìn)行了討論，提出了一種面向核的穩(wěn)定的聯(lián)盟形成算法KCA (Kernel-OrientedCoalitionAlgorithm)。該算法能夠在多項(xiàng)式時(shí)間內(nèi)為信息Agents找出一個(gè)穩(wěn)定的聯(lián)盟。另外，韓莉等[11]利用基于并行蟻群算法實(shí)現(xiàn)了多機(jī)器人聯(lián)盟的組成。
2) 在遺傳算法方面：
自從1983年Goldberg在他的博士論文中第一次把遺傳算法用于實(shí)際的工程系統(tǒng)——煤氣管道的優(yōu)化后，遺傳算法在其他工程領(lǐng)域也得到了廣泛的應(yīng)用，如機(jī)器學(xué)習(xí)、模型識(shí)別、神經(jīng)網(wǎng)絡(luò)參數(shù)結(jié)構(gòu)優(yōu)化、飛船控制系統(tǒng)優(yōu)化等。在遺傳算法的理論研究方而，主要是防止早熟收斂，有眾多的研究者對(duì)這個(gè)問題做了大量的工作。王煦法等，根據(jù)生物免疫原理，提出了基于免疫原理的遺傳算法;趙明旺將最速下降法和遺傳算子結(jié)合，得到了新的用于連續(xù)函數(shù)全局優(yōu)化的混合數(shù)值算法;鄭金華等提出了“狹義遺傳算法”，創(chuàng)造性的拋開了變異算子，在解決單峰連續(xù)問題時(shí)表現(xiàn)出極好的效果；蒙祖強(qiáng)等提出的基于切平面土升的狹義遺傳算法，可以很好地解決多元 (連續(xù))函數(shù)的優(yōu)化問題。此外，人們對(duì)遺傳算法的并行實(shí)現(xiàn)也做了大量的研究。己經(jīng)提出了四種基本的并行遺傳算法模型: 1.全局并行遺傳算法 (GPGA) ; 2.粗粒度并行遺傳算法 ((CPGA); 3.細(xì)粒度并行遺傳算法 FPGA; 4.混合并行遺傳算法 (HPGA)。在這四種基本模型的基礎(chǔ)上，不同領(lǐng)域的研究者根據(jù)具體問題的不同也提出了其他一些并行遺傳算法模型。

發(fā)展趨勢(shì)：
現(xiàn)在，聯(lián)盟形成己經(jīng)成為多機(jī)器人系統(tǒng)研究的一個(gè)重要方面?；谏飳W(xué)自然遺傳進(jìn)化的遺傳算法，是目前一種較成熟的進(jìn)化算法;是一種新的全局優(yōu)化搜索算法;是解決復(fù)雜問題的有效方法。遺傳算法具有很好的魯棒性，這是其他普通的優(yōu)化搜索算法所無法比擬的。它采用了許多獨(dú)特的方法和技術(shù)，利用選擇、交叉和變異等遺傳算子構(gòu)成的隨機(jī)技術(shù)來指導(dǎo)對(duì)搜索空間進(jìn)行高效搜索，被認(rèn)為是目前最好的搜索算法之一。近些年來，隨著計(jì)算機(jī)硬件技術(shù)的不斷提高以及對(duì)遺傳算法的研究的深入，遺傳算法的并行實(shí)現(xiàn)研究取得了許多成果。遺傳算法在形成Agent聯(lián)盟(尤其在大規(guī)模Agent系統(tǒng))中具有廣闊的應(yīng)用前景。[12]

三、 設(shè)計(jì)（研究）的重點(diǎn)和難點(diǎn)，擬采用的途徑（研究手段）
重點(diǎn):
根據(jù)多智能體系統(tǒng) (特別是大規(guī)模智能體系統(tǒng))中聯(lián)盟形成的解空間的復(fù)雜性、多智能體系統(tǒng)的分布并行性以及遺傳算法的特性，主要任務(wù)如下：
1. 建立智能體聯(lián)盟/聯(lián)盟結(jié)構(gòu)問題的數(shù)學(xué)模型并研究怎樣運(yùn)用遺傳算法來實(shí)現(xiàn)聯(lián)盟形成以及算法的并行實(shí)現(xiàn)問題。
2. 針對(duì)單個(gè)不可分割的任務(wù)，提出基于遺傳算法的單個(gè)聯(lián)盟形成算法。針對(duì)己經(jīng)分割成幾個(gè)子任務(wù) (子任務(wù)之間沒有優(yōu)先關(guān)系)的任務(wù)，提出基于遺傳算法的聯(lián)盟結(jié)構(gòu)形成算法。并對(duì)上述兩種算法給出模擬實(shí)驗(yàn)結(jié)果。
難點(diǎn)：
與其他的最優(yōu)化問題一樣，聯(lián)盟形成問題需要在復(fù)雜而龐大的搜索空間中尋找最優(yōu)解或滿意解，在求解此類問題時(shí)，如果遍歷整個(gè)搜索空間，就會(huì)產(chǎn)生搜索的組合爆炸，在多項(xiàng)式時(shí)間內(nèi)無法完成搜索。因此，在使用遺傳算法解決聯(lián)盟優(yōu)化問題時(shí)，難點(diǎn)在于：
1. 如何利用遺傳算法一方面使得尋找最優(yōu)解或可行解的開銷極大地減少，另一方面使它所找到..