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

Abstract

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.

Nowadays, systems formed by biological structures have gained importance and attracted the attention of researchers. Some social systems in nature exhibit collective intelligence, although they are created by simple individuals with limited abilities. The organizations of these individuals and their indirect communication among these individuals are used to solve the optimization problems encountered in engineering and daily life. They also contribute to the development of the artificial intelligence systems. The Particle Swarm Optimization (PSO) algorithm which is a meta-heuristic algorithm based on the social behavior of birds. In this article, 2 algorithms based on PSO, called APSO and HAPSO, were proposed to solve the Multiple Travelling Salesman Problem (MTSP). The aim in the MTSP is to find the tours for all m salesmen, who all start and end at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The APSO algorithm is based on the PSO and 2-opt algorithms, the path-relink and swap operators. On the other hand, the HAPSO algorithm is based on the GRASP, PSO and 2-opt algorithms, the path-relink and swap operators. In the experiments, the 9TSP instances were used and the HAPSO and APSO algorithms were compared in detail on these samples for the 2, 3, 4, 5, 6, 7, 8 and 9 salesmen in terms of the tour charts, the computational times and the boxplots. When the tour graphs are examined, the lengths of the tours created by HAPSO algorithm are shorter. Another method used to compare algorithms is the boxplot. Through the box graph, the statistical information about the results of the algorithms are visualized and thus the interpretation of this information is easy. When the boxplots are examined, it is seen that HAPSO algorithm is more stable and more robust. In addition, on the 5 TSP instances the HAPSO and APSO algorithms were compared with the Genetic Algorithm and Ant Colony Optimization algorithms in the literature. According to the results, the HAPSO algorithm has the better performance than the other algorithms on the most instances. In addition, the HAPSO algorithm produces more stable results than the APSO algorithm and the performance of the HAPSO algorithm is better in all the MTSP instances. Therefore, the HAPSO algorithm is more robust than the APSO algorithm.