A novel metaheuristic for traveling salesman problem: blind mole-rat algorithm

Yıl 2016, Cilt: 22 Sayı: 1, 64 - 70, 29.02.2016

Tevfik Yıldırım Can Berk Kalaycı Özcan Mutlu

Öz

Traveling Salesman Problem (TSP) is the problem of finding a minimum distance tour of cities beginning and ending at the same city and that each city are visited only once. As the number of cities increases, it is difficult to find an optimal solution by exact methods in a reasonable duration. Therefore, in recent five decades many heuristic solution methods inspired of nature and biology have been developed. In this paper, a new metaheuristic method inspired of the by-passing the obstacle strategy of blind mole rats living in their individual tunnel systems under the soil is designed for solving TSP. The method is called as Blind Mole-rat Algorithm. The proposed algorithm is tested on different size of symmetric TSP problems and the results are compared to the best known results. Initial test results are promising although proposed metaheuristic is not yet competitive enough among other algorithms in the literature.

Keywords: Traveling salesman problem, Combinatorial optimization, Metaheuristic, Blind mole-Rat algorithm

Anahtar Kelimeler

-

Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması

Öz

Gezgin Satıcı Problemi (GSP), başlangıç ve bitiş şehirleri aynı olan ve her şehrin sadece bir kez ziyaret edildiği minimum mesafeli turu bulma problemidir. Şehir sayısı arttıkça, kesin yöntemler ile kabul edilebilir sürelerde bir optimum çözüm bulunması zordur. Bu nedenle, son elli yılda GSP’nin çözümü için doğadan ve biyolojiden esinlenen birçok meta-sezgisel yöntem geliştirilmiştir. Bu çalışmada, toprak altındaki bireysel tünel sistemlerinde yaşayan kör farelerin toprak altındaki engelleri geçme stratejisinden esinlenilerek GSP’nin çözümü için yeni bir meta-sezgisel tasarlanmıştır. Geliştirilen yönteme Kör Fare Algoritması adı verilmiştir. Bu yeni sezgisel ile farklı boyutlardaki simetrik test veri setleri için deneyler yapılmış ve sonuçları bilinen en iyi sonuçlar ile kıyaslanmıştır. Önerilen meta-sezgisel henüz literatürdeki diğer algoritmalarla yarışabilecek düzeyde olmamasına rağmen, başlangıç test çözümlerinin umut verici olduğu söylenebilir.

Anahtar Kelimeler: Gezgin satıcı problemi, Kombinatoryel eniyileme, Meta-Sezgisel, Kör fare algoritması

Anahtar Kelimeler

Gezgin satıcı problemi, Kombinatoryel eniyileme, Meta-Sezgisel, Kör fare algoritması

Kaynakça

• Rego C, Gamboa D, Glover F, Osterman C. “Traveling Salesman Problem Heuristics: Leading Methods, Implementations and Latest Advances”. European Journal of Operational Research, 211(3), 427-441, 2011.
• Sallabi OM, El-Haddad Y. “An Improved Genetic Algorithm to Solve the Traveling Salesman Problem”. World Academy of Science, Engineering and Technology International Journal of Computer, Electrical, Automation, Control and Information Engineering, 3(4), 984-987, 2009.
• Laporte G. “The Travelling Salesman Problem: An Overview of Exact and Approximate Algorithms”. European Journal of Operational Research, 59(2), 231-247, 1992.
• Ahmadvand M, Yousefikhoshbakt M, Darani MN. “Solving the Travelling Salesman Problem by an Efficient Hybrid Metaherustic Algorithm”. Journal of Advance in Computer Research, 3(3), 75-84, 2012.
• Yong W. “Hybrid Max-Min Ant System with Four Vertices and Three Lines Inequality for Traveling Salesman Problem”. Soft Computing, 19(3), 585-586, 2015.
• Mondal RN, Hossain SK, Saha SK. “An Approach for Solving Travelling Salesman Problem”. International Journal of Applied Operational Research, 3(22), 15-26, 2013.
• Davendra D. Traveling Salesman Problem, Theory and Applications. Intech, Crotia, Intech, 2010.
• Cerny V. “Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm”. Journal of Optimization Theory and Applications, 45(1), 4151, 1985.
• Sureja NM, Chawda BV. “Random Travelling Salesman Problem Using SA”. International Journal of Emerging Technology and Advanced Engineering, 2(4), 621-624, 2012.
• Larranaga P, Kuijpers CMH, Murga RH, Inza I, Dizdarevic S. “Genetic Algorithms for the Traveling Salesman Problem: A Review of Representations and Operators”. Artificial Intelligence Review, 13(2), 129-170, 1999.
• Liu YH. “Different Initial Solution Generators in Genetic Algorithms for Solving the Probabilistic Traveling Salesman Problem”. Applied Mathematics and Computation, 216(1), 125-137, 2010.
• Wang Y. “The Hybrid Genetic Algortihm with Two Local Optimization Strategies For Traveling Salesman”. Computers & Industrial Engineering, 70, 124-133, 2014.
• Hopfield JJ, Tank DW. “Neural Computation of Decisions in Optimization Problems”. Biological Cybernetics, 52, 141152, 1985.
• Leung KS, Jin HD, Xu ZB. “An Expanding Self-Organizing Neural Network for the Traveling Salesman Problem”. Neurocomputing, 62, 267-292, 2004.
• Masutti TAS, de Castro LN. “A Self-Organizing Neural Network Using Ideas From the Immune System to Solve the Traveling Salesman Problem”. Information Sciences, 179(10), 1454-1468, 2009.
• Fritzke B, Wilke P. “FLEXMAP-A Neural Network for the Traveling Salesman Problem With Linear Time and Space Complexity”. IEEE International Joint Conference on Neural Networks, Singapore, 18-21 November 1991.
• Dorigo M, Maniezzo V, Coloni A. “Positive Feedback as a Search Strategy”. Dipartimento di Elettronica, Politecnico di Milano, Milano, Italy, Technical Report 91-016, 1991.
• Dorigo M, Gambardella LM. “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem”. IEEE Transactions on Evolutionary Computation, 1(1), 53-66, 1997.
• Dorigo M, Stützle T. Ant Colony Optimization, UK, The MIT Press, 2004.
• Wang KP, Huang L, Zhou CG, Pang W. “Particle Swarm Optimization for Travelling Salesman Problem”. Machine Learning and Cybernetics, 3, 1583-1585, 2003.
• Pang W, Wang K, Zhou C, Dong, L. “Fuzzy Discrete Particle Swarm Optimization for Solving Traveling Salesman Problem”. Proceedings of the Fourth International Conference on Computer and Information Technology (CIT’04), Wuhan, China, 14-16 September, 2004.
• Goldbarg EFG, Souza GR, Goldbarg MC. Particle Swarm for the Traveling Salesman Problem. Editors: Gottlieb J, Günther RR. Evolutioary Computation in Combinatorial Optimization, 99-110, Berlin, Germany, Springer Berlin Heidelberg, 2006.
• Shi XH, Liang YC, Lee HP, Lu C, Wang QX. “Particle Swarm Optimization-Based Algorithms for TSP and Generalized TSP”. Information Processing Letters, 103(5), 169-176, 2007.
• Chen WN, Zhang J, Chung HSH, Zhong WL, Wu WG, Shi YH. “A Novel Set-Based Particle Swarm Optimization Method for Discrete Optimization Problems”. IEEE Transactions on Evolutionary Computation, 14(2), 278-300, 2010.
• Karaboğa D. Yapay Zekâ Optimizasyon Algoritmaları. Ankara, Türkiye, Nobel Yayın Dağıtım, 2011.
• Lucic P, Teodorovic D. “Transportation Modeling: An Artificial Life Approach”. Proceedings of the 14th IEEE International Conference on Tools with Artificial Intelligence, Washington, USA, 4-6 November 2002.
• Koçer HE, Akça MR. “An Improved Artificial Bee Colony Algorithm with Local Search for Traveling Salesman Problem”. Cybernetics and Systems, 45(8), 635-649, 2014.
• Feng X, Lau FCM, Yu H. “A Novel Bio-Inspired Approach Based on the Behaviour of Mosquitoes”. Information Sciences, 233, 87-108, 2013.
• Shah-Hosseini H. “The Intelligent water Drops Algorithm: A Nature-Insoired Swarm-Based Optimization Algorithm”. International Journal of Bio-Inspired Computation, 1(1/2), 71-79, 2009.
• Quaarab A, Ahiod B, Yang XS. “Discrete Cuckoo Search Algorithm for the Traveling Salesman Problem”. Neural Computing & Applications, 24, 1659-1669, 2014.
• Lengzhi S, Li Y. “An Improve Cuckoo Search Algorithm for Traveling Salesman Problems”. Applied Mechanics and Materials, 651-653, 2291-2295, 2014.
• Gündüz M, Kıran MS, Özceylan E. “A Hierarchic Approach Based on Swarm Intelligence to Solve the Traveling Salesman Problem”. Turkish Journal of Electrical Engineering & Computer Sciences, 23(1), 103-117, 2015.
• Chen SM, Chien CY. “Solving the Traveling Salesman Problem Based on the Genetic Simulated Annealing Ant Colony System with Particle Swarm Optimization Techniques, With Particle Swarm Optimization Techniques”. Expert System with Applications, 38(12), 14439-11450, 2011.
• Mahi M, Baykan ÖK, Kodaz H. “A New Hybrid Method Bases on Particle Swarm Optimization, Ant Colony Optimization and 3-Opt Algorithms for Traveling Salesman Problem”. Applied Soft Computing, 30, 484-490, 2015.
• Geng, X, Chen Z, Yang W, Shi K, Zhao K. “Solving the Traveling Salesman Problem Based on Adaptive Simulated Annealing Algorithm with Greedy Search”. Applied Soft Computing, 11(4), 3680-3689, 2011.
• Dong G, Guo WW, Tickle K. “Solving The Traveling Salesman Problem Using Cooperative Genetic Ant Systems”. Expert Systems and Applications, 39(5), 5006-5011, 2012.
• Yang XS. “A New Metaheuristic Bat-Inspired Algorithm”. Studies in Computational Intelligence, 284, 65-74, 2010.
• Yang XS. “Bat Algorithm: Literature Review and Applications”. International Journal of Bio-Inspired Computation, 5(3), 141-149, 2013.
• Saji Y, Riffi ME. “Discrete Bat-Inspired Algorithm for Travelling Salesman Problem”. Complex Systems Second World Conference, Agadir, Morocco, 10-12 November, 2014.
• Kumbharana SN, Pandey GM. “Solving Travelling Salesman Problem Using Firefly Algorithm”. International Journal for Research & Advanced Technologies, 2(2), 53-57, 2013.
• Bouzidi M, Riffi MS. “Adaptation of The Harmony Search Algorithm To Solve The Travelling Salesman”. Journal of Theoretical and Applied Information Technology, 62(1), 157-160, 2014.
• Verma OP, Jain R, Chhabra V. “Solution of Travelling Salesman Problem Using Bacterial Foraging Optimisation Algorithm” International Journal of Swarm Intelligence, 1(2), 179-192, 2014.
• Bouzidi A, Riffi MS. “Discrete Cat Swarm Optimization to Resolve the Traveling Salesman Problem”. Interneational Journal of Advanced Research in Computer Science and Software Engineering, 3(9), 13-18, 2013.
• Mo H, Xu L. “Biogeography migration algorithm for traveling salesman problem”. International Journal of Intelligent Computing and Cybernetics, 4(3), 311-330, 2011.
• Cai Y. “Artficial Fish School Algorithm Applied in a Combinatorial Optimization Problem”. International Journal of Intelligent Systems and Applications, 2(1), 37-43, 2010.
• Xing B, Gao WJ. Innovatie Computational Intelligence: A Rough Guide to 134 Clever Algorithms. 1st ed. Switzerland, Springer International Publishing, 2014.
• Yang XS. Nature Inspired Metaheuristic Algorithms. United Kingdom, Luniver Press, 2010.
• Taherdangkoo M, Shirzadi MH, Bagheri MH. “A Novel MetaHeuristic Algorithm for Numerical Function Optimization: Blind, Naked Mole-Rats (BNMR) Algorithm”. Scientific Research and Essays, 7(41), 3566-3583, 2012.
• Taherdangkoo M, Shirzadi MH, Yazdi M, Bagheri MH. “A Robust Clustering Method Based on Blind, Naked Mole-Rats (BNMR) Algortihm”. Swarm and Evolutionary Computation, 10, 1-11, 2013.
• Wikipedia the Free Encyclopedia. “Animal Echolocation”. http://en.wikipedia.org/wiki/Animal_echolocation (27.05.2014).
• Jarvis UM, Sherman PW. “Heterocephalus Glaber”. Mammalian Species, 706, 1-9, 2002.
• Kimchi T, Terkel J. “Mole Rats (Spalax ehrenbergi) Select Bypass Burrowing Strategies in Accordance with Obstacle Size”. Naturwissenschaften, 90(1), 36-39, 2003.
• Kimchi T, Reshef M, Terkel J. “Evidence for the Use of Reflected Self-Generated Seismic Waves for Spatial Orientation in a Blind Subterranean Mammal”. Journal of Experimental Biology, 208, 647-659, 2005.
• WildeScreen Arkive. “Egyptian Blind Mole Rat (Spalax aegyptiacus)”. http://goo.gl/DqqTS5 (29.04.2015).
• Dorigo M, Gambardella LM. “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem”. IEEE Transactions on Evolutionary Computation, 1(1), 53-66 1997.