# Self-Tuning Lam Annealing: Learning Hyperparameters While Problem Solving
## 1 Introduction  
Optimization problems of industrial relevance are often NP-Hard, such as applications of various classical problems such as the optimization variants of NP-Complete problems like the traveling salesperson, graph coloring, largest common subgraph, and bin packing, among many others [1]. Approaches that are guaranteed to provide optimal solutions to such problems have worst case run-times that are exponential. Thus, it is common to turn to metaheuristics, such as genetic algorithms [2] and other forms of evolutionary computation, simulated annealing [3, 4, 5], tabu search [6], ant colony optimization [7], stochastic local search [8], among many others. Metaheuristics offer a trade-off between time and solution quality. Although not guaranteed to optimally solve the problem, they can often find near optimal solutions, or at least sufficiently optimal solutions, in a fraction of the time of the alternatives. They are also usually characterized by an anytime [9] property, where solution quality improves with additional runtime. Thus, one can run such an algorithm as long as time allows, utilizing whatever solution is found at the time it is needed. In this paper, we specifically concern ourselves with Simulated Annealing (SA). [PERSON], [PERSON], and [PERSON] introduced SA several decades ago [3]. Since then, it has been applied to optimization problems from a variety of industries, such as in transportation [10, 11], assembly lines [12], machine vision [13], path planning for robotics [14, 15], networking [16, 17], wireless sensor networks [18, 19], scheduling [20], manufacturing [21],software testing [22; 23], and industrial cutting [24], among many others. SA is a stochastic local search algorithm inspired by an analogy to the metallurgic process of annealing, where a metal is heated and then slowly cooled until it achieves a state of equilibrium. As a local search algorithm, SA iteratively generates random neighbors of the current solution configuration. A random neighbor with a cost that is equal to or better than that of the current solution is accepted. A random neighbor with a cost that is worse than that of the current solution may still be accepted, but the decision is randomized and depends upon the cost difference and a _temperature_ parameter. The higher the temperature, the higher the probability that a random neighbor will be accepted. Near the end of a run of SA, when temperature is low, the probability of accepting a neighbor of higher cost than the current solution becomes low. Algorithm 1 provides pseudocode for the basic form of SA. ```
1:## Notation:
2:##\(N\) is the run length in number of evaluations. 3:##\(C(S)\) is the real-valued cost of solution \(S\). 4:##\(\eta(S)\) is the set of neighbors of solution \(S\). 5:##\(U()\) generates a uniform random value in \([0,1)\). 6:\(S\leftarrow\) GenerateRandomInitialState
7:\(T\gets T_{0}\)
8:for\(i=1\)to\(N\)do
9:\(S^{\prime}\leftarrow\) random selection from \(\eta(S)\)
10:if\(C(S^{\prime})\leq C(S)\)or\(U()<e^{(C(S)-C(S^{\prime}))/T}\)then
11:\(S\gets S^{\prime}\)
12:\(T\gets f(T)\)
13:return Best solution found during run
```  
**Algorithm 1** Simulated Annealing  
SA uses the Boltzmann distribution in deciding whether to accept a randomly chosen neighbor \(S^{\prime}\). Specifically, if the cost \(C(S^{\prime})\) of the random neighbor is less than or equal to the cost \(C(S)\) of the current solution \(S\), then it definitely accepts the neighbor. SA always accepts neighbors that are not worse than the current solution. Otherwise, if the cost of the neighbor is higher than the cost of the current solution, the neighbor is accepted with probability, \(e^{(C(S)-C(S^{\prime}))/T}\) (line 10 of Algorithm 1). The temperature \(T\) of the SA changes during the run (line 12 of Algorithm 1).