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

作者：吴宇翔; 王晓峰^*; 于卓; 谢志新; 莫淳惠; 曹泽轩

来源：郑州大学学报(理学版）, 2023, 55(04): 46-53.

DOI：10.13705/j.issn.1671-6841.2022158

• 最大可满足性问题
• 模拟退火算法
• Metropolis接受准则
• 启发式算法

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

• 单位
  北方民族大学