文件名称：论文研究-两种改进的模拟退火算法求解大值域约束满足问题.pdf
文件大小：1.55MB
文件格式：PDF
更新时间：2022-08-11 17:23:38
约束满足问题,RB模型,模拟退火算法,遗传算法
随机约束满足问题的相变现象及求解算法是NP-完全问题的研究热点。RB（revised B）模型是一个非平凡的随机约束满足问题，它具有精确的可满足性相变现象和极易产生难解实例这两个重要特征。针对RB模型这类具有大值域的随机约束满足问题，提出了两种基于模拟退火的改进算法即RSA（revised simulated annealing algorithm）和GSA（genetic-simulated annealing algorithm）。将这两种算法用于求解RB模型的随机实例，数值实验结果表明，在进入相变区域时，RSA和GSA依然可以有效地找到随机实例的解，并且在求解效率上明显优于随机游走算法。在接近相变阈值点时，由这两种算法得到的最优解仅使得极少数的约束无法满足。