Dergiler / Uluslararası Teknolojik Bilimler Dergisi / 2017 / Cilt: 9 - Sayı: 2
GA, AS, ACS VE MMAS ALGORİTMALARI PERFORMANSLARININ GEZGİN SATICI PROBLEMİ ÇÖZÜMÜ ÜZERİNDE DEĞERLENDİRİLMESİ
- Sayfa
- 50–60
- DOI
- —
Özet
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.
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.