计算机应用

作者：李飞龙, 赵春艳, 范如梦

单位：上海理工大学 理学院, 上海 200093

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

基金：国家自然科学基金资助项目（11301339）；国家自然科学基金国际（地区）合作与交流项目（11491240108）。

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

来源：2019年第12期

《计算机应用》期刊编辑部

查看计算机应用杂志2019年第12期