改进的模拟退火算法求解规则可满足性问题

作者：张九龙; 王晓峰; 芦磊; 牛鹏飞; 程亚南

来源：现代电子技术, 2022, 45(05): 122-128.

DOI：10.16652/j.issn.1004-373x.2022.05.021

• 模拟退火算法
• 规则可满足问题
• 随机正则(k,d)-SAT
• 启发式策略
• 随机3-SAT问题
• Metropolis接受准则
• 规则可满足性实例生成模型

对于随机k-SAT问题，限定每个变元出现的次数恰好出现d次，形成随机规则(k,d)-SAT问题，目前国内外对该问题的相关研究较少，且研究随机规则(k,d)-SAT问题比研究k-SAT问题更为具体。文中给出一种随机规则(k,d)-SAT问题的生成实例模型——RRIG(N,k,d)模型，并用改进的模拟退火算法SARSAT求解规则随机规则(k,d)-SAT问题。将变元出现次数d加入到扰动策略中，利用变元出现次数和子句间约束关系中的启发信息对候选解中的赋值选择性改动，加快算法收敛至较优解的速度；同时，模拟退火算法中的Metropolis接受准则和改进后的退火策略保证了算法能够有效跳出局部最优解，最后使用RRIG(N,k,d)模型生成不同参数的测试实例，并与其他相关算法进行比较，结果表明SARSAT算法能有效解决规则可满足问题。

• 出版日期2022
• 单位北方民族大学