QEAM: An Approximate Algorithm Using P Systems with Active Membranes

Authors

  • Gexiang Zhang School of Electrical Engineering, Southwest Jiaotong University Chengdu, 610031, P.R. China
  • Jixiang Cheng School of Electrical Engineering, Southwest Jiaotong University Chengdu, 610031, P.R. China
  • Marian Gheorghe Faculty of Engineering and Informatics, University of Bradford, Bradford, West Yorkshire BD7 1DP, UK,
  • Florentin Ipate Faculty of Mathematics and Computer Science, University of Bucharest Academiei 14, Bucharest, Romania
  • Xueyuan Wang School of Information Engineering Southwest University of Science and Technology MianYang 621010, P.R.China

Keywords:

Membrane computing, active membranes, approximate optimization approach, quantum-inspired evolutionary algorithm, satisfiability problemThis paper proposes an approximate optimization approach, called QEAM, which combines a P system with active membranes

Abstract

This paper proposes an approximate optimization approach, called QEAM, which combines a P system with active membranes and a quantum-inspired evolutionary algorithm. QEAM uses the hierarchical arrangement of the compartments and developmental rules of a P system with active membranes, and the objects consisting of quantum-inspired bit individuals, a probabilistic observation and the evolutionary rules designed with quantum-inspired gates to specify the membrane algorithms. A large number of experiments carried out on benchmark instances of satisfiability problem show that QEAM outperforms QEPS (quantum-inspired evolutionary algorithm based on P systems) and its counterpart quantum-inspired evolutionary algorithm.

References

Alhazov, A.; Martin-Vide, C.; Pan, L.Q. (2003); Solving a PSPACE- complete problem by recognizing P systems with restricted active membranes, Fund Inform, ISSN 0169-2968, (2): 67-77.

Bonissone, P.P.; Subbu, R.; Eklund, N.; Kiehl, T.R. (2006); Evolutionary algorithms + domain knowledge = real-world evolutionary computation, IEEE T Evolut Comput, ISSN 1089-778X, 10(3):256-280.

Cheng, J.; Zhang, G.; Zeng, X.(2011); A novel membrane algorithm based on differential evolution for numerical optimization, Int J Unconv Comput, ISSN 1548-7199, 7(3):159-183.

Cook, S. (1971); The complexity of theorem-proving procedures, Proc. of STOC, 151-158.

Folino, G.; Pizzuti, C.; Spezzano, G. (2001); Parallel hybrid method for SAT that couples genetic algorithms and local search, IEEE T Evolut Comput, ISSN 1089-778X, 5(4):323-334.

Garcia, S.; Molina, D.; Lozano, M.; Herrera, F.(2009); A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC 2005 special session on real parameter optimization, J Heuristics, ISSN 1381-1231, 15(6):617-644.

Gheorghe, M.; Păun, Gh.; Prez-Jimenez, M.J.; Rozenberg, G. (2013); Frontiers of membrane computing: Open problems and research topics, Int J Found Comput Sci, ISSN 129-0541, 24(5):547-623.

Glover, F.; Taillard, E.; Werra de, D. (1993); A users guide to tabu search, Ann Oper Res, ISSN 0254-5330, 41(1):3-28.

Gottlieb, J.; Marchiori, E.; Rossi, C. (2002); Evolutionary algorithms for the satisfiability problem, Evolut Comput, ISSN 1063-6560, 10(1):35-50.

Han, K.H.; Kim, J.H.(2002); Quantum-inspired evolutionary algorithm for a class of combinatorial optimization, IEEE T Evolut Comput, ISSN 1089-778X, 6(6):580-593.

Huang, L.; Suh, I.H.; Abraham, A.(2011), Dynamic multi-objective optimization based on membrane computing for control of time-varying unstable plants, Inform Sciences, ISSN 0020-0255, 181(11): 2370-2391.

Hwang, G.J.; Yin, P.Y.; Yeh, S.H.(2006); A tabu search approach to generating test sheets for multiple assessment criteria, IEEE T Educ, ISSN 0018-9359, 49(1):88-97.

Leporati, A.; Pagani, D. (2006); A membrane algorithm for the min storage problem, Lect Notes Comput Sci, ISSN 0302-9743, 4361:443-462.

Moore, M.; Narayanan, A. (1995); Quantum-inspired computing. Tech. rep., Department of Computer Science, University Exeter, Exeter, U.K.

Narayanan, A.; Moore, M. (1996); Quantum-inspired genetic algorithms, Proc of IEEE CEC, 61-66.

Nishida, T.Y.(1996); Membrane algorithm with brownian subalgorithm and genetic subalgorithm. Int J Found Comput Sci, ISSN 129-0541, 18(6):1353-1360.

Pan, L.Q., Alhazov, A., Ishdorj, T.O. (2005); Further remarks on P systems with active membranes, separation, merging, and release rules. Soft Comput, ISSN 1432-7643, 9(9):686-690.

Pan, L.Q.; Martín-Vide, C. (2005); Solving multidimensional 0-1 knapsack problem by P systems with input and active membranes, J Parallel Distr Comput, ISSN 0743-7315, 65(12):1578-1584.

Păun, Gh. (2000); Computing with membranes, J Comput Syst Sci, ISSN 0022-0000, 61(1):108-143.

Păun, Gh. (2001); P systems with active membranes: attacking NP-complete problems. J Automata Lang Comb, ISSN 1430-189X, 6(1):75-90.

Păun, Gh. (2007); Tracing some open problems in membrane computing. Rom J Inf Sci Tech, ISSN 1453-8245, 10(4):303-314.

Păun, Gh.; Rozenberg, G.; Salomaa, A., eds. (2010); The Oxford Handbook of Membrane Computing. Oxford University Press.

Whitley, D. (2001); An overview of evolutionary algorithms: practical issues and common pitfalls. Inform Software Tech, ISSN 0950-5849, 43(14):817-831.

Xiao, J.H.; Zhang, X.Y.; Xu, J.(2012); A membrane evolutionary algorithm for DNA sequence design in DNA computing. Chinese Sci Bull, ISSN 1001-6538, 57(6):698-706.

Xiao, J.H.; Jiang, Y.; He, J.J.; Cheng, Z.(2013); A dynamic membrane evolutionary algorithm for solving DNA sequences design with minimum free energy. MATCH-Commun Math Ch, ISSN 0340-6253, 70(3):971-986.

Yang, S.; Wang, N. (2012): A novel P systems based optimization algorithm for parameter estimation of proton exchange membrane fuel cell model. Int J Hydrogen Energ, ISSN 0360-3199, 37(10): 8465- 8476.

Zhang, G.; Gheorghe, M.; Wu, C. (2008); A quantum-inspired evolutionary algorithm based on P systems for knapsack problem, Fund Inform, ISSN 0169-2968, 87(1):93-116.

Zhang, G. (2011); Quantum-inspired evolutionary algorithms: a survey and empirical study. J Heuristics, ISSN 1381-1231, 17(3): 303-351.

Zhang, G.; Cheng, J.; Gheorghe, M. (2011); A membrane-inspired approximate algorithm for traveling salesman problems, Rom J Inf Sci Tech, ISSN 1453-8245, 14(1):3-19.

Zhang, G.; Cheng, J.; Gheorghe, M.; Meng, Q. (2013); A hybrid approach based on differential evolution and tissue membrane systems for solving constrained manufacturing parameter optimization problems, Appl Soft Comput, ISSN 1568-4946, 13(3):1528-1542.

Zhang, G.X.; Cheng, J.X; Gheorghe, M. (2014); Dynamic behavior analysis of membrane-inspired evolutionary algorithms, Int J Comput Commun Control, ISSN 1841-9836, 9(2):227-242.

Zhang, G.; Liu, C.; Rong, H. (2010); Analyzing radar emitter signals with membrane algorithms. Math Comput Model, ISSN 0895-7177, 52(11-12):1997-2010.

Zhang, G.; Zhou, F.; Huang, X.; Cheng, J.; Gheorghe, M.; Ipate, F.; Lefticaru, R. (2012); A novel membrane algorithm based on particle swarm optimization for solving broadcasting problems, J Univers Comput Sci, ISSN 0948-695x, 18(13):1821-1841.

Zhang, X.; Zeng, X.; Luo, B.; Zhang, Z.(2012); A uniform solution to the independent set problem through tissue P systems with cell separation, Front Comput Sci, ISSN 2095-2228, 6(4):477-488.

Published

2015-04-01

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.