量子免疫算法的改进及其在组合优化中的应用 第4页
The performance of the algorithm can be evaluated by using the optimal value and the convergence condition searched by algorithm. From Table 1, Figure 3 and Figure 4, superiority and inferiority of each algorithm performance can be drawn. Solving the 0-1 knapsack problems, the speed of Greedy algorithm is quicker, but significantly its global optimization ability is worse than quantum genetic algorithm and quantum immune algorithm. At the same time, from the table, the speed of global optimization of the quantum immune algorithm is obviously accelerated. However, due to adding of the operation in vaccination and immune selection, the average running time of the algorithm may be slightly longer than that of Quantum Genetic Algorithm.
6 Conclusion
The quantum immune algorithm, which is proposed by introducing the immune operators and vaccination into the quantum genetic algorithm, can effectively use priori knowledge of the problem and partial optimal solution to speed up the convergence of algorithm to the global optimum solution. It shows more outstanding performance than quantum genetic algorithm for solving 0-1 knapsack problems.
References
[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] Li Cheng，Li Fei，Improved quantum genetic algorithm and its application in FIR filter design.Computer Engineering and Applications[J]，2009，45（4）：239-241.
[6] Wang Lei，Pan Jin，Jiao Licheng，the Immune Algorithm[J].Chinese Joural of Electronics，2000，28（7），74-78
[7] Gao Yan，Wei Yaoguang，Fu Dongmei，Research of Artificial Genetic Algorithm and its Application in Function Optimization1 [J]Control and Information，2007，23（2），183-184
[8] Jiang Li，Wu Kun，A Research on the Applica tion of Greedy Algor ithm of
Solv ing 0-1’s Knapsack Problem[J]，Computer and Engineering,2007,6,32-34
Li Zhao-hua(1983-), male, Master，major in modern communication technology and intelligent signal processing.
Li Fei(1966-),female,Master Instructor, major in modern communication technology and intelligent signal processing, quantum information processing