两种改进的模拟退火算法求解大值域约束满足问题
发布时间：2019-06-20 03:53
【摘要】：随机约束满足问题的相变现象及求解算法是NP-完全问题的研究热点。RB(revised B)模型是一个非平凡的随机约束满足问题,它具有精确的可满足性相变现象和极易产生难解实例这两个重要特征。针对RB模型这类具有大值域的随机约束满足问题,提出了两种基于模拟退火的改进算法即RSA(revised simulated annealing algorithm)和GSA(genetic-simulated annealing algorithm)。将这两种算法用于求解RB模型的随机实例,数值实验结果表明,在进入相变区域时,RSA和GSA依然可以有效地找到随机实例的解,并且在求解效率上明显优于随机游走算法。在接近相变阈值点时,由这两种算法得到的最优解仅使得极少数的约束无法满足。
[Abstract]:The phase transition phenomenon and algorithm of stochastic constraint satisfaction problem are the research hotspots of NP- complete problem. RB (revised B) model is a non-trivial stochastic constraint satisfaction problem, which has two important characteristics: accurate satisfied phase transition phenomenon and easy to produce difficult examples. In order to solve the problem of satisfying stochastic constraints with large range, such as RB model, two improved algorithms based on simulated annealing, RSA (revised simulated annealing algorithm) and GSA (genetic-simulated annealing algorithm).), are proposed. The two algorithms are used to solve the random examples of RB model. The numerical experimental results show that RSA and GSA can still find the solution of random examples effectively when they enter the phase transition region, and the efficiency of the solution is obviously better than that of random walk algorithm. When the threshold point of phase transition is close to the threshold point of phase transition, the optimal solution obtained by these two algorithms makes only a very small number of constraints unsatisfied.
【作者单位】： 上海理工大学理学院;
【基金】：国家自然科学基金资助项目(11301339,11491240108,11471215) 上海高校青年教师培养计划资助项目
【分类号】：TP18
[Abstract]:The phase transition phenomenon and algorithm of stochastic constraint satisfaction problem are the research hotspots of NP- complete problem. RB (revised B) model is a non-trivial stochastic constraint satisfaction problem, which has two important characteristics: accurate satisfied phase transition phenomenon and easy to produce difficult examples. In order to solve the problem of satisfying stochastic constraints with large range, such as RB model, two improved algorithms based on simulated annealing, RSA (revised simulated annealing algorithm) and GSA (genetic-simulated annealing algorithm).), are proposed. The two algorithms are used to solve the random examples of RB model. The numerical experimental results show that RSA and GSA can still find the solution of random examples effectively when they enter the phase transition region, and the efficiency of the solution is obviously better than that of random walk algorithm. When the threshold point of phase transition is close to the threshold point of phase transition, the optimal solution obtained by these two algorithms makes only a very small number of constraints unsatisfied.
【作者单位】： 上海理工大学理学院;
【基金】：国家自然科学基金资助项目(11301339,11491240108,11471215) 上海高校青年教师培养计划资助项目
【分类号】：TP18
【相似文献】
相关期刊论文 前10条
1 刘彦秀;姜华;潘全科;;基于全局和声搜索的模拟退火算法改进[J];计算机工程与科学;2010年11期
2 谢玉珑,王继红,俞汝勤;通用模拟退火用于稳健多元分析校正[J];高等学校化学学报;1993年02期
3 李洪瑞;基于模拟退火算法的多目标数据关联[J];情报指挥控制系统与仿真技术;1998年10期
4 郭茂祖,姜俊峰,李静梅;模拟退火算法中冷却调度选取方法的研究[J];计算机工程;2000年09期
5 钟太勇;许小勇;;模拟退火算法求算一维非线性方程的根[J];郧阳师范高等专科学校学报;2006年06期
6 郑玉|，
本文编号：2502900
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/2502900.html
