A comparative study of metaheuristics algorithms based on their performance of complex benchmark problems

  • Tithli Sadhu Department of Chemistry, National Institute of Technology Durgapur, West Bengal, India; Department of Biochemistry, School of Agriculture, SR University, Hanumakonda, Telangana, India
  • Somanth Chowdhury Department of Chemical Engineering, National Institute of Technology Durgapur, West Bengal, India
  • Shubham Mondal Department of Computer Science and Engineering, Institute of Engineering and Management Kolkata, West Bengal, India
  • Jagannath Roy Department of Mathematics, National Institute of Technology Warangal, Telangana, India
  • Jitamanyu Chakrabarty Department of Chemistry, National Institute of Technology Durgapur, West Bengal, India
  • Sandip Kumar Lahiri Department of Chemical Engineering, National Institute of Technology Durgapur, West Bengal, India
Keywords: Metaheuristic, Algorithms, Optimization, Performance, Benchmark problems

Abstract

Metaheuristic approaches with extremely important improvements are very promising in the solution of intractable optimization problems. The objective of the present study is to test the capability of applications and compare the performance of the four selected algorithms from “classical” (simulated annealing (SA), genetic algorithm (GA), particle swarm optimization (PSO), and differential evolution (DE)) and “new generation” (firefly algorithm (FFA), krill herd (KH), grey wolf optimization (GWO), and symbiotic organism search (SOS)) each by solving selected benchmark problems that are used in the literature for algorithm testing purpose. The selected test problems had very complex objective functions and associated constraints with multiple local optima. Among all selected algorithms, the “new generation” SOS and KH algorithm successfully solved most of all the selected benchmark problems and achieved the best solution for most of them. Among four “classical” algorithms, DE, and PSO effectively attained the optimal solution which was very close to the best one. However, the “new generation” algorithm performed much better than the “classical” one. Therefore, no firm conclusion can be done about the universally best algorithm and their performance may be varied for different benchmark problems. However, in this study for the seven selected test problems, SOS and KH exhibited the most promising result and great potential with respect to execution time also. This study gives some insights to use SOS and KH as the best-performing algorithms to the novice user who can easily get lost in the plethora of large optimization algorithms.

Downloads

Download data is not yet available.

References

Adam, S. P., Alexandropoulos, S. A. N., Pardalos, P. M., & Vrahatis, M. N. (2019). No free lunch theorem: A review. In Demetriou, I., Pardalos, P. (Eds.), Approximation and Optimization. Springer Optimization and Its Applications (pp. 57–82). Springer, Cham.

Bai, Q. (2010). Analysis of particle swarm optimization algorithm. Computer and information science, 3(1), 180–184. DOI: https://doi.org/10.5539/cis.v3n1p180

Banzhaf, W., Nordin, P., Keller, R. E., & Francone, F. D. (1998). Genetic programming: an introduction: on the automatic evolution of computer programs and its applications. (1st ed.). Morgan Kaufmann Publishers Inc, (Chapter 5).

Beheshti, Z., & Shamsuddin, S. M. H. (2013). A review of population-based meta-heuristic algorithms. International Journal of Advances in Soft Computing and its Applications, 5(1), 1–35.

Bolaji, A. L. A., Al-Betar, M. A., Awadallah, M. A., Khader, A. T., & Abualigah, L. M. (2016). A comprehensive review: Krill Herd algorithm (KH) and its applications. Applied Soft Computing, 49, 437–446. DOI: https://doi.org/10.1016/j.asoc.2016.08.041

Cheng, M. Y., & Prayogo, D. (2014). Symbiotic organisms search: a new metaheuristic optimization algorithm. Computers & Structures, 139, 98–112. DOI: https://doi.org/10.1016/j.compstruc.2014.03.007

Das, S., Biswas, A., Dasgupta, S., & Abraham, A. (2009). Bacterial foraging optimization algorithm: theoretical foundations, analysis, and applications. In Abraham, A., Hassanien, AE., Siarry, P., Engelbrecht, A. (Eds.), Foundations of Computational Intelligence (pp. 23–55). Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/978-3-642-01085-9_2

Deb, K. (2000). An efficient constraint handling method for genetic algorithms. Computer methods in applied mechanics and engineering, 186(2–4), 311-338. DOI: https://doi.org/10.1016/S0045-7825(99)00389-8

Dokeroglu, T., Sevinc, E., Kucukyilmaz, T., & Cosar, A. (2019). A survey on new generation metaheuristic algorithms. Computers & Industrial Engineering, 137, 106040.

Dorigo, M., & Di Caro, G. (1999). Ant colony optimization: a new meta-heuristic, in Proceedings of the 1999 congress on evolutionary computation-CEC99. IEEE, 1470–1477.

Emary, E., Zawbaa, H. M., & Hassanien, A. E. (2016). Binary grey wolf optimization approaches for feature selection. Neurocomputing, 172, 371–381. DOI: https://doi.org/10.1016/j.neucom.2015.06.083

Enitan, A. M., & Adeyemo, J. (2011). Food processing optimization using evolutionary algorithms. African Journal of Biotechnology, 10(72), 16120–16127. DOI: https://doi.org/10.5897/AJB11.410

Floudas, C., Aggarwal, A., & Ciric, A. (1989). Global optimum search for nonconvex NLP and MINLP problems. Computers & Chemical Engineering, 13(10), 1117–1132. DOI: https://doi.org/10.1016/0098-1354(89)87016-4

Gandomi, A. H., & Alavi, A. H. (2012). Krill herd: a new bio-inspired optimization algorithm. Communications in nonlinear science and numerical simulation, 17(12), 4831–4845. DOI: https://doi.org/10.1016/j.cnsns.2012.05.010

Geem, Z.W., Kim, J. H., & Loganathan, G.V. (2001). A new heuristic optimization algorithm: harmony search. Simulation, 76(2), 60–68. DOI: https://doi.org/10.1177/003754970107600201

Glover, F., & Laguna, M. (1998). Tabu Search. In Du DZ., & Pardalos P.M. (Eds.), Handbook of Combinatorial Optimization (pp. 2093–2229). Springer, Boston, MA. DOI: https://doi.org/10.1007/978-1-4613-0303-9_33

Goldberg, D.E. (1989). Genetic algorithms in search, Optimization, and Machine Learning. (1st ed.). Addison-Wesley Publishing Company, (Chapter 3).

Ho, Y. C., & Pepyne, D. L. (2001, December). Simple explanation of the no free lunch theorem of optimization, in Proceedings of the 40th IEEE Conference on Decision and Control. IEEE, 4409–4414.

Ho, Y. C., & Pepyne, D. L. (2002). Simple explanation of the no-free-lunch theorem and its implications. Journal of optimization theory and applications, 115(3), 549–570. DOI: https://doi.org/10.1023/A:1021251113462

Karaboga, D. (2005). An idea based on honey bee swarm for numerical optimization. Technical report-tr06, Erciyes university, engineering faculty, computer engineering department.

Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization, in Proceedings of ICNN'95-international conference on neural networks. IEEE, 1942–1948.

Kirkpatrick, S., Gelatt, C.D., & Vecchi, M.P. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680. DOI: https://doi.org/10.1126/science.220.4598.671

Kohli, M., & Arora, S. (2018). Chaotic grey wolf optimization algorithm for constrained optimization problems. Journal of computational design and engineering, 5(4), 458–472. DOI: https://doi.org/10.1016/j.jcde.2017.02.005

Lahiri, S. K., & Ghanta, K. C. (2009). Development of a hybrid artificial neural network and genetic algorithm model for regime identification of slurry transport in pipelines. Chemical Product and Process Modeling, 4(1), Article 22. DOI: 10.2202/1934-2659.1343. DOI: https://doi.org/10.2202/1934-2659.1343

Lahiri, S. K., & Ghanta, K. C. (2010). Artificial neural network model with parameter tuning assisted by genetic algorithm technique: study of critical velocity of slurry flow in pipeline. Asia‐Pacific Journal of Chemical Engineering, 5(5), 763–777. DOI: https://doi.org/10.1002/apj.403

Lahiri, S. K., Khalfe, N. M., & Wadhwa, S. K. (2012). Particle swarm optimization technique for the optimal design of shell and tube heat exchangers. Chemical Product and Process Modeling, 7(1), Article 14. DOI: 10.1515/1934-2659.1612. DOI: https://doi.org/10.1515/1934-2659.1612

Li, B., & Jiang, W. (1997). Chaos optimization method and its application. Control theory and application, 14(4), 613–615.

Marques-Silva, J. P., & Sakallah, K. A. (1999). GRASP: A search algorithm for propositional satisfiability. IEEE Transactions on Computers, 48(5), 506–521. DOI: https://doi.org/10.1109/12.769433

Michalewicz, Z. (1995). Genetic algorithms, numerical optimization, and constraints. In Eshelman, L. (Eds.), Proceedings of the Sixth International Conference on Genetic Algorithms (pp. 151–158). Morgan Kauffman, San Mateo.

Mirjalili, S., & Lewis, A. (2016). The whale optimization algorithm. Advances in engineering software, 95, 51–67. DOI: https://doi.org/10.1016/j.advengsoft.2016.01.008

Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey wolf optimizer. Advances in engineering software, 69, 46–61. DOI: https://doi.org/10.1016/j.advengsoft.2013.12.007

Mirjalili, S., Saremi, S., Mirjalili, S. M., & Coelho, L. D. S. (2016). Multi-objective grey wolf optimizer: a novel algorithm for multi-criterion optimization. Expert Systems with Applications, 47, 106–119. DOI: https://doi.org/10.1016/j.eswa.2015.10.039

Mittal, N., Singh, U., & Sohi, B. S. (2016). Modified grey wolf optimizer for global engineering optimization. Applied Computational Intelligence and Soft Computing, 2016, 7950348. DOI: https://doi.org/10.1155/2016/7950348

Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & operations research, 24(11), 1097–1100. DOI: https://doi.org/10.1016/S0305-0548(97)00031-2

Niu, P., Niu, S., & Chang, L. (2019). The defect of the Grey Wolf optimization algorithm and its verification method. Knowledge-Based Systems, 171, 37–43.

Qin, H., Fan, P., Tang, H., Huang, P., Fang, B., & Pan, S. (2019). An effective hybrid discrete grey wolf optimizer for the casting production scheduling problem with multi-objective and multi-constraint. Computers & Industrial Engineering, 128, 458–476.

Rangaiah, G.P. (2010). Stochastic Global Optimization: Techniques and Applications in Chemical Engineering. (1st ed.). World Scientific, (Chapter 3). DOI: https://doi.org/10.1142/7669

Rao, S. S. (2019). Engineering optimization: theory and practice. (5th ed.). Wiley, (Chapter 13).

Shopova, E. G., & Vaklieva-Bancheva, N. G. (2006). BASIC- a genetic algorithm for engineering problems solution. Computers and Chemical Engineering, 30(8), 1293–1309. DOI: https://doi.org/10.1016/j.compchemeng.2006.03.003

Storn, R., & Price, K. (1997). Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization, 11(4), 341–359. DOI: https://doi.org/10.1023/A:1008202821328

Summanwar, V., Jayaraman, V., Kulkarni, B., Kusumakar, H., Gupta, K., & Rajesh, J. (2002). Solution of constrained optimization problems by multi-objective genetic algorithm. Computers & Chemical Engineering, 26(10), 1481–1492. DOI: https://doi.org/10.1016/S0098-1354(02)00125-4

Wang, F. S., & Chen, L. H. (2013). Heuristic optimization. In Dubitzky, W., Wolkenhauer, O., Cho, KH., Yokota, H. (Eds.), Encyclopedia of Systems Biology (pp. 885–885). Springer, New York. DOI: https://doi.org/10.1007/978-1-4419-9863-7_411

Wolpert, D. H., & Macready, W. G. (1997). No free lunch theorems for optimization. IEEE transactions on evolutionary computation, 1(1), 67–82. DOI: https://doi.org/10.1109/4235.585893

Yang, X. S. (2010a). Firefly algorithm, stochastic test functions and design optimisation. International journal of bio-inspired computation, 2(2), 78–84. DOI: https://doi.org/10.1504/IJBIC.2010.032124

Yang, X. S. (2010b). A new metaheuristic bat-inspired algorithm. In González J.R., Pelta D.A., Cruz C., Terrazas G., & Krasnogor N. (Eds.), Nature Inspired Cooperative Strategies for Optimization (NICSO 2010) (pp. 65–74). Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/978-3-642-12538-6_6

Yang, X. S., & Deb, S. (2009). Cuckoo search via Lévy flights, in 2009 World congress on nature & biologically inspired computing (NaBIC). IEEE, 210–214. DOI: https://doi.org/10.1109/NABIC.2009.5393690

Published
2022-10-06
How to Cite
Sadhu, T., Chowdhury, S., Shubham Mondal, Jagannath Roy, Chakrabarty, J., & Lahiri, S. K. (2022). A comparative study of metaheuristics algorithms based on their performance of complex benchmark problems. Decision Making: Applications in Management and Engineering. https://doi.org/10.31181/dmame0306102022r
Section
Regular articles