An hybrid approach to solve traveling salesman problem using genetic algorithm

Abstract

Gezgin postacı problemi, kombinasyonel optimizasyon sınıfından zorlu ve populer bir problemdir. Bu problem sklkla genetik algoritma ile cozumlenir. Bu problemin dogası geregi, geleneksel genetik algoritmalar baska yaklasımlar ile karsılastı- rıldıgında zayıf kalır. Geleneksel ciftlesme ve mutasyon yontemleri bu problemin cozumu icin yetersiz kalmaktadr. Bu operatorlerin kullanımı cogunlukla uygun olmayan turlarla sonlanır. Bu sebepten dolayı, arastrmacılar bu probleme uygunolarak genetik algoritma ile kombine calısacak elemanlar onermisler ve sonucunda tur kalitesi ve zaman acısından kaliteli cozumler cıkarmıslardır. Bu arastırmada, literaturden basarlı elemanlar analiz edip kendi onerdigimiz algoritmamızda efektif olarak kullanmak istedik. Ayrca, bizim operatorlerimizle iyi calsan yeni bir secim yontemi onerdik. Bizim hibrid yaklasmmzda kullanmak uzere, greedy ciftlesme ve untwist yerel operatorlerinin yetkinliklerini genislettik. Coklu populasyonlar birlikte calısarak daha iyi sonuclar vermektedir. Deneysel sonuclarmza gore, onerdigimiz yeni elemanlar literaturdeki muadillerini geride bırakmaktadr.

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 eciently 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.