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

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

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

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