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

摘要：

对于随机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算法能有效解决规则可满足问题.

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

所属期刊栏目：45

分类号：TN911.1-34

资助基金：国家自然科学基金;北方民族大学重大专项;宁夏自然科学基金项目;宁夏自然科学基金项目;宁夏自然科学基金项目;宁夏自然科学基金项目;北方民族大学校级科研一般项目

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

页数：共7页

页码：122-128