Random Key Cuckoo Search for the Quadratic Assignment Problem
DOI:
https://doi.org/10.14738/tmlai.54.3666Keywords:
Nature-Inspired Metaheuristic, Cuckoo Search, Le´vy Flights, Combinatorial Optimization, Quadratic Assign- ment Problem, Random-Key.Abstract
This paper proposes an adaptation of the Random- Key Cuckoo Search (RKCS) algorithm for solving the famous Quadratic Assignment Problem (QAP). We used a simplified and efficient random-key encoding scheme to convert a continous space (real numbers) into a combinatorial space. We also consid- ered the displacement of a solution in both spaces by using Le´vy flights. The performance of the RKCS for QAP is tested against a set of benchmarks of QAP from the well-known QAPLIB library, and the comparison with a set of other methaheuristics is also carried out.
References
(1) Ahmed, Z.: A simple genetic algorithm using sequential constructive crossover for the quadratic assignment problem. Journal of Scientific and Industrial Research (2014)
(2) Avriel, M.: Nonlinear programming: analysis and methods. Courier
Dover Publications (2012)
(3) Bean, J.: Genetic algorithms and random keys for sequencing and optimization. ORSA journal on computing 6, 154–154 (1994)
(4) Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys (CSUR) 35(3), 268–308 (2003)
(5) Brixius, N.W., Anstreicher, K.M.: The Steinberg wiring problem. SIAM (2001)
(6) Brown, C.T., Liebovitch, L.S., Glendon, R.: Le´vy flights in dobe ju/?hoansi foraging patterns. Human Ecology 35(1), 129–138 (2007)
(7) Burkard, R.E.: Quadratic assignment problems. Springer (2013)
(8) Burkard, R.E., Karisch, S.E., Rendl, F.: Qap–a quadratic assignment problem library. Journal of Global Optimization 10(4), 391–403 (1997)
(9) Burkard, R.E., Offermann, D.M.J.: Entwurf von schreibmaschinen- tastaturen mittels quadratischer zuordnungsprobleme. Zeitschrift fu¨ r Operations Research 21(4), B121–B132 (1977)
(10) Christofides, N., Benavent, E.: An exact algorithm for the quadratic assignment problem on a tree. Operations Research 37(5), 760–768 (1989)
(11) Demirel, N.C¸ ., Toksarı, M.D.: Optimization of the quadratic assignment problem using an ant colony algorithm. Applied Mathematics and Computation 183(1), 427–435 (2006)
(12) Eiselt, H.A., Laporte, G.: A combinatorial optimization problem arising in dartboard design. Journal of the Operational Research Society pp.
–118 (1991)
(13) Elshafei, A.N.: Hospital layout as a quadratic assignment problem.
Operational Research Quarterly pp. 167–179 (1977)
(14) FlNKE, G., Burkard, R., Rendl, F.: Quadratic assignment problems.
Surveys in combinatorial optimization p. 61 (2011)
(15) Gambardella, L.M., Taillard, E., Dorigo, M.: Ant colonies for the quadratic assignment problem. Journal of the operational research society pp. 167–176 (1999)
(16) Helal, A.M., Abdelbar, A.M.: Incorporating domain-specific heuristics in a particle swarm optimization approach to the quadratic assignment problem. Memetic Computing 6(4), 241–254 (2014)
(17) Hochbaum, D.S.: Approximation algorithms for NP-hard problems.
PWS Publishing Co. (1996)
(18) Krarup, J., Pruzan, P.M.: Computer-aided layout design. In: Mathemat- ical programming in use, pp. 75–94. Springer (1978)
(19) Layeb, A.: A novel quantum inspired cuckoo search for knapsack problems. International Journal of Bio-Inspired Computation 3(5), 297–
(2011)
(20) Li, X., Yin, M.: A hybrid cuckoo search via le´vy flights for the permutation flow shop scheduling problem. International Journal of Production Research 51(16), 4732–4754 (2013)
(21) Mamaghani, A.S., Meybodi, M.R.: Solving the quadratic assignment problem with the modified hybrid pso algorithm. In: Application of Information and Communication Technologies (AICT), 2012 6th
International Conference on, pp. 1–6. IEEE (2012)
(22) Maniezzo, V., Colorni, A.: The ant system applied to the quadratic as- signment problem. Knowledge and Data Engineering, IEEE Transactions on 11(5), 769–778 (1999)
(23) Misevicius, A.: Restart-based genetic algorithm for the quadratic assign- ment problem. In: Research and Development in Intelligent Systems XXV, pp. 91–104. Springer (2009)
(24) Nugent, C.E., Vollmann, T.E., Ruml, J.: An experimental comparison of techniques for the assignment of facilities to locations. Operations research 16(1), 150–173 (1968)
(25) Ouaarab, A., Ahiod, B., Yang, X.S.: Discrete cuckoo search algorithm for the travelling salesman problem. Neural Computing and Appli- cations pp. 1–11 (2013). DOI 10.1007/s00521-013-1402-2. URL http://dx.doi.org/10.1007/s00521-013-1402-2
(26) Ouaarab, A., Ahiod, B., Yang, X.S.: Improved and discrete cuckoo search for solving the travelling salesman problem. In: Cuckoo Search and Firefly Algorithm, pp. 63–84. Springer (2014)
(27) Ouaarab, A., Ahiod, B., Yang, X.S.: Random-key cuckoo search for the travelling salesman problem. Soft Computing pp. 1–8 (2014). DOI
1007/s00500-014-1322-9. URL http://dx.doi.org/10.1007/s00500-
-1322-9
(28) Shlesinger, M.F., Zaslavsky, G.M., Frisch, U.: Le´vy flights and related topics in physics. In: Levy flights and related topics in Physics, vol. 450 (1995)
(29) Skorin-Kapov, J.: Tabu search applied to the quadratic assignment problem. ORSA Journal on computing 2(1), 33–45 (1990)
(30) Taillard, E.: Robust taboo search for the quadratic assignment problem.
Parallel computing 17(4), 443–455 (1991)
(31) Taillard, E.: Robust taboo search for the quadratic assignment problem.
Parallel computing 17(4), 443–455 (1991)
(32) Taillard, E.D.: Comparison of iterative searches for the quadratic assign- ment problem. Location science 3(2), 87–105 (1995)
(33) Wilhelm, M.R., Ward, T.L.: Solving quadratic assignment problems by simulated annealing. IIE transactions 19(1), 107–119 (1987)
(34) Yang, X.S., Deb, S.: Cuckoo search via le´vy flights. In: Nature &
Biologically Inspired Computing, 2009. NaBIC 2009. World Congress on, pp. 210–214. IEEE (2009)
