量子协同免疫算法用于SAT问题的求解  

Quantum cooperative immune algorithm for SAT problems

作　　者：吴秋逸[1] 李阳阳[1] 焦李成[1] 

机构地区：[1]西安电子科技大学智能信息处理研究所和智能感知与图像理解教育部重点实验室,陕西西安710071

出　　处：《系统工程与电子技术》2009年第6期1441-1445,共5页Systems Engineering and Electronics

基　　金：国家高技术研究发展计划(863项目)(2006AA01Z107);国家重点基础研究发展规划(973项目)(2006CB705700);国家自然科学基金项目(60703108);陕西省自然科学基金项目(2007F32)资助课题

摘　　要：根据协同策略和量子免疫计算理论,提出一种求解SAT问题的量子协同免疫算法。该算法在将SAT问题转化为函数优化问题的基础上,采用多个子种群。分别采用量子比特编码来表达个体,采用通用的量子旋转门策略演化个体,采用量子交叉操作阻止早熟收敛;各种群独立演化,同时引入量子协同理论,采用协同算子使得算法的搜索效率更高。实验采用标准SATLAB库中的3 700个不同规模的问题对算法进行测试,并与简单克隆选择算法、量子遗传算法、量子免疫克隆选择算法进行比较。结果表明,量子协同免疫算法的平均成功率最高,平均运行时间和平均评价次数最少。A quantum cooperative immune algorithm for SAT problems is proposed, which is based on the synergism strategy and the principles of quantum-inspired immune computing. Based on converting the SAT problems into global problems, many subpopulations are adopted. Individuals in a population are represented by quantum bits （qubits）. In the individual＇s updating, the quantum rotation gate strategy and adjusting rotation angle mechanism are applied to accelerate convergence. By using the cooperative strategy, information among the subpopulation is exchanged and the diversity of population is improved. In experiments, 3 700 different benchmark SAT problems in SATLIB are used to test the performance of the quantum cooperative immune algorithm, moreover, the performance of QCIA is compared with the standard immune clonal selection algorithm （ICSA）, quantum genetic algorithm and quantum glonal selection algorithm. All experimental results show that the success ratio of QCIA is the highest and that the run time and number of function evaluations are the least among the three algorithms.

关 键 词：SAT问题 量子编码 人工免疫系统 协同理论 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]