## 3 Single-Objective Parameter Tuning
### The Tuning Algorithm
#### 3.1.2 F-Race  
F-race uses a racing approach to find the optimal parameter configuration for a meta-heuristic. The general strategy of F-race is to continuously evaluate control parameter configurations on different problem instances and eliminate configurations that perform statistically significantly worse than the rest. It continues until only one configuration remains. Suppose a sequence of problem instances \(i_{k}\in I\) and candidate configurations \(\Theta_{k}\subset\Theta\). At each step \(k\), each candidate configuration \(\theta_{j}\in\Theta_{k}\) is evaluated on problem instance \(i_{k}\) to form  
\[\mathbf{c}_{k}(\theta_{j})=\left[c(\theta_{j}|i_{1}),c(\theta_{j}|i_{2}), \ldots,c(\theta_{j}|i_{k})\right] \tag{2}\]  
by appending the performance value of configuration \(\theta_{j}\) on problem instance \(i_{k}\) to \(\mathbf{c}_{k-1}(\theta_{j})\). The set of configurations \(\Theta_{k}\) is generated by eliminating the worst-performing candidates from \(\Theta_{k-1}\). This leads to a nested sequence of sets of parameter configurations,  
\[\Theta\supset\Theta_{1}\supseteq\Theta_{2}\supseteq\cdots\supseteq\Theta_{k} \tag{3}\]  
To eliminate the worst-performing candidates from \(\Theta_{k-1}\), the Friedman test [7] is used to determine whether there is a statistically significant difference between candidates. For each step \(k\), candidates are ranked in non-decreasing order to form a rank matrix:  
\[R= \begin{bmatrix}r_{1}(\theta_{1})&r_{1}(\theta_{2})&\cdots&r_{1}(\theta_{m} )\\ r_{2}(\theta_{1})&r_{2}(\theta_{2})&\cdots&r_{2}(\theta_{m})\\ \vdots&\vdots&\ddots&\vdots\\ r_{k}(\theta_{1})&r_{k}(\theta_{2})&\cdots&r_{k}(\theta_{m})\end{bmatrix}  \tag{4}\]  
where \(r_{l}(\theta_{j})\) is the rank of configuration \(\theta_{j}\in\Theta_{k}\) based on the performance value \(c(\theta_{j}|i_{l})\), and \(m=|\Theta_{k}|\). The following test statistic is used:  
\[T=\frac{(m-1)\sum\limits_{j=1}^{m}\left(R_{j}-\frac{k(m+1)}{2}\right)^{2}}{ \left(\sum\limits_{l=1}^{k}\sum\limits_{j=1}^{m}R_{j}^{2}\right)-\frac{km(m+1) ^{2}}{4}} \tag{5}\]where \(R_{j}=\sum_{t=1}^{k}R_{ij}\). Under the null hypothesis that all configurations perform equally, \(T\) is approximately \(\chi^{2}\) distributed with \(m-1\) degrees of freedom. Thus, if \(T\) is larger than the \(\alpha-1\) quantile of the \(\chi^{2}\) distribution, the null hypothesis is rejected and there exists at least one configuration that performs statistically significantly differently from the rest. If this is the case, pairwise comparisons of the configurations should be performed. Two candidates \(\theta_{j}\) and \(\theta_{k}\) are considered to be statistically significantly different if  
\[\frac{|R_{j}-R_{h}|}{\sqrt{\frac{2k\left(1-\frac{T}{k(m-1)}\right)\left(\left( \sum_{t=1}^{k}\sum_{j=1}^{m}R_{j}^{2}\right)-\frac{\ln(m+1)^{2}}{4}\right)}{( k-1)(m-1)}}}>t_{1-\frac{k}{2}} \tag{6}\]  
where \(t_{1-\frac{k}{2}}\) is the \((1-\frac{k}{2})\) quantile of the Student's t-distribution. For the purpose of eliminating a candidate in F-race, each candidate is compared to the candidate that has the best expected rank,  
\[ER(\theta_{j})=\frac{1}{k}R_{j} \tag{7}\]  
Every candidate that shows a significant difference in performance compared to the best candidate is eliminated from the race. When only searching for one configuration, the possibility that more than one optimal configuration might exist is not considered. [PERSON] and [PERSON] [8] suggested that regression analysis be performed on the \(p\)-values of the Friedman test. Every time the Friedman test is conducted, and the null hypothesis is not rejected, the \(p\)-value of the test is recorded. After at least ten recordings, a least-squares regression is performed on the \(p\)-values. If the gradient of this regression line is greater than or equal to zero, it implies that the remaining configurations are similar enough that further evaluation is unnecessary and will waste computational resources.