Temperature Scheduling in Simulated Annealing
The purpose of this page is to describe the notion of temperature scheduling in simulated annealing. The type of temperature schedule used in one's algorithm and the size and difficulty of terrain of the search space have connections to the convergence properties of ones algorithm. These topics are also considered briefly below, with an emphasis on the diamond problem. Additionally, prospective temperature scheduling strategies are also proposed, which will serve as a backbone to potential simulated annealing runs in the near future.
Introduction
There are three major stages in the temperature scheduling process of a simulated annealing algorithm: warming up, equilibrium, cooling -down and frozen. The warming up period allows the search to get far away from the initial solution, thus ensuring that the solution will not depend on where it started. During this phase the temperature is kept very high and "walking uphill" is equally (if not more) likely at walking downhill. The equilibrium point of the schedule signifies the ending of the warming up phase and the beginning of the cooling (or decrement) phase. The equilibrium phase is given by a certain number of "steps" in the solution space. The cooling phase of scheduling is the period during which the temperature is reduced, thereby allowing the solution to settle in on a particular solution. The frozen stage is the exit switch of the program. When the annealing run hits a certain temperature or the ratio of succesive steps in solution space are less than a user set ratio, the program ends, signifying the end of the temperature scheduling process. There are several different ways that each of the above stages can be guided, which depend on the method that is in use. The two main types of strategies are adaptive and geometric. Geometric styled schedules allow the user to set the initial temperature, the number of steps taken by the program before it switches to the cooling portion and the decrement factor. Adaptive scheduling involves using formula's that involve computing the average neighborhood size of a solution and other factors. While the user still has to set certain parameters in this method, the temperature is influenced more by the search space.
Cooling Schedule Information
The three cooling schedules featured in the ParSA Library are the SA_EasyScheduler, the SA_AartsScheduler and the SA_MIRScheduler. Each of these rely on different principles who's aim is to find the best solution in the least amount of time. The SA_EasyScheduler relies on many user set parameters that include the initial temperature, the initial chain length for temperature (equilibrium), the decrement factor, and the frozen factor. Cite the turkish paper here with concurrence for large problems and a constant cooling factor. Difficulty of determiing starting temperature difficult tho.The SA_Aarts Scheduler requires that the user set three parameters, epsilon, delta and omega that govern the temperature scheduling process. epsilon is the the frozen parameter. omega is the smoothing parameter. delta is the distance factor, which shows up in the temperature decrement calculator. its rough dependence is given in the graph at the left.
The MIR scheduler, which stands for Multiple Independent runs is based off of the idea that runs of shorter chain lengths linked together will find a more accurate solution than one sequential run of the same lenght. the reason that this provides a more accurate search is that the search can span a larger area in the search space. Thus, with more space covered the the solution given is more likely to be closer to the global optimum.
Difficulty of the problem
The size and terrain of a particular search space are two concepts that one should include when speaking of the difficulty of a search space. The computing time drastically increases with the size (or dimensionality) of search space [1]. However, it is still possible to have higher dimensional problems that are unimodal or have very few local minima. Thus, one must also take into account the shape of search space when contemplating the difficulty.
In the diamond problem, a solution consists of values given to two amplitudes and three phases. The amplitudes represent the intensity of the light from the reference mirror and the diamond {the front and the back only differ by a constant). The phases represent each of the three surfaces: the reference mirror and the front and back of the diamond. Each of these quantities is represented by a certain order Legendre polynomial, which is represented in the form of a matrix with the number of rows and columns to match the order with an offset of one. Since the order Legendre Polynomial for each of the amplitudes and phases is set by the user, the dimensionality of the problem varies depending on the desired order. Thus, the lowest dimensionality that the diamond problem could take on would be 11 and the highest would be (cutting the Legendre polynomial order off at five) 125. However, it is most likely somewhere in between most likely slightly greater than 50, due to wanting to fully exploit the range of the Legendre polynomials to give the greatest accuracy in mapping the diamond surface.
[1] Esin Onbasoglu and Ozdamar Yeditepe University, Istanbul, Turkey Journal of Global Optimization 2001
Prospective strategies
Each of the above cooling schedule classes have parameters that guide every portion of the cooling process. the warming up, the equilibrium determination, the cooling and the frozen.