Enhancement of Quadratic Assignment Problem Using Slime Mould Algorithm

Authors

  • S. Rajalakshmi  Department of Computer Science and Engineering, Pondicherry Engineering College, Puducherry, India
  • Dr. Kanmani  Department of Information Technology, Pondicherry Engineering College, Puducherry, India
  • C. Varsha  Department of Information Technology, Pondicherry Engineering College, Puducherry, India
  • E Daphne Auxilia  Department of Information Technology, Pondicherry Engineering College, Puducherry, India

Keywords:

Metaheuristics, Combinatorial optimization, Slime Mould Algorithm, Quadratic Assignment Problem

Abstract

The QAP problem is one of the most challenging NP-hard combinatorial optimization problems.The aim is to minimise the sum of the distances multiplied by the corresponding flows by assigning all facilities to different locations. As a result, this paper proposes the SlimeMould Algorithm Quadratic Assignment Problem (SMAQAP) for solving this problem in a reasonable amount of time.Slime mould algorithm (SMA) is a new stochastic optimizer with a mathematical model that uses adaptive weights to simulate the slime mould's mechanism of producing positive and negative feedback propagation wave centred on the bio-oscillator in order to form the effective approach for linking food with high exploratory ability.Then, we tested our algorithm on QAPLIB's benchmark instances. The proposed SMAQAP is compared with genetic algorithm (GA), particle swarm optimization (PSO) algorithm and firefly algorithm (FA) to solve the quadratic assignment problems.

References

  1. Samanta, Suman, Deepu Philip & Shankar Chakraborty.(2019). "A quick convergent artificial bee colony algorithm for solving quadratic assignment problems." Computers & Industrial Engineering, 137 : 106070.
  2. Li, Shimin, et al.(2020)."Slime mould algorithm: A new method for stochastic optimization." Future Generation Computer Systems.
  3. Kılıç, Haydar, and UğurYüzgeç.(2019)."Tournament selection based antlion optimization algorithm for solving quadratic assignment problem." Engineering science and technology, an international journal 22.2 , 673-691.
  4. Cubukcuoglu, Cemre, et al.(2019)."A Memetic Algorithm for the Bi-Objective Quadratic Assignment Problem." Procedia Manufacturing, 39, 1215-1222.
  5. Yang, Xin-She.(2020)."Nature-inspired optimization algorithms: challenges and open problems." Journal of Computational Science, 101104.
  6. Bujok, Petr, Josef Tvrdík, and RadkaPoláková.(2019)."Comparison of nature-inspired population-based algorithms on continuous optimisation problems." Swarm and Evolutionary Computation, 50 , 100490.
  7. Kumar, Manoj, AryabarttaSahu, and PinakiMitra.(2020)."A comparison of different metaheuristics for the quadratic assignment problem in accelerated systems." Applied Soft Computing , 106927.
  8. Hameed, AsaadShakir, et al.(2018)."Review on the Methods to Solve Combinatorial Optimization Problems Particularly: Quadratic Assignment Model." International Journal of Engineering & Technology 7.3.20 , 15-20.
  9. Hu, Kang, Guo-Li Zhang, and Bo Xiong.(2018)."An improved particle swarm algorithm for constrained optimization problem." 2018 International Conference on Machine Learning and Cybernetics (ICMLC).Vol. 2.IEEE.
  10. Luthra, Ishani, et al.(2017)."Comparative study on nature inspired algorithms for optimization problem." 2017 International conference of Electronics, Communication and Aerospace Technology (ICECA).Vol. 2.IEEE, 2017.
  11. Fan, Xumei, et al.(2020)."Review and classification of bio-inspired algorithms and their applications." Journal of Bionic Engineering 17 , 611-631.
  12. Sharma, Manik, and PrableenKaur.(2020). "A comprehensive analysis of nature-inspired meta-heuristic techniques for feature selection problem." Archives of Computational Methods in Engineering , 1-25.
  13. Immanuel, Savio D., and Udit Kr Chakraborty.(2019)."Genetic algorithm: an approach on optimization." 2019 International Conference on Communication and Electronics Systems (ICCES).IEEE.
  14. Dokeroglu, Tansel, Ender Sevinc, and AhmetCosar.(2019)."Artificial bee colony optimization for the quadratic assignment problem." Applied soft computing 76 , 595-606.
  15. Mamaghani, Ali Safari, and Mohammad Reza Meybodi.(2012)."Solving the Quadratic Assignment Problem with the modified hybrid PSO algorithm." 2012 6th International Conference on Application of Information and Communication Technologies (AICT).IEEE.
  16. Rameshkumar, K.(2018)."Extension of PSO and ACO-PSO algorithms for solving Quadratic Assignment Problems." IOP Conference Series: Materials Science and Engineering. Vol. 377.No. 1.IOP Publishing.
  17. Guo, Meng-Wei, Jie-Sheng Wang, and Xue Yang.(2020)."An chaotic firefly algorithmto solve quadratic assignment problem." EngLett 28.2 , 337-342.
  18. Congying, Lv, Zhao Huanping, and Yang Xinfeng.(2011)."Particle swarm optimization algorithm for quadratic assignment problem." Proceedings of 2011 International Conference on Computer Science and Network Technology.Vol. 3.IEEE.
  19. Azarbonyad, Hosein, and Reza Babazadeh.(2014)."A genetic algorithm for solving quadratic assignment problem (QAP)." arXiv preprint arXiv:1405.5050.
  20. Ahuja, Ravindra K., James B. Orlin, and Ashish Tiwari.(2000)."A greedy genetic algorithm for the quadratic assignment problem." Computers & Operations Research 27.10 , 917-934.
  21. Poli, Riccardo, James Kennedy, and Tim Blackwell.(2007)."Particle swarm optimization." Swarm intelligence 1.1, 33-57.
  22. Shi, Yuhui.(2001)."Particle swarm optimization: developments, applications and resources." Proceedings of the 2001 congress on evolutionary computation (IEEE Cat. No. 01TH8546). Vol. 1. IEEE.
  23. Fister, Iztok, et al.(2013)."A comprehensive review of firefly algorithms." Swarm and Evolutionary Computation 13, 34-46.
  24. Yang, Xin-She.(2020)."Firefly algorithm, stochastic test functions and design optimisation." International journal of bio-inspired computation 2.2 , 78-84.
  25. Yang, Xin-She.(2010)."Firefly algorithm, Levy flights and global optimization." Research and development in intelligent systems XXVI. Springer, London, 209-218.
  26. Mirjalili, Seyedali.(2019)."Genetic algorithm." Evolutionary algorithms and neural networks. Springer, Cham, 43-55.
  27. Houck, Christopher R., Jeff Joines, and Michael G. Kay.(1995)."A genetic algorithm for function optimization: a Matlab implementation." Ncsu-ie tr 95.09 , 1-10.
  28. Genlin, Ji.(2004) "Survey on genetic algorithm [J]." Computer Applications and Software 2 , 69-73.
  29. Loiola, Eliane Maria, et al.(2007)."A survey for the quadratic assignment problem." European journal of operational research 176.2, 657-690.
  30. Burkard, Rainer E., Stefan E. Karisch, and Franz Rendl.(1997). "QAPLIB–a quadratic assignment problem library." Journal of Global optimization 10.4 391-403.
  31. Karaboga, Dervis, and Bahriye Akay.(2009)."A comparative study of artificial bee colony algorithm." Applied mathematics and computation 214.1, 108-132.
  32. Karaboga, Dervis, et al.(2014)."A comprehensive survey: artificial bee colony (ABC) algorithm and applications." Artificial Intelligence Review 42.1, 21-57.
  33. Ghandeshtani, Kambiz Shojaee, et al.(2010)."New simulated annealing algorithm for quadratic assignment problem." The fourth international conference on advanced engineering computing and applications in sciences.
  34. Rutenbar, Rob A.(1989). “Simulated annealing algorithms: An overview." IEEE Circuits and Devices magazine 5.1 ,19-26.
  35. Zhao, Juan, Zheng-Ming Gao, and Wu Sun.(2020)."The improved slime mould algorithm with Levy flight." Journal of Physics: Conference Series. Vol. 1617. No. 1. IOP Publishing.
  36. Houssein, Essam H., et al.(2021)."Hybrid slime mould algorithm with adaptive guided differential evolution algorithm for combinatorial and global optimization problems." Expert Systems with Applications 174 , 114689.
  37. Adithyan, T. Ajay, et al.(2017)."Nature inspired algorithm." 2017 international conference on trends in electronics and informatics (ICEI). IEEE.
  38. Dixit, Manish, Nikita Upadhyay, and Sanjay Silakari.(2015)."An exhaustive survey on nature inspired optimization algorithms." International Journal of Software Engineering and Its Applications 9.4, 91-104.
  39. Kar, Arpan Kumar.(2016). "Bio inspired computing–a review of algorithms and scope of applications." Expert Systems with Applications 59, 20-32.
  40. Yang, Xin-She, et al.,(2013). Swarm intelligence and bio-inspired computation: theory and applications. Newnes.
  41. Livingstone, David J., et al.(2008). Artificial neural networks: methods and applications. Totowa, NJ, USA:: Humana Press.
  42. Kosko, Bart. (1994). "Fuzzy systems as universal approximators." IEEE transactions on computers 43.11 ,1329-1333.
  43. Eiben, Agoston Endre, and Selmar K. Smit. (2011). "Evolutionary algorithm parameters and methods to tune them." Autonomous search. Springer, Berlin, Heidelberg, 15-36.
  44. Fleming, Wendell H., and Raymond W. Rishel.(2012). “Deterministic and stochastic optimal control”. Springer Science & Business Media, Vol.1.
  45. Beekman, Madeleine, and Tanya Latty. (2015). "Brainless but multi-headed: decision making by the acellular slime mould Physarum polycephalum." Journal of molecular biology, 3734-3743.
  46. Brabazon, Anthony, and Seán McGarraghy. (2020) "Slime mould foraging: an inspiration for algorithmic design." International Journal of Innovative Computing and Applications, 30-45.
  47. Lenstra, Jan Karel, and AHG Rinnooy Kan. (1975) "Some simple applications of the travelling salesman problem." Journal of the Operational Research Society, 717-733.
  48. Zubaidi, Salah L., et al.(2020) "Hybridised Artificial Neural Network Model with Slime Mould Algorithm: A Novel Methodology for Prediction of Urban Stochastic Water Demand." Water ,2692.
  49. Paz, Azaria, and Shlomo Moran. (1981) "Non deterministic polynomial optimization problems and their approximations." Theoretical Computer Science,251-277.

International Journal of Scientific Research in Science and Technology

Downloads

Published

2021-04-10

Issue

Volume 9, Issue 1, March-April-2021

Section

Research Articles

License

Copyright (c) IJSRST

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
S. Rajalakshmi, Dr. Kanmani, C. Varsha, E Daphne Auxilia, " Enhancement of Quadratic Assignment Problem Using Slime Mould Algorithm, International Journal of Scientific Research in Science and Technology(IJSRST), Online ISSN : 2395-602X, Print ISSN : 2395-6011, Volume 9, Issue 1, pp.565-576, March-April-2021.