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

作     者：吴宇翔 王晓峰 于卓 谢志新 莫淳惠 曹泽轩 WU Yuxiang;WANG Xiaofeng;YU Zhuo;XIE Zhixin;MO Chunhui;CAO Zexuan

作者机构：北方民族大学计算机科学与工程学院宁夏银川750021 北方民族大学图像图形智能处理国家民委重点实验室宁夏银川750021 

出 版 物：《郑州大学学报（理学版）》 (Journal of Zhengzhou University:Natural Science Edition)

年 卷 期：2023年第55卷第4期

页      面：46-53页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：国家自然科学基金项目(62062001) 宁夏自然科学基金项目(2022AAC05040)。 

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

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