资源描述：
《多agent联盟结构动态生成算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.ac.cnJournalofSoftware,Vol.18,No.3,March2007,pp.574−581http://www.jos.org.cnDOI:10.1360/jos180574Tel/Fax:+86-10-62562563©2007byJournalofSoftware.Allrightsreserved.∗多Agent联盟结构动态生成算法+张新良,石纯一(清华大学计算机科学与技术系,北京100084)ADynamicFormationAlgori
2、thmofMulti-AgentCoalitionStructure+ZHANGXin-Liang,SHIChun-Yi(DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084,China)+Correspondingauthor:Phn:+86-10-62783505,E-mail:xinliangzhang@alcatel-lucent.comZhangXL,ShiCY.Adynamicformationalgorithmofmulti-Agentcoa
3、litionstructure.JournalofSoftware,2007,18(3):574−581.http://www.jos.org.cn/1000-9825/18/574.htmAbstract:Tosolvethenumberofcoalitionstructureincreaserapidly,algorithmSCS(searchofcoalitionstructure),fastdynamicformationofAgentcoalition,isgiven.ItcanprunethegraphofAgentcoalitions
4、tructure,ndecreasethesearchingspace.,andprovedthatafterpruning,thenumberofcoalitionstructureisofthatn−k(k−1)beforepruning.Finally,anexperimentisgiven.ThisworkcanbeseenasanimprovementofJenningsandSandholm’srelatedwork.Keywords:multi-Agentsystem;coalition;coalitionstructure;SCSa
5、lgorithm摘要:针对多Agent联盟数量是Agent个数指数倍的问题,基于Agent合作收益独立性,给出了Agent联盟快速动态生成算法——SCS(searchofcoalitionstructure)算法;依Agent联盟之间的同构关系,将Agent联盟结构图剪n枝,然后进行Agent联盟结构搜索,可降低搜索空间大小,并证明了是剪枝前搜索量的.最后,以机器人n−k(k−1)足球赛RoboCup为背景给出了实验分析,表明了SCS算法的效率.SCS算法是对Jennings和Sandholm等人相关工作的改进.关键词:多Agent系统;联盟;联盟
6、结构;SCS(searchofcoalitionstructure)算法中图法分类号:TP18文献标识码:A多Agent合作求解是多Agent系统(multi-Agentsystem,简称MAS)理论与技术研究的重点,Agent联盟可看作是Agent合作求解的一种形式.在MAS中,联盟内的Agent通常采取合作策略,而不同联盟内的Agent,则采取一般的求解策略.Agent如何联盟以使整体收益最大是多Agent合作求解的关键.近年来,越来越多的研究者考[1−7][1]虑了Agent动态联盟形成算法.Jennings采用对联盟结构中最大联盟规模不小于
7、n(q−1)/q的逐步搜索的[2]办法,其中,q=(n+1)/4到n,可得到收益不低于最优收益的1/(2q−1)的联盟结构.Anderson分析了RoboCup中足球机器人之间的联盟动态形成问题.文献[3]中,Klusch等人提出了Agent联盟satecore状态,用来表示Agent联∗SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNos.60573076,60496323(国家自然科学基金)Received2005-01-27;Accepted2006-02
8、-23张新良等:多Agent联盟结构动态生成算法575[4][5]盟的均衡状态.Gerber和Konishi则重点考虑了A
