A novel quantum-inspired pseudorandom proportional evolutionary algorithm for the multidimensional knapsack problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A novel quantum-inspired pseudorandom proportional evolutionary algorithm for the multidimensional knapsack problem

Full text

Pdf (717 KB)

Source

ACM/SIGEVO Summit on Genetic and Evolutionary Computation archive
Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation table of contents

Shanghai, China

SESSION: Full papers table of contents

Pages 545-552

Year of Publication: 2009

ISBN:978-1-60558-326-6

Authors

Ling Wang	School of Mechatronics and Automation, Shanghai University, Shanghai, China, Shanghai, China
Xiuting Wang	School of Mechatronics and Automation, Shanghai University, Shanghai, China, Shanghai, China
Minrui Fei	School of Mechatronics and Automation, Shanghai University, Shanghai, China, Shanghai, China

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 37, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1543834.1543908 What is a DOI?

ABSTRACT

This paper proposes a novel quantum-inspired pseudorandom proportional evolutionary algorithm (QPPEA), whose core is that the pseudorandom proportional operation is introduced in the update strategy. As the traditional quantum evolutionary algorithm (QEA) generates the binary solution completely depending on the probability and the amplitude of rotation angel is small, the efficiency of QEA is low. To make up for it, pseudorandom proportional operation inspired by ant colony algorithm is introduced in QPPEA. Further more, for the sake of the introduction of pseudorandom proportional operation, quantum mutation operator based on quantum NOT gate is used to keep the diversity of population. The simulation results on a class of the multidimensional knapsack problems (MKP) demonstrate that QPPEA can effectively enhance the searching efficiency and improve the optimization performance.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Kuk-Hyun Han and Jong-Hwan Kim. 2002. Quantum--Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization. Evolutionary Computation, IEEE Transactions on. 6, 6 (Dec. 2002), 580--593.
	2	Kuk-Hyun Han, and Jong-Hwan Kim. 2004. Quantum-Inspired Evolutionary Algorithms with a New Termination Criterion, H_Gate, and Two-Phase Scheme. IEEE Transactions on Evolutionary Computation. 8, 2 (Apr. 2004), 156--169.
	3	Fraser, A. S. 1957. Simulation of genetic systems by automatic digital computers. Aust. J. Biol. Sci., 10, (1957), 484--491.
	4	Paul B. 1980. The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. Journal of Statistical Physics. V22, 5 (May. 1980), 563--591.
	5	Li, B. B., Wang, L. 2007. A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling Source: IEEE Transactions on Systems Man and Cybernetics. 37, 3 (Jun. 2007), 576--591.
	6	Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.212-219, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237866]
	7	P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, Proceedings of the 35th Annual Symposium on Foundations of Computer Science, p.124-134, November 20-22, 1994 [doi>10.1109/SFCS.1994.365700]
	8	Kuk-Hyun Han, Jong-Hwan Kim. 2006. Evolutionary Computation, 2006. CEC 2006. IEEE Congress on. 16-21 (July. 2006), 2622--2629.
	9	Luo, Z. Y., Wang, P., Li, Y. G., et al. 2008. Quantum-inspired evolutionary tuning of SVM parameters. Progress in Natural Science. 18, 4 (2008), 475--480.
	10	Pan-chi, L., Shi-yong, L. 2008. Quantum ant colony algorithm for continuous space optimization. Control Theory & Applications, 2008.
	11	Xiaoming You , Sheng Liu , Dianxun Shuai, On Improved Parallel Immune Quantum Evolutionary Algorithm Based on Learning Mechanism, Proceedings of the Sixth International Conference on Intelligent Systems Design and Applications, p.908-913, October 16-18, 2006 [doi>10.1109/ISDA.2006.209]
	12	Rolf Landauer, Information is inevitably physical, Feynman and computation: exploring the limits of computers, Perseus Books, Cambridge, MA, 1999
	13	Hey, T. 1999. Quantum computing: an introduction; Computing & Control Engineering Journal. 10, 3 (June. 1999), 105 -- 112.
	14	Kuk-Hyun Han, Jong-Hwan Kim, 2000. Genetic quantum algorithm and its application to combinatorial optimization problem. Evolutionary Computation, 2000. Proceedings of the 2000 Congress on. 2, 16--19 (July, 2000), 1354--1360.
	15	Birattari, M., Pellegrini, P., Dorigo, M. 2007. On the Invariance of Ant Colony Optimization. Evolutionary Computation, IEEE Transactions on. 11, 6 (Dec. 2007), 732 -- 742.
	16	Vittorio Maniezzo, Luca Maria Gambardella, Fabio de Luigi. Ant Colony Optimization. 2004.
	17	Min Kong , Peng Tian , Yucheng Kao, A new ant colony optimization algorithm for the multidimensional Knapsack problem, Computers and Operations Research, v.35 n.8, p.2672-2683, August, 2008 [doi>10.1016/j.cor.2006.12.029]
	18	Anne L. Oken. 1994. Penalty Functions and the Knapsack Problem, Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence, Proceedings of the First IEEE Conference on, Orlando, FL, USA, (June, 1994), 554--558.
	19	Hasan Pirkul. 1987. A Heuristic Solution Procedure for the Multiconstraint Zero-One Knapsack Problem. Naval Research Logistics. (1987), 161--172.
	20	Wang, L., Tang, F., Wu, H. 2005. Hybrid genetic algorithm based on quantum computing for numerical optimization and parameter estimation. Applied Mathematics and Computation. 171, 2 (Dec. 2005), 1141--1156.