×

Biogeography migration algorithm for traveling salesman problem. (English) Zbl 1260.68384

Summary: Biogeography-based optimization algorithm is a new kind of optimization algorithm based on biogeography. It is designed based on the migration strategy of animals to solve the problem of optimization. The purpose of this paper is to present a new algorithm-biogeography migration algorithm for traveling salesman problem (TSPBMA). A new special migration operator is designed for producing new solutions.
The paper gives the definition of TSP and models of TSPBMA; introduces the algorithm of TSPBMA in detail and gives the proof of convergence in theory; provides simulation results of TSPBMA compared with other optimization algorithms for TSP and presents some concluding remarks and suggestions for further work.
The TSPBMA is tested on some classical TSP problems. The comparison results with the other nature-inspired optimization algorithms show that TSPBMA is useful for TSP combination optimization. Especially, the designed migration operator is very effective for TSP solving. Although the proposed TSPBMA is not better than ant colony algorithm in the respect of convergence speed and accuracy, it provides a new way for this kind of problem.
The migration operator is a new strategy for solving TSPs. It has never been used by any other evolutionary algorithm or swarm intelligence before TSPBMA.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1016/j.ipl.2004.06.013 · Zbl 1178.90282 · doi:10.1016/j.ipl.2004.06.013
[2] Bellmore, M. and Nemhauser, G.L. (1968), ”The traveling salesman problem: a survey”,Operations Research, Vol. 16 No. 2, pp. 16538-58. · Zbl 0213.44604 · doi:10.1287/opre.16.3.538
[3] DOI: 10.1016/j.eswa.2009.10.031 · doi:10.1016/j.eswa.2009.10.031
[4] Colorni, A., Dorigo, M., Maniezzo, V. and Trubian, M. (1994), ”Ant system for job-shop scheduling”,Belgian Journal of Operations Research, Statistics and Computer Science, Vol. 34, pp. 295-305. · Zbl 0814.90047
[5] Du, D., Simon, D. and Ergezer, M. (2009), ”Biogeography-based optimization combined with evolutionary strategy and immigration refusal”,IEEE International Conference on Systems, Man, and Cybernetics. San Antonio, TX, pp. 1023-8. · doi:10.1109/ICSMC.2009.5346055
[6] Endoh, S., Toma, N. and Yamada, K. (1998), ”Immune algorithm for n-TSP”,IEEE International Conference on Systems, Man, and Cybernetics, Vol. 4 No. 11, pp. 3844-9. · doi:10.1109/ICSMC.1998.726687
[7] Ergezer, M., Simon, D. and Du, D.W. (2009), ”Oppositional biogeography-based optimization”,IEEE Conference on Systems, Man, and Cybernetics, San Antonio, TX, pp. 1035-40. · doi:10.1109/ICSMC.2009.5346043
[8] Ma, H. and Chen, X. (2009), ”Equilibrium species counts and migration model tradeoffs for biogeography-based optimization”,48th IEEE Conference on Decision and Control. Shanghai, pp. 3306-10. · doi:10.1109/CDC.2009.5400004
[9] Rarick, R., Simon, D., Villaseca, F.E. and Vyakaranam, B. (2009), ”Biogeography-based optimization and the solution of the power flow problem”,IEEE Conference on Systems, Man, and Cybernetics, San Antonio, TX, pp. 1029-34. · doi:10.1109/ICSMC.2009.5346046
[10] DOI: 10.1109/72.265964 · doi:10.1109/72.265964
[11] DOI: 10.1108/17563781011049205 · Zbl 1214.68084 · doi:10.1108/17563781011049205
[12] DOI: 10.1016/j.ipl.2007.03.010 · Zbl 1187.90238 · doi:10.1016/j.ipl.2007.03.010
[13] DOI: 10.1109/TEVC.2008.919004 · Zbl 05740389 · doi:10.1109/TEVC.2008.919004
[14] Simon, D. (2010), ”A probabilistic analysis of a simplified biogeography-based optimization algorithm”,Evolutionary Computation,, February 13, pp. 1-22.
[15] Simon, D., Ergezer, M. and Du, D.W. (2009), ”Population distributions in biogeography-based optimization algorithms with elitism”,IEEE Conference on Systems, Man, and Cybernetics, San Antonio, TX, pp. 1017-22. · doi:10.1109/ICSMC.2009.5346058
[16] Wang, H. (2009), ”Traveling salesman problem by genetic algorithm”,Computer and Modernization, Vol. 7, pp. 12-15.
[17] DOI: 10.1287/ijoc.12.3.237.12636 · Zbl 1040.90570 · doi:10.1287/ijoc.12.3.237.12636
[18] DOI: 10.1577/1548-8659(1987)7<232:MHSIMF>2.0.CO;2 · doi:10.1577/1548-8659(1987)7<232:MHSIMF>2.0.CO;2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.