Changes

Jump to navigation Jump to search
no edit summary
Line 1: Line 1:  
<font; color="red"> THIS PAGE IS A WORK IN PROGRESS </font>
 
<font; color="red"> THIS PAGE IS A WORK IN PROGRESS </font>
 +
 
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.   
 
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 ==
 
== 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.
+
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 successive 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==
 
==Cooling Schedule Information==
Line 14: Line 15:     
[1] Esin Onbasoglu and Ozdamar Yeditepe University, Istanbul, Turkey Journal of Global Optimization 2001
 
[1] Esin Onbasoglu and Ozdamar Yeditepe University, Istanbul, Turkey Journal of Global Optimization 2001
 +
 +
== Convergence and Simulated Annealing ==
 +
The ParSA library documentation gives a formula, which it states is proven in [2].  The documentation states that this formula is based in
    
==Prospective strategies==
 
==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.
 
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.
1,359

edits

Navigation menu