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

• 作者: 李阳阳 焦李成
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 量子编码 遗传算法 人工免疫系统 克隆算子 SAT问题
• 年，卷（期）: 2007,（2）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 176-183
• 页数: 8页
• 分类号: TP3
• 字数: 7778字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2007.02.003

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	焦李成	西安电子科技大学智能信息处理研究所	514	14586	52.0	103.0
2	李阳阳	西安电子科技大学智能信息处理研究所	21	248	9.0	15.0