Frequency Model Based Crossover Operators for Genetic Algorithms Applied To the Quadratic Assignment Problem

Hachemi Bennaceur and Zakir Ahmed

Department of Computer Science, Al Imam Mohammad Ibn Saud Islamic University, Saudi Arabia

 Abstract: The quadratic assignment problem aims to find an optimal assignment of a set of facilities to a set of locations that minimizes an objective function depending on the flow between facilities and the distance between locations. In this paper we investigate a Genetic Algorithm (GA) using new crossover operators to guide the search towards unexplored regions of the search space. First, we define a frequency model which keeps in memory a frequency value for each pair of facility and location. Then, relying on the frequency model we propose three new crossover operators to enhance genetic algorithm for the quadratic assignment problem. The first and second ones, called Highest Frequency crossover (HFX) and Greedy Highest Frequency crossover (GHFX), are based only on the frequency values, while the third one, called Highest Frequency Minimum Cost crossover (HFMCX), combines the frequency values with the cost induced by assigning facilities to locations. The experimental results comparing the proposed crossover operators to three efficient crossover operators, namely, One Point crossover (OPX), Swap Path crossover (SPX) and Sequential Constructive crossover (SCX), show effectiveness of our proposed operators both in terms of solution quality and computational time.

Keywords: Frequency model, quadratic assignment problem, GA, HFX.