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

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.