Çoklu gezgin satıcı probleminin sezgisel algoritmalar ile çözümü

Günümüzde, biyolojik yapıların oluşturduğu sistemler önem kazanmakta ve araştırmacıların ilgisini çekmektedir. Doğadaki bazı sosyal sistemler, sınırlı yetenekli basit bireyler tarafından oluşturulmalarına rağmen kolektif zekâ davranışları sergilemektedirler. Bu bireylerin kendi içerisindeki organizasyonları ve dolaylı iletişimleri, mühendislikte ve günlük yaşantıda karşılaşılan optimizasyon problemlerinin çözümünde kullanılmaktadır. Ayrıca, yapay zekâ sistemlerinin gelişmesine de katkı sunmaktadırlar. Parçacık Sürü Optimizasyonu (PSO) algoritması kuşların sosyal davranışlarına dayalı bir metasezgisel algoritmadır. Bu tez çalışmasında, Çoklu Gezgin Satıcı Problemini (ÇGSP) çözmek için PSO tabanlı 2 algoritma, APSO ve HAPSO, geliştirilmiştir. ÇGSP'de amaç, başlangıç ve bitiş noktası depo olan m adet satıcı için her bir ara şehir bir kere ziyaret edilmek şartıyla gezilen bütün şehirlerin toplam tur maliyetini minimize etmektir. APSO algoritması ÇGSP'yi çözmek için PSO, 2-opt algoritmalarını ve path-relink, takas operatörlerini kullanmaktadır. Diğer taraftan, HAPSO algoritması ÇGSP'yi çözmek için Açgözlü Rasgeleleştirilmiş Adaptif Arama Prosedürü (GRASP) algoritması, PSO, 2-opt algoritmalarını ve path-relink, takas operatörlerini kullanmaktadır. Deneylerde, 9 Gezgin Satıcı Problemi(GSP) örneği kullanılmıştır ve bu örnekler üzerinde HAPSO algoritması ve APSO algoritması tur grafikleri, çalışma süreleri ve kutu grafikleri açısından 2, 3, 4, 5, 6, 7, 8 ve 9 satıcı için detaylı olarak karşılaştırılmıştır. Tur grafikleri incelendiğinde HAPSO algoritması ile oluşturulan turların uzunluklarının daha kısa olduğu görülmüştür. Algoritmaları kıyaslamak için kullanılan bir diğer yöntem ise kutu grafiğidir. Kutu grafiği sayesinde algoritmaların sonuçları ile ilgili istatistiksel bilgiler görselleştirilmektedir ve böylece bu bilgilerin yorumlanması kolaylaşmaktadır. Kutu grafikleri incelendiğinde, HAPSO algoritmasının daha istikrarlı ve daha gürbüz olduğu görülmektedir. Ayrıca, 5 GSP örneği üzerinde APSO ve HAPSO algoritmaları literatürdeki Genetik Algoritma ve Karınca Koloni Optimizasyonu algoritmaları ile karşılaştırılmıştır. Sonuçlara göre, HAPSO algoritması birçok örnekte diğer algoritmalardan daha iyi performans sergilemiştir. Ayrıca, HAPSO algoritması APSO algoritmasından daha kararlı sonuçlar üretmektedir ve HAPSO algoritmasının performansı tüm ÇGSP örneklerinde daha iyidir. Bu nedenle, HAPSO algoritması APSO algoritmasından daha gürbüzdür.