QEAM: An Approximate Algorithm Using P Systems with Active Membranes

Gexiang Zhang, Jixiang Cheng, Marian Gheorghe, Florentin Ipate, Xueyuan Wang

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.

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

Full Text:

PDF

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.




DOI: https://doi.org/10.15837/ijccc.2015.2.1757



Copyright (c) 2017 Gexiang Zhang, Jixiang Cheng, Marian Gheorghe, Florentin Ipate, Xueyuan Wang

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

CC-BY-NC  License for Website User

Articles published in IJCCC user license are protected by copyright.

Users can access, download, copy, translate the IJCCC articles for non-commercial purposes provided that users, but cannot redistribute, display or adapt:

  • Cite the article using an appropriate bibliographic citation: author(s), article title, journal, volume, issue, page numbers, year of publication, DOI, and the link to the definitive published version on IJCCC website;
  • Maintain the integrity of the IJCCC article;
  • Retain the copyright notices and links to these terms and conditions so it is clear to other users what can and what cannot be done with the  article;
  • Ensure that, for any content in the IJCCC article that is identified as belonging to a third party, any re-use complies with the copyright policies of that third party;
  • Any translations must prominently display the statement: "This is an unofficial translation of an article that appeared in IJCCC. Agora University  has not endorsed this translation."

This is a non commercial license where the use of published articles for commercial purposes is forbiden. 

Commercial purposes include: 

  • Copying or downloading IJCCC articles, or linking to such postings, for further redistribution, sale or licensing, for a fee;
  • Copying, downloading or posting by a site or service that incorporates advertising with such content;
  • The inclusion or incorporation of article content in other works or services (other than normal quotations with an appropriate citation) that is then available for sale or licensing, for a fee;
  • Use of IJCCC articles or article content (other than normal quotations with appropriate citation) by for-profit organizations for promotional purposes, whether for a fee or otherwise;
  • Use for the purposes of monetary reward by means of sale, resale, license, loan, transfer or other form of commercial exploitation;

    The licensor cannot revoke these freedoms as long as you follow the license terms.

[End of CC-BY-NC  License for Website User]


INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL (IJCCC), With Emphasis on the Integration of Three Technologies (C & C & C),  ISSN 1841-9836.

IJCCC was founded in 2006,  at Agora University, by  Ioan DZITAC (Editor-in-Chief),  Florin Gheorghe FILIP (Editor-in-Chief), and  Misu-Jan MANOLESCU (Managing Editor).

Ethics: This journal is a member of, and subscribes to the principles of, the Committee on Publication Ethics (COPE).

Ioan  DZITAC (Editor-in-Chief) at COPE European Seminar, Bruxelles, 2015:

IJCCC is covered/indexed/abstracted in Science Citation Index Expanded (since vol.1(S),  2006); JCR2016: IF=1.374. .

IJCCC is indexed in Scopus from 2008 (CiteScore 2017 = 1.04; SNIP2017 = 0.616, SJR2017 =0.326):

Nomination by Elsevier for Journal Excellence Award Romania 2015 (SNIP2014 = 1.029): Elsevier/ Scopus

IJCCC was nominated by Elsevier for Journal Excellence Award - "Scopus Awards Romania 2015" (SNIP2014 = 1.029).

IJCCC is in Top 3 of 157 Romanian journals indexed by Scopus (in all fields) and No.1 in Computer Science field by Elsevier/ Scopus.

 

 Impact Factor in JCR2017 (Clarivate Analytics/SCI Expanded/ISI Web of Science): IF=1.29 (Q3). Scopus: CiteScore2017=1.04 (Q2); Editors-in-Chief: Ioan DZITAC & Florin Gheorghe FILIP.