An Improved Tabu Search Method For The Weighted Constraint Satisfaction Problem
An Improved Tabu Search Method For The Weighted Constraint Satisfaction Problem
复制标题
加权约束满足问题的改进禁忌搜索方法
DOI：
10.1080/03155986.2001.11732431
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
T. Ibaraki
中科院分区：
文献类型：
--
作者：
K. Nonobe;T. Ibaraki
摘要针对组合优化问题的一般求解问题，本文考虑了加权约束满足问题（WCSP），它要求在给定若干约束及其重要权的情况下，最小化未满足约束的总权。我们提出了一个禁忌搜索算法WCSP的特点，它使用的评价函数，定义在修改后的权重的约束，用于指导搜索，它采用了自动控制机制的权重的评价函数。使用该代码，我们解决了一些问题，包括那些从真实的应用，如广义分配，集覆盖，并行车间调度，排产和护士调度。单元制造中出现的许多问题也可以用WCSP来表示，包括单元形成和工具选择问题。计算结果表明，权值的控制机制使禁忌搜索算法具有更强的搜索能力，算法具有较好的实用性。
Abstract Aiming at developing a general problem solver for combinatorial optimization problems, we consider in this paper the weighted constraint satisfaction problem (WCSP), which, given a number of constraints and their weights of importance, asks to minimize the total weight of unsatisfied constraints. We propose a tabu search algorithm for WCSP with the features that it uses an evaluation function, defined in terms of the modified weights of constraints, for guiding the search, and that it incorporates an automatic control mechanism of the weights in the evaluation function. Using this code, we solved a number of problems including those from real applications such as generalized assignment, set covering, parallel shop scheduling, timetabling and nurse scheduling. Many problems that arise in cellular manufacturing can also be formulated as WCSP, including the problems of cell formation and tool selection. Our computational results indicate that the control mechanism of weights makes our tabu search more powerful, and our algorithm is practically usable.