Combinatorial optimization of permutation-based quadratic assignment problem using optics inspired optimization

Document Type: Research Paper

Authors

1 Department of Industrial Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran.

2 Department of Industerial Engineering, Tarbiat Modares University, Tehran, Iran.

Abstract

A lot of real-world problems such as the assignment of special rooms in hospitals, operating room layout, image processing, etc., could be formulated in terms of Quadratic assignment problem. Different exact methods are suggested to solve these problems, but because of the special structure of these problems, by increasing the size of the problem, finding an exact solution become more complicated and even impossible. So, employing meta-heuristic algorithms is inevitable, due to this problem we use optics inspired optimization (OIO) in this paper. The obtained results and its comparison with the solutions of the central library of Quadratic assignment problem (QAPLIB) show that the proposed algorithm can exactly solve small-sized problems with 100% efficiency while the efficiency of medium-to-large size instances is 96%. Accordingly, one can conclude that the proposed OIO has generally high efficiency for solving permutation-based problems.

Keywords


[1]    Ahmed, Z. H. (2015). An improved genetic algorithm using adaptive mutation operator for the quadratic assignment problem. In Telecommunications and Signal Processing (TSP), th International Conference on, pp. 1-5. IEEE.

[2]    Azarbonyad, H., Babazadeh, R. (2014). A genetic algorithm for solving quadratic assignment problem (QAP). arXiv preprint arXiv:1405.5050.

[3]    Abdel-Baset, M., Gunsekaran, Doaa., El-Shahat, Seyedali Mirjalili.(2018). Integrating the whale algorithm with Tabu search for quadratic assignment problem: A new approach for locating hospital departments, Applied Soft Computing Journal.

[4]    Armour, GC., Buffa, ES. (1963). Heuristic algorithm and simulation approach to relative location of facilities. Journal of Management Science. Volume 9 Issue 2, Pages 294-309.

[5]    Ahmed, Z. H. (2018). A hybrid algorithm combining lexisearch and genetic algorithms for the quadratic assignment problem. Cogent Engineering, 5(1), 1423743.

[6]    Abdel-Baset, M., Wu, H., Zhou, Y., & Abdel-Fatah, L. (2017). Elite opposition flower pollination algorithm for quadratic assignment problem. Journal of Intelligent & Fuzzy Systems, 33(2), 901-911.

[7]    Burkard, R.E. (2002). Selected topics on assignment problems. Discrete Applied Mathematics, 123(1-3), 257-302.

[8]    Billionnet, A., Elloumi, S. (2001). Best reduction of the quadratic semi-assignment problem. Discrete Applied Mathematics, 109(3), 197-213.

[9]    Burkard, R.E. (1975). Numerische Erfahrungen mit Summen- und Bottleneck-Zuordnungsproblemen, in Numerische Methoden bei graphentheoretischen und kombinatorischen Problemen, hrsg. von L. Collatz, G. Meinardus und H. Werner, Birkäuser Verlag Basel-Stuttgart ISNM Bd. 29(1975), 9–25.

[10] Dickey, J.W.,Hopkins, J.W. (1972). Campus building arrangement using topaz. Transportation Research, 6, 59-68.

[11] Dorigo, M., Birattari, M., Stutzle, T.(2006). Ant colony optimization, IEEE Comput. Intell. Mag. 1 (4) pp, 28–39.

[12] Formato, A.   (2007). Central force optimization: a new metaheuristic with applications in applied electromagnetics. Progress in Electromagnetics Research, PIER 77, 425-491.

[13]          Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-We.

[14]    Kashan, A. H., Karimiyan, S., Karimiyan, M., & Kashan, M. H. (2012, November). A modified League Championship Algorithm for numerical function optimization via artificial modeling of the “between two halves analysis”. In The 6th International Conference on Soft Computing and Intelligent Systems, and The 13th International Symposium on Advanced Intelligence Systems (pp. 1944-1949). IEEE.

[15] Helber, S., Böhme, D., Oucherif, F., Lagershausen, S., & Kasper, S. (2016). A hierarchical facility layout planning approach for large and complex hospitals. Flexible Services and Manufacturing Journal, 28(1-2), 5-29.

[16] Haydar, Kiliç., Ugur, Yuzgeç. (2019). Tournament selection based antlion optimization algorithm for solving quadratic assignment problem. Engineering Science and Technology, an International Journal, Volume 22, Issue 2, Pages 673-691.

 

[17] Karaboga, D., Gorkemli, B., Ozturk, C., Karaboga, N. (2014). A comprehensive survey: artificial bee colony (ABC) algorithm and applications, Artif. Intell. Rev. 42 (1), pp 21–57.

[18] Kaveh, M. Khayatazad. (2012). A new meta-heuristic method: Ray Optimization. Computers and Structures, 112-113, 283-294.

[19] Koopmans, T.C., Beckmann, M. (1957). Assignment problems and the location of economic activities, Econometrica 25 (1).

[20] Nanda, S.J., Panda, G. (2014). A survey on nature inspired metaheuristic algorithms for partitional clustering, Swarm Evol. Comput. 16, pp 1–18.

[21] Pradeepmon, T. G., Sridharan, R., & Panicker, V. V. (2018). Development of modified discrete particle swarm optimization algorithm for quadratic assignment problems. International Journal of Industrial Engineering Computations, 9.

[22] Price, K.V., Storn, R.M., Lampinen, J.A. (2005). Differential evolution: a practical approach to global, Optimization vol 28.

[23] Poli,R., Kennedy,J., Blackwell,T .(2007). Particle swarm optimization, Swarm Intell. 1 (1) PP,33–57.

[24] Tamura, K. Yasuda. (2011). Primary study of spiral dynamics inspired optimization. IEEJ Transactions on Electrical and Electronic Engineering, 6, 98-100.

[25] Umut, Tosun. (2015). On the performance of parallel hybrid algorithms for the solution of the quadratic assignment problem”, Engineering Applications of Artificial Intelligence, Vol. 39.

[26] XIA, X., ZHOU, Y. (2018). Performance Analysis of ACO on the Quadratic Assignment Problem. Chinese Journal of Electronics, 27(1).

[27] Burkard, R. E. (1997). Efficiently solvable special cases of hard combinatorial optimization problems. Mathematical programming79(1-3), 55-69.

[28] Kashan, A. H. (2015). A new metaheuristic for optimization: optics inspired optimization (OIO). Computers & Operations Research55, 99-125.

[29] Ugi, I., Brandt, J., Friedrich, J., Gasteiger, J., Jochum, C., Lemmen, P., & Schubert, W. (1979). The deductive solution of chemical problems by computer programs on the basis of a mathematical model of chemistry. In Organic Chemistry (pp. 1303-1318). Pergamon.

[30] Dokeroglu, T., Sevinc, E., & Cosar, A. (2019). Artificial bee colony optimization for the quadratic assignment problem. Applied Soft Computing76, 595-606.

[31] Kılıç, H., & Yüzgeç, U. (2019). Tournament selection based antlion optimization algorithm for solving quadratic assignment problem. Engineering Science and Technology, an International Journal22(2), 673-691.

[32] Konkar, R. (2012). Analysing spherical aberration in concave mirrors. Resonance17(8), 779-790.