Open Access

ARTICLE

Appropriate Combination of Crossover Operator and Mutation Operator in Genetic Algorithms for the Travelling Salesman Problem

by Zakir Hussain Ahmed^1,*, Habibollah Haron², Abdullah Al-Tameem³

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 2024, 79(2), 2399-2425. https://doi.org/10.32604/cmc.2024.049704

Received 16 January 2024; Accepted 28 March 2024; Issue published 15 May 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

---