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

摘要

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