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

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

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