An Improved Adaptive Genetic Algorithm Design for Solving Traveling Salesman Problem

Abstract

Gelişen teknoloji ve bilimle birlikte optimizasyon problemlerinin çözümü için yapılan çalışmalar gün geçtikçe artmaktadır. Yaşamın farklı alanlarında karşılaşılan herhangi bir problemin doğru şekilde ve en kısa sürede çözülebilmesi için optimizasyon kavramına ihtiyaç duyulmaktadır. Optimizasyon, problem çözümleri için karar verme süreçlerini hızlandırmakta ve verilen kararların doğruluğunu arttırmaktadır. Bu çalışmada, birçok gerçek dünya problemine uygulanabilen optimizasyon problemlerinden biri olan Gezgin Satıcı Problemini (GSP) çözmek için kullanılan genetik algoritmanın geliştirilmesi amaçlanmıştır. Genetik Algoritmanın (GA) başarısını artırmak için mevcut literatürdeki hibrit yaklaşımlar yerine doğadaki bireylerin çevre koşullarına adaptasyonuna dayalı yeni bir süreç önerilmektedir. Bu çalışma kapsamında, klasik GA için literatürde var olan farklı çaprazlama ve mutasyon operatörleri kullanılmıştır. Problem çözümü için kullanılan bu operatörler karşılaştırılmış, sonuçlar değerlendirilip sunulmuştur. En uygun çözüme yaklaştıran çaprazlama ve mutasyon operatörleri seçimi yapıldıktan sonra adaptasyon süreci önerilmiştir. Mutasyon operatöründen esinlenerek farklı adaptasyon operatörleri önerilmiştir. Bu adaptasyon operatörleri ile geliştirilen GA'nın performansının, klasik GA'dan daha iyi olduğu karşılaştırmalı deneylerle gösterilmiştir. Çalışma kapsamında kullanılan veri setleri TSPLIB'den alınmış ve yapılan tüm deneysel çalışmaların sonuçları buradaki kriterlere göre değerlendirilmiştir.

Studies for the solution of optimization problems are increasing with the developing technology and science day by day. The term of optimization is needed in order to solve any problem encountered in different areas of life correctly, effectively and in the shortest time. Optimization speeds up the decision-making processes and increases the accuracy of the decision for problem solutions. In this study, it is aimed to develop the genetic algorithm (GA) used to solve the traveling salesman problem (TSP), one of the optimization problems that can be applied to many real world problems. In order to increase the success of the GA, a new process based on the adaptation of individuals in nature to environmental conditions is proposed in the current literature instead of hybrid approaches. In this study, different crossover and mutation operators were used for classical GA that exists in the literature. These operators were compared for problem solving and the results were evaluated and presented. The adaptation process is developed after the selection of crossover and mutation operators approaching the most suitable solution is completed. Different adaptation operators have been developed inspired by the mutation operator. Comparative experiments have shown that the performance of GA developed with these adaptation operators is better than classical GA. The data sets used in the study were taken from TSPLIB and the results of all experimental studies were evaluated according to the criteria there.