An Approximate Algorithm Combining P Systems and Active Evolutionary Algorithms for Traveling Salesman Problems

Xiaoxiao Song, Jun Wang

Abstract


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.

Keywords


P systems, active evolutionary algorithms, traveling salesman problems

Full Text:

PDF

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/




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



Copyright (c) 2017 Xiaoxiao Song, Jun 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); JCR2018: IF=1.585..

IJCCC is indexed in Scopus from 2008 (CiteScore2018 = 1.56):

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 JCR2018 (Clarivate Analytics/SCI Expanded/ISI Web of Science): IF=1.585 (Q3). Scopus: CiteScore2018=1.56 (Q2); Editors-in-Chief: Ioan DZITAC & Florin Gheorghe FILIP.