Solving Quadratic Assignment Problem by Using Meta-heuristic Search Method

Authors

Iraq T. Abass Department of Mathematics, College of Education for Pure Sciences, Ibn Al-Haitham University of Baghdad, Iraq
Rawaa Abdulsattar Department of Mathematics, College of Education for Pure Sciences, Ibn Al-Haitham University of Baghdad, Iraq
Leong WJ Department of Mathematics, University Putra Malaysia (UPM) Kuala Lampur 0060, Malaysia

DOI:

https://doi.org/10.30526/36.4.3195

Keywords:

Tabu Search, Quadratic Assignment Problems, Assignment Problems.

Abstract

While analytical solutions to Quadratic Assignment Problems (QAP) have indeed been since a long time, the expanding use of Evolutionary Algorithms (EAs) for similar issues gives a framework for dealing with QAP with an extraordinarily broad scope. The study's key contribution is that it normalizes all of the criteria into a single scale, regardless of their measurement systems or the requirements of minimum or maximum, relieving the researchers of the exhaustively quantifying the quality criteria. A tabu search algorithm for quadratic assignment problems (TSQAP) is proposed, which combines the limitations of tabu search with a discrete assignment problem. The effectiveness of the proposed technique has been compared to well-established alternatives, and its operating principle is illustrated with a numerical example.

After repeating the solution of each issue (8) once and recording the algorithm results, it showed its agreement, once from a total (375) repetition of the experiment while the number of times the Artificial Bee Colony (ABC) arrived (2) as for the Firefly (FA) Algorithm giving (117), also Genetic (GA) and Particle Swarm (PSO) gives (120) and the Tabu Search algorithm (174). The proposed technique (TSQAP) is shown to yield a superior solution with low computing complexity. MATLAB was used to generate all of the findings (R2020b).

References

Hammadi, A. M. K., & Ibrahim, H. A. A. .Proposed Combinatorial Algorithms for Solving Quadratic Assignment Problems. Diyala Journal for Pure Science, 12(3-part 1), (2016).

. Al-Bayati, Hassan Abdel-Sattar, “Using the Compound Harmonious Search Algorithm to Solve the Quadratic Specialization Problem with Practical Application,” Master’s thesis, College of Administration and Economics, University of Baghdad, 2015.

Glover F. -Tabu Search, Part I - ORSA Journal on Computing 1, pp. 190-206, (1989). DOI: https://doi.org/10.1287/ijoc.1.3.190

Burkard, R.E., Karisch, S.E.,and, Rendl, F., "QAPLIB – a Quadratic Assignment Problem Library", Journal of global optimization, 10(4), 391-403, 1996. DOI: https://doi.org/10.1023/A:1008293323270

Sheah, R. H., & Abbas, I. T. (2021). Using Multi-Objective Bat Algorithm For Solving Multi-Objective Non-Linear Programming Problem. Iraqi Journal of Science, 997-1015.

Sattar, H. A., & Cheetar, A. (2019). A New Strategy Based on GSABAT to solve single objective optimization problem. International Journal of Swarm Intelligence Research (IJSIR), 10(3), 1-22.

Atiya, B., Bakheet, A. J. K., Abbas, I. T., Bakar, M., Abu, R., Soon, L. L., & Monsi, M. B. (2016, June). Application of Simulated Annealing to Solve Multi-Objectives for Aggregate Production Planning. In AIP Conference Proceedings (Vol. 1739, No. 1). AIP Publishing. DOI: https://doi.org/10.1063/1.4952566

Glover F. -Tabu Search, Part II - ORSA Journal on Computing 2, pp. 4-32, (1990). DOI: https://doi.org/10.1287/ijoc.2.1.4

Glover F., Taillard E., Laguna M., de Werra D. -Tabu Search -Volume 41 of the Annals of Operations Research, (1993). DOI: https://doi.org/10.1007/BF02078647

Zaidan, A. A., Atiya, B., Abu Bakar, M. R., & Zaidan, B. B. (2019). A New Hybrid Algorithm of Simulated Annealing and Simplex Downhill for Solving Multiple-Objective Aggregate Production Planning on Fuzzy Environment. Neural computing and applications, 31, 1823-1834. DOI: https://doi.org/10.1007/s00521-017-3159-5

Balicki, Jerzy. "Tabu Programming for Multiobjective Optimization Problems." International Journal of Computer Science and Network Security 7.10: 44-51, (2007).

Hansen, Michael Pilegaard. "Tabu Search for Multiobjective Optimization: MOTS." Proceedings of the 13th International Conference on Multiple Criteria Decision Making, (1997).

Yang X-S. Nature-Inspired Metaheuristic Algorithms. Beckington, UK: Luniver Press; 2008.

Bakar, M. R. A., Abbas, I. T., Kalal, M. A., AlSattar, H. A., Bakhayt, A. G. K., & Kalaf, B. A. (2017). Solution for Multi-Objective Optimisation Master Production Scheduling Problems Based on Swarm Intelligence Algorithms. Journal of Computational and Theoretical Nanoscience, 14(11), 5184-5194. DOI: https://doi.org/10.1166/jctn.2017.6729

Abu Bakar, M. R., Bakheet, A. J. K., Kamil, F., Kalaf, B. A., Abbas, I. T., & Soon, L. L. (2016). Enhanced Simulated Annealing for Solving Aggregate Production Planning. Mathematical Problems in Engineering, 2016. DOI: https://doi.org/10.1155/2016/1679315

Abdul-Zahra, I., Abbas, I. T., Kalaf, B. A., Bakar, R. A., June, L. W., & Monsi, M. B. (2016). The Role of Dynamic Programming in the Distribution of Investment Allocations between Production Lines with an Application. International Journal of Pure and Applied Mathematics, 106(2), 365-380. DOI: https://doi.org/10.12732/ijpam.v106i2.2

Fister I, Yang X-S, Brest J. A Comprehensive Review of Firefly Algorithms. Swarm Evol Comput 2013;13:34_46. DOI: https://doi.org/10.1016/j.swevo.2013.06.001

Yang X-S. Firefly Algorithms for Multimodal Optimization. International symposium on stochastic algorithms. Sapporo, Japan: Springer Berlin Heidelberg; 2009. DOI: https://doi.org/10.1007/978-3-642-04944-6_14

Dey, N., Chaki, J., Moraru, L., Fong, S., & Yang, X. S. (2020). Firefly Algorithm and its Variants in Digital Image Processing: A Comprehensive Review. Applications of Firefly Algorithm and Its Variants: Case Studies and New Developments, 1-28.

Kumar, V., & Kumar, D. (2021). A Systematic Review on Firefly Algorithm: Past, Present, and Future. Archives of Computational Methods in Engineering, 28, 3269-3291.

Nayak, J., Naik, B., Pelusi, D., & Krishna, A. V. (2020). A Comprehensive Review and Performance Analysis of Firefly Algorithm for Artificial Neural Networks. Nature-Inspired Computation in Data Mining and Machine Learning, 137-159.

Xiong, T., Bao, Y., & Hu, Z. (2014). Multiple-Output Support Vector Regression with a Firefly Algorithm for Interval-Valued Stock Price Index Forecasting. Knowledge-Based Systems, 55, 87-100. DOI: https://doi.org/10.1016/j.knosys.2013.10.012

Lolla, P. R., Rangu, S. K., Dhenuvakonda, K. R., & Singh, A. R. (2021). A Comprehensive Review of Soft Computing Algorithms for Optimal Generation Scheduling. International Journal of Energy Research, 45(2), 1170-1189.

Dorigo M. Optimization, learning and natural algorithms. PhD thesis. Italy: Dipartimento di Elettronica, Politecnico di Milano; 1992 [in Italian].

Dorigo M, Maniezzo V, Colorni A. An System Optimization by a Colony of Cooperating Agents. IEEE Trans Syst Man Cybern: B 1996;26:29_41. DOI: https://doi.org/10.1109/3477.484436

Dorigo, M., Birattari, M., & Stutzle, T. (2006). Ant Colony Optimization. IEEE computational intelligence magazine, 1(4), 28-39. DOI: https://doi.org/10.1109/CI-M.2006.248054

Yang, X. S. (2020). Nature-inspired optimization algorithms. Academic Press.

Kotary, J., Fioretto, F., Van Hentenryck, P., & Wilder, B. (2021). End-to-end Constrained Optimization Learning: A survey. arXiv preprint arXiv:2103.16378.

Yang, X. S. (2020). Nature-Inspired Optimization Algorithms: Challenges and open problems. Journal of Computational Science, 46, 101104.

Karaboga D. An Idea Based on Honey Bee Swarm for Numerical Optimization. Technical report-tr06, Vol. 200. Kayseri, Tu¨rkiye: Erciyes University; 2005.

Simon, D. (2013). Evolutionary optimization algorithms. John Wiley & Sons.

Van den Bosch, A. (2004). Wrapped Progressive Sampling Search for Optimizing Learning Algorithm Parameters. In Proceedings of the Belgium-Netherlands Conference on Artificial Intelligence, BNAIC'04, 21-22 oktober, 2004 (pp. 219-226). Unknown Publisher.

Yu, F., & Xu, X. (2014). A Short-Term Load Forecasting Model of Natural Gas Based on Optimized Genetic Algorithm and Improved BP Neural Network. Applied Energy, 134, 102-113. DOI: https://doi.org/10.1016/j.apenergy.2014.07.104

Zang, H., Zhang, S., & Hapeshi, K. (2010). A Review of Nature-Inspired Algorithms. Journal of Bionic Engineering, 7(4), S232-S237. DOI: https://doi.org/10.1016/S1672-6529(09)60240-7

Mitchell M. An Introduction to Genetic Algorithm. Cambridge: The MIT Press; 1999.

Thede, S. M. (2004). An Introduction to Genetic Algorithms. Journal of Computing Sciences in Colleges, 20(1), 115-123.

Han, S., & Xiao, L. (2022). An Improved Adaptive Genetic Algorithm. In SHS Web of Conferences (Vol. 140, p. 01044). EDP Sciences.

Niu, X. F., & Ma, W. P. (2022). An Improved Multiple Populations Quantum Genetic Algorithm. Laser Physics Letters, 19(9), 095203.

Zalzala AMS, Fleming PJ. Genetic Algorithms in Engineering Systems. London: Institution of Electrical Engineers; 1997. DOI: https://doi.org/10.1049/PBCE055E

Khatri, K. A., Shah, K. B., Logeshwaran, J., & Shrestha, A. (2023). Genetic Algorithm Based Techno-Economic Optimization of an Isolated Hybrid Energy System. CRF, 1(1), 1.

Sabeti, V., Sobhani, M., & Hasheminejad, S. M. H. (2022). An Adaptive Image Steganography Method Based on Integer Wavelet Transform Using Genetic Algorithm. Computers and Electrical Engineering, 99, 107809.

Lotf, J. J., Azgomi, M. A., & Dishabi, M. R. E. (2022). An Improved Influence Maximization Method for Social Networks Based on Genetic Algorithm. Physical A: Statistical Mechanics and its Applications, 586, 126480.

Liu, Q., Wang, C., Li, X., & Gao, L. (2023). An Improved Genetic Algorithm with Modified Critical Path-Based Searching for Integrated Process Planning and Scheduling Problem Considering Automated Guided Vehicle Transportation Task. Journal of Manufacturing Systems, 70, 127-136.

Burkad.R,,Dell'Amico.M and Martello.S., ."Assignment Problems”, Society for Industrial and Applied Mathematics ,Philadephia, .(2009). DOI: https://doi.org/10.1137/1.9780898717754

Tang, M., Ji, B., Fang, X., & Yu, S. S. (2022). Discretization-Strategy-Based Solution for Berth Allocation and Quay Crane Assignment Problem. Journal of Marine Science and Engineering, 10(4), 495.

Liu, L., Yang, J., Kong, X., & Xiao, Y. (2022). Multi-Mission Selective Maintenance and Repairpersons Assignment Problem with Stochastic Durations. Reliability Engineering & System Safety, 219, 108209.

Zhu, L., Zhou, Y., Jiang, R., & Su, Q. (2023). Surgical Cases Assignment Problem Using A Multi-Objective Squirrel Search Algorithm. Expert Systems with Applications, 121217.

Raheem, S. H., Kalaf, B. A., & Salman, A. N. (2021). Comparison of Some of Estimation Methods of Stress-Strength Model: R= P (Y< X< Z). Baghdad Science Journal, 18(2 (Suppl.)), 1103-1103.

Kalaf, B. A. (2021, May). A New Algorithm to Estimate the Parameters of Nonlinear Regression. In Journal of Physics: Conference Series (Vol. 1879, No. 3, p. 032042). IOP Publishing.

Mahdi, G. J., Kalaf, B. A., & Khaleel, M. A. (2021). Enhanced Supervised Principal Component Analysis for Cancer Classification. Iraqi Journal of Science, 1321-1333.