全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

一种改进的分布约束优化算法MULBS+

DOI: 10.3969/j.issn.1005-3026.2015.02.008, PP. 188-193

Keywords: 分布式约束优化,动态子图,图密度,MULBS,MULBS+

Full-Text   Cite this paper   Add to My Lib

Abstract:

完备算法虽然能够求得分布式约束优化问题最优解,但要消耗大量资源及时间,相反,非完备算法通过求得次优解来提高效率.MULBS作为一个有效的非完备算法,虽然在求解质量和时间上有所提高,但在解决赋值冲突时采用的回溯策略及并行搜索方面存在不足.通过对该算法的深入分析,本文针对上述问题进行了改进,提出其改进算法MULBS+.通过在回溯策略中引入最小冲突选择机制,以及在约束图密度较大时采用基于动态子图划分的并行搜索策略,进一步提高了算法的性能.实验表明,该算法除增加一定的通信信息外,其执行时间及求解质量均优于原算法.

References

[1]  Enembreck F,Barthès Jean-Paul A.Distributed constraint optimization with MULBS:a case study on collaborative meeting scheduling[J].Journal of Network and Computer Applications,2012,35(1):164-175.
[2]  Petcu A.FRODO:a framework for open and distributed constraint optimization.technical report.No.2006/001[R].Lausanne:Swiss Federal Institute of Technology,2006.
[3]  Gutierrez P,Meseguer P,Yeoh W.Generalizing ADOPT and BnB-ADOPT[C]// Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-11).Barcelona,2011:554-559.
[4]  Marconi M,Helmut P.Multi-user eco-driving training environment based on distributed constraint optimization[C]//Proceedings of AAMAS.St.Paul,2013:925-932.
[5]  Lesser V,Corkill D.Challenges for multi-agent coordination theory based on empirical observations[C]//Proceedings of AAMAS.Paris,2014:1157-1160.
[6]  Thomas L.Distributed constraint optimization:privacy guarantees and stochastic uncertainty[D].Lausanne:Swiss Federal Institute of Technology in Lausanne,2011.
[7]  Tambe M.Towards flexible teamwork [J]. Journal of Artificial Intelligence Research, 1997,7(1):83-124.
[8]  Scerri P,Johnson L,Pynadath D,et al.A prototype infrastructure for distributed robot,agent,person teams[C]//Proceedings of AAMAS.Melbourne,2003:433-440.
[9]  Yokoo M,Hirayama K.Distributed breakout algorithm for solving distributed constraint satisfaction problems[C]// Proceedings of the Second International Conference on Multiagent Systems.Kyoto,1996:401-408.
[10]  Fitzpatrick S,Meertens L.An experimental assessment of a stochastic,anytime,decentralized,soft colourer for sparse graphs[C]// Proceedings of the International Symposium on Stochastic Algorithms:Foundations and Applications.Berlin,2001:49-64.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133