Dynamic Behavior Analysis of Membrane-Inspired Evolutionary Algorithms

  • Gexiang Zhang Southwest Jiaotong University
  • Jixiang Cheng
  • Marian Gheorghe The University of Sheffield

Abstract

A membrane-inspired evolutionary algorithm (MIEA) is a successful instance of a model linking membrane computing and evolutionary algorithms. This paper proposes the analysis of dynamic behaviors of MIEAs by introducing a set of population diversity and convergence measures. This is the first attempt to obtain additional insights into the search capabilities of MIEAs. The analysis is performed on the MIEA, QEPS (a quantum-inspired evolutionary algorithm based on membrane computing), and its counterpart algorithm, QIEA (a quantum-inspired evolutionary algorithm), using a comparative approach in an experimental context to better understand their characteristics and performances. Also the relationship between these measures and fitness is analyzed by presenting a tendency correlation coefficient to evaluate the importance of various population and convergence measures, which is beneficial to further improvements of MIEAs. Results show that QEPS can achieve better balance between convergence and diversity than QIEA, which indicates QEPS has a stronger capacity of balancing exploration and exploitation than QIEA in order to prevent premature convergence that might occur. Experiments utilizing knapsack problems support the above made statement.

Author Biographies

Gexiang Zhang, Southwest Jiaotong University
School of Electrical Engineering
Marian Gheorghe, The University of Sheffield
Department of Computer Science

References

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

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

[3] Pan, L.; Păun, Gh.; (2009); Spiking neural P systems with anti-spikes, Int J Comput Commun, ISSN: 1841-9836, 4: 273-282.

[4] Zhang, X.; Wang, J.; Pan, L. ; (2009); A note on the generative power of axon P systems, Int. J. Comput. Commun. ISSN: 1841-9836, 4: 92-98.

[5] Lu, C.; Zhang, X.; (2010); Solving vertex cover problem by means of tissue P systems with cell separation, Int J Comput Commun, ISSN: 1841-9836, 5: 540-550.

[6] Zhang, X.; Luo, B.; Pan, L.; (2012); Small universal tissue P systems with symport/antiport rules, Int J Comput Commun, ISSN: 1841-9836, 7: 173-183

[7] Zhang, G.X.; Liu, C.X.; Rong, H.N. (2010)Łť Analyzing radar emitter signals with membrane algorithms, Math. Comput. Model, ISSN: 0895-7177, 52: 1997-2010.

[8] Zhang, G.X.; Cheng, J.X.; 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:1528-1542.

[9] Păun, Gh.; Pérez-Jiménez, M.J. (2006); Membrane computing: brief introduction, recent results and applications, Biosystems, ISSN: 0303-2647, 85: 11-22.

[10] Nishida, T.Y. (2004); An application of P-system: A new algorithm for NP-complete optimization problems, Proc. of WMSCI, 109-112.

[11] Huang, L.; He, X.; Wang, N.; Xie, Y. (2007); P systems based multi-objective optimization algorithm, Prog. Nat. Sci., 17: 458-465.
http://dx.doi.org/10.1080/10020070708541023

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

[13] Cheng, J.X.; Zhang, G.X.; Gheorghe, M.; Zeng, X.X. (2011);

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

[14] Zhang, G.X.; Gheorghe, M.; Li, Y.Q. (2012); A membrane algorithm with quantum-inspired subalgorithms and its application to image processing, Nat. Comput., ISSN: 1567-781, 11: 701-717.

[15] Zhang, G.X.; Zhou, F.; Huang, X.L.; Cheng, J.X.; Gheorghe, K.; Ipate, F.; Lefticaru, R. A novel membrane algorithm based on particle swarm optimization for solving broadcasting problems, J. Univers. Comput. Sci., ISSN: 0948-695X, 18: 1821-1841.

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

[17] 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. Comput. Chem., ISSN: 0340-6253, 70: 971-986.

[18] He, J.J.; Xiao, J.H.; Shi, X.L.; Song, T. (2013); A membrane-inspired algorithm with a memory mechanism for knapsack problems, J. Zhejiang U.-SCI. C, ISSN: 1869-1951, 14: 612-622.

[19] Xiao, J.H.; Huang, Y.F.; Cheng, Z; He, J.J.; Niu, Y.Y. (2014); A hybrid membrane evolutionary algorithm for solving constrained optimization problems. Optik, ISSN: 0030-4026, 125: 897-902.

[20] 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: 580-593.

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

[22] Burke, E.K.; Gustafson, S.; Kendall, G. (2004); Diversity in genetic programming: an analysis of measures and correlation with fitness, IEEE T. Evolut. Comput., ISSN 1089-778X, ISSN 1089-778X, 8: 47-62.

[23] Herrera, F.; Lozano, M. (1996); Adaptation of genetic algorithm parameters based on fuzzy logic controllers. Genetic Algorithms and Soft Computing, 95-125.
Published
2014-02-28
How to Cite
ZHANG, Gexiang; CHENG, Jixiang; GHEORGHE, Marian. Dynamic Behavior Analysis of Membrane-Inspired Evolutionary Algorithms. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 9, n. 2, p. 227-242, feb. 2014. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/794>. Date accessed: 12 aug. 2020. doi: https://doi.org/10.15837/ijccc.2014.2.794.

Keywords

membrane computing, membrane algorithms