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

An Improved Distributed Constraint Optimization Algorithm MULBS^+

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

Although complete algorithms can be used in finding the optimal solution of a distributed constraint optimization problem, the resource and time consumptions are heavy. On the contrary, the shortcoming can be avoided in incomplete algorithms by obtaining suboptimal solutions. As an effective incomplete algorithm, MULBS can improve the quality of solution and reduce the runtime of solving process. However, there are shortcomings in parallel search and backtracking processes in dealing with conflict assignments. Based on thorough analysis of MULBS, an improved algorithm MULBS ~ is proposed, which overcomes the disadvantages of backtrack strategy caused by conflict and parallel search strategy in the original algorithm. In MULBS ~ , a minimal conflict selection mechanism is introduced in backtracking. On the other hand, MULBS ~ adopts global parallel search strategy based on dynamic graph partitioning which can quickly find a better solution in a constraint graph with large density. Experiments show that the proposed algorithm is better than the original one in both execution time and solution quality, except a certain increase of communication information.