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

摘要：

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

关键词：分布式约束优化、动态子图、图密度、MULBS、MULBS+

所属期刊栏目：36

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61100090;中央高校基本科研业务费专项资金资助项目N110204006,N120804001;沈阳市科技计划项目F12-277-1-80;宁夏回族自治区自然科学基金资助项目NZ13265

在线出版日期：2015-07-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：188-193