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

Quantum-Inspired Immune Clonal Algorithm for SAT Problem

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

This paper proposes a new immune clonal algorithm, called a quantum-inspired immune clonal algorithm （QICA）, which is based on the concept and principles of quantum computing, to deal with SAT problem, and proves its global convergence in theory. In the algorithm, individuals in a population are represented by quantum bits（qubits）. In the individualrs updating, the quantum rotation gate strategy and dynamic adjusting rotation angle mechanism are applied to accelerate convergence. By using clonal operator in artificial immune system （AIS）, information among the subpopulation is exchanged by adopting the quantum crossover operation for improvement of diversity of the population and avoiding prematurity. In experiments, QICA is tested on SAT problem, and compared with other algorithms. The results indicated that QICA performs much better than the four other algorithms both in the quality of solution and in the computational cost.