两种改进的模拟退火算法求解大值域约束满足问题-计算机应用研究.PDFVIP

两种改进的模拟退火算法求解大值域约束满足问题 作者 原志强, 赵春艳 机构 上海理工大学 理学院 发表期刊 《计算机应用研究》 预排期卷 2017 年第34 卷第12 期 访问地址 /article/02-2017-12-020.html 发布日期 2017-01-23 15:04:42 引用格式 原志强, 赵春艳. 两种改进的模拟退火算法求解大值域约束满足问题[J/OL]. [2017-01-23]. http:/ //article/02 -2017-12-020.html. 摘要 随机约束满足问题的相变现象及求解算法是NP-完全问题的研究热点。RB 模型（revised B）是一 个非平凡的随机约束满足问题，它具有精确的可满足性相变现象和极易产生难解实例这两个重要 特征。针对 RB 模型这一类具有大值域的随机约束满足问题，提出了两种基于模拟退火的改进算 法即RSA （revised simulated annealing algorithm）和GSA （genetic-simulated annealing algorithm）。 将这两种算法用于求解RB 模型的随机实例，数值实验结果表明：… 关键词 约束满足问题, RB 模型, 模拟退火算法, 遗传算法 中图分类号 TP301.5 基金项目 国家自然科学基金资助项目11491240108; 上海高校青年教师培养计 划资助项目 优先出版 计 算 机 应 用 研 究 第34 卷 两种改进的模拟退火算法求解大值域约束满足问题* 1 2 原志强 ，赵春艳 (上海理工大学 理学院，上海200093) 摘 要：随机约束满足问题的相变现象及求解算法是NP-完全问题的研究热点。RB 模型（revised B）是一个非平凡的 随机约束满足问题，它具有精确的可满足性相变现象和极易产生难解实例这两个重要特征。针对RB 模型这一类具有大 值域的随机约束满足问题，提出了两种基于模拟退火的改进算法即RSA （revised simulated annealing algorithm）和GSA （genetic-simulated annealing algorithm）。将这两种算法用于求解RB 模型的随机实例，数值实验结果表明：在进入相变 区域时，RSA 和GSA 算法依然可以有效地找到随机实例的解，并且在求解效率上明显优于随机游走算法。在接近相变 阈值点时，由这两种算法得到的最优解仅使得极少数的约束无法满足。 关键词：约束满足问题；RB 模型；模拟退火算法；遗传算法 中图分类号：TP301.5 Two improved simulated annealing algorithms for solving constraint satisfaction problems with large domains 1 2 Yuan Zhiqiang , Zhao Chunyan (College of Science,