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

针对最大正则可满足性问题求解算法的研究空缺,以及提升求解最大可满足性问题的智能优化算法的精度,基于蝙蝠算法(bat algorithm,BA),提出了一种基于离散混沌量子的蝙蝠算法。在该算法中,将连续数值转化为离散的二进制编码,对算法进行了离散化处理。该研究运用量子理论、引入量子比特编码和启发式量子变异,通过量子旋转门改变非最优个体的概率振幅来实现变异,解决了早熟和收敛速度慢的问题。在位置更新中,使用混沌映射替代固定参数,增强了灵活性和多样性,提高了全局寻优能力和求解效率。实验结果表明:在随机正则可满足性问题实例产生模型产生的不同规模算例上,所提算法的求解精度远远高于传统启发式算法;同时,与获奖的求解器相比,也具有一定的竞争力,验证了该算法的有效性。

求解SAT问题的量子免疫克隆算法

将量子计算应用于人工免疫系统中的克隆算子,提出了一种基于量子编码的免疫克隆算法(Quantum-InspiredImmuneClonalAlgorithm,QICA)来求解SAT问题,并从理论上证明了算法的全局收敛性.算法中采用量子位的编码方式来表达种群中的抗体,针对这种编码方式采用量子旋转门和动态调整旋转角度策略对抗体进行演化,加速原有克隆算子的收敛;利用克隆算子的局部寻优能力强的特点,在各个子群体间采用量子交叉操作来增强信息交流,提高种群的多样性防止早熟.实验中,用标准SATLIB库中的3700个不同规模的标准SAT问题对QICA的性能作了全面的测试,并与单纯的量子遗传算法和简单免疫克隆算法以及著名的WalkSAT和PFEA2算法进行比较,仿真实验表明:QICA具有更高的成功率和运算效率.对于具有250个变量、1065个子句的SAT问题,QICA也仅用了1.357s,显示出了优越的性能.