作者:原志强; 赵春艳约束满足问题rb模型模拟退火算法遗传算法
摘要:随机约束满足问题的相变现象及求解算法是NP-完全问题的研究热点。RB(revisedB)模型是一个非平凡的随机约束满足问题,它具有精确的可满足性相变现象和极易产生难解实例这两个重要特征。针对RB模型这类具有大值域的随机约束满足问题,提出了两种基于模拟退火的改进算法即RSA(revisedsimulatedannealingalgorithm)和GSA(genetic-simulatedannealingalgorithm)。将这两种算法用于求解RB模型的随机实例,数值实验结果表明,在进入相变区域时,RSA和GSA依然可以有效地找到随机实例的解,并且在求解效率上明显优于随机游走算法。在接近相变阈值点时,由这两种算法得到的最优解仅使得极少数的约束无法满足。
注:因版权方要求,不能公开全文,如需全文,请咨询杂志社