基于溢出性原理的联盟结构生成算法_张利凯_王黎明

ID:4143598

大小:389.56 KB

页数:6页

时间:2017-11-29

基于溢出性原理的联盟结构生成算法_张利凯_王黎明_第1页
基于溢出性原理的联盟结构生成算法_张利凯_王黎明_第2页
基于溢出性原理的联盟结构生成算法_张利凯_王黎明_第3页
基于溢出性原理的联盟结构生成算法_张利凯_王黎明_第4页
基于溢出性原理的联盟结构生成算法_张利凯_王黎明_第5页
资源描述:

《基于溢出性原理的联盟结构生成算法_张利凯_王黎明》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

1、网络出版时间:2013-11-1216:39网络出版地址:http://www.cnki.net/kcms/detail/61.1450.TP.20131112.1639.039.html基于溢出性原理的联盟结构生成算法张利凯王黎明(郑州大学信息工程学院河南郑州450001)摘要:联盟结构的生成问题中由于搜索空间的联盟结构数目太大,因而搜索联盟结构的最底两层建立一个最坏情况下的边界值是必要的,边界值将最优的联盟结构限制在某个限界内,通过进一步的搜索可以在任意时间内得到一个较优值。根据联盟的溢出性质,文中提出了一种新的建立边界值方法,即对任意不相交的联盟集合计算其上下边界的值,通过搜索特

2、定的联盟结构集合建立最坏情况下的边界值。联盟的边界值建立以后,可以在任意时间内得到一个较优值,通过搜索剩余的联盟结构集合,可以对边界值和返回的联盟结构进一步优化。在此基础上文中提出了基于溢出性质的任意时间算法。实验结果表明,采用新的方法建立边界值,使得算法的收敛速度更快,效率更高。关键词:联盟联盟结构溢出性划分搜索边界值中图分类号:TP301.4文献标识码:AALGORITHMFORCOALITIONSTRUCTUREGENERATIONWITHEXTERNALITIESZhangLikai,WangLiming(SchoolofInformationEngineering,Zheng

3、zhouUniversity,Zhengzhou450001,China)AbstractThesearchspaceofcoalitionstructuregraphissobiginCharacteristicFunctionGamesthatitisnecessarytobuildaworst-caseboundtoboundthebestcoalitionstructurebysearchingthelasttwolevelsofcoalitionstructuregraph.,anditcanfinallygetabettercoalitionstructurefromit.

4、Inpartitionfunctiongames,onecoalitionmaybeaffectedbytheformationofotherdistinctcoalitions,soanewmethodofbuildingtheworst-caseboundisproposed.Webuildtheworst-caseboundbycomputingtheupperandlowerboundsonthevaluesofanysetofcoalitionsandsearchingthesetofthecoalitionstructure.Soanytimealgorithmbasedo

5、nexternalitiesisproposed.Itisabletogetagoodresultafterbuildingtheworst-casebound,andtheresultcouldbeoptimizedthroughfurthersearch.Theefficiencyofalgorithmisimprovedandasatisfactoryvalueisabletobegainedatanytime.KeywordsCoalitionCoalitionstructureExternalitiesDistributionsearchBound0引言在多agent系统中,

6、联盟形成是多agent交互的一种重要形式。由于单个agent能力有限,无法独立完成某一任务或者通过多个agent协作能提高求解效率,agent之间经常需要协作来完成任务求解。在划分函数论中的溢出性质使得联盟结构的生成问题变得更加复杂。文献[1]证明了对联盟结构图搜索完最底2层和最顶层以后,可得到收益不低于最优收益的1/⌈n/2⌉的agent联盟结构。文献[2~3]给出了一种满足某种质量要求的算法,可以在任意时间得出较优值,但要得到最优值仍要搜索O(nn)的空间。文献[4]提出一种随机算法,该算法能够在O(2n)的八分之一的时间内建立最坏情况下的边界值,而以前的算法建立最坏边界值需要的时

7、间为O(2n)。文献[5]的算法解决了联盟结构空间的大量重复搜索的问题,空间复杂度是动态规划算法空间复杂度的三分之一,但是此算法只能得到近似最优的联盟结构。文献[6]根据联盟的溢出性质将划分函数论中的联盟结构生成划分为超加、超减、子加和子减四类,缺点是算法的效率仍然偏低。文献[7]将特征函数论中的动态规划算法应用到划分函数论中,此算法能够在程序运行结束时可以得到一个最优值,但是不能再任意时间内返回一个临时值。文献[8]通过搜索具有溢出性质的联盟

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
正文描述:

《基于溢出性原理的联盟结构生成算法_张利凯_王黎明》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

1、网络出版时间:2013-11-1216:39网络出版地址:http://www.cnki.net/kcms/detail/61.1450.TP.20131112.1639.039.html基于溢出性原理的联盟结构生成算法张利凯王黎明(郑州大学信息工程学院河南郑州450001)摘要:联盟结构的生成问题中由于搜索空间的联盟结构数目太大,因而搜索联盟结构的最底两层建立一个最坏情况下的边界值是必要的,边界值将最优的联盟结构限制在某个限界内,通过进一步的搜索可以在任意时间内得到一个较优值。根据联盟的溢出性质,文中提出了一种新的建立边界值方法,即对任意不相交的联盟集合计算其上下边界的值,通过搜索特

2、定的联盟结构集合建立最坏情况下的边界值。联盟的边界值建立以后,可以在任意时间内得到一个较优值,通过搜索剩余的联盟结构集合,可以对边界值和返回的联盟结构进一步优化。在此基础上文中提出了基于溢出性质的任意时间算法。实验结果表明,采用新的方法建立边界值,使得算法的收敛速度更快,效率更高。关键词:联盟联盟结构溢出性划分搜索边界值中图分类号:TP301.4文献标识码:AALGORITHMFORCOALITIONSTRUCTUREGENERATIONWITHEXTERNALITIESZhangLikai,WangLiming(SchoolofInformationEngineering,Zheng

3、zhouUniversity,Zhengzhou450001,China)AbstractThesearchspaceofcoalitionstructuregraphissobiginCharacteristicFunctionGamesthatitisnecessarytobuildaworst-caseboundtoboundthebestcoalitionstructurebysearchingthelasttwolevelsofcoalitionstructuregraph.,anditcanfinallygetabettercoalitionstructurefromit.

4、Inpartitionfunctiongames,onecoalitionmaybeaffectedbytheformationofotherdistinctcoalitions,soanewmethodofbuildingtheworst-caseboundisproposed.Webuildtheworst-caseboundbycomputingtheupperandlowerboundsonthevaluesofanysetofcoalitionsandsearchingthesetofthecoalitionstructure.Soanytimealgorithmbasedo

5、nexternalitiesisproposed.Itisabletogetagoodresultafterbuildingtheworst-casebound,andtheresultcouldbeoptimizedthroughfurthersearch.Theefficiencyofalgorithmisimprovedandasatisfactoryvalueisabletobegainedatanytime.KeywordsCoalitionCoalitionstructureExternalitiesDistributionsearchBound0引言在多agent系统中,

6、联盟形成是多agent交互的一种重要形式。由于单个agent能力有限,无法独立完成某一任务或者通过多个agent协作能提高求解效率,agent之间经常需要协作来完成任务求解。在划分函数论中的溢出性质使得联盟结构的生成问题变得更加复杂。文献[1]证明了对联盟结构图搜索完最底2层和最顶层以后,可得到收益不低于最优收益的1/⌈n/2⌉的agent联盟结构。文献[2~3]给出了一种满足某种质量要求的算法,可以在任意时间得出较优值,但要得到最优值仍要搜索O(nn)的空间。文献[4]提出一种随机算法,该算法能够在O(2n)的八分之一的时间内建立最坏情况下的边界值,而以前的算法建立最坏边界值需要的时

7、间为O(2n)。文献[5]的算法解决了联盟结构空间的大量重复搜索的问题,空间复杂度是动态规划算法空间复杂度的三分之一,但是此算法只能得到近似最优的联盟结构。文献[6]根据联盟的溢出性质将划分函数论中的联盟结构生成划分为超加、超减、子加和子减四类,缺点是算法的效率仍然偏低。文献[7]将特征函数论中的动态规划算法应用到划分函数论中,此算法能够在程序运行结束时可以得到一个最优值,但是不能再任意时间内返回一个临时值。文献[8]通过搜索具有溢出性质的联盟

显示全部收起
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。
关闭