A Hybrid Distribution Algorithm Based on Membrane Computing for Solving the Multiobjective Multiple Traveling Salesman Problem

• Autorzy: He J. , Zhang K.

Identyfikatory

DOI

10.3233/FI-2015-1151

• Języki publikacji: EN

Abstrakty

EN

The multiobjective multiple traveling salesman problem (MmTSP), in which multiple salesmen and objectives are involved in a route, is known to be NP-hard. The MmTSP is more appropriate for real-life applications than the classical traveling salesman problem (TSP), however it has not received the same amount of attention. Due to the high complexity of the MmTSP, a promising algorithm for solving it must be based on a global search procedure. This paper proposes a hybrid global search algorithm, that belongs to the membrane computing framework. The search behavior of the algorithm is enhanced by a communication mechanism. The multichromosome representation is considered to reduce the excess runtime. The effectiveness of the proposed algorithm is tested on the MmTSP with disparately-scaled objective functions, salesmen and problem sizes. The experimental results are compared with the NSGA-II and several evolutionary strategies with decomposition, including simulated annealing algorithm, hill climbing method, pure evolutionary algorithm, and genetic algorithm.

Słowa kluczowe

EN

evolutionary multiobjective optimization; membrane computing; multiobjective multiple traveling salesman problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 136, nr 3
• Strony: 199--208
• Opis fizyczny: Bibliogr. 22 poz., rys., tab.

Twórcy

autor

He J.

• School of Computer Science, Wuhan University of Science and Technology, Wuhan 420081, P.R.China

autor

Zhang K.

• Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System Wuhan 430081, P.R.China

Bibliografia

• [1] The P System Web Page: http://ppage.psystems.eu.
• [2] Alhazov, A., Freund, R., Oswald, M., Verlan, S.: Partial halting and minimal parallelism based on arbitrary rule partitions, Fundamenta Informaticae, 91(1), April 2009, 17–34.
• [3] Alhazov, A., Rogozhin, Yu., Verlan, S.: Minimal cooperation in symport/antiport tissue P systems, International Journal of Foundations of Computer Science, 18(1), February 2007, 163–180.
• [4] Bernardini, F., Gheorghe, M.: Population P systems, Journal of Universal Computer Science, 10(5), 2004, 509–539.
• [5] Besozzi, D., Cazzaniga, P., Pescini, D., Mauri, G.: Modelling metapopulations with stochastic membrane systems, Biosystems, 91(3), 2008, 499–514.
• [6] Cheng, J., Zhang, G., Neri, F.: Enhancing distributed differential evolution with multicultural migration for global numerical optimization, Information Sciences, 247, 2013, 72–93.
• [7] He, J., Xiao, J., Shao, Z.: An adaptive membrane algorithm for solving combinatorial optimization problems, Acta Mathematica Scientia, 34(5), 2014, 1377–1394.
• [8] He, J., Xiao, J., Shi, X., Song, T.: A membrane-inspired algorithm with a memory mechanism for knapsack problems, Journal of Zhejiang University-Science C, 14(8), 2013, 612–622.
• [9] Miettinen, K.: Nonlinear multiobjective optimization, International Series in Operations Research & Management Science, vol. 12, Springer, 1999.
• [10] Pan, L., Pérez-Jiménez, M. J.: Computational complexity of tissue-like P systems, Journal of Complexity, 26(3), 2010, 296-315.
• [11] Păun, G.: Computing with membranes, Journal of Computer and System Sciences, 61(1), 2000. Also in Turku Center for Computer Science–TUCS, Report 208, November 1998, 108–143.
• [12] Păun, G.: Membrane Computing: An Introduction, Springer, 2002.
• [13] Păun, G., Rozenberg, G., Salomaa, A., eds.: The Oxford Handbook of Membrane Computing, Oxford University Press, 2010, ISBN 0199556679.
• [14] Shim, V. A., Tan, K. C., Chia, J. Y.: Probabilistic based evolutionary optimizers in bi-objective travelling salesman problem, in: Simulated Evolution and Learning, Springer, 2010, 588–592.
• [15] Singh, A., Baghel, A. S.: A new grouping genetic algorithm approach to the multiple traveling salesperson problem, Soft Computing, 13(1), 2009, 95–101.
• [16] Xiao, J., Zhang, X., Xu, J.: A membrane evolutionary algorithm for DNA sequence design in DNA computing, Chinese Science Bulletin, 57(6), 2012, 698–706.
• [17] Xiao, J., Jiang, Y., He, J., Cheng, Z.: A dynamic membrane evolutionary algorithm for solving DNA sequences design with minimum free energy, MATCH Communications in Mathematical and in Computer Chemistry, 70(3), 2013, 971–986.
• [18] Zhang, G., Cheng, J., Gheorghe, M.: Dynamic behavior analysis of membrane-inspired evolutionary algorithms, International Journal of Computers Communications & Control, 9(2), 2014, 227–242.
• [19] Zhang, G., Cheng, J., Gheorghe, M., Meng, Q.: A hybrid approach based on differential evolution and tissue membrane systems for solving constrained manufacturing parameter optimization problems, Applied Soft Computing, 13(3), 2013, 1528–1542.
• [20] Zhang, G., Zhou, F., Huang, X., Cheng, J., Gheorghe, M., Ipate, F., Lefticaru, R.: A novel membrane algorithm based on particle swarm optimization for solving broadcasting problems, Journal of Universal Computer Science, 18(13), 2012, 1821–1841.
• [21] Zhang, Q., Li, H.: MOEA/D: A multiobjective evolutionary algorithm based on decomposition, Evolutionary Computation, IEEE Transactions on, 11(6), 2007, 712–731.
• [22] Zhao, J., Wang, N.: A bio-inspired algorithm based on membrane computing and its application to gasoline blending scheduling, Computers & chemical engineering, 35(2), 2011, 272–283.