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

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

doi:10.31796/ogummf.1186895

EN TR

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

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İ

Öz

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.

Anahtar Kelimeler

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.

Details

Primary Language

English

Subjects

Industrial Engineering

Journal Section

Research Article

Authors

İslam Altın ^*
0000-0002-8133-7806
Türkiye

Aydın Sipahioğlu
0000-0001-8743-2911
Türkiye

Early Pub Date

April 27, 2023

Publication Date

April 29, 2023

Submission Date

October 10, 2022

Acceptance Date

April 19, 2023

Published in Issue

Year 1970 Volume: 31 Number: 1

DOI

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

IZ

https://izlik.org/JA28JU43MF

APA

Altın, İ., & Sipahioğlu, A. (2023). PARAMETER-LESS AND METAPHOR-LESS METAHEURISTIC ALGORITHM SUGGESTION FOR SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS. Eskişehir Osmangazi Üniversitesi Mühendislik Ve Mimarlık Fakültesi Dergisi, 31(1), 599-609. https://doi.org/10.31796/ogummf.1186895

AMA

1.Altın İ, Sipahioğlu A. PARAMETER-LESS AND METAPHOR-LESS METAHEURISTIC ALGORITHM SUGGESTION FOR SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS. Eskişehir Osmangazi Üniversitesi Mühendislik ve Mimarlık Fakültesi Dergisi. 2023;31(1):599-609. doi:10.31796/ogummf.1186895

Chicago

Altın, İslam, and Aydın Sipahioğlu. 2023. “PARAMETER-LESS AND METAPHOR-LESS METAHEURISTIC ALGORITHM SUGGESTION FOR SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS”. Eskişehir Osmangazi Üniversitesi Mühendislik Ve Mimarlık Fakültesi Dergisi 31 (1): 599-609. https://doi.org/10.31796/ogummf.1186895.

EndNote

Altın İ, Sipahioğlu A (April 1, 2023) PARAMETER-LESS AND METAPHOR-LESS METAHEURISTIC ALGORITHM SUGGESTION FOR SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS. Eskişehir Osmangazi Üniversitesi Mühendislik ve Mimarlık Fakültesi Dergisi 31 1 599–609.

IEEE

[1]İ. Altın and A. Sipahioğlu, “PARAMETER-LESS AND METAPHOR-LESS METAHEURISTIC ALGORITHM SUGGESTION FOR SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS”, Eskişehir Osmangazi Üniversitesi Mühendislik ve Mimarlık Fakültesi Dergisi, vol. 31, no. 1, pp. 599–609, Apr. 2023, doi: 10.31796/ogummf.1186895.

ISNAD

Altın, İslam - Sipahioğlu, Aydın. “PARAMETER-LESS AND METAPHOR-LESS METAHEURISTIC ALGORITHM SUGGESTION FOR SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS”. Eskişehir Osmangazi Üniversitesi Mühendislik ve Mimarlık Fakültesi Dergisi 31/1 (April 1, 2023): 599-609. https://doi.org/10.31796/ogummf.1186895.

JAMA

1.Altın İ, Sipahioğlu A. PARAMETER-LESS AND METAPHOR-LESS METAHEURISTIC ALGORITHM SUGGESTION FOR SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS. Eskişehir Osmangazi Üniversitesi Mühendislik ve Mimarlık Fakültesi Dergisi. 2023;31:599–609.

MLA

Altın, İslam, and Aydın Sipahioğlu. “PARAMETER-LESS AND METAPHOR-LESS METAHEURISTIC ALGORITHM SUGGESTION FOR SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS”. Eskişehir Osmangazi Üniversitesi Mühendislik Ve Mimarlık Fakültesi Dergisi, vol. 31, no. 1, Apr. 2023, pp. 599-0, doi:10.31796/ogummf.1186895.

Vancouver

1.İslam Altın, Aydın Sipahioğlu. PARAMETER-LESS AND METAPHOR-LESS METAHEURISTIC ALGORITHM SUGGESTION FOR SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS. Eskişehir Osmangazi Üniversitesi Mühendislik ve Mimarlık Fakültesi Dergisi. 2023 Apr. 1;31(1):599-60. doi:10.31796/ogummf.1186895

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

Abstract

Keywords

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

Öz

Anahtar Kelimeler

References

Details

Primary Language

Subjects

Journal Section

Authors

Early Pub Date

Publication Date

Submission Date

Acceptance Date

Published in Issue

DOI

IZ

Cite