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

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

References

1. 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
2. Arnaout, J. P. (2014). Worm optimization: A novel optimization algorithm. Proceedings of the 2014 International Conference on Industrial Engineering and Operations Management., 2499–2505.
3. 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
4. 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
5. Feng, X., Liu, Y., Yu, H., & Luo, F. (2019). Physarum-energy optimization algorithm. Soft Computing. https://doi.org/10.1007/s00500-017-2796-z
6. 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
7. 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
8. 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

9. Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.
10. 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
11. 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
12. Koza, J. R. (1992). Genetic programming. 1: On the programming of computers by means of natural selection (1st ed.). MIT Press.
13. Liu, S., & Lin, Y. (2011). Grey Systems. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-16158-2
14. 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
15. 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
16. Reinelt, G. (2013). Tsplib. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.
17. 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
18. 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
19. 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
20. 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
21. 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
22. 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
23. 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