# Adjustable Pheromone Reinforcement Strategies for Problems with Efficient Heuristic Information
## 6 Experimental Settings  
For experiments, we have implemented MMAS for TSP and ATSP both with and without local optimization in C++. For TSP, implemented local optimization was the 2-opt that always accepts the first improvement gained by 2-exchange. For ATSP, we used 2.5-opt also with the first improvement. For all algorithms, the parameter \(\alpha\) was set to 1; for problem instances of size 100 or more, the favorite list size was set to 30, and an initial value for the pheromone trail was set according to the following equation:  
\[\tau_{0}=\frac{1}{\rho\cdot\mathbf{f}(\mathbf{s}^{mn})}, \tag{5}\]  
where \(\mathbf{f}(\mathbf{s}^{mn})\) is the cost of an approximate solution obtained by the nearest neighbor heuristic, and the upper trail limit \(\tau_{\text{MAX}}\) was set equal to \(\tau_{0}\). For MMAS algorithms without local optimization, the colony size \(m\) was set equal to the size of the problem \(n\), \(\beta\) was set to 4, and \(\rho\) was set to 0.02, while for MMAS algorithms with local optimization, the colony size \(m\) was set equal to 25, \(\beta\) was set to 2, and \(\rho\) to 0.2. These parameters are recommended in the literature for MMAS designed for TSP and ATSP [8;37]. For each problem instance, we tested 24 pheromone reinforcement strategies: 1/5-best, 1/4-best, 1/3-best, 1/2-best, 2-best, 4-best, 8-best, 16-best, 32-best, 64-best, 128-best, max-2-best, max-4-best, max-8-best, max-16-best, max-32-best, max-64-best, max-128-best, 5-1-ib-gb, 3-1-ib-gb, 2-1-ib-gb, 1-1-ib-gb, iteration-best = 1/1-best = 1-best = max-1-best, and global-best = \(\infty\)-best = max-\(\infty\)-best. Each experiment was allowed 10,000 iterations, and each experiment was repeated 101 times. All together, 7.05 \(\times\) 10\({}^{11}\) solutions were constructed by MMASs, not counting changes achieved by local optimization. The experiments were conducted on computer cluster Isabella. For TSP, we used well-known problem instances available in TSPLIB (TSPLIB collection of TSP instances is publicly available at [[http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/)]([http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/)), accessed on 1 April 2023) and VLSI Data Sets (VLSI Data Sets collection of TSP instances is publicly available at [[https://www.math.uwaterloo.ca/tsp/vlsi/](https://www.math.uwaterloo.ca/tsp/vlsi/)]([https://www.math.uwaterloo.ca/tsp/vlsi/](https://www.math.uwaterloo.ca/tsp/vlsi/)), accessed on 1 April 2023), and for ATSP instances from 8 th DIMACS Implementation Challenges (ATSP instances from 8 th DIMACS Implementation Challenge are publicly available at [[http://dimacs.rutgers.edu/archive/Challenges/TSP/atsp.html](http://dimacs.rutgers.edu/archive/Challenges/TSP/atsp.html)]([http://dimacs.rutgers.edu/archive/Challenges/TSP/atsp.html](http://dimacs.rutgers.edu/archive/Challenges/TSP/atsp.html)), accessed on 1 April 2023). Their characteristics and stopping criteria for MMAS without local optimization and for MMAS with 2-opt local optimization are listed in Tables 1 and 2. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Problem** & **Size** & **Optimal** & **Iterations for** & **Iterations for** \\
**Instance** & **Size** & **Solution** & **MMAS No LO** & **MMAS \& 2-OPT** \\ \hline gr21 & 21 & 2707 & 100 & 100 \\ bays29 & 29 & 2020 & 400 & 100 \\ swiss42 & 42 & 1273 & 200 & 100 \\ hk48 & 48 & 11,461 & 200 & 100 \\ eil51 & 51 & 426 & 500 & 100 \\ berlin52 & 52 & 7542 & 300 & 100 \\ st70 & 70 & 675 & 800 & 100 \\ eil76 & 76 & 538 & 500 & 100 \\ kroA100 & 100 & 21,282 & 800 & 100 \\ kroD100 & 100 & 21,294 & 1400 & 100 \\ eil101 & 101 & 629 & 900 & 200 \\ lin105 & 105 & 14,379 & 400 & 100 \\ pr124 & 124 & 59,030 & 800 & 100 \\ xqf131 & 131 & 564 & 4500 & 2900 \\ pr144 & 144 & 58,537 & 8700 & 100 \\ ch150 & 150 & 6528 & 900 & 100 \\ \hline \hline \end{tabular}
\end{table}