GA, AS, ACS VE MMAS ALGORİTMALARI PERFORMANSLARININ GEZGİN SATICI PROBLEMİ ÇÖZÜMÜ ÜZERİNDE DEĞERLENDİRİLMESİ

Abstract

Gezgin Satıcı Problemi (GSP) bir çok alanda kendisine uygulama bulmuş önemli bir optimizasyon problemidir. Bu çalışmada, sezgisel optimizasyon algoritmalarından Genetik Algoritma (GA), Karınca Sistemi (Ant SystemAS/ANT), Karınca Koloni Sistemi (Ant Colony System-ACS) ve Max-Min Karınca Sistemi (Max-Min Ant System-MMAS) algoritmaları ile GSP çözülerek, çözümlerin performansları incelenmiştir. Algoritmaların tamamı bir arayüz üzerinde bulunmaktadır. Arayüzde istenilen sayıda rastgele oluşturulan noktalar (şehirler) ile haritalar oluşturulabilmekte veya hazır kütüphanelerden veri seti yüklenebilmektedir. Bu algoritmaların performansları maliyet (yol uzunluğu) ve tekrar sayısı olarak görülebilmektedir. Algoritmalar 36, 56, 76, 101 ve 150 nokta (şehir)’den oluşan 5 harita üzerinde denenmiştir. Her harita çözümünde en az maliyetli çözümü MMAS, en yüksek maliyetli çözümü GA’nın oluşturduğu görülmüştür. Sıralama azdan yükseğe doğru MMAS, AS, ACS ve GA biçiminde gerçekleşmiştir. Algoritmaların TSPLIB kütüphanesi içerindeki ch150 veri seti için performansları literatür ile karşılaştırılmış GA, AS ve MMAS’de daha düşük maliyetlere ulaşıldığı görülmüştür.

Keywords

• Genetik Algoritma
• Karınca Kolonisi Optimizasyonu
• Gezgin Satıcı Problemi

GA, AS, ACS AND MMAS ALGORITHMS PERFORMANCE EVALUATION ON TRAVELING SALESMAN PROBLEM SOLVING

Abstract

Travelling Salesman Problem (TSP) is an important optimization method that have been applied to various areas. In this study, TSP is solved by using several heuristic algorithms like Genetic Algorithm (GA), Ant System (AS/ANT), Ant Colony System (ACS) and Max-Min Ant System (MMAS), performances of these algorithms are then measured. Applied algorithms are implemented inside an interface. Using this interface, maps can be generated with as much as required random points (cities) or loaded from dataset. Performance criterion of the measurement may be seen as the cost (path length) and the number repetitions. Performance measurements of these algorithms are tested on 5 different maps consisting of 36, 56, 76, 101 and 150 points. At each test for solving TSP for each map, the least cost is observed for MMAS and the highest cost is observed for GA. Ascending sort of these algorithms based on their cost is observed as MMAS (least), AS, ACS and GA (highest). The performance of the algorithms for the ch150 dataset in the TSPLIB library was found to be lower in GA, AS and MMAS compared to the literature.

Keywords

• Genetic Algorithm
• Ant Colony Optimization
• Travel Salesman Problem

References

1. Albayrak, M., Allahverdi, N. (2011). Development a new mutation operator to solve the Traveling Salesman Problem by aid of Genetic Algorithms, Expert Systems with Applications 38, 1313–1320.
2. Biroğul S., Güvenç U. (2007). Genetik Algoritma İle Çözümü Gerçekleştirilen Atölye Çizelgeleme Probleminde Ürün Sayısının Etkisi, No. 23, Akademik Bilişim.
3. Chena, S.M., Chiena, C.Y. (2011). Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques, Expert Systems with Applications, Volume 38, Issue 12, November–December, Pages 14439–14450.
4. Dereli T., Daş G. S. (2010). Konteyner Yükleme Problemleri İçin Karınca Kolonisi Optimizasyonu Yaklaşımı, Gazi Üniv. Müh. Mim. Fak. Der. Cilt 25, No 4, 881-894.
5. Dorigo, M., Socha, K., 2013, An Introduction to Ant Colony Optimization, IRIDIA 2013 Technical Report Series ISSN 1781-3794, TR/IRIDIA/2006-01.
6. Dorigo, M. (1992). Optimization, Learning and Natural Algorithms (in Italian). PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Milan, Italy.
7. Dorigo, M., Gambardella, L.M. (1997). Ant Colony System: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1(1):53– 66.
8. Dorigo,M., Maniezzo, V. and Colorni, A. (1991). Positive feedback as a search strategy, Technical Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, Milan, Italy.

9. Dorigo, M., Maniezzo V. and Colorni, A. (1996). Ant System: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics – Part B, 26(1):29– 41.
10. Erdem, Y., Keskintürk, T. (2011). Kanguru Algoritması Ve Gezgin Satıcı Problemine Uygulanması, İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi Yıl:10 Sayı 19 Bahar s.51- 63.
11. Holland, J. H. (1975). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press.
12. Karaboga, D., Gorkemli, B. (2011). A Combinatorial Artificial Bee Colony Algorithm for Traveling Salesman Problem, Innovations in Intelligent Systems and Applications (INISTA), 2011 International Symposium on, 15-18 June, 50 – 53, 978-1-61284-919-5.
13. Kuşcu, Ö., Küçüksille, E.U. (2011). Heuristic Methods in Vehicle Routing Systems, Elektronika ir Elektrotechnika, January, No.1, 65-70.
14. La Maire, B.F.J., Mladenov, V.M. (2012). Comparison of Neural Networks for Solving the Travelling Salesman Problem, Neural Network Applications in Electrical Engineering (NEUREL), 2012 11th Symposium on, 20-22 Sept., 21 – 24, 978-1-4673-1569-2.
15. Puris, A., Bello, R. & Herrea, F. (2010). Analysis of the efficacy of a Two-Stage methodology for ant colony optimization: Case of study with TSP and QAP, Expert Systems with Applications 37, 5443–5453.
16. Saiyed, A. R. (2012). The Traveling Salesman Problem, 1-15.
17. Stützle, T. and Hoos, H.H. (2000). MAX–MIN Ant System, Future Generation Computer Systems, 16(8):889–914.
18. TSP Test Data. (2009). http://www.math.uwaterloo.ca/tsp/data/ (Erişim: 01.08.2016)
19. Wang, Y. (2014). The Hybrid Genetic Algorithm with two Local Optimization Strategies for Traveling Salesman Problem, Computers & Industrial Engineering, Volume 70, April 2014, Pages 124–133.