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

Tevfik YILDIRIM, (Pamukkale Üniversitesi, Denizli, Türkiye)
Can Berk KALAYCI, (Pamukkale Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Denizli, Türkiye)
Özcan MUTLU (Pamukkale Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Denizli, Türkiye)
Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi
6 2
Yıl: 2016 Cilt: 22 Sayı: 1 Sayfa Aralığı: 64 - 70 Metin Dili: Türkçe İndeks Tarihi: 29-07-2022

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 Kelime:

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

Ö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
Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık
  • 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), 41- 51, 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 Applied Computation, 216(1), 125-137, 2010. Mathematics and
  • 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, 141- 152, 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, Techniques". Expert System with Applications, 38(12), 14439-11450, 2011. Swarm Optimization
  • 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.
  • 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.
APA YILDIRIM T, Kalayci C, Mutlu Ö (2016). Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması. , 64 - 70.
Chicago YILDIRIM Tevfik,Kalayci Can,Mutlu Özcan Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması. (2016): 64 - 70.
MLA YILDIRIM Tevfik,Kalayci Can,Mutlu Özcan Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması. , 2016, ss.64 - 70.
AMA YILDIRIM T,Kalayci C,Mutlu Ö Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması. . 2016; 64 - 70.
Vancouver YILDIRIM T,Kalayci C,Mutlu Ö Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması. . 2016; 64 - 70.
IEEE YILDIRIM T,Kalayci C,Mutlu Ö "Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması." , ss.64 - 70, 2016.
ISNAD YILDIRIM, Tevfik vd. "Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması". (2016), 64-70.
APA YILDIRIM T, Kalayci C, Mutlu Ö (2016). Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 22(1), 64 - 70.
Chicago YILDIRIM Tevfik,Kalayci Can,Mutlu Özcan Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi 22, no.1 (2016): 64 - 70.
MLA YILDIRIM Tevfik,Kalayci Can,Mutlu Özcan Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, vol.22, no.1, 2016, ss.64 - 70.
AMA YILDIRIM T,Kalayci C,Mutlu Ö Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi. 2016; 22(1): 64 - 70.
Vancouver YILDIRIM T,Kalayci C,Mutlu Ö Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi. 2016; 22(1): 64 - 70.
IEEE YILDIRIM T,Kalayci C,Mutlu Ö "Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması." Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 22, ss.64 - 70, 2016.
ISNAD YILDIRIM, Tevfik vd. "Gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması". Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi 22/1 (2016), 64-70.
Sayfa Oluşturulma Tarihi
23-04-2024 0:7

İLETİŞİM

TÜBİTAK ULAKBİM TR Dizin

Yüzüncüyıl, İşçi Blokları Mahallesi

Muhsin Yazıcıoğlu Caddesi No:51/C

06530 Çankaya / ANKARA +90 (312) 298 92 00

trdizin@tubitak.gov.tr

TÜBİTAK ULAKBİM Ulusal Akademik Ağ ve Bilgi Merkezi Cahit Arf Bilgi Merkezi © Tüm Hakları Saklıdır. Gizlilik Politikası Kullanım Şartları