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

摘要：

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

关键词：最大可满足性问题、模拟退火算法、Metropolis 接受准则、启发式算法

所属期刊栏目：55

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金;宁夏自然科学基金项目

在线出版日期：2023-05-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：46-53