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

• 作者: 李飞龙 范如梦 赵春艳
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 随机约束满足问题 RB模型 相变现象 禁忌搜索 模拟退火 算法效率
• 年，卷（期）: 2019,（12）
• 所属期刊栏目: 先进计算
• 页码范围: 3584-3589
• 页数: 6页
• 分类号: TP301.6
• 字数: 6352字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2019050834

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵春艳	上海理工大学理学院	6	17	1.0	4.0
2	李飞龙	上海理工大学理学院	1	0	0.0	0.0
3	范如梦	上海理工大学理学院	2	0	0.0	0.0