Investigation Of Crossover Operators Using Genetic Algorithms In The Solution Of The Traveling Salesman Problem Based On Case Studies

Gezgin Satıcı Probleminin Genetik Algoritmalar Kullanarak Çözümünde Çaprazlama Operatörlerinin Örnek Olaylar Bazlı İncelenmesi

Abstract

The Traveling salesman problem is a difficult (NP-hard) problem that has been studied intensively by researchers and academics in the field of optimization for many years. Genetic algorithms are one of the best methods used to solve various NP-hard problems, such as TSP (traveling salesman problem). Many crossover operators have been proposed for the tsp problem and new ones have been proposed in each study. Our aim in this study is to guide the researchers who want to work on this subject by taking out a detailed inventory of the TSPLIB case studies and the crossover operators that are used in the studies that are investigating the tsp solution. Studies in the literature have been examined in a wide range of contexts (based on keyword and year), and the sample events and the results have been analyzed.

Özet

Gezgin satıcı problemi, optimizasyon alanında araştırmacı ve akademisyenler tarafından üzerinde uzun yıllardır yoğun olarak çalışılan çözümü zor (NP-hard) bir problemdir. Genetik algoritmalar GSP (gezgin satıcı problemi) gibi çeşitli NP-hard problemleri çözmek için kullanılan en iyi yöntemlerden biridir. GSP problemi için çok sayıda çaprazlama operatörü önerilmiştir ve her çalışmada yenileri önerilmeye devam etmektedir. Bu çalışmanın amacı GSP çözümünü araştıran çalışmalarda kullanılan TSPLIB örnek olaylarının ve incelenen çaprazlama operatörlerinin detaylı bir envanterini çıkarmak ve bu konuda çalışmak isteyen araştırmacılara yön göstermektir. Literatürdeki çalışmalar geniş bir kapsamda (anahtar kelime ve yıl bazında) incelenerek ortak kullanılan örnek olayların ve bulunan sonuçların analizi yapılarak tablolaştırılmıştır.

Keywords: Gezgin Satıcı Problemi, Genetik Algoritmalar, Çaprazlama operatörü, TSPLIB