Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (12): 3584-3589.DOI: 10.11772/j.issn.1001-9081.2019050834

• Advanced computing • Previous Articles     Next Articles

Solving random constraint satisfaction problems based on tabu search algorithm

LI Feilong, ZHAO Chunyan, FAN Rumeng   

  1. College of Science, University of Shanghai for Science and Technology, Shanghai 200093, China
  • Received:2019-05-16 Revised:2019-07-08 Online:2019-07-23 Published:2019-12-10
  • Contact: 赵春艳
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (11301339), the National Natural Science Foundation of China — International (Regional) Cooperation and Exchange Program (11491240108).


李飞龙, 赵春艳, 范如梦   

  1. 上海理工大学 理学院, 上海 200093
  • 作者简介:李飞龙(1994-),男,安徽阜阳人,硕士研究生,主要研究方向:计算理论与计算复杂性;赵春艳(1982-),女,河南焦作人,讲师,博士,主要研究方向:NP-完全问题、计算理论与计算复杂性;范如梦(1995-),女,河南驻马店人,硕士研究生,主要研究方向:计算理论与计算复杂性。
  • 基金资助:

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

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

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

CLC Number: