量子免疫算法的改进及在组合优化问题中的应用 第3页
交叉，量子变异概率为0.15，疫苗浓度 设为0.4。
5.2 仿真结果
对每组数据，使用贪婪算法，量子遗传算法，量子免疫算法各独立运行50次，统计运行结果如下表所示：
测试使用数据 算法 搜索最优值 算法平均运行时间 平均收敛代数
第一组数据 贪婪算法 351 0.005316 无
QGA算法 369 0.643356 240.8
QIA算法 369 0.649120 152.4
第二组数据 贪婪算法 763 0.005513 无
QGA算法 816 0.653031 260.6
QIA算法 816 0.674332 192.2
表1 三种算法仿真结果
图3 0-1背包第一组数据仿真结果
图4 0-1背包第二组数据仿真结果
各算法的性能可以用算法搜索到的最优值和收敛状况来评价，从表1和图3图4中可以得出各算法性能的优劣。贪婪算法在解决0-1背包问题中，运算速度较快，但其全局寻优能力明显低于量子遗传算法和量子免疫算法。同时，从表中也可以看出，量子免疫算法，全局寻优速度明显加快。但由于其增加了接种疫苗操作和免疫选择操作，算法平均运行时间要稍长于量子遗传算法。
6 结论
将免疫算法的免疫算子和疫苗接种引入到量子遗传算法中，提出了量子免疫算法，可以有效地利用问题的先验知识和迭代中产生的局部最优解信息，加快算法想全局最优解收敛的速度，在求解0-1背包问题中表现出了较量子遗传算法更加优异的性能。
参考文献
[1] Thomas H Cormen,Charles E Leiserson. Introduction to Algorithms[M] .The MIT Press, 2002
[2] Grosan,Crina. Improving the performance of evolutionary algorithms for the multiobjective 0/1 knapsack problem using dominance[M].Institute of Electrical and Elec-tronics Engineers Inc, 2004.
[3] Narayanna A, Moore M, Quantum-inspired Genetic Algorithms[C], Proceedings of IEEE International Conference on Evolutional Evolution,1996,61-66
[4] Han K.-H., Kim J.-H, Genetic Quantum Algorithm and its Application to Combinatorial Optimization[C], Proceedings of the 2000 IEEE Congress on Evolutionary Computation, 2000,1354-1360
[5] 李成，李飞，改进量子遗传算法及其在FIR滤波器设计中的应用[J],计算机工程与应用，2009，45（4），239-241
[6] 王磊，潘进，焦李成，免疫算法[J].电子学报，2000，28（7），74-78
[7] 高岩，位耀光，付冬梅等，免疫遗传算法的研究及其在函数优化中的应用[J].微计算机信息，2007，23（2），183-184
[8] 蒋力，武坤，0-1背包问题贪婪算法应用研究[J]，计算机与数字工 程,2007,6,32-34
作者介绍：
李兆华(1983－)，男，硕士研究生，主要研究领域为现代通信中的智能信号处理技术。
李飞(1966－)，女，教授，硕士生导师，主要研究领域为现代通信中的智能信号处理技术，量子信息处理技术。