Sample Solution

Simulated Annealing follows a somewhat similar strategy as Randomized Hill Climbing; random positions are chosen at the start of each iteration to spread out the search space, but rather than choosing adjacent neighbors, the algorithm picks a neighbor based on a probability distribution given by a ‘temperature’ value (hence the name ‘annealing’) [2]. The algorithm will always move to ‘better’ neighbors, but will also move to worse neighbors given a certain acceptance probability (calculated with the temperature). As the temperature cools, the acceptance probability decreases proportionally until the algorithm essentially resembles basic hill climbing and a local (ideally global) minima is found.
Two important hyperparameters are involved in tuning a simulated annealing model: the initial temperature of the annealing algorithm, and a ‘cooling factor’ (also referred to as a ‘cooling schedule’) which determines the rate of temperature decrease. Using a 70/30 train/test split, we ran a grid search on these two hyperparameters over 1,000 iterations, results of which can be seen on Table 2. Note that we began initial temperature at 1,000 as too low of a temperature would result in the algorithm not expanding its search space to the full scope of the problem and operating as basic hill climbing, as mentioned previously.

Initial Temperature