两种改进的模拟退火算法求解大值域约束满足问题

• 作者: 原志强 赵春艳
• 来源期刊: 计算机应用研究
• 关键词: 约束满足问题 RB模型 模拟退火算法 遗传算法
• 年，卷（期）: 2017,（12）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 3611-3616
• 页数: 6页
• 分类号: TP301.5
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2017.12.021

摘要

随机约束满足问题的相变现象及求解算法是NP-完全问题的研究热点.RB(revised B)模型是一个非平凡的随机约束满足问题,它具有精确的可满足性相变现象和极易产生难解实例这两个重要特征.针对RB模型这类具有大值域的随机约束满足问题,提出了两种基于模拟退火的改进算法即RSA (revised simulated annealing algorithm)和GSA(genetic-simulated annealing algorithm).将这两种算法用于求解RB模型的随机实例,数值实验结果表明,在进入相变区域时,RSA和GSA依然可以有效地找到随机实例的解,并且在求解效率上明显优于随机游走算法.在接近相变阈值点时,由这两种算法得到的最优解仅使得极少数的约束无法满足.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	原志强	上海理工大学理学院	2	17	1.0	2.0
2	赵春艳	上海理工大学理学院	6	17	1.0	4.0