基于禁忌搜索算法求解随机约束满足问题

为了求解具有增长取值域的随机约束满足问题（CSP），提出了一种基于禁忌搜索并与模拟退火相结合的算法。首先，利用禁忌搜索得到一组启发式的初始赋值，即由一个随机初始化的可行解通过邻域构造一组候选解，再利用禁忌表使候选解向最小化目标函数值的方向移动；如果得到的最优赋值不是问题的解，就把它作为启发式的初始赋值，再执行模拟退火对这组赋值进行修正直到得到全局最优解。数值实验结果表明，所提算法在接近问题的理论相变阈值时仍然能有效地找到问题的解，与其他局部搜索算法相比，表现出了显著的优越性，可用于随机CSP的算法设计。

Solving random constraint satisfaction problems based on tabu search algorithm

A novel algorithm based on tabu search and combined with simulated annealing was proposed to solve random Constraint Satisfaction Problem (CSP) with growing domain. Firstly, tabu search was used to obtain a set of initial heuristic assignments, which meant a set of candidate solutions were constructed based on a randomly initialized feasible solution through neighborhood, and then the tabu table was used to move the candidate solutions to the direction of minimizing the objective function value. If the obtained optimal assignment was not the solution of the problem, the assignment would be used as the initial heuristic assignment and then simulated annealing was performed to correct the set of assignments until the global optimal solution was obtained. The numerical experiments demonstrate that, the proposed algorithm can effectively find the solution of problem when approaching the theoretical phase transition threshold of problem, and it shows obvious superiority compared with other local search algorithms. The proposed algorithm can be applied to the algorithm design of random CSP.