QEAM: An Approximate Algorithm Using P Systems with Active Membranes
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 membranesAbstract
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
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.