Gezgin satıcı probleminde genetik algoritmalar için yeni seçilim operatörlerinin geliştirilmesi

Abstract

Gezgin satıcı problemi (GSP) rota planlama, baskı devre kart tasarımı, bilgisayar kablolama, üretim planlama gibi birçok gerçek hayat problemlerinde kullanılmaktadır. GSP’nin çözümü için meta-sezgisel algoritmalar yani, Tavlama benzetimi, karınca kolonisi, sinir ağları, tabu arama, parçacık sürüsü optimizasyonu ve genetik algoritma kullanılmaktır. Son yıllarda, araştırmacılar genetik algoritması üzerinde keşif ve sömürü arasındaki dengenin iyileştirilmesi amacıyla, seçilim, mutasyon ve çaprazlama operatörleri önermişlerdir. Literatürde yer alan 6 seçilim operatörü, 6 mutasyon operatörü ve 11 çaprazlama operatörü uygulanmış ve yöntemlerin performansları yakınsama oranları ve hesaplama süreleri açısından değerlendirilmiştir. Ayrıca keşif ve sömürü dengesini iyileştirmek amacıyla, Keşif-Sömürü Denge Seçim (KSDS) ve Hibrit Seçim operatörleri (HS) önerilmiştir. Yöntemler, 30 farklı TSPLIB veri setinde ve çelik üretim verilerinde test edilmiş ve kritik fark diyagramları kullanılarak yöntemler arasındaki istatiksel farklar görselleştirilmiştir. Ayrıca yöntemlerin birbirinden ne derece iyileştirilmiş olduğunu gözlemlemek için t-test istatiksel testleri yapılmıştır. Sonuçlar önerilen seçim operatörlerinin literatürdeki diğer yöntemlere kıyasla daha etkili performans gösterdiği görülmüştür. Mutasyon yöntemlerinde Değişim Mutasyon (DM) operatörü en etkili sonuçları verirken, çaprazlama yöntemlerinde ise Geliştirilmiş Açgözlü Çaprazlama (GAÇ) yöntemi en iyi sonuçları vermiştir. Traveling salesman problem (TSP) is used in many real-world problems such as route planning, printed circuit board design, computer wiring, production planning. Meta-heuristic algorithms such as simulated annealing, ant colony, neural networks, tabu search, particle swarm optimization and genetic algorithm are used to solve TSP. In recent years, researchers have proposed selection, mutation and crossover operators in order to improve the balance between exploration and exploitation on genetic algorithm. 6 selection operators, 6 mutation operators and 11 crossover operators in the literature were applied and the performances of the methods were evaluated in terms of convergence rates and computation times. In addition, Exploration-Exploration Balance Selection (EEBS) and Hybrid Selection (HS) operators were proposed to improve the balance between exploration and exploitation. The methods were tested on 30 different TSPLIB data sets and steel production data and statistical differences between the methods were visualized using critical difference diagrams. In addition, t-test statistical tests were performed to observe to what extent the methods were improved from each other. The results show that the proposed selection operators perform better than other methods in the literature. In mutation methods, the Swap Mutation (SWPM) operator gives the most effective results, while in crossover methods, the Improved Greedy Crossover (IGX) method gives the best results.