A NOVEL DISCRETE RAT SWARM OPTIMIZATION ALGORITHM FOR THE QUADRATIC ASSIGNMENT PROBLEM

Toufik Mzili, Ilyass Mzili, Mohammed Essaid Riffi, Dragan Pamucar, Vladimir Simic, Mohamed Kurdi

DOI Number
https://doi.org/10.22190/FUME230602024M
First page
529
Last page
552

Abstract


The quadratic assignment problem (QAP) is an NP-hard problem with a wide range of applications in many real-world applications. This study introduces a discrete rat swarm optimizer (DRSO)algorithm for the first time as a solution to the QAP and demonstrates its effectiveness in terms of solution quality and computational efficiency. To address the combinatorial nature of the QAP, a mapping strategy is introduced to convert real values into discrete values, and mathematical operators are redefined to make then suitable for combinatorial problems. Additionally, a solution quality improvement strategy based on local search heuristics such as 2-opt and 3-opt is proposed. Simulations with test instances from the QAPLIB test library validate the effectiveness of the DRSO algorithm, and statistical analysis using the Wilcoxon parametric test confirms its performance. Comparative analysis with other algorithms demonstrates the superior performance of DRSO in terms of solution quality, convergence speed, and deviation from the best-known values, making it a promising approach for solving the QAP.


Keywords

Discrete rat swarm optimizer, Quadratic assignment problem, Combinatorial optimization, Swarm intelligence

Full Text:

PDF

References


Koopmans, T.C., Beckmann, M., 1957, Assignment Problems and the Location of Economic Activities. Econometrica, 25(1), pp. 53-76.

Lberni, A., Marktani, M.A., Ahaitouf, A., Ahaitouf, A., 2020, Adaptation of the Whale Optimization Algorithm to the Optimal Sizing of Analog Integrated Circuit: Low Voltage Amplifier Performances, Proc IEEE 2nd International Conference on Electronics, Control, Optimization and Computer Science ICECOCS 2020, Kenitra, Morocco, pp. 1-6.

Lin, H., Li, P., 2015, Circuit performance classification with active learning guided sampling for support vector machines, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 34(9), pp. 1467-1480.

Domschke, W., Krispin, G., 1997, Location and layout planning, OR Spektrum, 19(3), pp. 181 -194.

Mittal, S., Katal, A., 2016, An Optimized Task Scheduling Algorithm in Cloud Computing, Proc. IEEE 6th International Conference on Advanced Computing IACC 2016, Bhimavaram, India, pp. 197-202.

Mzili, T., Mzili, I., Riffi , M.E., 2023, Optimizing production scheduling with the Rat Swarm search algorithm: A novel approach to the flow shop problem for enhanced decision making, Decision Making: Applications in Management and Engineering, 6(2), pp.16 - 42.

Silva, A., Coelho, L.C., Darvish, M., 2021, Quadratic assignment problem variants: A survey and an effective parallel memetic iterated tabu search, European Journal of Operational Research, 292(3), pp. 1066-1084.

Hafiz, F., Abdennour, A., 2016, Particle Swarm Algorithm variants for the Quadratic Assignment Problems - A probabilistic learning approach, Expert Systems with Applications, 44, pp. 413-431.

Jiyue, E., Liu, J., Wan, Z., 2023, A novel adaptive algorithm of particle swarm optimization based on the human social learning intelligence, Swarm and Evolutionary Computation, 80, 101336.

Riffi, M.E., Saji, Y., Barkatou, M., 2017, Incorporating a modified uniform crossover and 2-exchange neighborhood mechanism in a discrete bat algorithm to solve the quadratic assignment problem, Egyptian Informatics Journal, 18(3), pp. 221-232.

Agharghor, A., Riffi, M.E., Chebihi, F., 2019, Improved hunting search algorithm for the quadratic assignment problem, Indonesian Journal of Electrical Engineering and Computer Science, 14(1), pp. 143-154.

Xu, G.N., Zhang, T., Lai, Q., 2021, A new firefly algorithm with mean condition partial attraction, Applied Intelligence, 52(4), pp. 4418-4431.

Mirjalili, S.Z., Mirjalili, S., Saremi, S., Faris, H., Aljarah, I., 2017, Grasshopper optimization algorithm for multi-objective optimization problems, Applied Intelligence, 48(4), pp. 805-820.

Mirjalili, S., Gandomi, A.H., Mirjalili, S., Saremi, S., Faris, H., Mirjalili, S., 2017, Salp Swarm Algorithm: A bio-inspired optimizer for engineering design problems, Advances in Engineering Software, 114, pp. 163-191.

Medjahed, S.A., Ouali, M., 2018, Spectral band selection using binary Gray Wolf optimizer and signal to noise ration measure, Lecture notes in networks and systems, pp. 75-89.

Dhiman, G., Garg, M., Nagar, A.K., Kumar, V., Dehghani, M., 2020, A novel algorithm for global optimization: Rat Swarm Optimizer, Journal of Ambient Intelligence and Humanized Computing, 12(8), pp. 8457-8482.

Dowsland, K.A., Thompson, J., 2012, Simulated annealing, Handbook of natural computing, Springer, Berlin, Heidelberg, pp. 1623-1655.

Sabri, N.M., Puteh, M., Mahmood, M.R., 2013, A review of gravitational search algorithm, Int. J. Advance. Soft Comput. Appl, 5(3), pp. 1-39.

Abualigah, L., Elaziz, M. A., Sumari, P., Khasawneh, A.M., Alshinwan, M., Mirjalili, S., Gandomi, A.H., 2022, Black hole algorithm: A comprehensive survey, Applied Intelligence, 52(10), pp. 11892–11915.

Golabian, H., Arkat, J., Tavakkoli-Moghaddam, R., Faroughi, H., 2022, A multi-verse optimizer algorithm for ambulance repositioning in emergency medical service systems, Journal of Ambient Intelligence and Humanized Computing, 13(1), pp. 549-570.

Pereira, J.L.J., Francisco, M.B., Diniz, C.A., Oliver, G.A., Cunha Jr, S.S., Gomes, G.F, 2021, Lichtenberg algorithm: A novel hybrid physics-based meta-heuristic for global optimization, Expert Systems with Applications, 170(15), 114522.

Zhao, F., Li, G., Yang, C., Abraham, A., Liu, H, 2014, A human–computer cooperative particle swarm optimization based immune algorithm for layout design. In Neurocomputing, 132, pp. 68–78.

Samareh Moosavi, S. H., Bardsiri, V. K, 2019, Poor and rich optimization algorithm: A new human-based and multi populations algorithm. Engineering Applications of Artificial Intelligence, 86, pp. 165–181.

Arnold, D. V., 2002, Noisy Optimization With Evolution Strategies, in Genetic Algorithms and Evolutionary Computation, Springer US.

Koza, J.R., Poli, R., 2005, Genetic programming, Search methodologies, pp. 127-164, Springer, Boston, MA.

Simon, D., 2008, Biogeography-based optimization, IEEE transactions on evolutionary computation, 12(6), pp. 702-713.

Opara, K. R., Arabas, J., 2019, Differential Evolution: A survey of theoretical analyses, Swarm and evolutionary computation, 44, pp. 546-558.

Katoch, S., Chauhan, S.S., Kumar, V., 2021, A review on genetic algorithm: past, present, and future, Multimedia Tools and Applications, 80(5), pp. 8091-8126.

Mzili , T., Riffi , M.E., Mzili, I., Dhiman, G., 2022, A novel discrete Rat swarm optimization (DRSO) algorithm for solving the traveling salesman problem, Decision Making: Applications in Management and Engineering, 5(2), pp. 287-299.

Clerc, M., 2004, Discrete Particle Swarm Optimization, illustrated by the Traveling Salesman Problem, in Onwubolu, G.C., Babu, B.V., New optimization techniques in engineering, pp. 219-239.

Di Blanco, Y. E., Desbiez, A. L. J., Jiménez-Pérez, I., Kluyber, D., Massocato, G. F., Di Bitetti, M. S., 2017, Habitat selection and home-range use by resident and reintroduced giant anteaters in 2 South American wetlands, Journal of Mammalogy, 98(4), pp. 1118–1128.

Cheng, M.Y., Prayogo, D., 2014, Symbiotic Organisms Search: A new metaheuristic optimization algorithm, Computers & Structures, 139, pp. 98-112.

Jain, M., Singh, V., Rani, A., 2019, A novel nature-inspired algorithm for optimization: Squirrel search algorithm, Swarm and evolutionary computation, 44, pp. 148-175.

James, P.C., Verbeek, N.A., 1983, The food storage behaviour of the northwestern crow, Behaviour, 85(3-4), pp. 276-291.

Geem, Z.W., 2009, Music-inspired harmony search algorithm, Studies in Computational Intelligence, Springer Berlin Heidelberg.

Mzili, I., Riffi, M. E., Benzekri, F., 2017, Penguins search optimization algorithm to solve quadratic assignment problem, Proc. 2nd international Conference on Big Data, Cloud and Applications, pp. 1-6.

Bouzidi, A., Riffi, M.E., 2014, Discrete cat swarm optimization algorithm applied to combinatorial optimization problems, Proc. 2014 5th Workshop on Codes, Cryptography and Communication Systems WCCCS, El Jadida, Morocco, pp. 30-34.

Bouzidi, S., Bouzidi, M., Riffi, M.E., 2019, Solving the Quadratic Assignment Problem using the Swallow Swarm Optimization Problem, International Journal of Engineering and Advanced Technology, 8(6), pp. 3116-3120.

Gao, X.Z., Govindasamy, V., Xu, H., Wang, X., Zenger, K., 2015, Harmony search method: theory and applications, Computational intelligence and neuroscience, 2015, 258491.

Krishnamoorthy, M.S., 1975, An NP-hard problem in bipartite graphs., ACM SIGACT News, 7(1), pp. 26-26.

Loiola, E. M., De Abreu, N. M. M., Boaventura-Netto, P.O., Hahn, P., Querido, T., 2007, A survey for the quadratic assignment problem, European Journal of Operational Research, 176(2), pp. 657–690.

Tseng, L.Y, Liang, S.C., 2006, A hybrid metaheuristic for the quadratic assignment problem, Computational Optimization and Applications, 34(1), pp. 85-113.

Mohassesian, E., Karasfi, B., 2017, A new method for improving the performance of fast local search in solving QAP for optimal exploration of state space, Proc. 2017 Artificial Intelligence and Robotics IRANOPEN, Qazvin, Iran, pp. 64-72.

Semlali, S.C.B., Riffi, M.E., Chebihi, F., 2019, Parallel hybrid chicken swarm optimization for solving the quadratic assignment problem, International Journal of Electrical and Computer Engineering, 9(3), 2064.

Riffi, M.E., Sayoti, F., 2019, Hybrid Algorithm for Solving the Quadratic Assignment Problem, International Journal of Interactive Multimedia & Artificial Intelligence, 5(4), 68.

Taheri, S. M., Hesamian, G., 2012, A generalization of the Wilcoxon signed-rank test and its applications, Statistical Papers, 54(2), pp. 457–470.




DOI: https://doi.org/10.22190/FUME230602024M

Refbacks

  • There are currently no refbacks.


ISSN: 0354-2025 (Print)

ISSN: 2335-0164 (Online)

COBISS.SR-ID 98732551

ZDB-ID: 2766459-4