Simulated AnnealingSimulated Annealing, SA. TaxonomySimulated Annealing is a global optimization algorithm that belongs to the field of Stochastic Optimization and Metaheuristics. Simulated Annealing is an adaptation of the MetropolisHastings Monte Carlo algorithm and is used in function optimization. Like the Genetic Algorithm, it provides a basis for a large variety of extensions and specialization's of the general method not limited to Parallel Simulated Annealing, Fast Simulated Annealing, and Adaptive Simulated Annealing. InspirationSimulated Annealing is inspired by the process of annealing in metallurgy. In this natural process a material is heated and slowly cooled under controlled conditions to increase the size of the crystals in the material and reduce their defects. This has the effect of improving the strength and durability of the material. The heat increases the energy of the atoms allowing them to move freely, and the slow cooling schedule allows a new lowenergy configuration to be discovered and exploited. MetaphorEach configuration of a solution in the search space represents a different internal energy of the system. Heating the system results in a relaxation of the acceptance criteria of the samples taken from the search space. As the system is cooled, the acceptance criteria of samples is narrowed to focus on improving movements. Once the system has cooled, the configuration will represent a sample at or close to a global optimum. StrategyThe information processing objective of the technique is to locate the minimum cost configuration in the search space. The algorithms plan of action is to probabilistically resample the problem space where the acceptance of new samples into the currently held sample is managed by a probabilistic function that becomes more discerning of the cost of samples it accepts over the execution time of the algorithm. This probabilistic decision is based on the MetropolisHastings algorithm for simulating samples from a thermodynamic system. ProcedureAlgorithm (below) provides a pseudocode listing of the main Simulated Annealing algorithm for minimizing a cost function. Input :
ProblemSize , $iterations_{max}$, $temp_{max}$
Output :
$S_{best}$
$S_{current}$ $\leftarrow$ CreateInitialSolution (ProblemSize )$S_{best}$ $\leftarrow$ $S_{current}$ For ($i=1$ To $iterations_{max}$)$S_{i}$ $\leftarrow$ CreateNeighborSolution ($S_{current}$)$temp_{curr}$ $\leftarrow$ CalculateTemperature ($i$, $temp_{max}$)If (Cost ($S_{i}$) $\leq$ Cost ($S_{current}$))$S_{current}$ $\leftarrow$ $S_{i}$ If (Cost ($S_{i}$) $\leq$ Cost ($S_{best}$))$S_{best}$ $\leftarrow$ $S_{i}$ End ElseIf (Exp ( $\frac{Cost{S_{current}}  Cost{S_{i}}}{temp_{curr}}$ ) > Rand ())$S_{current}$ $\leftarrow$ $S_{i}$ End End Return ($S_{best}$)Heuristics
Code ListingListing (below) provides an example of the Simulated Annealing algorithm implemented in the Ruby Programming Language. The algorithm is applied to the Berlin52 instance of the Traveling Salesman Problem (TSP), taken from the TSPLIB. The problem seeks a permutation of the order to visit cities (called a tour) that minimizes the total distance traveled. The optimal tour distance for Berlin52 instance is 7542 units. The algorithm implementation uses a twoopt procedure for the neighborhood function and the classical $P(accept) \leftarrow \exp(\frac{ee'}{T})$ as the acceptance function. A simple linear cooling regime is used with a large initial temperature which is decreased each iteration. def euc_2d(c1, c2) Math.sqrt((c1[0]  c2[0])**2.0 + (c1[1]  c2[1])**2.0).round end def cost(permutation, cities) distance =0 permutation.each_with_index do c1, i c2 = (i==permutation.size1) ? permutation[0] : permutation[i+1] distance += euc_2d(cities[c1], cities[c2]) end return distance end def random_permutation(cities) perm = Array.new(cities.size){i i} perm.each_index do i r = rand(perm.sizei) + i perm[r], perm[i] = perm[i], perm[r] end return perm end def stochastic_two_opt!(perm) c1, c2 = rand(perm.size), rand(perm.size) exclude = [c1] exclude << ((c1==0) ? perm.size1 : c11) exclude << ((c1==perm.size1) ? 0 : c1+1) c2 = rand(perm.size) while exclude.include?(c2) c1, c2 = c2, c1 if c2 < c1 perm[c1...c2] = perm[c1...c2].reverse return perm end def create_neighbor(current, cities) candidate = {} candidate[:vector] = Array.new(current[:vector]) stochastic_two_opt!(candidate[:vector]) candidate[:cost] = cost(candidate[:vector], cities) return candidate end def should_accept?(candidate, current, temp) return true if candidate[:cost] <= current[:cost] return Math.exp((current[:cost]  candidate[:cost]) / temp) > rand() end def search(cities, max_iter, max_temp, temp_change) current = {:vector=>random_permutation(cities)} current[:cost] = cost(current[:vector], cities) temp, best = max_temp, current max_iter.times do iter candidate = create_neighbor(current, cities) temp = temp * temp_change current = candidate if should_accept?(candidate, current, temp) best = candidate if candidate[:cost] < best[:cost] if (iter+1).modulo(10) == 0 puts " > iteration #{(iter+1)}, temp=#{temp}, best=#{best[:cost]}" end end return best end if __FILE__ == $0 # problem configuration berlin52 = [[565,575],[25,185],[345,750],[945,685],[845,655], [880,660],[25,230],[525,1000],[580,1175],[650,1130],[1605,620], [1220,580],[1465,200],[1530,5],[845,680],[725,370],[145,665], [415,635],[510,875],[560,365],[300,465],[520,585],[480,415], [835,625],[975,580],[1215,245],[1320,315],[1250,400],[660,180], [410,250],[420,555],[575,665],[1150,1160],[700,580],[685,595], [685,610],[770,610],[795,645],[720,635],[760,650],[475,960], [95,260],[875,920],[700,500],[555,815],[830,485],[1170,65], [830,610],[605,625],[595,360],[1340,725],[1740,245]] # algorithm configuration max_iterations = 2000 max_temp = 100000.0 temp_change = 0.98 # execute the algorithm best = search(berlin52, max_iterations, max_temp, temp_change) puts "Done. Best Solution: c=#{best[:cost]}, v=#{best[:vector].inspect}" end Download: simulated_annealing.rb.
ReferencesPrimary SourcesSimulated Annealing is credited to Kirkpatrick, Gelatt, and Vecchi in 1983 [Kirkpatrick1983]. Granville, Krivanek, and Rasson provided the proof for convergence for Simulated Annealing in 1994 [Granville1994]. There were a number of early studies and application papers such as Kirkpatrick's investigation into the TSP and minimum cut problems [Kirkpatrick1983a], and a study by Vecchi and Kirkpatrick on Simulated Annealing applied to the global wiring problem [Vecchi1983]. Learn MoreThere are many excellent reviews of Simulated Annealing, not limited to the review by Ingber that describes improved methods such as Adaptive Simulated Annealing, Simulated Quenching, and hybrid methods [Ingber1993]. There are books dedicated to Simulated Annealing, applications and variations. Two examples of good texts include "Simulated Annealing: Theory and Applications" by Laarhoven and Aarts [Laarhoven1988] that provides an introduction to the technique and applications, and "Simulated Annealing: Parallelization Techniques" by Robert Azencott [Azencott1992] that focuses on the theory and applications of parallel methods for Simulated Annealing. Bibliography

Free CourseGet one algorithm per week...
Own A CopyThis 438page ebook has...


Please Note: This content was automatically generated from the book content and may contain minor differences. 

Do you like Clever Algorithms? Buy the book now. 