QEAM: An Approximate Algorithm Using P Systems with Active Membranes

  • 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

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

[1] 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.

[2] 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.

[3] 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.

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

[5] 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.

[6] 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.

[7] 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.

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

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

[10] 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.

[11] 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.

[12] 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.

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

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

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

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

[17] 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.

[18] 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.

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

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

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

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

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

[24] 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.

[25] 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.

[26] 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.

[27] 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.

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

[29] 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.

[30] 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.

[31] 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.

[32] 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.

[33] 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.

[34] 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
How to Cite
ZHANG, Gexiang et al. QEAM: An Approximate Algorithm Using P Systems with Active Membranes. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 10, n. 2, p. 263-279, apr. 2015. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/1757>. Date accessed: 22 jan. 2021. doi: https://doi.org/10.15837/ijccc.2015.2.1757.

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