计算机应用研究2017，Vol.34Issue(12)：3611-3616,6.DOI:10.3969/j.issn.1001-3695.2017.12.021
两种改进的模拟退火算法求解大值域约束满足问题
Two improved simulated annealing algorithms for solving constraint satisfaction problems with large domains
摘要
Abstract
Phase transitions and solving algorithms of random constraint satisfaction problems have attracted special attention in the research of NP-complete problems.Model RB is a nontrivial random constraint satisfaction problem.Precisely speaking,model RB is a random CSP with exact satisfiability phase transition,and it is quite easy to generate hard instances.This paper proposed two improved simulated annealing algorithms (i.e.RSA and GSA) to solve the random instances of model RB with large domains.Numerical experiment results show that RSA and GSA algorithms can efficiently find solutions of the instances generated by model RB in the threshold region,and the two algorithms perform much better than random walk algorithm.Unfortunately,the algorithms fail to find solutions in the region that is very close to the satisfiability threshold.However,the optimal solution finally obtained only makes few of the constraints not be satisfied.关键词
约束满足问题/RB模型/模拟退火算法/遗传算法Key words
constraint satisfaction problems(CSP)/model RB/simulated annealing algorithm/genetic algorithm分类
信息技术与安全科学引用本文复制引用
原志强,赵春艳..两种改进的模拟退火算法求解大值域约束满足问题[J].计算机应用研究,2017,34(12):3611-3616,6.基金项目
国家自然科学基金资助项目(11301339,11491240108,11471215) （11301339,11491240108,11471215）
上海高校青年教师培养计划资助项目 （）
