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

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

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

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