# The Pheromone-Based Harmony Search Algorithm for the Asymmetric Traveling Salesman Problem
## 6 Research Methodology  
The effectiveness of the suggested approach, taking into consideration the application of a pheromone, was tested on the basis of nineteen instances of the ATSP the characteristic of which was presented in Table 1 (on the basis of [35], where the optimal (best obtainable) route lengths for particular tasks are presented; they are available in the TSPLIB library, described in [36]). In addition, the effectiveness of the methods was verified on the basis of a case study, involving the visit of 40 points located in the Silesian Voivodeship in Poland (it can model e.g., problems related to the distribution of many products; the distance matrix has been prepared with an accuracy to the one meter). A case study map with the locations marked is shown in Figure 1.  
All tasks were solved 30 times by the HS algorithm and three variants of the PBHS (differing in the value of the parameter \(\rho\)). To solve the case study we also used the NNA that is often used when companies do not use the right optimization software.  
On the basis of work [15] the following parameter values were set: \(R=1000\), \(HMS=5\), \(HMCR=0.98\) and \(PAR=0.25\). Additionally, when analyzing the convergence of the technique (presented in [37]) it was assumed that \(IT=1\),000,000, and as the value of the parameter \(\rho\): 0.25, 0.5 and 0.75 were selected (tests were conducted for each of them in order to select the recommended approach to the designed method).  
The algorithms analysed in this work were implemented in language C#, and tests were conducted on a Lenovo Legion Y520 laptop (with: Intel Core i7-7700 HQ, 32 GB RAM (SO-DIMM DDR4, 2400 MHz), 1000 GB SATA 7200 RPM, 240 GB SSD M.2 PCIe and Windows 10 Home 64-bit).  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**No.** & **Name** & **Number of Vertices** & **Optimum** \\ \hline
1 & br17 & 17 & 39 \\
2 & ftv33 & 34 & 1286 \\
3 & ftv35 & 36 & 1473 \\
4 & ftv38 & 39 & 1530 \\
5 & p43 & 43 & 5620 \\
6 & ftv44 & 45 & 1613 \\
7 & ftv47 & 48 & 1776 \\
8 & ry48p & 48 & 14,422 \\
9 & ft53 & 53 & 6905 \\
10 & ftv55 & 56 & 1608 \\
11 & ftv64 & 65 & 1839 \\
12 & ft70 & 70 & 38,673 \\
13 & ftv70 & 71 & 1950 \\
14 & kro124p & 100 & 36,230 \\
15 & ftv170 & 171 & 2755 \\
16 & rbg323 & 323 & 1326 \\
17 & rbg358 & 358 & 1163 \\
18 & rbg403 & 403 & 2465 \\
19 & rbg443 & 443 & 2720 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Description of benchmark tests.  
Both the average error (defined on the basis of Formula (10)) and the actual time of running algorithms were subjected to evaluation. The second measure makes it possible to take into consideration time overhead connected with the introduced modifications and as a result enables defining of the usefulness of the technique in practical adaptations. In addition, we analyzed the number of iterations, after which the algorithm achieved convergence for tasks from TSPLIB.  
\[\text{Average error}=\frac{\text{average objective function value}-\text{ optimum}}{\text{optimum}}\cdot 100\%. \tag{10}\]  
The effectiveness of the proposed method was assessed by comparing the obtained average error with the results achieved by the following algorithms appearing in the literature on the subject:  
* Adaptive Multi-Crossover Population Algorithm (AMCPA) [35],
* GA [35],
* Greedy Local Search (GLS) with starting solution constructed by NNA [15],
* Hill Climbing (HC) with starting solution constructed by NNA [15],
* NNA [15].  
We chose them, because the first two methods are population-based (like the HS), while the rest of them are classic algorithms commonly used to solve the ATSP instances.