计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2008年
10期
1756-1762
,共7页
苏射雄%胡山立%郑盛福%林超峰%骆剑彬
囌射雄%鬍山立%鄭盛福%林超峰%駱劍彬
소사웅%호산립%정성복%림초봉%락검빈
多Agent系统%联盟形成%任一时间算法%联盟结构生成%势结构%特征函数
多Agent繫統%聯盟形成%任一時間算法%聯盟結構生成%勢結構%特徵函數
다Agent계통%련맹형성%임일시간산법%련맹결구생성%세결구%특정함수
联盟形成是多Agent系统中的一个关键问题.人们寻求能极大化联盟值总和的联盟结构,但通常情况下可能的联盟结构的数目太大,以致不允许进行穷尽搜索而找出最优解.Sandholm等人已经证明,要建立最坏情况下的限界K(n),搜索联盟结构图的最底两层是必要且是充分的.Dang等人给出的算法是所见到的第1个不以层为单位的搜索算法,对于较小的限界明显地优于Sandholm等人给出的算法.深刻分析了联盟结构间的关系,采用更小的搜索粒度(势结构),提出基于势结构的任一时间算法,在搜索最底两层及顶层后,进一步搜索势结构集合CCS(n,6)对应的未搜索过的联盟结构,渐进地给出越来越低的限界,大大改进了Sandholm等人(快1035倍,当n=100,K=2)和Dang等人(快1018倍,当n=100,K=3)的工作.
聯盟形成是多Agent繫統中的一箇關鍵問題.人們尋求能極大化聯盟值總和的聯盟結構,但通常情況下可能的聯盟結構的數目太大,以緻不允許進行窮儘搜索而找齣最優解.Sandholm等人已經證明,要建立最壞情況下的限界K(n),搜索聯盟結構圖的最底兩層是必要且是充分的.Dang等人給齣的算法是所見到的第1箇不以層為單位的搜索算法,對于較小的限界明顯地優于Sandholm等人給齣的算法.深刻分析瞭聯盟結構間的關繫,採用更小的搜索粒度(勢結構),提齣基于勢結構的任一時間算法,在搜索最底兩層及頂層後,進一步搜索勢結構集閤CCS(n,6)對應的未搜索過的聯盟結構,漸進地給齣越來越低的限界,大大改進瞭Sandholm等人(快1035倍,噹n=100,K=2)和Dang等人(快1018倍,噹n=100,K=3)的工作.
련맹형성시다Agent계통중적일개관건문제.인문심구능겁대화련맹치총화적련맹결구,단통상정황하가능적련맹결구적수목태대,이치불윤허진행궁진수색이조출최우해.Sandholm등인이경증명,요건립최배정황하적한계K(n),수색련맹결구도적최저량층시필요차시충분적.Dang등인급출적산법시소견도적제1개불이층위단위적수색산법,대우교소적한계명현지우우Sandholm등인급출적산법.심각분석료련맹결구간적관계,채용경소적수색립도(세결구),제출기우세결구적임일시간산법,재수색최저량층급정층후,진일보수색세결구집합CCS(n,6)대응적미수색과적련맹결구,점진지급출월래월저적한계,대대개진료Sandholm등인(쾌1035배,당n=100,K=2)화Dang등인(쾌1018배,당n=100,K=3)적공작.
