# Self-Tuning Lam Annealing: Learning Hyperparameters While Problem Solving
## 2 Methods
### Self-Tuning Lam
#### 2.3.5 Putting It All Together
Figure 4: OneMax (each 0-bit costs 100): Self-Tuning Lam, Modified Lam, and target acceptance rates for (**a**) 1000 iterations, (**b**) 10,000 iterations, (**c**) 100,000 iterations, and (**d**) 1 million iterations. Figure 3: OneMax (each 0-bit costs 10): Self-Tuning Lam, Modified Lam, and target acceptance rates for (**a**) 1000 iterations, (**b**) 10,000 iterations, (**c**) 100,000 iterations, and (**d**) 1 million iterations. Although our focus is in better matching the target Lam rate, we also provide results on the optimization objective in Tables 2-4 for all three scales of OneMax. In all three cases, all runs of length 100,000 or more iterations optimally solved the problem by the end of the run. Nearly all 10,000 iteration runs optimally solved the problem as well. Any difference in solution quality for longer runs is negligible. For the shortest runs (1000 iterations), the Modified Lam found higher quality (lower cost) solutions on average when the cost per bit was either 10 or 100 (Tables 3 and 4, respectively), but the Self-Tuning Lam found better solutions when the cost per bit was 1 (Table 2). There is a simple explanation for why the Modified Lam finds better solutions for short runs when 0-bits cost 10 or 100. Ironically, it is exactly due to its failure to match the target acceptance rate. OneMax has no local optima, so accepting any neighbor of increasing cost will definitely increase time to find the optimal. When we scale the cost of 0-bits to 10 or 100, the initial temperature \(T_{0}=0.5\) is so low relative to the costs that the probability of accepting neighbors of increased cost is very near 0, and the run is so short that there is insufficient time to increase \(T\) to converge with the target acceptance rate (e.g., see Figures 3a and 4a). Thus, the Modified Lam is behaving like a strict hill climber, and a strict hill climber should necessarily outperform SA on OneMax. We include OneMax results to demonstrate the Self-Tuning Lam's ability to more effectively match the target acceptance rate independent of the cost scale, which it does quite nicely. #### 3.1.2 TwoMax: Single Global Optimum and Single Local Optimum

We next consider the classic TwoMax problem [38] over bit vectors \(x\) of length \(n\), characterized by one global optimum, and one local optimum, where we must maximize:

\[f(x)=|18\cdot\text{CountOfOneBits}(x)-8\cdot n|. \tag{28}\]

The global maximum is \(x\) of all ones, with \(f(x)=10n\); and the local maximum is \(x\) of all zeros, with \(f(x)=8n\). We transform the problem to minimizing the cost function:

\[C(x)=10\cdot n-|18\cdot\text{CountOfOneBits}(x)-8\cdot n|. \tag{29}\] \begin{table}
\begin{tabular}{c c c c} \hline \hline \(N\) & **Modified Lam** & **Self-Tuning Lam** & **T-Test \(p\)-Value** \\ \hline
1000 & 231.0 & 1661.0 & \(<\)10\({}^{-66}\) \\
10,000 & 0.00 & 6.00 & 0.01 \\
100,000 & 0.00 & 0.00 & n/a \\
1,000,000 & 0.00 & 0.00 & n/a \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Average solution cost for the OneMax problem, case when each 0-bit costs 100. \begin{table}
\begin{tabular}{c c c c} \hline \hline \(N\) & **Modified Lam** & **Self-Tuning Lam** & **T-Test \(p\)-Value** \\ \hline
1000 & 24.5 & 16.5 & \(<\)10\({}^{-26}\) \\
10,000 & 0.01 & 0.04 & 0.17 \\
100,000 & 0.00 & 0.00 & n/a \\
1,000,000 & 0.00 & 0.00 & n/a \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Average solution cost for the OneMax problem, case when each 0-bit costs 1. \begin{table}
\begin{tabular}{c c c c} \hline \hline \(N\) & **Modified Lam** & **Self-Tuning Lam** & **T-Test \(p\)-Value** \\ \hline
1000 & 24.5 & 16.5 & \(<\)10\({}^{-26}\) \\
10,000 & 0.01 & 0.04 & 0.17 \\
100,000 & 0.00 & 0.00 & n/a \\
1,000,000 & 0.00 & 0.00 & n/a \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Average solution cost for the OneMax problem, case when each 0-bit costs 10. The global minimum has a cost of 0, and the local minimum has a cost of \(2n\). We again use bit vectors of length 256, so the local minimum for this problem has a cost of 512.