# Hyper-Heuristic Based on ACO and Local Search for Dynamic Optimization Problems +
## 4 Computational Tests  
### Experimental Setup  
During the literature review, we noticed that the computational experiments for DTSPs remain in a small number of TSP instances from TSPLib, mainly from the family KROA (more specifically KROA100, KROA150 and KROA200. The KROA family has been proposed by [49] and came from examples of truck-dispatching problems. We compare the results in the literature with the ones obtained by HULK, considering the magnitude of change \(m=0.10\). To be fair to the literature, we first perform the tests without arc blocking with the same set of parameters used here. We also compute the results from the family KROA considering arc blocking. We investigate the proposed hyper-heuristic, which cleverly combines the flexibility of ACO to provide solutions for symmetric and asymmetric dynamic changes with the power of improvement of two good local search operators. Comparisons of the performance of the following strategies were investigated for DTSPs:  
* \(\mathcal{MMAS}\) + US: for each best-so-far ant found by \(\mathcal{MMAS}\), we apply the US local search operator pursuing improvements (detailed in [8]).
* \(\mathcal{MMAS}\) + LK: for each best-so-far ant found by \(\mathcal{MMAS}\), we apply the LK local search operator pursuing improvements (detailed in [8]).
* HULK: proposed hyper-heuristic that combines ACO with the LSOs LK and US, biased by a self-adjusting weighted roulette wheel (detailed in Algorithm 2).  
The initial parameters for tested methods use the following values: \(\alpha=1\), \(\beta=5\), \(\gamma=0.5\), \(\delta=0.5\), \(\rho=0.8\) and \(\omega=50\) (number of ants). In addition to the instances of the KROA family, DTSPs are generated from six originally symmetric static benchmark instances obtained from TSPLIB (Available from [[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 9 August 2021): d198, pcb442, u574, pcb1173, rat783 and lin318, using the dynamic generator described in Section 2.2. The first four benchmark instances originate from the operation of drilling holes in printed circuit boards [50], the fifth benchmark instance arises from rattled grid [51] and the sixth benchmark instance from the travel cost between cities [34].  
The frequency of change \(f\) was set to change every 100 algorithmic evaluations, and the amplitude of change \(m\) was set to 0.05, 0.1, 0.2 and 0.4, denoting small to medium changing environments; we also allowed blocking up to 1% of the arcs selected for dynamic change trying to keep at least one Hamiltonian cycle. On the whole, there were 72 instances to be tested as follows: a series of four DTSP test cases were constructed from each stationary instance, for symmetric and asymmetric changes, to systematically investigate the performance of the algorithms (all asymmetric problem instances had an extension of.atsp at the end of the problem label). For the asymmetric instances only asymmetric dynamic changes were allowed. Thirty independent runs for each algorithm were performed on a DTSP, kept at the same set of random seeds. For each run, we allowed 100 environmental changes, storing the best-so-far solution for each of them. All seeds used in the random generators were kept for all environmental changes, and the random numbers were uniformly distributed. To be fair, all methods performed the same number of evaluations. The proportional evaluations required when applying LSOs were added to the total evaluations of the algorithms.  
To evaluate the methods overall performance, the _offline performance_[52] is used as defined in Equation (15).  
\[\bar{P}_{offline}=\frac{1}{E}\sum_{t=1}^{E}\phi(\pi^{bs},t)\,, \tag{15}\]  
where \(E\) is the total number of evaluations and \(\pi^{bs}\) is the best-so-far solution quality after each dynamic change.