Multi-Hyb: A Hybrid Algorithm for Solving DisCSPs with Complex Local Problems
Multi-Hyb: A Hybrid Algorithm for Solving DisCSPs with Complex Local Problems
复制标题
Multi-Hyb：一种用于解决具有复杂局部问题的 DisCSP 的混合算法
DOI：
10.1109/wi-iat.2009.181
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
K. Hui
中科院分区：
文献类型：
--
作者：
David Lee;I. Arana;Hatem Ahriz;K. Hui
粗粒度分布式约束满足问题(DisCSP)是一个约束问题，其中多个代理协作确定全局解，每个代理负责解决一部分(复杂的局部问题)。因此，代理通过为他们复杂的局部问题找到一个与其他代理针对自己的局部问题提出的解决方案相兼容的解决方案来解决整体问题。目前已经提出了几种求解DisCSP的方法，可分为系统搜索和局部搜索。提出了一种求解粗粒度DisCSPs的两阶段混合算法--多层次混合算法，在求解过程中采用了系统搜索和局部搜索相结合的方法。阶段1使用系统搜索生成全局问题的关键部分解决方案。同时，基于惩罚的局部搜索算法试图使用这些局部解来寻找问题的全局解。如果在第一阶段没有找到全局解，则使用从第一阶段学到的信息来通知在下一阶段执行的搜索。第二阶段在第一阶段获得的以下知识的指导下，对复变量运行系统搜索算法：(I)部分解；(Ii)看起来更难满足的复杂局部问题。实验评估表明，在以下几个问题类中，多HIB算法具有竞争性：(I)通信开销和(Ii)所需的计算工作量。
A coarse-grained Distributed Constraint Satisfaction Problem (DisCSP) is a constraint problem where several agents, each responsible for solving one part (a complex local problem), cooperate to determine an overall solution. Thus, agents solve the overall problem by finding a solution to their complex local problem which is compatible with the solutions proposed by other agents for their own local problems. Several approaches to solving DisCSPs have been devised and can be classified as systematic search and local search techniques. We present Multi-Hyb, a two-phase hybrid algorithm for solving coarse-grained DisCSPs which uses both systematic and local search during problem solving. Phase 1 generates key partial solutions to the global problem using systematic search. Concurrently, a penalty-based local search algorithm attempts to find a global solution to the problem using these partial solutions. If a global solution is not found in phase 1, the information learnt from phase 1 is used to inform the search carried out during the next phase. Phase two runs a systematic search algorithm on complex variables guided by the following knowledge obtained in phase 1: (i) partial solutions and; (ii) complex local problems which appear more difficult to satisfy. Experimental evaluation demonstrates that Multi-Hyb is competitive in several problem classes in terms of: (i) the communication cost and (ii) the computational effort needed.
分布式约束满足中的简单-困难-简单成本概况
DOI：
--
发表时间：
2005
期刊：
情報処理学会論文誌 45巻・9号
影响因子：
--
作者：
Hirayama;K
通讯作者：
K