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

作　　者：Zakir Hussain Ahmed 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

出　　处：《Computers, Materials & Continua》2024年第5期2399-2425,共27页计算机、材料和连续体（英文）

基　　金：the Deanship of Scientific Research at Imam Mohammad Ibn Saud Islamic University(IMSIU)(Grant Number IMSIU-RP23030).

摘　　要：Genetic algorithms(GAs)are very good metaheuristic algorithms that are suitable for solving NP-hard combinatorial optimization problems.AsimpleGAbeginswith 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.

关 键 词：Travelling salesman problem genetic algorithms crossover operator mutation operator comprehensive sequential constructive crossover insertion mutation 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]