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)
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2017 Transactions on Machine Learning and Artificial Intelligence
This work is licensed under a Creative Commons Attribution 4.0 International License.
