AN ADAPTIVE MEMBRANE ALGORITHM FOR SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS

doi:10.1016/S0252-9602(14)60090-4

Abstract

Abstract:

Membrane algorithms (MAs), which inherit from P systems, constitute a new parallel and distribute framework for approximate computation. In the paper, a membrane algorithm is proposed with the improvement that the involved parameters can be adaptively chosen. In the algorithm, some membranes can evolve dynamically during the computing
process to specify the values of the requested parameters. The new algorithm is tested on a well-known combinatorial optimization problem, the travelling salesman problem. The em-pirical evidence suggests that the proposed approach is efficient and reliable when dealing with 11 benchmark instances, particularly obtaining the best of the known solutions in eight instances. Compared with the genetic algorithm, simulated annealing algorithm, neural net-work and a fine-tuned non-adaptive membrane algorithm, our algorithm performs better than them. In practice, to design the airline network that minimize the total routing cost on the CAB data with twenty-five US cities, we can quickly obtain high quality solutions using our algorithm.

Key words: membrane algorithm, adaptation, travelling salesman problem

CLC Number:

90C08

HE Juan-Juan, XIAO Jian-Hua, SHAO Ze-Hui. AN ADAPTIVE MEMBRANE ALGORITHM FOR SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS[J].Acta mathematica scientia,Series B, 2014, 34(5): 1377-1394.

Trendmd

References

[1] Back T, Hammel U, Schwefel H P. Evolutionary computation: Comments on the history and current state. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 3–17

[2] Wolpert D H, Macready W G. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 67–82

[3] P?aun G. Computing with membranes. Journal of Computer and System Sciences, 2000, 61(1):108–143
(first circulated at TUCS Research Report No. 208, November 1998)

[4] Mart´?n-Vide C, Pazos J, P?aun G, et al.. Tissue P systems. Theoretical Computer Science, 2003, 296(2): 295–326

[5] Ionescu M, P?aun G, Yokomori T. Spiking neural P systems. Fundamenta Informaticae, 2006, 71(2/3): 279–308

[6] P?aun G, Suzuki Y, Tanaka H, et al.. On the power of membrane division in P systems. Theoretical Computer Science, 2004, 324(1): 61–85

[7] Pan L, P?aun G. Spiking neural P systems with anti-spikes. International Journal of Computers, Commu-nications & Control, 2009, 4(3): 273–282

[8] Song T, Jiang Y, Shi X, et al.. Small universal spiking neural P systems with anti-spikes. Journal of Computational and Theoretical Nanoscience, 2013, 10(4): 999–1006

[9] Pan L, Wang J, Hoogeboom H. Spiking neural P systems with astrocytes. Neural Computation, 2012, 24(3): 805–825

[10] Jiang K, Song T, ChenW, et al.. Homogeneous spiking neural P systems working in sequential mode induced
by maximum spike number. International Journal of Computer Mathematics, 2013, 90(4): 831–844

[11] Song T, Pan L, P?aun G. Asynchronous spiking neural P systems with local synchronization. Information Sciences, 2013, 219: 197–207

[12] Krishna S, Rama R. A variant of P systems with active membranes: solving NP-complete problems. Romanian Journal of Information Science and Technology, 1999, 2(4): 357–367

[13] Song T, Mac´?as-Ramos L F, Pan L, et al.. Time-free solution to SAT problem using P systems with active
membranes. Theoretical Computer Science, 2013 [DOI:10.1016/j.tcs.2013.11.014]

[14] He J, Miao Z, Zhang Z, et al.. Solving multidimensional 0-1 knapsack problem by tissue P systems with cell division. Bio-Inspired Computing, 2009. BIC-TA’09. Fourth International Conference on IEEE, 2009: 1–5

[15] Pan L, P?aun G, P´erez-Jim´enez M J. Spiking neural P systems with neuron division and budding. Science
China Information Sciences, 2011, 54(8): 1596–1607

[16] Nishida T. An application of P-system: a new algorithm for NP-Complete optimization problem//Proc 8th World Multi-Conference on Systemics, Cybernetics and Informatics, 2004: 109–112

[17] Liang H, Xiongxiong H, Ning W, et al.. P systems based multi-objective optimization algorithm. Progress in Natural Science, 2007, 17(4): 458–465

[18] Cheng J, Zhang G, Zeng X. A Novel Membrane Algorithm Based on Differential Evolution for Numerical Optimization. International Journal of Unconventional Computing, 2011, 7(3): 159–183

[19] Zhang G, Zhou F, Huang X, et al.. A novel membrane algorithm based on particle swarm optimization for solving broadcasting problem. Journal of Universal Computer Science, 2012, 18(13): 1821–1841

[20] Zhang G, Gheorghe M,Wu C. A quantum-inspired evolutionary algorithm based on P systems for knapsack problem. Fundamenta Informaticae, 2008, 87(1): 93–116

[21] Zhang G, Cheng J, Marian G, et al.. A hybrid approach based on differential evolution and tissue membrane systems for solving constrained manufacturing parameter optimization problems. Applied Soft Computing, 2013, 13(3): 1528–1542

[22] Xiao J, Huang Y, Cheng Z, et al.. A hybrid membrane evolutionary algorithm for solving constrained optimization problems. Optik-International Journal for Light and Electron Optics, 2014, 125(2): 897–902

[23] Zhang G, Liu C, Rong H. Analyzing radar emitter signals with membrane algorithms. Mathematical and Computer Modelling, 2010, 52(11): 1997–2010

[24] Xiao J, Zhang X, Xu J. A membrane evolutionary algorithm for DNA sequence design in DNA computing. Chinese Science Bulletin, 2012, 57(6): 698–706

[25] Xiao J, Jiang Y, He J, et al.. A dynamic membrane evolutionary algorithm for solving DNA sequences design with minimum free energy. 2013, 70(3): 971–986

[26] He J, Song T. A Bio-inspired algorithm for the fleet size and mix vehicle routing problem. Journal of Computational and Theoretical Nanoscience (In press)

[27] Zhang G. Quantum-inspired evolutionary algorithms: a survey and empirical study. Journal of Heuristics, 2011, 17(3): 303–351

[28] Cheng J, Zhang G, Ferrante Neri. Enhancing distributed differential evolution with multicultural migration for global numerical optimization. Information Sciences, 2013, 247: 72–93

[29] Leporati A, Pagani D. A Membrane Algorithm for the Min Storage Problem. Membrane Computing. Berlin, Heidelberg: Springer, 2006: 443–462

[30] He J, Xiao J, Shi X, et al.. A membrane-inspired algorithm with a memory mechanism for knapsack problems. Journal of Zhejiang University: Science C, Computers & Electronics, 2013, 14(8): 612–622

[31] Maekawa K, Mori N, Tamaki H, et al.. A genetic solution for the traveling salesman problem by means of a thermodynamical selection rule. Proceedings of IEEE International Conference on Evolutionary Compu-tation, 1996: 529–534

[32] Yoneda M. URL http://www.mikilab.doshisha.ac.jp/dia/research/person/yoneda/research/2002 7 10/SA/
07-sareslut.html

[33] Tanaka T, Matsuda S, Furuya T, et al.. Performance comparisons of two Hopfield neural networks for large-scale travelling salesman problems. NASA, 1997(19990036336): 54–55

[34] Tomassini G. TSPLIB. URL http://www.iwr.uni-heidelberg.de/groups/comopt/softwar/TSPLIB95/

[35] P?aun G. Membrane Computing: An Introduction. Springer, 2002

[36] Prins C. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 2004, 31(12): 1985–2002

[37] Baker B M, Ayechew M A. A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 2003, 30(5): 787–800

[38] O´Kelly M E. A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research, 1987, 32(3): 393–404

[39] Yang J, Zhang R, Liu M. Construction of optimal blocking schemes for robust parameter designs. Acta Mathematica Scientia, 2013, 33B(5): 1431–1438

[40] Sahebi H R, Razani A. A solution of a general equilibrium problem. Acta Mathematica Scientia, 2013, 33B(6): 1598–1614

[41] Xu R, Ding Y. Global solutions and finite time blow up for damped Klein-Gordon equation. Acta Mathe-matica Scientia, 2013, 33B(3): 643–652