A Quantum-Inspired Evolutionary Algorithm Based on P systems for Knapsack Problem

• Autorzy: Zhang G-X. , Gheorghe M. , Wu C-Z.
• Języki publikacji: EN

Abstrakty

EN

This paper introduces an evolutionary algorithm which uses the concepts and principles of the quantum-inspired evolutionary approach and the hierarchical arrangement of the compartments of a P system. The P system framework is also used to formally specify this evolutionary algorithm. Extensive experiments are conducted on a well-known combinatorial optimization problem, the knapsack problem, to test the effectiveness of the approach. These experimental results show that this evolutionary algorithm performs better than quantum-inspired evolutionary algorithms, for certain arrangements of the compartments of the P system structure utilized.

Słowa kluczowe

EN

quantum-inspired evolutionary algorithm; P systems; knapsack problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 87, nr 1
• Strony: 93--116
• Opis fizyczny: bibliogr. 24 poz., tab., wykr.

Twórcy

autor

Zhang G-X.

autor

Gheorghe M.

autor

Wu C-Z.

• School of Electrical Engineering, Southwest Jiaotong University Chengdu, Sichum, 610031, P.R. China,

Bibliografia

• [1] Bäck, T., Hammel, U., Schwefel, H.-P.: Evolutionary computation: comments on the history and current state, IEEE Transactions on Evolutionary Computation, 1(1), 1997, 3-17.
• [2] Ciobanu, G.: Distributed algorithms over communicating membrane systems, BioSystems, 70(2), 2003, 123-133.
• [3] Garey, M. R., Johnson, D. S.: Computers and intractability: a guide to the theory of NP-completeness, W. H. Freeman & Co. New York, NY, USA, 1979.
• [4] Han, K. H., Kim, J. H.: Genetic quantum algorithm and its application to combinatorial optimization problem, Proc. of the 2000 IEEE Congress on Evolutionary Computation, 2000, 1354-1360.
• [5] Han, K. H., Kim, J. H.: Quantum-inspired evolutionary algorithm for a class of combinatorial optimization, IEEE Trans. Evolutionary Computation, 6(6), 2002, 580-593.
• [6] Huang, L., He, X.-X.,Wang, N., Xie, Y.: P systems based multi-objective optimization algorithm, Progress in Natural Science, 17(4), 2007, 458-465.
• [7] Huang, L., Wang, N.: An optimization algorithm inspired by membrane computing, Proc. Second International Conference on Advances in Natural Computation (L. Jiao, L.Wang, X. Gao, J. Liu, F.Wu, Eds.), LNCS 4222, Springer-Verlag, Berlin, 2006, 49-52.
• [8] Leporati, A., Pagani, D.: A membrane algorithm for the min storage problem, Proc. Workshop on Membrane Computing (H. J. Hoogeboom, Gh. Păun, G. Rozenberg, A. Salomaa, Eds.), LNCS 4361, Springer-Verlag, Berlin, 2006, 443-462.
• [9] Li, B., Zhuang, Z. Q.: Genetic algorithm based on quantum probability representation, Proc. of the Third International Conference on IntelligentData Engineering and Automated Learning (H. Yin et al., Eds.), LNCS 2412, Springer-Verlag, Berlin, 2002, pp. 500-505.
• [10] Moore, M., Narayanan, A.: Quantum-Inspired Computing, Department of Computer Science, University of Exeter, Exeter, U.K., 1995.
• [11] Narayanan, A., Moore, M.: Quantum-inspired genetic algorithm, Proc. IEEE International Conference on Evolutionary Computation, Nagoya, Japan, 1996, 61-66.
• [12] Nishida, T. Y.: An approximate algorithm for NP-complete optimization problems exploiting P systems, Proc. First Brainstorming Workshop on Uncertainty in Membrane Computing, Palma de Mallorca, Spain, 2004, 185-192.
• [13] Nishida, T. Y.: Membrane algorithms: approximate algorithms for NP-complete optimization problems, Applications of membrane computing (G. Ciobanu, Gh. Păun, M.J. Pérez-Jiménez, Eds.), Springer-Verlag, Berlin, 2006, 303-314.
• [14] Nishida, T. Y.: Membrane Algorithms, Proc. Workshop on Membrane Computing (R. Freund, Gh. Păun, G. Rozenberg, A. Salomaa, Eds.) LNCS 3850, Springer-Verlag, Berlin, 2006, 55-66.
• [15] Pan, L. Q., Martin-Vide, C.: Solving multidimensional 0-1 knapsack problem by P systems with input and active membranes, Journal of Parallel Distributed Computing, 65(12), 2005, 1578-1584.
• [16] Păun, Gh.: Computing with membranes, Journal of Computer and System Sciences, 61(1), 2000, 108-143.
• [17] Păun, Gh.: P systems with active membranes: attacking NP-complete problems, Journal of Automata, Language and Combinatorics, 6(1), 2001, 75-90.
• [18] Păun, Gh.: Further twenty-six open problems in membrane computing, Proc. 3rd Brainstorming Meeting on Membrane Computing, Sevilla, Spain, 2005, 249-262.
• [19] Păun, Gh., Rozenberg, G.: A guide to membrane computing, Theor. Comput. Sci., 287(1), 2002, 73-100.
• [20] Pérez-Jiménez, M. J., Romero-Jiménez, A. R., Sancho-Caparrini, F.: Computationally hard problems addressed through P systems, G. Ciobanu, G. Păun, Applications of membrane computing (G. Ciobanu, M. J. Pérez-Jiménez, Gh. Păun, Eds.), Springer-Verlag, Berlin, 2006, 315-346.
• [21] Srinivas, M., Patnaik, L. M.: Genetic algorithms: a survey, IEEE Computer, 27(6), 1994, 17-26.
• [22] Zaharie, D., Ciobanu, G.: Distributed evolutionary algorithms inspired by membranes in solving continuous optimization problems, Proc.Workshop onMembrane Computing (H. J. Hoogeboom,Gh. Păun, G. Rozenberg, A. Salomaa, Eds.), LNCS 4361, Springer-Verlag, Berlin, 2006, 536-553.
• [23] Zhang, G. X., Hu, L. Z., Jin, W. D.: Resemblance coefficient and a quantum genetic algorithm for feature selection, Proc. 7th International Conference on Discovery Science (E. Suzuki, S. Arikawa, Eds.), LNAI 3245, Springer-Verlag, Berlin, 2004, 155-168.
• [24] Zhang, G. X., Rong, H. N.: Real-observation quantum-inspired evolutionary algorithm for a class of numerical optimization problems, Proc. International Conference on Computational Science (Y. Shi, G. D. van Albada, J. Dongarra, P. M. A. Sloot, Eds.), LNCS 4490, Springer-Verlag, Berlin, 2007, 989-996