面向多智能體協(xié)作的啟發(fā)式聯(lián)盟結(jié)構(gòu)生成算法研究.pdf

1、近年來,在計算機人工智能領(lǐng)域,多智能體系統(tǒng)(Multi-Agent Systems,MAS)正在變得越來越重要。在MAS中,與Agent獨立工作相比,在許多任務(wù)中Agent采取聯(lián)盟或合作行為往往會取得更好的結(jié)果,因此,聯(lián)盟結(jié)構(gòu)生成(Coalition Structure Generation,CSG)問題成為了多智能體系統(tǒng)中的一個活躍的研究領(lǐng)域。
　　聯(lián)盟結(jié)構(gòu)被定義為一個劃分,就是把系統(tǒng)中所有智能體分成多個獨立不相交的聯(lián)盟。在多智

2、能體系統(tǒng)中,哪些智能體會形成聯(lián)盟,如何形成聯(lián)盟,是一個重要的問題。對此,博弈論提供了一些解決問題的方案:在一個確定的博弈中,可以挑選穩(wěn)定的結(jié)果。但是,尋求最優(yōu)聯(lián)盟結(jié)構(gòu)是一個NP完全問題。為了找到最優(yōu)的聯(lián)盟結(jié)構(gòu),通過遍歷搜索的方式在理論上是可行的。但由于需要搜索的聯(lián)盟劃分的數(shù)目是根據(jù)智能體的數(shù)目按貝爾數(shù)增長的,所以遍歷搜索會隨著搜索空間的增加而變得越來越不可能實現(xiàn)。
　　本文根據(jù)建立的無線通信系統(tǒng)背景下的MAS模型,從博弈論的視角提

3、出了兩個啟發(fā)式聯(lián)盟結(jié)構(gòu)生成算法,并對聯(lián)盟結(jié)構(gòu)的穩(wěn)定性和算法的復(fù)雜度進行了分析。算法通過基于成本的融合-分離的方式,允許各智能體采取不同的態(tài)度,以決定是否與其它成員(或聯(lián)盟)協(xié)作而融合或背叛聯(lián)盟而脫離,從而形成最終接近或達到最優(yōu)的聯(lián)盟結(jié)構(gòu)。蒙特卡洛式仿真實驗的結(jié)果表明,兩個算法在非遍歷搜索空間的情況下,都能取得較好的結(jié)果。當Mt<=100時,與非合作的情況相比,成員的效用分別提高了40.74％和43.37％。在Mt<=20時,用戶的平均效