An Approximate Algorithm Combining P Systems and Active Evolutionary Algorithms for Traveling Salesman Problems
Keywords:
P systems, active evolutionary algorithms, traveling salesman problemsAbstract
An approximate algorithm combining P systems and active evolutionary algorithms (AEAPS) to solve traveling salesman problems (TSPs) is proposed in this paper. The novel algorithm uses the same membrane structure, subalgorithms and transporting mechanisms as Nishida’s algorithm, but adopts two classes of active evolution operators and a good initial solution generating method. Computer experiments show that the AEAPS produces better solutions than Nishida’s shrink membrane algorithm and similar solutions with an approximate optimization algorithm integrating P systems and ant colony optimization techniques (ACOPS) in solving TSPs. But the necessary number of iterations using AEAPS is less than both of them.References
Păun, G. (2000); Computing with membranes, Journal of Computer and System Sciences, SSN 0022-0000, 61(1): 108-143.
Nishida, T.Y. (2004); An application of P-system: A new algorithm for NP-complete optimization roblems, Proceedings of the 8th World Multi-Conference on Systems, Cybernetics nd Informatics, V: 109-112.
Nishida, T.Y. (2005); An approximate algorithm for NP-complete optimization problems xploiting P-systems, Proceedings of the 6th International Workshop on Membrane Computing, SBN 978-3-540-30948-2, 26-43.
Nishida, T.Y. (2006); Membrane algorithms: Approximate algorithms for NP-complete optimization roblems, Applications of Membrane Computing, ISBN 978-3-540-29937-0, 303- 14.
Huang, L.; He, X.X.; Wang, N.; Xie, Y. (2007); P systems based multi-objective optimization lgorithm, Progress in Natural Science, ISSN 1002-0071, 17(4): 458-465.
Huang, L.; Wang, N. (2006); An optimization algorithm inspired by membrane computing, CNC 2006, LNCS, ISBN 3-540-45901-4, 4222: 49-52.
Cheng, J.X.; Zhang, G.X.; Zeng, X.X. (2011);
Cheng, J.X.; Zhang, G.X.; Zeng, X.X. (2011); A novel membrane algorithm based on differential volution for numerical optimization, International Journal of Unconventional Computing, SSN: 1548-7199, 7(3): 159-183.
Zhang, G.X.; Liu, C.X.; Gheorghe, M.; Ipate, F. (2009); Solving satisfiability problems ith membrane algorithm, Proceedings of the 4th International Conference on Bio-Inspired omputing: Theories and Applications, ISBN 978-1-4244-3866-2, 29-36.
Zhang, G.X.; Gheorghe, M.; Wu, C.Z. (2008); A quantum-inspired evolutionary algorithm ased on P systems for knapsack problem, Fundamenta Informaticae, ISSN 0169-2968, 87(1): 3-116.
Liu, C.X.; Zhang, G.X.; Zhu, Y.H.; Fang, C.; Liu, H.W. (2009); A quantum-inspired evolutionary lgorithm based on P systems for radar emitter signals, Proceedings of the 4th nternational Conference on Bio-Inspired Computing: Theories and Applications, ISBN 978- -4244-6438-8, 1-5.
Liu, C.X.; Zhang, G.X.; Liu, L.W.; Gheorghe, M.; Ipate, F. (2010); An improved membrane lgorithm for solving time-frequency atom decomposition, WMC 2009. LNCS, ISSN 0302- 743, 5957: 371-384.
Liu, C.X.; Zhang, G.X.; Liu, H.W. (2009); A memetic algorithm based on P systems for IR digital filter design, Proceedings of the 8th IEEE International Conference on Pervasive ntelligence and Computing, ISBN: 978-0-7695-3929-4, 330-334.
Huang, L.; Suh, I.H. (2009); Controller design for a marine diesel engine using membrane omputing, International Journal of Innovative Computing Information and Control, ISSN 349-4198, 5(4): 899-912.
Zhang, G.X.; Liu, C.X.; Rong, H.N. (2010); Analyzing radar emitter signals with membrane lgorithms, Mathematical and Computer Modelling, ISSN 0895-7177, 52(11-12): 1997-2010.
Yang, S.P.; Wang, N. (2012); A P systems based hybrid optimization algorithm for parameter stimation of FCCU reactor-regenerator model, Chemical Engineering Journal, ISSN 385-8947, 211: 508-518.
Zhang, G.X.; Gheorghe, M.; Li, Y.Q. (2012); A membrane algorithm with quantum-inspired ubalgorithms and its application to image processing, Natural Computing, ISSN 1567-7818, 1(4): 701-717.
Zhang, G.X.; Cheng, J.X.; Gheorghe, M.; Meng, Q. (2013); A hybrid approach based on ifferential evolution and tissue membrane systems for solving constrained manufacturing arameter optimization problems, Applied Soft Computing, ISSN 1568-4946, 13(3): 1528- 542.
Zhang, G.X.; Zhou, F.; Huang, X.L. (2012);
Zhang, G.X.; Zhou, F.; Huang, X.L. (2012); A Novel membrane algorithm based on particle warm optimization for optimization for solving broadcasting problems, Journal of Universal omputer Science, ISSN 0948-695X, 18(13): 1821-1841.
Tu, M.; Wang, J.; Song, X.X.; Yang, F.; Cui, X.R. (2013); An artificial fish swarm algorithm ased on P systems, ICIC Express Letters, Part B: Applications, ISSN 1881-803X, 4(3): 47-753.
Cairns, J.; Overbaugh, J.; Miller, S. (1988); The origin of mutations, Nature, ISSN 0028- 836, 335: 142-145.
Hall, B.G. (1988); Adaptive evolution that requires multiple spontaneous mutations. I. Mutations nvolving an insertion sequence, Genetics, ISSN 0016-6731, 120(4): 887-897.
Hall, B.G. (1991); Is the occurrence of some spontaneous mutations directed by environmental hallenges?, The new biologist, ISSN 1043-4674, 3(8): 729-733.
Ponder, R.G.; Fonville, N.C.; Rosenberg, S.M. (2005);
Ponder, R.G.; Fonville, N.C.; Rosenberg, S.M. (2005); A switch from high-fidelity to errorprone NA double-strand break repair underlies stress-induced mutation, Molecular Cell, SSN 1097-2765, 19(6): 791-804.
Slack, A.; Thornton, P.C.; Magner, D.B.; Rosenberg, S.M.; Hastings, P.J. (2006); On the echanism of gene amplification induced under stress in Escherichia coli, Plos Genetics, SSN 1553-7390, 2(4): 385-398.
Galhardo, R.S.; Hastings, P.J.; Rosenberg, S.M. (2007);
Galhardo, R.S.; Hastings, P.J.; Rosenberg, S.M. (2007); Mutation as a stress response and he regulation of evolvability, Critical Reviews in Biochemistry and Molecular Biology, ISSN 040-9238, 42(5): 399-435.
Rosenberg S.M.; Shee, C.; Frisch, R.L.; Hastings, P.J. (2012); Stress-induced mutation via NA breaks in Escherichia coli: a molecular mechanism with implications for evolution and edicine, Bioessays, ISSN 0265-9247, 34(10): 885-892.
Shi, L.; Li, H.Y.; Yang, J.A. (2004); Active evolution based genetic algorithm, Mini-micro ystems, ISSN 1000-1220, 5(25): 790-793.
Zhang, G.X.; Cheng, J.X.; Gheorghe M. (2010); An approximate algorithm combining P ystems and ant colony optimization for traveling salesman problems, Proceedings of the 8th rainstorming Week on Membrane Computing, ISBN 978-84-614-2357-6, 321-340.
Zhang, G.X.; Cheng, J.X.; Gheorghe M. (2011); A membrane-inspired approximate algorithm or traveling salesman problems, Romanian Journal of Information Science and echnology, ISSN 1453-8245, 14(1): 3-19.
Păun, G. (2007); Tracing some open problems in membrane computing, Romanian Journal f Information Science and Technology, ISSN 1453-8245, 10(4): 303-314.
Păun, G.; Rozenberg, G. (2002); A guide to membrane computing, Theoretical Computer cience, ISSN 0304-3975, 287(1): 73-100.
Erick, C.P. (1998); A survey of parallel genetic algorithms, Calculateurs Paralleles, ISSN 260-3198, 10(2): 141-171.
Croes, G.A. (1958); A method for solving traveling salesman problems, Operations Research, SSN 0030-364X, 6(6): 791-812.
Lin, S.; Kernighan, B.W. (1973); An Effective Heuristic Algorithm for the Traveling- alesman Problem, Operations Research, ISSN 0030-364X, 21(2): 498-516.
Helsgaun K. (2000); An effective implementation of the Lin-Kernighan traveling salesman euristic, European Journal of Operational Research, ISSN 0377-2217, 126(1): 106-130.
Bentley, J.J. (1992); Fast algorithm for geometric traveling salesman problems, Informs ournal on Computing, ISSN 1091-9856, 4(4): 387-411.
http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
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.
