量子免疫算法的改进及在组合优化问题中的应用
摘要：本文将免疫算法的免疫算子思想引入到量子遗传算法中，提出了改进的算法：量子免疫算法。算法在保持量子遗传算法优点的同时，提高了算法的全局收敛性。并将此算法应用在经典组合优化问题中，仿真结果表明，此改进算法具有良好的性能。
关键字：量子免疫算法；量子遗传算法；组合优化；贪婪算法
The Improvement Quantum Immune Algorithm and It’s Application
on Combinatorial Optimization
Li Zhao-hua, Li Fei
College of Communication & Information Engineering，Nanjing University of Posts and Telecommunications，Nanjing 210003，China
Abstract: this paper introduces a new improved algorithm: the quantum immune algorithm, which combine the immune algorithm with the quantum genetic algorithm. It get a shorter global convergence time. And it shows a good performance while applying in the Combinatorial Optimization.
Key words: quantum immune algorithm; quantum genetic algorithm; Combinatorial Optimization; greed algorithm
1 引言
量子遗传算法是量子计算理论和遗传算法结合的产物，具有较好的种群多样性和收敛性，但对于问题中给出的信息，往往无法直接反映在算法迭代过程中，将人工免疫中的疫苗接种思想引入到量子遗传算法中，提出量子免疫算法（Quantum Immune Algorithm,QIA），可以较好的解决这个问题。背包问题(Knapsack problem)是一种组合优化的经典问题[1]。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题有着广泛的应用背景，如预算控制，项目选择，材料切割，货物装载等[2]。解决方法一般采用贪婪算法或动态规划算法，但前者无法取得全局最优解，后者的运算量太大。本文尝试使用量子免疫算法来解决此问题。
2 量子免疫算法
2.1 量子遗传算法
遗传算法（Genetic Algorithm，GA）是在模拟达尔文的进化论和孟德尔的遗传学理论的基础上，产生和发展起来的一种优化问题求解的随机优化方法。算法仅用目标函数在概率准则引导下进行并行全局自适应搜索，就能够处理许多传统优化方法难以解决的复杂问题，因此在许多优化领域得到了广泛应用并成为跨学科研究的热点。
量子遗传算法（Quantum Genetic Algorithm，QGA）是量子计算理论和遗传算法原理相结合的产物。算法以量子计算原理为基础，将量子比特的几率幅表示应用于染色体的编码，使得一条染色体可以表达多个态的叠加，算法过程中执行量子交叉可以充分利用所有染色体的信息，产生更多的新个体，量子变异可以阻止未成熟收敛和提高算法全局搜索能力，利用量子旋转门操作实现种群染色体的更新来搜索最优解，该算法比 GA 具有更好的种群多样性和收敛性，因而QGA 具有种群规模小、寻优能力强、收敛速度快和计算时间短的特点[3][4]。
在量子信息理论中，信息的载体不再是经典的比特而是量子比特，它可以处于 0、1 两个本征态的任意叠加态，其状态可以表示为 ，其中 表示相应状态出现的概率， 分别表示量子比特处于状态 0 和 1 的概率，并且满足 。其算法流程如下[5]：
（1）初始化种群 ；
（2）对种群 进行测量得到一组确定的状态 ；
（3）对 中的个体进行适应度评估；
（4）记录最佳适应度值和对应个体作为下一步种群更新目标值参考；
（5）While 不满足停止条件 do
①对种群进行一次测量，得到状态 并进行适应度函数评估；
②记录目前最佳适应度值和个体，同前次已记录的参数比较，取最优者作为下一次种群更新的目标。
③按照一定的策略对种群进行交叉和变异，利用量子旋转门进行对种群进行更新，得到子代
End;
2.2 量子免疫算法
遗传算法与量子遗传算法都是根据适应度函数优劣作为种群演化的唯一标准，无法使用待求问题的其他先验知识，同时，最优个体仅仅作为种群演化的目标，没有充分利用最优个体每个基因位的信息。因此，将免疫算法的免疫算子引入到量子遗传算法中，提出量子免疫算法，可以充分利用问题的先验知识，以及迭代中产生的最优个体，加快算法的收敛速度与搜索最优解的能力。
算法的运行框架如下图所示：
图1 量子免疫算法运行框图
（1）获取疫苗：1125