PARAMETER-LESS AND METAPHOR-LESS METAHEURISTIC ALGORITHM SUGGESTION FOR SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS

Year 2023, , 599 - 609, 29.04.2023

İslam Altın , Aydın Sipahioğlu

https://doi.org/10.31796/ogummf.1186895

Abstract

Many optimization problems are complex, challenging and take a significant amount of computational effort to solve. These problems have gained the attention of researchers and they have developed lots of metaheuristic algorithms to use for solving these problems. Most of the developed metaheuristic algorithms are based on some metaphors. For this reason, these algorithms have algorithm-specific parameters to reflect the nature of the inspired metaphor. This violates the algorithm's simplicity and brings extra workload to execute the algorithm. However, the optimization problems can also be solved with simple, useful, metaphor-less and algorithm-specific parameter-less metaheuristic algorithms. So, it is the essential motivation behind this study. We present a novel metaheuristic algorithm called Discrete Rao Algorithm (DRA) by updating some components of the generic Rao algorithm to solve the combinatorial optimization problems. To evaluate the performance of the DRA, we perform experiments on Traveling Salesman Problem (TSP) which is the well-known combinatorial optimization problem. The experiments are performed on different sized benchmark problems in the literature. The computational results show that the developed algorithm has obtained high quality solutions in a reasonable computation time and it is competitive with other algorithms in the literature for solving the TSP.

Keywords

Metaheuristic Algorithms, Rao Algorithm, Discrete Optimization, Traveling Salesman Problem

KOMBİNATORYAL ENİYİLEME PROBLEMLERİNİN ÇÖZÜMÜ İÇİN PARAMETRESİZ VE METAFORSUZ METASEZGİSEL ALGORİTMA ÖNERİSİ

Abstract

Pek çok eniyileme problemi karmaşıktır ve çözülebilmesi için önemli miktarda hesaplama çabası gerektirmektedir. Söz konusu eniyileme problemleri araştırmacıların ilgisini çekmiş ve araştırmacılar bu problemlerin çözümünde kullanmak üzere birçok metasezgisel algoritma önermişlerdir. Geliştirilen metasezgisel algoritmaların çoğu metaforlara dayanmaktadır. Bu sebeple algoritmalar ilham alınan metaforların doğasını yansıtmak üzere parametre değerlerine sahiptirler. Bu durum algoritmanın sade olan yapısını bozmakta ve algoritmayı çalıştırmak için fazladan iş yükü getirmektedir. Ancak eniyileme problemleri sade, kullanışlı, metaforsuz ve parametresiz algoritmalarla da çözdürülebilir. Bu çalışmanın temel motivasyonu tam olarak söz konusu sade ve metaforsuz algoritma tasarımıdır. Bu çalışmada kombinatoryal eniyileme problemlerini çözmek için yeni bir metasezgisel yöntem olan Kesikli Rao Algoritması geliştirilmiştir. Kesikli Rao Algoritması (KRA) bilinen Rao algoritmasının bazı bileşenlerinde güncellemeler yapılarak elde edilmiştir. KRA’nın performansı iyi bilinen bir kombinatoryal eniyileme problemi olan Gezgin Satıcı Problemi (GSP) için değerlendirilmiştir. Literatürde yer alan farklı boyutlardaki test problemleri kullanılmıştır. Sonuç olarak, geliştirilen algoritma ile makul çözüm sürelerinde yüksek kaliteli çözümler elde edilmiştir ve geliştirilen algoritmanın GSP için literatürdeki diğer algoritmalarla yarışabilir nitelikte olduğu görülmüştür.

Keywords

Metasezgisel Algoritmalar, Rao Algoritması, Kesikli Eniyileme, Gezgin Satıcı Problemi

References

• Agrawal, P., Abutarboush, H. F., Ganesh, T., & Mohamed, A. W. (2021). Metaheuristic algorithms on feature selection: A survey of one decade of research (2009-2019). IEEE Access, 9, 26766-26791. doi: http://doi.org/10.1109/access.2021.3056407
• Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2011). The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics). Princeton, USA: Princeton University Press.
• Černý, V. (1985). Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications, 45(1), 41-51. doi: https://doi.org/10.1007/bf00940812
• Dede, T., Atmaca, B., Grzywinski, M., & Rao, R. V. (2022). Optimal design of dome structures with recently developed algorithm: Rao series. Structures, 42, 65-79. doi: https://doi.org/10.1016/j.istruc.2022.06.010
• Dorigo, M. (1992). Optimization, learning and natural algorithms (Ph. D. Thesis), Politecnico di Milano, Milano.
• Ezugwu, A. E., Shukla, A. K., Nath, R., Akinyelu, A. A., Agushaka, J. O., Chiroma, H., & Muhuri, P. K. (2021). Metaheuristics: A comprehensive overview and classification along with bibliometric analysis. Artificial Intelligence Review, 54(6), 4237-4316. doi: https://doi.org/10.1007/s10462-020-09952-0
• Gupta, S., Kumar, N., Srivastava, L., Malik, H., Anvari-Moghaddam, A., & García Márquez, F. P. (2021). A robust optimization approach for optimal power flow solutions using rao algorithms. Energies, 14(17), 5449. doi: https://doi.org/10.3390/en14175449
• Gutin, G., & Punnen, A. P. (Eds.). (2006). The traveling salesman problem and its variations (Vol. 12). New York, USA: Springer Science & Business Media.
• Hatamlou, A. (2013). Black hole: A new heuristic optimization approach for data clustering. Information Sciences, 222, 175-184. doi: https://doi.org/10.1016/j.ins.2012.08.023
• He, S., Wu, Q. H., & Saunders, J. R. (2006). A novel group search optimizer inspired by animal behavioural ecology. Proceedings of the International Conference on Evolutionary Computation, 1272-1278, Vancouver, Canada.
• Holland, J. H. (1975). Adaptation in natural and artificial systems. Ann Arbor, USA: University of Michigan Press.
• Hussain, K., Mohd Salleh, M. N., Cheng, S., & Shi, Y. (2019). Metaheuristic research: A comprehensive survey. Artificial Intelligence Review, 52(4), 2191-2233. doi: https://doi.org/10.1007/s10462-017-9605-z
• Karaboga, D., & Basturk, B. (2007). A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm. Journal of Global Optimization, 39(3), 459-471. doi: https://doi.org/10.1007/s10898-007-9149-x
• Kashan, A. H. (2009). League championship algorithm: A new algorithm for numerical function optimization. Proceedings of the International Conference of Soft Computing and Pattern Recognition, 43-48, Malacca, Malaysia. Kaveh, A., & Bakhshpoori, T. (2016). Water evaporation optimization: A novel physically inspired optimization algorithm. Computers & Structures, 167, 69-85. doi: https://doi.org/10.1016/j.compstruc.2016.01.008
• Kaveh, A., & Khayatazad, M. (2012). A new meta-heuristic method: Ray optimization. Computers & Structures, 112-113, 283-294. doi: https://doi.org/10.1016/j.compstruc.2012.09.003
• Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Proceedings of the ICNN’95-International Conference on Neural Networks, 4, 1942–1948, Perth, WA, Australia.
• Kirkpatrick, S., Gelatt Jr, 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
• Koza, J. R. (1992). Genetic programming: On the programming of computers by means of natural selection. Cambridge: MIT Press.
• Laporte, G. (1992). The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(2), 231-247. doi: https://doi.org/10.1016/0377-2217(92)90138-y
• Matai, R., Singh, S. P., & Mittal, M. L. (2010). Traveling salesman problem: An overview of applications, formulations, and solution approaches. D. Davendra (Ed.), In Traveling salesman problem, theory and applications (pp. 1-25). Rijeka, Croatia: IntechOpen.
• Miller, C. E., Tucker, A. W., & Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems. Journal of the ACM (JACM), 7(4), 326-329. doi: https://doi.org/10.1145/321043.321046
• Moscato, P. (1989). On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms (C3P Report 826). Pasadena, USA: California Institute of Technology.
• Mucherino, A., & Seref, O. (2007). Monkey search: A novel metaheuristic search for global optimization. Proceedings of the American Institute of Physics (AIP) Conference on Data Mining, Systems Analysis, and Optimization in Biomedicine, 953(1), 162-173, Gainesville, USA.
• Neos Guide website. (2022). Retrieved from https://neos-guide.org/guide/types/#discrete
• Papadimitriou, C. H., & Steiglitz, K. (1998). Combinatorial optimization: Algorithms and complexity. North Chelmsford, USA: Courier Corporation.
• Pham, H. A., & Tran, T. D. (2022). Optimal truss sizing by modified Rao algorithm combined with feasible boundary search method. Expert Systems with Applications, 191, 116337. doi: https://doi.org/10.1016/j.eswa.2021.116337
• Rao, R. V. (2020). Rao algorithms: Three metaphor-less simple algorithms for solving optimization problems. International Journal of Industrial Engineering Computations, 11(1), 107-130. doi: https://doi.org/10.5267/j.ijiec.2019.6.002
• Rao, R. V., & Keesari, H. S. (2021). A self-adaptive population Rao algorithm for optimization of selected bio-energy systems. Journal of Computational Design and Engineering, 8(1), 69-96. doi: https://doi.org/10.1093/jcde/qwaa063
• Rao, R. V., & Pawar, R. B. (2020a). Constrained design optimization of selected mechanical system components using Rao algorithms. Applied Soft Computing, 89, 106141. doi: https://doi.org/10.1016/j.asoc.2020.106141
• Rao, R. V., & Pawar, R. B. (2020b). Quasi-oppositional-based rao algorithms for multi-objective design optimization of selected heat sinks. Journal of Computational Design and Engineering, 7(6), 830-863. doi: https://doi.org/10.1093/jcde/qwaa060
• Rao, R. V., Savsani, V. J., & Vakharia, D. P. (2011). Teaching–learning-based optimization: A novel method for constrained mechanical design optimization problems. Computer-aided Design, 43(3), 303-315. doi: https://doi.org/10.1016/j.cad.2010.12.015
• Rashedi, E., Nezamabadi-Pour, H., & Saryazdi, S. (2009). GSA: A gravitational search algorithm. Information Sciences, 179(13), 2232-2248. doi: https://doi.org/10.1016/j.ins.2009.03.004
• Singh, A., & Kumar, A. (2021). Applications of nature-inspired meta-heuristic algorithms: A survey. International Journal of Advanced Intelligence Paradigms, 20(3-4), 388-417. doi: https://doi.org/10.1504/ijaip.2021.119026
• Suyanto, S., Wibowo, A. T., Al Faraby, S., Saadah, S., & Rismala, R. (2021). Evolutionary rao algorithm. Journal of Computational Science, 53, 101368. doi: https://doi.org/10.1016/j.jocs.2021.101368
• Talbi, E. G. (2009). Metaheuristics: From design to implementation. Hoboken, USA: John Wiley & Sons.
• TSPLIB website. (2022). Retrieved from http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
• Wei, W., Ouyang, H., Wu, W., Li, S., & Zou, D. (2022). A behavior-selection based Rao algorithm and its applications to power system economic load dispatch problems. Applied Intelligence, 52(10), 11966–11999. doi: https://doi.org/10.1007/s10489-021-02849-7
• Yang, X. S. (2009). Firefly algorithms for multimodal optimization. Proceedings of the 5th International Symposium on Stochastic Algorithms - Foundations and Applications, 169-178, Sapporo, Japan.
• Yang, X. S., & Deb, S. (2009). Cuckoo search via Lévy flights. Proceedings of the World Congress on Nature & Biologically Inspired Computing (NaBIC), 210-214, Coimbatore, India.