Perspective Chapter: Experimental Analysis of Black Hole Algorithm with Heuristic Algorithms in Traveling Salesman Problem

Abstract

Black hole algorithm (BHA) is a popular metaheuristic algorithm proposed and applied for data clustering in 2013. BHA was applied to continuous and discrete problems; it is also hybridized with some algorithms in the literature. The pure BHA shows better performance than others in discrete optimization, such as traveling salesman problems. However, it requires improving the algorithm with competitive heuristics. Many heuristics have often been used to construct the initial tour of a salesman, such as the nearest neighbor algorithm (NN), nearest insertion algorithm (NI), cheapest insertion algorithm (CI), random insertion algorithm (RI), furthest insertion algorithm (FI), and minimal spanning tree algorithm (MST). In addition, the black hole algorithm is combined with popular heuristics, such as swap/or insert, reverse/or 2-opt swap, and swap-reverse/or 3-opt swap, and tested with proper parameters in this study. In the experimentation, classical datasets are used via TSP-library. The experimental results are given as best, average solutions/or deviations, and CPU time for all datasets. Besides, the hybrid algorithms demonstrate a better performance rate to get optimality. Finally, hybrid algorithms solve the discrete optimization problem in a short computing time for all datasets.

1. Introduction

Meta-heuristic algorithms are nature-inspired heuristics that are the subject of operations research, computer science, industrial engineering, transportation science, and other research fields [1, 2, 3]. The algorithms are generally applied to continuous and global optimization problems. Most algorithms are successful at continuous space, but others give average performance on continuous problems. On the other hand, it is needed to improve and develop variations of metaheuristics to handle with discrete problems in discrete space [4, 5]. Many heuristics have often been used to construct a traveling tour of a salesman, such as initial algorithms; nearest neighbor algorithm (NN), nearest insertion algorithm (NI), cheapest insertion algorithm (CI), random insertion algorithm (RI), furthest insertion algorithm (FI), minimal spanning tree algorithm (MST), and Christofides’ heuristic algorithm (CH) [6]. Other heuristics are used to obtain improved new solutions, such as tour improvement algorithms; 2-opt, 3-opt, and k-opt algorithms proposed by Lin and Kernighan [7, 8, 9]. Mixed methods are the alternative to implement on constructed tours by 2-opt and 3-opt algorithms. Some tours may be raised from the optimal solution of a traveling salesman, so it is needed to eliminate them from the solution to obtain a complete tour. There should be added some constraints to the available linear programming model for traveling salesman in the cutting plane algorithm (CP). In the branch and bound method (BB), the problem is separated into different sub-problems. Then, this process continues to examine all sub-problems. The branch and cut algorithm (BC) is similar to the branch and bound algorithm. However, the local bounds are calculated via the cutting plane algorithm [10, 11, 12, 13].

Modern heuristic methods have been investigated to find optimal, near-optimal, and acceptable solutions to combinatorial problems in recent decades. Classical metaheuristics have often been used to solve continuous and engineering problems, such as simulated annealing (SA), tabu search (TS), ant colony optimization (ACO), particle swarm optimization (PSO), and genetic algorithm (GA) [14, 15]. Modern metaheuristics have also been used to solve those problems, such as artificial bee colony algorithm (ABC), harmony search algorithm (HS), artificial atom algorithm (A3), black hole algorithm (BH), worm optimization (WO), water-wave optimization (WWO), camel algorithm (CA), whale optimization algorithm (WOA), socio evolution and learning optimization (SELO), physarum-energy optimization (PEO), color harmony algorithm (CHA), stochastic paint optimizer (SPO), and fire hawk optimizer (FHO) [16, 17, 18, 19, 20].

Population-based meta-heuristics generally search for optimal solutions better than single or multisolution-based algorithms. The reason for that is that they search for a wide area of solution space and focus on optimal areas by escaping local solutions. However, single or multisolution-based algorithms run quite better at long iterations and CPU time, such as hill climbing (HC), simulated annealing, and tabu search [15]. While population-based algorithms find near-optimal or acceptable solutions to optimization problems in short iterations and CPU time, they often solve problems optimally in long iterations and CPU time [16, 17]. Although the optimization process has frequently been done by iteration, most of the comparisons are done by population size, CPU time, the percentage of best and average deviations, and the number of objective function evaluations [21, 22].

The rest of the paper is organized as follows: In Section 2, the traveling salesman problem is clearly explained. The black hole algorithm, its variations, and the pseudocode are given in Section 3. In Section 4, the experimental analysis of the application of the proposed algorithms is described, and finally, Section 5 includes a conclusion and future works.

2. Traveling salesman problem

The traveling salesman problem is a wide research area that has been worked on by many scientists. TSP is a combinatorial problem, yet its optimal solution has not been found in polynomial time. Many heuristic algorithms have been proposed for combinatorial problems, but none of them guarantees the optimal solution in a reasonable time [23]. There exist many variants of TSP, such as symmetric (s-TSP) and asymmetric traveling salesman problem (a-TSP), traveling purchaser problem (TPP), Hamiltonian cycle problem (HCP), sequential ordering problem (SOP), multiple traveling salesman problem (m-TSP), orienteering problem (OP), vehicle routing problem (VRP), and its variants [24]. Vehicle routing problem has also important variants that are most applicable in transportation, industry, engineering, and science such as vehicle routing problem with profits (VRPP), team orienteering problem (TOP), capacitated team orienteering problem (CTOP), the top with time windows (TOPTW), vehicle routing problem with pick-up and delivery (VRPPD), vehicle routing problem with LIFO, vehicle routing problem with time windows (VRPTW), capacitated vehicle routing problem (CVRP or CVRPTW), open vehicle routing problem (OVRP), inventory routing problem (IRP), and vehicle routing problem with transfers (VRPWT) [25, 26, 27]. Its variants can be reduced to a traveling salesman problem if certain assumptions are accepted or any alternative algorithm is found. The problem gets hard when the number of data increases, the distance matrix changes, some constraints are added, the objective function changes, and so on.

The popular variants of TSP are traveling purchaser problems, multiple traveling salesman problems, and vehicle routing problems. The traveling purchaser problem is a problem that purchaser travels and purchases a set of items from different places if a budget, fuel, time, and other constraints are satisfied. In addition, different objectives can be set under the constraints [28, 29]. The multiple traveling salesman problem is a problem in which more than one salesman travels and turns to the home under different objectives [30]. The vehicle routing problem (VRP) is a combinatorial problem to find the optimal set of routes for a fleet of vehicles to traverse to deliver to a given set of customers. The fleet of vehicles can be set as homogeneous or heterogeneous [27].

The formulation of TSP is briefly given in Eq. (1). The nodes, edges, sets, and vertices are given as follows: N is the set of n nodes, E is the set of the edges, and Dist_ij = (d_ij) is the symmetric distances (dij = dji) that are equal between nodes and the asymmetric distances (d_ij ≠ d_ji) that are not equal between nodes.

Tour_k = {v₁,v₂,……..,v_n,v₁} is a candidate tour for all the solution space, and k = 1,2,3,…..,m. v₁ indicates the first vertex, and v_n indicates the nth vertex of all the candidate tours.

$$\mathit{Min}.\sum _{i=1}^{n-1}\left(d_{v_i,v_{i+1}}\right)+d_{v_n,v_1}$$E1

Different TSP distances can be used in the solution of the discrete problem. Therefore, the optimal solution, deviation of solution, and CPU time change when different types of distances are used. The Euclidean distance is generally applied to calculate the distance between nodes using Eq. (2). In Eq. (2), x_i and x_j indicate the x-axis coordinates of Euclidean cities, and y_i and y_j indicate the y-axis coordinates of the Euclidean cities.

$$d_{i,j}=\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}$$E2

3. Black hole algorithm and its hybrids

The black hole algorithm is a metaheuristic algorithm proposed for data clustering in 2013. The algorithm principle is based on the black hole phenomenon and the stars that move toward the black hole. There is a possibility that a star reaches a better location in continuous space or a better objective in discrete space [31, 32]. Thus, the new star replaces the black hole. If a candidate star (solution) enters the radius of the event horizon in the algorithm, the candidate star will be sucked by the black hole. When a candidate star dies, another candidate star (solution) is randomly generated in the search space. Then, the old stars (solutions) and new stars create a new population [33, 34, 35].

The new candidates are generated in the continuous search space via Eq. (3).

$$x_i\left(t+1\right)=x_i\left(t\right)+\mathit{rand}\ast \left(x_{\mathit{BH}}-x_i\left(t\right)\right)$$E3

In this discrete application, update star locations via the selection of minimum multiple neighborhood operators in Eq. (4).

$$\mathit{\text{MMOp}}=min\left(\mathit{\text{swap}},\mathit{\text{insertion}},\mathit{\text{reversing}},\mathit{\text{swap}}-\mathit{\text{reversing}}\right)$$E4

The new candidates are updated by the objectives found in Eq. (5).

$$\begin{array}{l}{\mathit{\text{NewObj}}}_{\mathit{now}}^{i,t}<{\mathit{Obj}}_{\mathit{now}}^{i,t}\\ {\mathit{Obj}}_{\mathit{now}}^{i,t}=\mathit{New}{\mathit{Obj}}_{\mathit{now}}^{i,t}\end{array}$$E5

The black hole algorithm event-horizon condition in continuous search space is formulated in Eq. (6).

$$\left|f_{\mathit{BH}}-f_i\right|<\frac{f_{\mathit{BH}}}{{\sum }_{i=1}^N{f}_i}$$E6

The event-horizon condition is applied, and the specific parameter Q_Data is selected for discrete problems especially in each TSP dataset via Eqs. (6) and (7) [36].

$$\frac{Q_{\mathit{\text{Data}}}}{\left|{\mathit{Obj}}_{\mathit{BH}}-{\mathit{Obj}}_i\right|}<\frac{f_{\mathit{BH}}}{{\sum }_{i=1}^N{f}_i}$$E7

When the star enters the event-horizon radius of the black hole, the old star (solution) is updated by the new solution. The final population is generated by the current and the updated solutions. The black hole algorithm and its hybrids have a pure algorithm structure and less number of parameters; so, their use is effective and advantageous for scientific areas, technology, and research.

The pseudo-code of the improved and/or hybrid black hole algorithm is shown in Figure 1 [36].

Figure 1.

Pseudo-code of the improved and/or hybrid black hole algorithm.

The black hole algorithm can be hybridized with a constructive heuristic (Clarke and Wright, NN, k-NN, NI, CI, RI, FI, MST, or CH), with improving a local search (swap/or insert, reverse/or 2-opt swap, and swap-reverse/or 3-opt swap heuristic).

As noted above, even though those hybrid algorithms do not guarantee optimal solutions, they could solve the combinatorial problems in competitive CPU times. Most of the hybrid algorithms run in polynomial computational times, and they produce near-optimal or acceptable solutions, which are useful for science, engineering, and technology due to some criteria, such as security, design, flexibility, assembly, and production.

4. Experimental results

The 10 small and medium-scale datasets (52–195) are used from the TSPLIB library in the experimental study. In the study, all the computations were run 10 times independently on Intel® Core™ i7 12,650-H CPU 2.3–4.7 GHz speed with 64 GB RAM using MATLAB. In Table 1, the performance of hybrid metaheuristic algorithms BH + swap, BH + insertion, BH + reverse, and BH + swap-reverse are evaluated by algorithm results and percentage deviation. In this work, a type of 2-opt swap heuristic named reverse and one type of 3-opt swap heuristic named swap-reverse heuristics are used. In Table 1, BH + NN + reverse and other BH hybrid algorithms are also compared with each other. The standard appropriate) parameters are used for all the datasets using 1000–3000 iteration numbers and an increasing number of data (52–195).

Problem	Algorithm	Best	Ave.	BDev.	AvDev.	Time
berlin52	BH + swap	7769.84	7910.85	3.02	4.89	3.43
(7542)	BH + insertion	7635.3	7901.93	1.24	4.77	3.15
	BH + reverse	7583.71	7842.05	0.55	3.98	3.31
	BH + s-reverse	7899.49	8074.09	4.74	7.06	4.16
	BH + NN + reverse	7760.63	7785.24	2.9	3.23	3.71
st70	BH + swap	742.02	765.37	9.93	13.39	4.32
(675)	BH + insertion	709.7	756.13	5.14	12.02	4.1
	BH + reverse	708.84	743.11	5.01	10.09	3.67
	BH + s-reverse	772.66	794.77	14.47	17.74	4.88
	BH + NN + reverse	695.39	713.96	3.02	5.77	4.6
eil76	BH + swap	580.71	588.76	7.94	9.43	10.51
(538)	BH + insertion	578.7	585.95	7.56	8.91	10.45
	BH + reverse	575.46	583.98	6.96	8.55	9.4
	BH + s-reverse	566.9	583.39	5.37	8.44	13.09
	BH + NN + reverse	559.37	570.9	3.97	6.12	10.45
pr76	BH + swap	115,104	118,241	6.42	9.32	6.18
(108159)	BH + insertion	113,677	116,393	5.1	7.61	8.7
	BH + reverse	110,053	114,910	1.75	6.24	9.22
	BH + s-reverse	113,407	116,373	4.85	7.59	14.82
	BH + NN + reverse	110,919	112,468	2.55	3.98	9.89
rat99	BH + swap	1437.76	1474.48	18.72	21.76	9.3
(1211)	BH + insertion	1341.74	1453.95	10.8	20.06	9.87
	BH + reverse	1339.32	1399.75	10.6	15.59	12.16
	BH + s-reverse	1424.29	1479.18	17.61	22.15	12.6
	BH + NN + reverse	1278.04	1300.53	5.54	7.39	9.55
kroa100	BH + swap	22665.8	23788.2	6.5	11.78	26.1
(21282)	BH + insertion	22385.2	23697.5	5.18	11.35	24.06
	BH + reverse	22,550	23988.5	5.96	12.72	32.29
	BH + s-reverse	22465.1	23591.1	5.56	10.85	43.48
	BH + NN + reverse	21311.7	21920.1	0.14	3	28.93
eil101	BH + swap	677.92	702.8	7.78	11.73	30.72
(629)	BH + insertion	670.43	696.2	6.59	10.68	27.6
	BH + reverse	671.46	691.66	6.75	9.96	53.65
	BH + s-reverse	684.11	708.91	8.76	12.7	32.5
	BH + NN + reverse	655.14	662.11	4.16	5.26	32.12
bier127	BH + swap	131,090	137,349	10.83	16.12	42.1
(118282)	BH + insertion	127,183	134,630	7.53	13.82	35.9
	BH + reverse	127,443	135,921	7.74	14.91	39.69
	BH + s-reverse	131,046	136,960	10.79	15.79	31.93
	BH + NN + reverse	123,558	125,358	4.46	5.98	29.11
kroa150	BH + swap	33735.6	36374.7	27.19	37.14	48.3
(26524)	BH + insertion	33340.2	35639.8	25.7	34.37	40.51
	BH + reverse	33319.1	35,195	25.62	32.69	30.89
	BH + s-reverse	34169.1	36700.8	28.82	38.37	45.34
	BH + NN + reverse	28533.9	28859.6	7.58	8.81	31.68
rat195	BH + swap	3605.09	3767.97	55.19	62.2	56.5
(2323)	BH + insertion	3468.81	3749.51	49.32	61.41	42.68
	BH + reverse	3402.19	3591.48	46.46	54.61	55.54
	BH + s-reverse	3636.24	3833.81	56.53	65.04	61.11
	BH + NN + reverse	2582.33	2599.01	11.16	11.88	46.23

Table 1.

Experimental results of BH and its hybrids on the TSP datasets.

The population size of algorithms BH + Heuristics is increased two times and taken as 100 for (berlin52-rat99), and 200 for (kroa100-rat195) in Table 1. The maximum iteration number is increased three times and taken as 1000 for (berlin52-st70), 2000 for (eil76-rat99), and 3000 for (kroa100-rat195) in Table 1.

In Table 1, for berlin52-bier127, the hybrid metaheuristics without an initial algorithm would give challenging near-optimal solutions. Particularly, in kroa150 and rat195, the deviations from best-known solutions can be simply observed. On the other hand, the swap-reverse heuristic gives worse solutions than the 3-opt swap heuristic algorithm. Because, if a 3-opt heuristic was applied, the best among the eight alternatives was taken. As concluded from Table 2, though the BH + NN + reverse heuristic CPU times are slightly different than the BH + insertion heuristic times, the obvious differences can be observed in the Best and Average deviations. This is valid for other BH hybrid algorithms (BH + swap, BH + reverse, and BH + swap-reverse). The conclusion drawn from Tables 1 and 2 is that the near-optimal and acceptable solutions are preferred by the decision-makers and managers who work with science, engineering, and technology due to some criteria mentioned, such as security, design, and flexibility.

	Best; deviation	Average deviation	CPU; time
BH + swap	15.35	19.78	23.75
BH + insertion	12.42	18.5	20.70
BH + reverse	11.74	16.93	24.98
BH + swap-reverse	15.75	20.57	26.39
BH + NN + reverse	4.55	6.14	20.63

Table 2.

Mean of best, average deviations, and CPU time on the TSP datasets.

Figure 2 presents a set of obtained solutions by the hybrid black hole algorithm with a reverse operator on the benchmark test data sets.

Figure 2.

A set of solutions found by the hybrid BH algorithm on the TSP datasets (black hole algorithm + nearest neighbor + reverse metaheuristic).

Figure 3 shows the performance of algorithms on a sample of TSP datasets (berlin52-bier127). All algorithms, except BH + NN + reverse, are competitive results and get fairly higher performance when Table 2 and Figure 3 are compared. Although the BH + swap-reverse hybrid metaheuristic shows slightly worse performance, it is quite better at three datasets: eil76, pr76, and kroa100. On the other hand, the proposed approach gets slightly better performance in the mean of average deviations when Table 2 and Figure 3 are compared.

Figure 3.

Average deviations of hybrid algorithms on the TSP datasets.

5. Conclusions and future work

In recent literature and engineering research of the field, solving discrete and engineering problems using hybrid heuristics and metaheuristics is an area of increasing interest. In this paper, the hybrid metaheuristics are experimented with the symmetric TSP instances. To evaluate the performance of hybrid metaheuristics, it has been tested on ten medium-scale datasets. The experimental results show that the proposed hybrid algorithm BH + NN + reverse finds better solutions compared to the BH + swap, BH + insertion, BH + reverse, and BH + swap-reverse for all of the datasets and all of the optimal solutions. As CPU time is considered, the hybrid algorithm is considerably fast (20.63 secs.) to find near-optimal solutions. BH + reverse is the second algorithm when compared to the BH + swap, BH + insertion, and BH + swap-reverse. However, it needs a longer computational time (24.98) compared to BH + swap (23.75 sec.) and BH + insertion (20.70 secs.). It is a remarkable result that BH + insertion is the third algorithm to find near-optimal solutions. It is slightly slower than the proposed hybrid algorithm.

When detailed investigation is made on sample datasets (berlin52-bier127), the hybrid algorithms without the initial algorithm are quite challenging algorithms with each other. However, the proposed algorithm BH + NN + reverse is the best among the five alternatives. When the CPU time is calculated, the BH + insertion is the fastest algorithm (15.48 secs.), the proposed one is the second alternative (16.05 secs.), and BH + swap is the third alternative (16.58 secs). Nevertheless, the BH + reverse metaheuristic is the last alternative among hybrid algorithms (20.42 secs.).

In previous studies, the effect of heuristic algorithms on the performance of meta-heuristics has been strongly underlined. The exploration and exploitation phase of the algorithm directly depends on the type of heuristic being used. Those heuristics respond to different optimal solutions with different metaheuristics in longer iteration and computation time. In general, different heuristic algorithms contribute differently to the combinatorial and engineering problems. Conversely, the experimental results are valid for medium-sized TSP problems and a few number of iterations (1000–3000) in the application.

In future works, the hybrid metaheuristics can be further analyzed and combined with other heuristics and metaheuristics. Many applications could be done using those hybrid algorithms to evaluate performance analysis and solve engineering problems in applied mathematics, chemistry, biology, genetics, and nanotechnology. In another aspect, there could be application areas in industrial engineering, computer engineering, operations research, and combinatorial optimization, such as scheduling, assignment, timetabling, routing, location selection, inventory allocation, and logistics. To sum up, there are interdisciplinary working fields between science, technology, combinatorial optimization, and hybrid metaheuristic algorithms.

Acknowledgments

The author is responsible for all the manuscript, data availability, and coded optimization algorithms. The author declares that this work did not receive funding in the public, commercial, and non-profit sectors.

Conflict of interest

The author declares that there is no conflict of interest.

Thanks

The author thanks the editors and reviewers for their valuable comments and suggestions, which increased the clarity and scope of the article.