# Rank-Based Ant System with Originality Reinforcement and Pheromone Smoothing
## 4 Experimental Results
### Experimental Setup  
Due to their stochastic nature, all ACO algorithms were run 30 times for each problem instance. During each run, the length of the best-found solution at each iteration is saved. This information is later used for comparing the performance of the algorithms by means of comparative tables and evolutionary curves (see Sections 4.3 and 4.4 for details). Regarding the parameter settings, typically recommended values, already used in several previous studies, were selected [11; 13; 14; 18]. The following pheromone and heuristic influence parameters were set for all ACO algorithms; \(\alpha=1,\beta=2\). The number of ants \(m\) was set equal to the number of cities \(n\) for all ACO algorithms with exception of ACS, leading to good algorithm performance (see [14] for details). In the case of ACS, the number of ants \(m\) per iteration was set equal to 10, as recommended in [12; 14]. Regarding the values of ACS-specific parameters, the following recommended values were considered: \(q_{0}=0.9\), \(\xi=0.1\)[12; 14]. Regarding Rank-based ACO variants, the following parameters were considered: \(w=6\), \(\rho=0.1\) and \(\tau_{0}=m/f(s_{gb})\), also selected in previous studies [14]. Furthermore, in the case of MMAS, the evaporation parameter is set to \(\rho=0.02\), the iteration-best solution is considered for pheromone reinforcement, and pheromone trails reinitialization to \(\tau_{max}\) is triggered whenever no improved tour has been found for more than 250 iterations [14]. With regard to the parameter settings of the proposed algorithm, the common parameters with \(AS_{Rank}\) are set with the same values for a fair comparison. Additionally, the pheromone smoothing strategy rescales the pheromone table to \([0.1\tau_{0},\tau_{0}]\) whenever the standard deviation of the lengths of the 80% of the ant tours of the iteration is zero. This criterion was chosen empirically, after observing that in most of the cases, AS\({}_{Rank}\) is not able to find a better solution once 80% of the ants have followed the same path (i.e., have \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Instance** & **Type** & **Optimal Solution** & **Dimension (\(n\))** \\ \hline brazil58 & TSP & 25,395 & 58 \\ \hline kroA100 & TSP & 21,282 & 100 \\ \hline ch130 & TSP & 6110 & 130 \\ \hline tsp225 & TSP & 3916 & 335 \\ \hline gr48 & TSP & 5046 & 48 \\ \hline pr76 & TSP & 108,159 & 76 \\ \hline gr202 & ATSP & 40,160 & 202 \\ \hline frv35 & ATSP & 1473 & 36 \\ \hline frv64 & ATSP & 1839 & 65 \\ \hline frv70 & ATSP & 1950 & 71 \\ \hline ESC78 & SOP & 18,230 & 80 \\ \hline fr70.1 & SOP & 39,313 & 71 \\ \hline p43.1 & SOP & 28,140 & 44 \\ \hline p43.4 & SOP & 83,005 & 44 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Problem instances used in this paper for the experiments and analysis. the same fitness). The results of the analysis are shown in Table 2, where for each problem instance, the number of simulations (from a total of 30 runs) is shown in which AS\({}_{Rank}\) has been able to find a better solution after different percentages \(d\) of solutions (from \(d=10\%\), 20%,..., to 100%) have reached null standard deviation (i.e., after the \(d\%\) of the ants have had the same fitness). The objective of this analysis is to find a good balance, avoiding applying the smoothing mechanism too late (wasting a lot of algorithm iterations with little chance of improving the best solution found so far) or, on the contrary, applying the smoothing mechanism too early (where the pheromone information could still be further exploited to find a better solution). The results of Table 2 show that quite often, AS\({}_{Rank}\) is able to find a better solution after 10% of the \(m\) solutions have the same fitness, e.g., 22 of the 30 runs for _brazil58_ instance, or 17 of the 30 runs in _kroA100_ instance. As we would expect, the higher percentage of solutions considered, the closer it gets to a stagnation situation and the harder it is for the algorithm to find a better solution.