关键词: 随机约束满足问题, RB模型, 相变现象, 禁忌搜索, 模拟退火, 算法效率

Abstract: 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.

Key words: random Constraint Satisfaction Problem (CSP), Revised B (RB) model, phase transition phenomenon, tabu search, simulated annealing, algorithm efficiency