基于溢出性原理的聯(lián)盟結(jié)構(gòu)生成算法研究.pdf

1、近年來，人工智能領(lǐng)域的多agent系統(tǒng)逐漸引起學(xué)者的關(guān)注。在多agent系統(tǒng)中，各個(gè)agent為了更好的完成任務(wù)，提高效率，采用相互合作的方式。與獨(dú)立工作相比，采用合作的方式效率更高。多agent系統(tǒng)中的各個(gè)agent通過不同的排列組合，被劃分成為不同的聯(lián)盟結(jié)構(gòu)。由于求解最優(yōu)聯(lián)盟結(jié)構(gòu)是一個(gè)NP難的問題，聯(lián)盟的增加是根據(jù)agent個(gè)數(shù)增加呈現(xiàn)指數(shù)增長的。因而，通過遍歷所有的聯(lián)盟結(jié)構(gòu)獲得最優(yōu)結(jié)果，只是理論上可行，在實(shí)際的應(yīng)用當(dāng)中，由于時(shí)間和

2、資源的限制，通?？梢垣@得次優(yōu)的聯(lián)盟結(jié)構(gòu)。
　　 本文首先對(duì)聯(lián)盟結(jié)構(gòu)生成問題的背景和所遇到的挑戰(zhàn)進(jìn)行闡述，同時(shí)詳細(xì)地描述了agent的基礎(chǔ)理論，對(duì)當(dāng)前聯(lián)盟結(jié)構(gòu)生成問題主要研究方法以及存在的問題進(jìn)行探討，從而提出本文研究的突破點(diǎn)。
　　 提出了利用剪枝函數(shù)對(duì)聯(lián)盟結(jié)構(gòu)圖進(jìn)行剪枝的方法。在特征函數(shù)論中，多agent系統(tǒng)中聯(lián)盟結(jié)構(gòu)的聯(lián)盟收益值都是相互獨(dú)立的。在聯(lián)盟結(jié)構(gòu)的生成過程中，一個(gè)聯(lián)盟的收益值不受其它agent劃分排列的影響。

3、將聯(lián)盟結(jié)構(gòu)圖中的聯(lián)盟結(jié)構(gòu)用整數(shù)拆分的形式進(jìn)行表示，通過剪枝函數(shù)，對(duì)搜索空間進(jìn)行橫向剪枝和縱向剪枝。此方法對(duì)于提高聯(lián)盟結(jié)構(gòu)圖的搜索效率取得了良好效果。
　　 提出了一種基于溢出性質(zhì)的聯(lián)盟結(jié)構(gòu)生成的任意時(shí)間算法，可以在任意時(shí)間得到一個(gè)次優(yōu)值。與特征函數(shù)論不同的是，在聯(lián)盟結(jié)構(gòu)生成的過程中，同一個(gè)聯(lián)盟在不同的聯(lián)盟結(jié)構(gòu)中的收益值是變化的，即為溢出性質(zhì)。根據(jù)溢出性質(zhì)，算法使用新的建立最壞情況下邊界值的方法。即對(duì)任意不相交的聯(lián)盟集合計(jì)算其上下