Analysis of the Computational Performance in Traveling Salesman Problem: An Application of the Grey Prediction Hybrid Black Hole Algorithm

Year 2024, , 281 - 292, 31.12.2024

Mehmet Fatih Demiral

https://doi.org/10.17093/alphanumeric.1506894

Abstract

Grey prediction evolution algorithm (GPEA) is a nature-inspired intelligent approach applied to global optimization and engineering problems in 2020. The performance of the GPEA is evaluated on benchmark functions, global optimization, and tested on six engineering-constrained design problems. The comparison shows the effectiveness and superiority of the GPEA. Although the pure GPEA is better than other algorithms in global optimization, and engineering problems, it shows poor performance in combinatorial optimization. In this work, GPEA hybridizes with the black hole algorithm and tabu search for the event horizon condition. Besides, the GPHBH is implemented with heuristics, such as 2-opt, 3-opt, and k-opt swap, and tries to improve with constructive heuristics, such as NN (nearest neighbor), and k-NN. All the algorithms have been tested under appropriate parameters in this work. The traveling salesman problem has been used as a benchmark problem so eight benchmark OR-Library datasets are experimented with. The experimental solutions are presented as best, average solutions, std. deviation and CPU time for all datasets. As a result, GPHBH and its derived forms give alternative and acceptable solutions to combinatorial optimization in admissible CPU time.

Keywords

Grey Prediction Evolution Algorithm, Heuristics, Hybrid Black Hole Algorithm, Metaheuristics

Ethical Statement

This article was prepared under the ethical rules.

References

• Aladag, C. H., Hocaoglu, G., & Basaran, M. A. (2009). The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem. Expert Systems with Applications, 36(10), 12349–12356. https://doi.org/10.1016/j.eswa.2009.04.051
• Arnaout, J. P. (2014). Worm optimization: A novel optimization algorithm. Proceedings of the 2014 International Conference on Industrial Engineering and Operations Management., 2499–2505.
• Deng, J. L. (1982). Control problems of grey systems. Systems & Control Letters, 1(5), 288–294. https://doi.org/10.1016/s0167-6911(82)80025-x
• Elloumi, W., El Abed, H., Abraham, A., & Alimi, A. M. (2014). A comparative study of the improvement of performance using a PSO modified by ACO applied to TSP. Applied Soft Computing, 25, 234–241. https://doi.org/10.1016/j.asoc.2014.09.031
• Feng, X., Liu, Y., Yu, H., & Luo, F. (2019). Physarum-energy optimization algorithm. Soft Computing. https://doi.org/10.1007/s00500-017-2796-z
• Halim, A. H., & Ismail, I. (2019). Combinatorial Optimization: Comparison of Heuristic Algorithms in Travelling Salesman Problem. Archives of Computational Methods in Engineering, 26(2), 367–380. https://doi.org/10.1007/s11831-017-9247-y
• Hatamlou, A. (2013). Black hole: A new heuristic optimization approach for data clustering. Information Sciences, 222, 175–184. https://doi.org/10.1016/j.ins.2012.08.023
• Hatamlou, A. (2018). Solving travelling salesman problem using black hole algorithm. Soft Computing, 22(24), 8167–8175. https://doi.org/10.1007/s00500-017-2760-y
• Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.
• Hu, Z., Xu, X., Su, Q., Zhu, H., & Guo, J. (2020). Grey prediction evolution algorithm for global optimization. Applied Mathematical Modelling, 79, 145–160. https://doi.org/10.1016/j.apm.2019.10.026
• Husseinzadeh Kashan, A. (2015). A new metaheuristic for optimization: Optics inspired optimization (OIO). Computers & Operations Research, 55, 99–125. https://doi.org/10.1016/j.cor.2014.10.011
• Koza, J. R. (1992). Genetic programming. 1: On the programming of computers by means of natural selection (1st ed.). MIT Press.
• Liu, S., & Lin, Y. (2011). Grey Systems. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-16158-2
• Liu, S., Zeng, B., Liu, J., Xie, N., & Yang, Y. (2015). Four basic models of GM(1, 1) and their suitable sequences. Grey Systems: Theory and Application, 5(2), 141–156. https://doi.org/10.1108/gs-04-2015-0016
• Peker, M., Şen, B., & Kumru, P. Y. (2013). An efficient solving of the traveling salesman problem: the ant colony system having parameters optimized by the Taguchi method. Turkish Journal of Electrical Engineering & Computer Sciences, 21, 2015–2036. https://doi.org/10.3906/elk-1109-44
• Reinelt, G. (2013). Tsplib. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.
• Siddique, N., & Adeli, H. (2017). Nature-Inspired Chemical Reaction Optimisation Algorithms. Cognitive Computation, 9(4), 411–422. https://doi.org/10.1007/s12559-017-9485-1
• Szeto, W., Wu, Y., & Ho, S. C. (2011). An artificial bee colony algorithm for the capacitated vehicle routing problem. European Journal of Operational Research, 215(1), 126–135. https://doi.org/10.1016/j.ejor.2011.06.006
• Tien, T.-L. (2012). A research on the grey prediction model GM(1,n). Applied Mathematics and Computation, 218(9), 4903–4916. https://doi.org/10.1016/j.amc.2011.10.055
• Xie, N.., & Liu, S. (2009). Discrete grey forecasting model and its optimization. Applied Mathematical Modelling, 33(2), 1173–1186. https://doi.org/10.1016/j.apm.2008.01.011
• Xu, X., Hu, Z., Su, Q., Li, Y., & Dai, J. (2020). Multivariable grey prediction evolution algorithm: A new metaheuristic. Applied Soft Computing, 89, 106086. https://doi.org/10.1016/j.asoc.2020.106086
• Yildirim, A. E., & Karci, A. (2018). Applications of artificial atom algorithm to small-scale traveling salesman problems. Soft Computing, 22(22), 7619–7631. https://doi.org/10.1007/s00500-017-2735-z
• Zheng, Y.-J. (2015). Water wave optimization: A new nature-inspired metaheuristic. Computers & Operations Research, 55, 1–11. https://doi.org/10.1016/j.cor.2014.10.008