Appropriate Combination of Crossover Operator and Mutation Operator in Genetic Algorithms for the Travelling Salesman Problem
Zakir Hussain Ahmed1,*, Habibollah Haron2, Abdullah Al-Tameem3
1 Department of Mathematics and Statistics, College of Science, Imam Mohammad Ibn Saud Islamic University (IMSIU), Riyadh, 11432, Kingdom of Saudi Arabia
2 Faculty of Computing, Universiti Teknologi Malaysia, Johor Bahru, 81310, Malaysia
3 College of Computer and Information Sciences, Imam Mohammad Ibn Saud Islamic University (IMSIU), Riyadh, 11432, Kingdom of Saudi Arabia
* Corresponding Author: Zakir Hussain Ahmed. Email: 
Computers, Materials & Continua https://doi.org/10.32604/cmc.2024.049704
Received 16 January 2024; Accepted 28 March 2024; Published online 26 April 2024
Abstract
Genetic algorithms (GAs) are very good metaheuristic algorithms that are suitable for solving NP-hard combinatorial optimization problems. A simple GA begins with a set of solutions represented by a population of chromosomes and then uses the idea of survival of the fittest in the selection process to select some fitter chromosomes. It uses a crossover operator to create better offspring chromosomes and thus, converges the population. Also, it uses a mutation operator to explore the unexplored areas by the crossover operator, and thus, diversifies the GA search space. A combination of crossover and mutation operators makes the GA search strong enough to reach the optimal solution. However, appropriate selection and combination of crossover operator and mutation operator can lead to a very good GA for solving an optimization problem. In this present paper, we aim to study the benchmark traveling salesman problem (TSP). We developed several genetic algorithms using seven crossover operators and six mutation operators for the TSP and then compared them to some benchmark TSPLIB instances. The experimental studies show the effectiveness of the combination of a comprehensive sequential constructive crossover operator and insertion mutation operator for the problem. The GA using the comprehensive sequential constructive crossover with insertion mutation could find average solutions whose average percentage of excesses from the best-known solutions are between 0.22 and 14.94 for our experimented problem instances.
Keywords
Travelling salesman problem; genetic algorithms; crossover operator; mutation operator; comprehensive sequential constructive crossover; insertion mutation
Open Access
Login
Register
Submit a Paper
Propose a Special lssue
Download PDF
Downloads
Citation Tools
