A New Recombination Operator for the Genetic Algorithm Solution of the Quadratic Assignment Problem

Abstract

The Quadratic Assignment Problem (QAP) is a well known combinatorial optimization problem with a diverse set of applications. It can be transformed into many problems such as the travelling salesman, weapon target assignment, and query optimization in distributed databases. Exhaustive search methods are inadequate to solve large data sets. Genetic algorithms and tabu search meta-heuristics may provide near optimal solutions for large QAP instances taking a reasonable time to complete. In this paper, we present a new recombination operator based on Order-1 crossover algorithm. The suggested approach runs quick sort partitioning algorithm to generate different chromosomes from partitions. The minimum cost partition produces offsprings with the other chromosome. The proposed approach shows outstanding performance especially for instance sizes smaller than 50 with respect to the optimal results proposed in QAPLIB. (C) 2014 Published by Elsevier B.V.