首页> 中文期刊> 《郑州大学学报(理学版)》 >一种求解Max-SAT问题的快速模拟退火算法

一种求解Max-SAT问题的快速模拟退火算法

         

摘要

最大可满足性问题(Max-SAT)是经典的NP难问题,目标是寻找一组变元赋值使得满足子句个数最多。近年来,随着算例规模在实际应用中的逐渐增大,传统的启发式算法已不再适用。传统模拟退火算法在求解Max-SAT问题时会出现收敛速度慢、局部搜索能力弱,以及无效的盲目扰动等弊端,为此提出一种改进的快速模拟退火算法,针对初始赋值的随机性和盲目性,采用变元权值计算初始解,结合基于概率的随机扰动和选择扰动两种方式,并在Metropolis接受准则中添加记忆功能,用于搜索当前局部最优解,引入高低温两种降温模式,较大程度地提高算法的全局搜索能力,进而加快算法的收敛速度,有效减少求解时间。最后,在公开数据集和随机生成的数据集上进行仿真实验,结果表明,所提算法在求解Max-3-SAT问题上优于传统启发式算法。

著录项

相似文献

  • 中文文献
  • 外文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号