Simulated Annealing
Inspired from annealing process of metals, Simulated Annealing (SA) represents the process of heating metals to the crystalline temperature then hold for a certain time before cooling. This process helps in changing physical and chemical properties of material so as to improve ductility, machinability, electrical and magnetic properties.
Simulated Annealing is a Meta-heuristic technique used to solve complex optimization problems where exact methods fail to find optimal solution. SA always reach near-optimal solutions, for many practical problems these solutions could be sufficient.
Simulated Annealing Terminology
Simulated annealing first starts with initial solution; randomly generated or obtained from heuristic algorithm, then the initial temperature and cooling schedule are determined. The temperature is set as a number between (0,1) of the objective function; also, the cooling schedule is set between (0,1).
Initial temperature should not be too hot so it would accept worst solutions; neither too cool so it would reject most of worst solutions.
A random number is generated, in case of worst solution, if the random number is lower than the probability function; thus, the solution is accepted, if not the solution is rejected. After a pre-determined number of accepted iterations, the initial temperature is cooled according to the cooling schedule. The cooling schedule should not be too high to avoid trapping in low temperatures; neither too low to avoid accepting worst solutions for long time.
Simulated Annealing Concepts
The Simulated Annealing algorithm may accept worst solution that may be a step or transit to reach the local minima as shown in the below figure. The concept of accepting worst solutions may lead the algorithm to reach search spaces that could not be reached by accepting better solutions.
Applications
SA algorithm has many applications as follows:
1- Assembly Line Balancing
2- Scheduling Problem
3- Traveling Sales Person
4- Vehicle Routing Problem
0 Comments