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.
- Full Text:
PDF
- DOI:10.5539/cis.v6n1p47
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)
Index
- Academic Journals Database
- BASE (Bielefeld Academic Search Engine)
- CiteFactor
- CNKI Scholar
- COPAC
- CrossRef
- DBLP (2008-2019)
- EBSCOhost
- EuroPub Database
- Excellence in Research for Australia (ERA)
- Genamics JournalSeek
- Google Scholar
- Harvard Library
- Infotrieve
- LOCKSS
- Mendeley
- PKP Open Archives Harvester
- Publons
- ResearchGate
- Scilit
- SHERPA/RoMEO
- Standard Periodical Directory
- The Index of Information Systems Journals
- The Keepers Registry
- UCR Library
- Universe Digital Library
- WJCI Report
- WorldCat
Contact
- Chris LeeEditorial Assistant
- cis@ccsenet.org