Simulated Annealing
The well-known optimisation technique.
An optimisation algorithm is a procedure which is executed iteratively by comparing various solutions until an optimum solution is obtained. There are distinct types of optimisation algorithms used today.
- Deterministic Methods
- Stochastic Methods
- Nature Inspired Techniques
This article is on the Simulated annealing technique which is generally stochastic method.
Simulated Annealing (SA) : It is a probailistic technique for approximating the global optimum of a given function.
“Annealing” refers to an analogy with thermodynamics, specifically with the way that metals cool and anneal. Simulated annealing is an effective and general form of optimisation. It is useful in finding global optima in the presence of a large number of local optima. Simulated annealing uses the objective function as an optimisation problem instead of the energy of the material.
Implementation of simulated annealing is surprisingly simple. The algorithm is basically a hill-climbing except instead of picking the best move, it picks a random move. If the selected move improves the solution, then it is always accepted. Otherwise, the algorithm makes the move anyway with some probability less than 1.
The probability decreases exponentially with the badness of move, which is the amount deltaE by which the solution is worsened( i.e. energy is increased).
Prob( accepting an uphill move)~ 1-exp( deltaE / KT ), where k should lie between 0.8 to 0.99 .
A parameter T is also used to determine the probability. It is analogous to temp. in an annealing system. At a higher value of T, uphill moves are like to occur. As T tends to zero, they become more and more unlikely, until algo. behaves like hill climbing.
In a SA optimisation problem, T starts at high and is gradually decreased according to annealing scheduling.
Simulated Annealing Algorithm
- SA distinguishes between different local optima.
- SA is a memoryless algorithm, the algorithm does not use any information gathered during the search
- SA is an iterative improvement algorithm.
Application
- Circuit partitioning and placements
- Graph partitioning
- Image processing
- VLSI: placements, routing
- Hardware/software partitioning
- Strategy scheduling for capital products with complex products structure
- Event-based learning situations.
Advantages:
- can deal with arbitrary systems and cost functions
- statistically guarantees to find an optimal solution
- It is relatively easy to code and even for complex problems
- Generally gives a good solution.
Disadvantages:
- For problems where the energy landscape is smooth, or there are few local minima, SA is overkill.
- Repeatedly annealing with a 1/log(k) schedule is very slow, especially if the cost function is expensive to compute.
Conclusion:
- Simulated annealing guarantees a convergence upon running a sufficiently large number of iterations.
- Simulated annealing algorithms are usually better than greedy algorithms when it comes to problems that have numerous locally optimum solution.
Thank you for reading this.
