A crossover operator for improving the efficiency of permutation-based genetic algorithms

Crossover is one of the most important operators in a genetic algorithm by which offspring production for the next generation is performed. There are a number of crossover operators for each type of chromosome representation of solutions that are closely related to different types of optimisation problems. Crossover operation in genetic algorithms, aimed at solving permutation-based combinatorial optimisation problems, is more computationally expensive compared to other cases. This is mainly caused by the fact that no duplicate numbers are allowed in a chromosome and therefore offspring legalisation is needed after each substring exchange. Under these conditions, the time required for performing crossover operation increases significantly with increasing chromosome size, which may deeply affect the efficiency of these genetic algorithms. In this paper, a genetic algorithm that uses path representation for chromosomes and benefits from an alternative form of the well-known partially mapped crossover is proposed. The results of numerical experiments performed on a set of benchmark problems clearly show that the use of this crossover operator can significantly increase the efficiency of permutation-based genetic algorithms and also help in producing good quality solutions. (C) 2020 Elsevier Ltd. All rights reserved.