Yet Another Local Search Method for Constraint Solving
Yet Another Local Search Method for Constraint Solving
复制标题
另一种约束求解的本地搜索方法
DOI：
10.1007/3-540-45322-9_5
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Daniel Diaz
中科院分区：
文献类型：
--
作者：
P. Codognet;Daniel Diaz
我们提出了一个通用的，域独立的局部搜索方法称为自适应搜索解决约束满足问题（CSP）。我们设计了一种新的算法，它利用了问题的约束和变量的结构，并且可以比全局成本函数更精确地引导搜索来优化（例如违反约束的数量）。我们还使用了自适应记忆的禁忌搜索的精神，以防止停滞在局部极小值和循环。该方法是通用的，可以应用于一大类约束（例如线性和非线性算术约束，符号约束等），并自然地处理过约束问题。一些经典的CSP问题的初步结果显示出非常令人鼓舞的性能。
We propose a generic, domain-independent local search method called adaptive search for solving Constraint Satisfaction Problems (CSP). We design a new heuristics that takes advantage of the structure of the problem in terms of constraints and variables and can guide the search more precisely than a global cost function to optimize (such as for instance the number of violated constraints). We also use an adaptive memory in the spirit of Tabu Search in order to prevent stagnation in local minima and loops. This method is generic, can apply to a large class of constraints (e.g. linear and non-linear arithmetic constraints, symbolic constraints, etc) and naturally copes with over-constrained problems. Preliminary results on some classical CSP problems show very encouraging performances.