Reducing Premature Convergence Problem in Genetic Algorithm: Application on Travel Salesman Problem


  •  Saleem Ramadan    

Abstract

Genetic algorithm (GA) is based on Darwin’s natural selection theory and is used extensively in combinatorial problems as these problems are demanding in terms of computational time. GA shows very good results in terms of both computational time and quality of solution for combinatorial problems as GAs have some traits that make them one of the best evolutionary algorithms (EAs). The use of both mutation and crossover operators make them, relative to other EAs, highly immune to be trapped in a local optima and thus less vulnerable to premature convergence problem. Traditionally, the solution for premature convergence problem is to maintain a certain degree of diversity of the GA’s population without affecting the convergence process itself. In this paper, this concept has been practiced where Frequency Crossover strategy (FC) along with nine different mutation strategies have been proposed and applied to travel salesman problem (TSP) to reduce the effect of premature convergence problem. Three sets of benchmark data have been used to test the effectiveness of this GA. The results showed that both the nine mutation types and the FC are essential for the proposed GA to perform well. While this GA has been applied on TSP in this paper, it is also believed that it is applicable on any problem that has an Order-Based chromosome representation.



This work is licensed under a Creative Commons Attribution 4.0 License.
  • ISSN(Print): 1913-8989
  • ISSN(Online): 1913-8997
  • Started: 2008
  • Frequency: quarterly

Journal Metrics

WJCI (2020): 0.439

Impact Factor 2020 (by WJCI): 0.247

Google Scholar Citations (March 2022): 6907

Google-based Impact Factor (2021): 0.68

h-index (December 2021): 37

i10-index (December 2021): 172

(Click Here to Learn More)

Contact