Best-order crossover for permutation-based evolutionary algorithms

摘要

Permutation-based encoding is used by many evolutionary algorithms dealing with combinatorial optimization problems. An important aspect of the evolutionary search process refers to the recombination process of existing individuals in order to generate new potentially better fit offspring leading to more promising areas of the search space. In this paper, we describe and analyze the best-order recombination operator for permutation-based encoding. The proposed operator uses genetic information from the two parents and from the best individual obtained up to the current generation. These sources of information are integrated to determine the best order of values in the new permutation. In order to evaluate the performance of best-order crossover, we address three well-known \(\mathcal {NP}\)-hard optimization problems i.e. Travelling Salesman Problem, Vehicle Routing Problem and Resource-Constrained Project Scheduling Problem. For each of these problems, a set of benchmark instances is considered in a comparative analysis of the proposed operator with eight other crossover schemes designed for permutation representation. All crossover operators are integrated in the same standard evolutionary framework and using the same parameter setting to allow a comparison focused on the recombination process. Numerical results emphasize a good performance of the proposed crossover scheme which is able to lead to overall better quality solutions.