Abstract The quadrati c 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 Genetic Algo rithm (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 m odel we propose three new crossover operators to enhance g enetic algorithm for the quadratic assignment problem. The first and second ones, called Highest Frequency crossover (HFX) and Greedy HFX (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 ope rators, namely, One Point crossover ( OPX ), Swap Path crossover (SP X) and Sequential Constructive crossover (SCX ), show effectiveness of our proposed operators both in terms of solution quality and computational time.

References

[1] Ahmed Z. , A Simple Genetic Algorithm Using Seq uential Constructive Crossover for the Quadratic Assignment Problem , Journal of Scientific and Industrial Research, vol. 73, no. 12, pp. 763- 766, 2014.

[2] Ahu ja R., Orlin J. , and Tiwari A., A Greedy Genetic Algorithm for the Quadratic Assignment Problem , Journal of Computers and Operations Research, vol. 27, no.10, pp. 917- 934, 2000.

[3] Benlic U. and Hao J., Breakout Local Search for the Quadratic Assignment Problem, Applied Mathematics and Computation , Journal of Applied Mathematics and Computation, vol. 219, no. 9, pp. 4800-4815, 2013.

[4] Brixius N. and Anstreicher K., The Steinberg Wiring Problem , Optimization Online , 2001.

[5] Burkard R ., Karisch S. , and Rendl F., QAPLIB -a Quadratic Assignment Problem Library , Journal of Global Optimization, vol. 10, pp. 391- 403, 1997.

[6] Carlson R. and Nemhauser G., Scheduling to Minimize Interaction Cost , Operations Research , vol. 14, no. 1, pp. 52- 58, 1966.

[7] Davis L., Job -shop Scheduling with Genetic Algorithms, in Proceeding of the 1st International Conference on Genetic , NJ, pp. 136- 140, 1985.

[8] Drezner Z., Extensive Experiments with Hybrid Genetic Algorithms for the Solution of the Quadratic Assign ment Problem, Journal of Computers and Operations Research , vol. 35, no. 3, pp.717- 736, 2008.

[ 9] Drezner Z. , A new genetic algorithm for the quadratic assignment problem , Informs Journal on Computing, vol. 15, no. 3, pp. 320- 330, 2003.

[ 10] Drezner Z. and Misev icius A., Enhancing the Performance of Hybrid Genetic Algorithms by Differential Improvement , Computers and Operations Research , vol. 40, no. 4, pp. 1038- 1046, 2013 .

[ 11] Elshafei A. , Hospital Layout as a Quadratic Assignment Problem , Journal of Operations Research Quarterly, vol. 28, no. 1, pp. 167-179, 1977.

[ 12] Geo rion A. and Graves G., Scheduling Parallel Production Lines with Changeover Costs: Practical Applications of a Quadratic Assignment/LP Approach, Journal of Operations Research , vol. 24, no. 4, pp. 595- 610, 1976.

[ 13] Goldberg D., Genetic Algorithms i n Search, Optimization, and Machine Learning, Addison- Wesley Longman, 1989. 145 Frequency Model Based Crossover Operators for Genetic Algorithms Applied to the Quadratic

[14] Goldberg D. and Lingle R., Alleles, Loci and the Travelling Salesman Problem, in Proceeding of 1 st International Conference on Genetic Al gorithms, Hilladale , NJ, pp. 154- 159, 1985.

[ 15] Holland J., Adaptation in Natural and Artificial Systems, MIT Press, 1975.

[ 16] Javidi M. and Hosseinpourfard R., Chaos Genetic Algorithm Instead Genetic Algorithm , The International Arab Journal of Information Technology , vol. 12, no. 2, pp. 163 -168, 2015.

[ 17] Koopmans T. and Beckman M. Assignment P roblems and the L ocation of Economic A ctivities , Journal of Econometric , vol. 25, no. 1, pp. 53- 76, 1957.

[ 18] Lim M., Yuan Y., and Omatu S., Efficient Genetic Alg orithms using Simple Genes Exchange Local Search Policy for the Quadratic Assignment Problem , Journal of Computational Optimization and Applications , vol. 15, no. 3, pp. 249- 268, 2000.

[ 19] Merz P. and Freisleben B., Fitness Landscape Analysis and Mimetic Algorithms for the Quadratic Assignment Problem , IEEE Transactions on Evolutionary Computation , vol. 4, pp. 337- 352, 2000.

[ 20] Migkikh V. , Topchy A., Topchy E., Kureichik V. , and Tetelbaum A. , Combined Genetic and Local Search Algorithm for the Quadratic Assi gnment Problem , in Proceedings of the Second Asia -Pacific Conference on Genetic Algorithms and Applications (APGA 00) , pp. 144- 151, 2000.

[ 21] Misevicius A., An Improved Hybrid Optimization Algorithm for the Quadratic Assignment Problem Journal of Mathematical Modelling and Analysis , Journal of Mathematical Modelling and Analysis , vol. 9, no. 2, pp. 149- 168, 2004.

[ 22] Misevicius A. and Kilda B., Comparison of Crossover Operators for the Quadratic Assignment Problem , Journal of Information Technology and Cont rol, vol. 34, no. 2, pp. 109- 119, 2005.

[ 23] Misevicius A. and Rubliauskas D., Performance of Hybrid Genetic Algorithm for the Grey Pattern Problem , Journal of Information Technology and Control , vol. 34, no. 1, pp. 15 -24, 2005.

[ 24] M isevicius A. and Guogis E., Communications in Computer and Information Science , Spring Link, 2012.

[ 25] Oliver I., Smith D., and Holland J., A Study of Permutation Crossover Operators on t he Travelling Salesman Problem, in Proceedi ngs of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, NJ, pp. 224- 230, 1987.

[26] Panos M. , Franz R. , and Henry W. , The Quadratic Assignment Problem: A Survey and Recent Developments, Journal of DIMACS Series in Discrete Mathematics and Theoretical Computer Science , vol. 16, pp. 1- 42, 1994.

[ 27] Tate D. E. and Smith A.E., A genetic approach to the quadratic assignment problem , Journal of Computers and Operations Research, vol. 22, no. 1, pp. 73- 83, 1995.

[ 28] V zquez M. and Whitley L. D., A Hybrid Genetic Algorithm for th e Quadratic Assignment Problem , in Proceedings of the 2nd Annual Conference on Genetic and Evolutionary Computation, Las Vegas, pp. 135- 142, 2000. Hachemi Bennaceur is Full Professor in Computer cience Department of Al Imam Mohammad bin Saud Islamic University. He worked for over twenty years in various academic institutions in France. He was promoted to full professor in 2007 at Artois University (Lille -Nord academy, France). During the same period he was successively researcher at the Computer Science Lab of Paris -Nord University (LIPN), and then at the Research Center of Computer Science of Lens (CRIL). His main research topics involve Constraint Programming and Reasoning with Propositional Logic (SAT). More recently, he is interested in Robot Path Planning and Multi -Robots Task Allocation applications. Zakir Hussain Ahmed is an Associate Professor in the Department of Computer Science at Al Imam Mohammad Ibn Saud Islamic University, Saudi A rabia. He obtained MSc in Mathematics (Gold Medalist), MTech in Information Technology and PhD in Mathematical Sc iences from Tezpur University (Central), Assam, India. He served in various institutions in India. His research interests include artificial intelligence, discrete optimization, digital image processing and pattern recognition. He has publications in the f ields of artificial intelligence, discrete optimization and image processing.