SDÜ Uluslararası Teknolojik Bilimler Dergisi, Cilt 9, Sayı 2 (2017)

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

Raed AL-BADRI, Tuncay AYDOĞAN

Ö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 System-AS/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.

Anahtar Kelimeler: Genetik Algoritma, Karınca Kolonisi Optimizasyonu, Gezgin Satıcı Problemi

Tam Metin: PDF