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

Improved simulated annealing algorithm for regular satisfiability problem

作　　者：张九龙 王晓峰[1,2] 芦磊 牛鹏飞 程亚南 ZHANG Jiulong;WANG Xiaofeng;LU Lei;NIU Pengfei;CHENG Yanan(School of Computer Science and Engineering,North Minzu University,Yinchuan 750021,China;The Key Laboratory of Images and Graphics Intelligent Processing of State Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China)

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

出　　处：《现代电子技术》2022年第5期122-128,共7页Modern Electronics Technique

基　　金：国家自然科学基金资助项目(62062001);北方民族大学重大专项资助(ZDZX201901);宁夏自然科学基金项目(2020AAC03214,2020AAC03219,2019AAC03120,2019AAC03119);北方民族大学校级科研一般项目(2019XYZJK05)。

摘　　要：对于随机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算法能有效解决规则可满足问题。As for the stochastic k-SAT problem,the number of occurrences of each argument is limited to exactly d,forming the stochastic regular( k,d)-SAT problem. At present,there are few domestic and foreign researches on this problem,and the study on the stochastic regular( k,d)-SAT problem is more specific than the study on the k-SAT problem. In this paper,an example model of stochastic regular( k,d)-SAT problem is presented,namely RRIG( N,k,d) model,and an improved simulated annealing algorithm(SARSAT)is used to solve the stochastic regular( k,d)-SAT problem. By adding the occurrence times of arguments d into the perturbation strategy,the heuristic information of the occurrence times of arguments and the constraint relationship between clauses is used to change the assignment selectivity of the candidate solutions, so as to accelerate the algorithm′s convergence speed to a better solution. The Metropolis acceptance criteria and the improved annealing strategy in the simulated annealing algorithm ensure that the algorithm can effectively jump out of the local optimal solution.Finally,RRIG( N,k,d) model is used to generate test instances with different parameters and is compared with other related algorithms. The results show that the SARSAT algorithm can effectively solve the regular satisfiability problem.

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

分 类 号：TN911.1-34[电子电信—通信与信息系统]