Afrika Akbabaları Optimizasyonu Kullanılarak Gezgin Satıcı Probleminin Çözümü için Verimli Bir Başlangıç Popülasyonu Oluşturma

Abstract

Günümüzde teknolojinin ve bilimin hızla ilerlemesi, optimizasyon problemlerinin çözümüne yönelik yeni yaklaşımların geliştirilmesine olanak sağlamaktadır. Optimizasyon, yaşamın çeşitli alanlarında karşılaşılan karmaşık problemlerin doğru ve etkin bir şekilde çözülmesine olanak tanıyarak karar süreçlerinin hızlanmasına katkıda bulunmada ve sonuçların doğruluğunu artırmaktadır. Bu çalışmada, AVOA(Afrika Akbabaları Optimizasyonu) algoritması, birçok gerçek dünya probleminde olduğu gibi GSP(Gezgin Satıcı Problemi) için uyarlanmıştır. GSP, bir satıcının tüm şehirleri yalnızca bir defa ziyaret edip başlangıç konumuna geri dönerek toplam yolculuk maliyetini en aza indirmeyi amaçlayan klasik bir kombinatoryal optimizasyon problemidir. Algoritmanın performansını artırmak için başlangıç popülasyonunun oluşturulmasında Sobol dizileri kullanılmış, ayrıca başlangıç popülasyonunun iyileştirilmesi amacıyla DBSCAN ve En Yakın Komşu (EYK) algoritmaları entegre edilmiştir. Sobol dizilerinin düşük sapma özelliği, çözüm uzayını homojen biçimde tarayarak algoritmanın çözüm kalitesine katkı sağlamıştır. Çalışma kapsamında, TSPLIB'den alınan 51 şehirlik(eil51) ve 280 şehirlik(a280) veri setleri kullanılarak Sobol tabanlı AVOA algoritmasının çeşitli varyantlarının performansı değerlendirilmiştir. Elde edilen bulgular, Sobol dizileriyle oluşturulan başlangıç popülasyonunun, rastgele yaklaşımlara kıyasla daha yüksek çözüm kalitesi ve daha tutarlı sonuçlar sağladığını ortaya koymuştur. Özellikle AVOA+EYK+SOBOL yaklaşımı, her iki veri setinde de en uygun çözümlerden bazılarını sunmuş ve düşük sapma ile standart sapma değerleri sayesinde istikrarlı sonuçlar elde edilmiştir. Ancak, MAGA algoritmasının en düşük ortalama çözüm değeri ile genel anlamda en başarılı sonucu verdiği gözlemlenmiştir. Bu bulgular, sezgisel ve meta-sezgisel algoritmaların optimizasyon problemlerindeki etkinliğini bir kez daha teyit etmektedir. Çalışma kapsamında, Sobol dizilerinin başlangıç popülasyonu oluşturmada sağladığı avantajlar ortaya konmuş ve AVOA algoritmasının, GSP gibi karmaşık optimizasyon problemlerine başarılı biçimde uyarlanabileceği gösterilmiştir. Bununla birlikte, başlangıç popülasyonunda yerel iyileştirme algoritmalarının entegrasyonu sayesinde AVOA'nın performansında belirgin bir artış sağlanmış, çözüm kalitesinde de anlamlı iyileşmeler elde edilmiştir. Gelecekte gerçekleştirilecek çalışmalarda, farklı hibrit optimizasyon yöntemlerinin değerlendirilmesi önerilmektedir.In recent years, the rapid advancement of science and technology has facilitated the development of novel approaches for addressing optimization problems. Optimization plays a critical role in solving complex problems across various domains by enhancing both the efficiency of decision-making processes and the accuracy of results. This study investigates the application of the African Vultures Optimization Algorithm (AVOA) to the Traveling Salesman Problem (TSP), a classical combinatorial optimization problem that seeks to minimize the total travel cost by requiring a salesman to visit each city exactly once and return to the point of origin. To improve the algorithm's performance, Sobol sequences were employed for generating the initial population, to improve the initial population, the DBSCAN and Nearest Neighbor (NN) algorithms were integrated.. The low-discrepancy property of Sobol sequences contributed to a more uniform exploration of the solution space, thereby enhancing solution quality. The empirical evaluation utilized two benchmark datasets from TSPLIB, namely eil51 (51 cities) and a280 (280 cities), to assess the performance of various Sobol-based AVOA variants. The results demonstrated that the initial population generated via Sobol sequences yielded superior solution quality and more stable outcomes compared to random initialization methods. Notably, the AVOA+NN+SOBOL variant produced some of the best solutions across both datasets, achieving robust performance characterized by low deviation and standard deviation values. However, the MAGA algorithm was found to deliver the overall best performance with the lowest mean solution value. Overall, the findings reaffirm the effectiveness of metaheuristic algorithms in addressing complex optimization problems. This study highlights the potential of Sobol sequences in enhancing initial population diversity and confirms the adaptability of the AVOA algorithm to challenging problems such as the TSP. Furthermore, the integration of local improvement techniques was shown to substantially improve the algorithm's performance and solution quality. Future research is encouraged to explore alternative hybrid optimization strategies to further advance the state of the art in this field.