求解Max-Re-SAT的离散混沌量子蝙蝠算法  

Discrete chaotic quantum bat algorithm for solution of Max-Re-SAT

作　　者：杨澜 王晓峰[2] 杨易 谢志新 赵星宇 庞立超 YANG Lan;WANG Xiaofeng;YANG Yi;XIE Zhixin;ZHAO Xingyu;PANG Lichao(School of Computer Science&Engineering,North Minzu University,Yinchuan 750021,China;The Key Laboratory of Images&Graphics Intelligent Processing of State Ethnic Affairs Commission(North Minzu University),Yinchuan 750021,China)

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

出　　处：《中国科技论文》2024年第5期591-599,共9页China Sciencepaper

基　　金：国家自然科学基金资助项目(62062001);宁夏回族自治区青年拔尖人才项目(2021)。

摘　　要：针对最大正则可满足性问题求解算法的研究空缺,以及提升求解最大可满足性问题的智能优化算法的精度,基于蝙蝠算法(bat algorithm,BA),提出了一种基于离散混沌量子的蝙蝠算法。在该算法中,将连续数值转化为离散的二进制编码,对算法进行了离散化处理。该研究运用量子理论、引入量子比特编码和启发式量子变异,通过量子旋转门改变非最优个体的概率振幅来实现变异,解决了早熟和收敛速度慢的问题。在位置更新中,使用混沌映射替代固定参数,增强了灵活性和多样性,提高了全局寻优能力和求解效率。实验结果表明:在随机正则可满足性问题实例产生模型产生的不同规模算例上,所提算法的求解精度远远高于传统启发式算法;同时,与获奖的求解器相比,也具有一定的竞争力,验证了该算法的有效性。As a possible countermeasure to the lack in algorithms for solving maximum regularization satisfiability problems as well as inadequate accuracy of intelligent optimization algorithms for solving maximum satisfiability problems,a discrete chaotic quantum based bat algorithm based on the bat algorithm(BA)was proposed herein.This algorithm was discretized by conversion of continuous values to discrete binary codes.By applying quantum theory,introducing quantum bit encoding and heuristic quantum mutation,the mutation is achieved by changing the probability amplitude of non optimal individuals through quantum rotation gates,solving the problems of precocity and slow convergence speed.In position update,chaotic mapping is used to replace fixed parameters,which enhances flexibility and diversity,and improves global optimization ability and solving efficiency.The experimental results show that the proposed algorithm has much higher accuracy than traditional heuristic algorithms in generating different scale examples in the stochastic regularization satisfiability problem instance generation model.At the same time,compared with the award-winning solver,it also has a certain level of competitiveness,verifying the effectiveness of the algorithm.

关 键 词：最大正则可满足性问题 二进制蝙蝠算法 量子比特编码 启发式量子变异 混沌映射 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]