摘要
为了求解具有增长取值域的随机约束满足问题(CSP),提出了一种基于禁忌搜索并与模拟退火相结合的算法。首先,利用禁忌搜索得到一组启发式的初始赋值,即由一个随机初始化的可行解通过邻域构造一组候选解,再利用禁忌表使候选解向最小化目标函数值的方向移动;如果得到的最优赋值不是问题的解,就把它作为启发式的初始赋值,再执行模拟退火对这组赋值进行修正直到得到全局最优解。数值实验结果表明,所提算法在接近问题的理论相变阈值时仍然能有效地找到问题的解,与其他局部搜索算法相比,表现出了显著的优越性,可用于随机CSP的算法设计。
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.
作者
李飞龙
赵春艳
范如梦
LI Feilong;ZHAO Chunyan;FAN Rumeng(College of Science,University of Shanghai for Science and Technology,Shanghai 200093,China)
出处
《计算机应用》
CSCD
北大核心
2019年第12期3584-3589,共6页
journal of Computer Applications
基金
国家自然科学基金资助项目(11301339)
国家自然科学基金国际(地区)合作与交流项目(11491240108)~~
关键词
随机约束满足问题
RB模型
相变现象
禁忌搜索
模拟退火
算法效率
random Constraint Satisfaction Problem(CSP)
Revised B(RB) model
phase transition phenomenon
tabu search
simulated annealing
algorithm efficiency
