COMPARISON OF CROSSOVER OPERATORS FOR THE QUADRATIC ASSIGNMENT PROBLEM

Abstract

Crossover (i.e. solution recombination) operators play very important role by constructing competitive genetic algorithms (GAs). In this paper, the basic conceptual features and specific characteristics of various crossover operators in the context of the quadratic assignment problem (QAP) are discussed. The results of experimental comparison of more than 10 different crossover operators for the QAP are presented. The results obtained demonstrate high efficiency of the crossovers with relatively low degree of disruption, namely, the swap path crossover (SPX), the cohesive crossover (COHX), the one point crossover (OPX). Another promising operator is so-called multiple parent crossover (MPX) operator based on special type of recombination of several solutions-parents. The results from the experiments show that MPX operator enables to achieve better solutions than other operators tested.