An hybrid approach to solve traveling salesman problem using genetic algorithm

Abstract

TSP is a challenging and popular problem from combinatorial optimization. TSP is often tackled with well known heuristic genetic algorithm. Due to the nature of the TSP, traditional GA's stay poor when competing with other approaches. Traditional crossover and mutation operators do not satisfy TSP needs. These operators mostly end up with illegal tours. For this reason, researchers proposed many adaptive elements and cooperation of other algorithms. When the logic of GA is combined with these elements, high quality solutions both in time and path length are obtained. In this research, we analyze successful elements from the literature to use them efficiently in a novel algorithm. We also propose a new selection method which works well with our operators. We extend the abilities of greedy crossover and untwist local operator to utilize in our hybrid approach. Multiple populations collaborate together to achieve better solutions. According to the experimental results, proposed novel elements outperforms their counterparts in the TSP literature. Multiple population approach provides better quality solutions.

Gezgin postacı problemi, kombinasyonel optimizasyon sınıfından zorlu ve popüler bir problemdir. Bu problem sıklıkla genetik algoritma ile çözümlenir. Bu problemin doğası gereği, geleneksel genetik algoritmalar başka yaklaşımlar ile karşılaştırıldığında zayıf kalır. Geleneksel çiftleşme ve mutasyon yöntemleri bu problemin çözümü için yetersiz kalmaktadır. Bu operatörlerin kullanımı çoğunlukla uygun olmayan turlarla sonlanır. Bu sebepten dolayı, araştırmacılar bu probleme uygun olarak genetik algoritma ile kombine çalışacak elemanlar önermişler ve sonucunda tur kalitesi ve zaman açısından kaliteli çözümler çıkarmışlardır. Bu araştırmada, literatürden başarılı elemanları analiz edip kendi önerdiğimiz algoritmamızda efektif olarak kullanmak istedik. Ayrıca, bizim operatörlerimizle iyi çalışan yeni bir seçim yöntemi önerdik. Bizim hibrid yaklaşımımızda kullanmak üzere, greedy çiftleşme ve untwist yerel operatörlerinin yetkinliklerini genişlettik. Çoklu populasyonlar birlikte çalışarak daha iyi sonuçlar vermektedir. Deneysel sonuçlarımıza göre, önerdiğimiz yeni elemanlar literatürdeki muadillerini geride bırakmaktadır.