| 求解SAT问题的量子免疫克隆算法 |
| |
| 引用本文： | 李阳阳,焦李成.求解SAT问题的量子免疫克隆算法[J].计算机学报,2007,30(2):176-183. |
| |
| 作者姓名： | 李阳阳 焦李成 |
| |
| 作者单位： | 西安电子科技大学智能信息处理研究所 西安710071 |
| |
| 基金项目： | 国家自然科学基金
,
国家重点基础研究发展计划(973计划)
,
高等学校博士学科点专项科研项目 |
| |
| 摘 要： | 将量子计算应用于人工免疫系统中的克隆算子,提出了一种基于量子编码的免疫克隆算法(Quantum-Inspired Immune Clonal Algorithm,QICA)来求解SAT问题,并从理论上证明了算法的全局收敛性.算法中采用量子位的编码方式来表达种群中的抗体,针对这种编码方式采用量子旋转门和动态调整旋转角度策略对抗体进行演化,加速原有克隆算子的收敛;利用克隆算子的局部寻优能力强的特点,在各个子群体间采用量子交叉操作来增强信息交流,提高种群的多样性防止早熟.实验中,用标准SATLIB库中的3700个不同规模的标准SAT问题对QICA的性能作了全面的测试,并与单纯的量子遗传算法和简单免疫克隆算法以及著名的WalkSAT和PFEA2算法进行比较,仿真实验表明:QICA具有更高的成功率和运算效率.对于具有250个变量、1065个子句的SAT问题,QICA也仅用了1.357s,显示出了优越的性能.
|
| 关 键 词： | 量子编码 遗传算法 人工免疫系统 克隆算子 SAT问题 求解 问题 量子遗传算法 免疫克隆算法 Problem Algorithm 显示 子句 变量 运算效率 成功率 仿真实验 比较 测试 性能 规模 标准 信息交流 增强 交叉操作 |
| 修稿时间： | 2005-12-042006-09-15 |
Quantum-Inspired Immune Clonal Algorithm for SAT Problem |
| |
| LI Yang-Yang,JIAO Li-Cheng.Quantum-Inspired Immune Clonal Algorithm for SAT Problem[J].Chinese Journal of Computers,2007,30(2):176-183. |
| |
| Authors: | LI Yang-Yang JIAO Li-Cheng |
| |
| Abstract: | |
| |
| Keywords: | quantum bit genetic algorithm artificial immune system clonal operator SAT problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
