25,161
edits
Changes
Created page with "'''Home * Programming * Algorithms * Simulated Annealing''' FILE:Bochumer Verein-23-50078.jpg|border|right|thumb| Glowing [https://en.wikipedia.org/wi..."
'''[[Main Page|Home]] * [[Programming]] * [[Algorithms]] * Simulated Annealing'''
[[FILE:Bochumer Verein-23-50078.jpg|border|right|thumb| Glowing [https://en.wikipedia.org/wiki/Train_wheel train wheels] <ref>[https://en.wikipedia.org/wiki/Train_wheel train wheel production], [https://de.wikipedia.org/wiki/Bochumer_Verein Bochumer Verein], [https://en.wikipedia.org/wiki/Bochum Bochum], Germany, [https://de.wikipedia.org/wiki/ExtraSchicht ExtraSchicht] [http://www.ruhr-guide.de/freizeit/industriekultur/extraschicht-2010/16187,0,0.html 2010], [[Arts#IndustrialHeritageTrail|The Industrial Heritage Trail]], [https://commons.wikimedia.org/wiki/File:Bochumer_Verein-23-50078.jpg image] by [https://commons.wikimedia.org/wiki/User:Rainer_Halama Rainer Halama], June 19, 2010, [https://creativecommons.org/licenses/by-sa/3.0/deed.en CC BY-SA 3.0], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://de.wikipedia.org/wiki/Gl%C3%BChen Glühen from Wikipedia.de] (German)</ref> ]]
'''Simulated Annealing''', (SA)<br/>
a [https://en.wikipedia.org/wiki/Monte_Carlo_method Monte Carlo] based algorithm for [https://en.wikipedia.org/wiki/Combinatorial_optimization combinatorial optimization problems] inspired by [https://en.wikipedia.org/wiki/Statistical_mechanics statistical mechanics] in [https://en.wikipedia.org/wiki/Thermodynamics thermodynamics] with the [https://en.wikipedia.org/wiki/Statistical_ensemble_(mathematical_physics) statistical ensemble] of the [https://en.wikipedia.org/wiki/Probability_distribution probability distribution] over all possible [https://en.wikipedia.org/wiki/Thermodynamic_state states] of a [https://en.wikipedia.org/wiki/Thermodynamic_system system] described by a [https://en.wikipedia.org/wiki/Markov_chain Markov chain], where its [https://en.wikipedia.org/wiki/Stationary_distribution stationary distribution] converts to an optimal distribution during a [https://en.wikipedia.org/wiki/Cooling cooling process] after reaching the [https://en.wikipedia.org/wiki/Thermodynamic_equilibrium equilibrium]. Thus, the annealing algorithm simulates a nonstationary [https://en.wikipedia.org/wiki/Markov_chain#Finite_state_space finite state Markov chain] whose [https://en.wikipedia.org/wiki/State_space state space] is the domain of the [https://en.wikipedia.org/wiki/Loss_function cost function] called [https://en.wikipedia.org/wiki/Internal_energy energy] to be minimized <ref>[[Mathematician#SBGelfand|Saul B. Gelfand]], [[Mathematician#SKMitter|Sanjoy K. Mitter]] ('''1985'''). ''Analysis of simulated annealing for optimization''. [http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4048220 24th IEEE Conference on Decision and Control] </ref>.
=History=
The annealing algorithm is an adaptation of the [https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm Metropolis–Hastings algorithm] to generate sample states of a [https://en.wikipedia.org/wiki/Thermodynamic_system thermodynamic system], invented by [[Mathematician#MRosenbluth|Marshall Rosenbluth]] and published by [https://en.wikipedia.org/wiki/Nicholas_Metropolis Nicholas Metropolis] et al. in 1953 <ref>[https://en.wikipedia.org/wiki/Nicholas_Metropolis Nicholas Metropolis], [http://scitation.aip.org/content/contributor/AU0719025 Arianna W. Rosenbluth], [[Mathematician#MRosenbluth|Marshall N. Rosenbluth]], [https://commons.wikimedia.org/wiki/File:Augusta_H._Teller_Los_Alamos_ID.png Augusta H. Teller], [[Mathematician#ETeller|Edward Teller]] ('''1953'''). ''[https://en.wikipedia.org/wiki/Equation_of_State_Calculations_by_Fast_Computing_Machines Equation of State Calculations by Fast Computing Machines]''. [https://en.wikipedia.org/wiki/Journal_of_Chemical_Physics Journal of Chemical Physics], Vol. 21, No. 6</ref> <ref>[https://en.wikipedia.org/wiki/Nicholas_Metropolis Nicholas Metropolis] ('''1987'''). ''The Beginning of the Monte Carlo Method''. [[Los Alamos National Laboratory|Los Alamos Science Special]], [http://library.lanl.gov/cgi-bin/getfile?00326866.pdf pdf]</ref> , later generalized by [[Mathematician#WKHastings|W. Keith Hastings]] at [[University of Toronto]] <ref>[[Mathematician#WKHastings|W. Keith Hastings]] ('''1970'''). ''[http://biomet.oxfordjournals.org/content/57/1/97 Monte Carlo Sampling Methods Using Markov Chains and Their Applications]''. [[University of Toronto]], [https://en.wikipedia.org/wiki/Biometrika Biometrika], Vol. 57, No. 1, [http://www2.stat.duke.edu/~scs/Courses/Stat376/Papers/Basic/Hastings1970.pdf pdf]</ref>. According to [[Mathematician#RJlauber|Roy Glauber]] and [[Mathematician#ESegre|Emilio Segrè]], the original algorithm was invented by [[Mathematician#EFermi|Enrico Fermi]] and reinvented by [[Stanislaw Ulam]] <ref>[https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm Metropolis–Hastings algorithm from Wikipedia]</ref>.
SA was independently described by [[Mathematician#SKirkpatrick|Scott Kirkpatrick]], [[Mathematician#CDGelatt|C. Daniel Gelatt]] and Mario P. Vecchi in 1983 <ref>[[Mathematician#SKirkpatrick|Scott Kirkpatrick]], [[Mathematician#CDGelatt|C. Daniel Gelatt]], [https://www.linkedin.com/in/mariovecchi Mario P. Vecchi] ('''1983'''). ''[http://science.sciencemag.org/content/220/4598/671 Optimization by Simulated Annealing]''. [https://en.wikipedia.org/wiki/Science_(journal) Science], Vol. 220, No. 4598, [http://wexler.free.fr/library/files/kirkpatrick%20(1983)%20optimization%20by%20simulated%20annealing.pdf pdf]</ref>, at that time affiliated with [https://en.wikipedia.org/wiki/Thomas_J._Watson_Research_Center IBM Thomas J. Watson Research Center, Yorktown Heights], and by Vlado Černý from [https://en.wikipedia.org/wiki/Comenius_University Comenius University], [https://en.wikipedia.org/wiki/Bratislava Bratislava] in 1985 <ref>[https://sites.google.com/site/cernyv/Home Vlado Černý] ('''1985'''). ''[http://link.springer.com/article/10.1007%2FBF00940812 Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm]''. [http://www.springer.com/mathematics/journal/10957 Journal of Optimization Theory and Applications], Vol. 45, No. 1</ref>.
=Quotes=
In the 2003 conference proceedings ''Celebrating the 50th Anniversary of the Metropolis Algorithm'' <ref>[http://cnls.lanl.gov/Conferences/MonteCarloMethods/ The Monte Carlo Method in Physical Sciences: Celebrating the 50th Anniversary of the Metropolis Algorithm]</ref> <ref>[http://cnls.lanl.gov/External/people/James_Gubernatis.php James Gubernatis] (ed.) ('''2003'''). ''[http://scitation.aip.org/content/aip/proceeding/aipcp/690 The Monte Carlo Method in Physical Sciences: Celebrating the 50th Anniversary of the Metropolis Algorithm]''. [http://scitation.aip.org/content/aip/proceeding/aipcp AIP Conference Proceedings]</ref>, [[Mathematician#MRosenbluth|Marshall Rosenbluth]] describes the algorithm in the following beautifully concise and clear manner <ref>[http://cnls.lanl.gov/External/people/James_Gubernatis.php James Gubernatis] ('''2005'''). ''Marshall Rosenbluth and the Metropolis Algorithm''. [https://en.wikipedia.org/wiki/Physics_of_Plasmas Physics of Plasmas], Vol. 12, No. 5, [http://www.z-cam.es/historique/Gubernatis_on_Rosenbluth.pdf pdf]</ref>:
A simple way to do this [sampling configurations with the [https://en.wikipedia.org/wiki/Boltzmann_distribution Boltzmann weight]], as emerged after discussions with [[Mathematician#ETeller|Teller]], would be to make a trial move: if it decreased the energy of the system, allow it; if it increased the energy, allow it with [https://en.wikipedia.org/wiki/Probability probability] exp(−ΔE/kT) as determined by a comparison with a [[Pseudorandom number generator|random number]]. Each step, after an initial annealing period, is counted as a member of the ensemble, and the appropriate ensemble average of any quantity determined.
=Applications=
SA has multiple applications in discrete [https://en.wikipedia.org/wiki/NP-hardness NP-hard] optimization problems such as the [https://en.wikipedia.org/wiki/Travelling_salesman_problem Travelling salesman problem], in [[Learning|machine learning]], in training of [[Neural Networks|neural networks]], and in the domain of computer games and computer chess in [[Automated Tuning|automated tuning]] as elaborated by [[Peter Mysliwietz]] in his Ph.D. thesis <ref>[[Peter Mysliwietz]] ('''1994'''). ''Konstruktion und Optimierung von Bewertungsfunktionen beim Schach.'' Ph.D. thesis (German)</ref> to optimize the [[Evaluation|evaluation]] weight vector in [[Zugzwang (Program)|Zugzwang]]. In its variant of [[Temporal Difference Learning|temporal difference learning]] to adjust pattern weights in [[Morph]], [[Robert Levinson]] at al. used simulated annealing as [https://en.wikipedia.org/wiki/Metaheuristic metaheuristic] to set its own learning rate for each pattern, the more frequently a pattern is updated, the slower becomes its learning rate <ref>[[Robert Levinson]] ('''1994'''). ''Experience-Based Creativity''. Artificial Intelligence and Creativity: An Interdisciplinary Approach, Kluwer</ref> <ref>[[Ari Shapiro]], [[Gil Fuchs]], [[Robert Levinson]] ('''2002'''). ''[http://www.arishapiro.com/researchportfolio/Learning%20Game%20Strategy/index.htm Learning a Game Strategy Using Pattern-Weights and Self-play]''. [[CG 2002]], [http://www.arishapiro.com//ShapiroA_CG2002.pdf pdf]</ref> <ref>[[Johannes Fürnkranz]] ('''2000'''). ''Machine Learning in Games: A Survey''. [https://en.wikipedia.org/wiki/Austrian_Research_Institute_for_Artificial_Intelligence Austrian Research Institute for Artificial Intelligence], OEFAI-TR-2000-3, [http://www.ofai.at/cgi-bin/get-tr?download=1&paper=oefai-tr-2000-31.pdf pdf]</ref>.
=Algorithm=
==Description==
The [https://en.wikipedia.org/wiki/Control_flow control flow] of the algorithm is determined by two nested loops, the outer loop over decreasing [https://en.wikipedia.org/wiki/Temperature temperature] simulates the cooling, and an inner loop times n Monte Carlo [[Iteration|iterations]]. Each time a randomly picked neighbor state inside the inner loop provides a better energy or [https://en.wikipedia.org/wiki/Fitness_function fitness] than the current state, the neighbor becomes the new current and even new optimum if fitter than fittest so far. Otherwise, if the neighbor fitness does not exceed current, it might still become current depending on the positive fitness or energy difference ΔE, and [https://en.wikipedia.org/wiki/Kelvin absolute temperature] T, with a [https://en.wikipedia.org/wiki/Probability probability] p according to the [https://en.wikipedia.org/wiki/Boltzmann_distribution Boltzmann factor]:
: [[FILE:SimulatedAnnealingBoltzmannFactor.jpg|none|border|text-bottom]]
where k the [https://en.wikipedia.org/wiki/Boltzmann_constant Boltzmann constant], and [https://en.wikipedia.org/wiki/E_(mathematical_constant) e] base of the [https://en.wikipedia.org/wiki/Exponential_function exponential function] whose negative exponent ensures the [0, 1] probability interval. Accepting worse solutions is a primary feature of SA, and important to stop [https://en.wikipedia.org/wiki/Greedy_algorithm greedy] [https://en.wikipedia.org/wiki/Exploitation exploitation] a [https://en.wikipedia.org/wiki/Local_optimum local optimum] but to explore other areas - higher temperatures favor [https://en.wikipedia.org/wiki/Exploration exploration], while decreasing temperatures make the algorithm to behave greedier in favoring exploitation of the hopefully global optimum.
==Animation==
[[FILE:Hill_Climbing_with_Simulated_Annealing.gif|none|border|text-bottom|560px|link=https://commons.wikimedia.org/wiki/File:Hill_Climbing_with_Simulated_Annealing.gif]]
Simulated annealing - searching for a maximum. <ref>Start temperature: 25 step: 0.1 End temperature: 0 - 1,000,000 iterations at each temperature: [https://en.wikipedia.org/wiki/GIF Animated GIF] [https://commons.wikimedia.org/wiki/File:Hill_Climbing_with_Simulated_Annealing.gif Hill Climbing with Simulated Annealing] by [https://en.wikipedia.org/wiki/User:Kingpin13?rdfrom=commons:User:Kingpin13 Kingpin13], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Simulated_annealing Simulated annealing from Wikipedia]</ref><br/>With the high temprature, the numerous local maxima are left quickly through the strong noise movement - <br/>but the global maximum is reliably found because of cooling temperature is no longer sufficient to leave it.
==Pseudo Code==
The [[C]] like pseudo code is based on [[Peter Mysliwietz|Peter Mysliwietz']] description as given in his Ph.D. thesis <ref>[[Peter Mysliwietz]] ('''1994'''). ''Konstruktion und Optimierung von Bewertungsfunktionen beim Schach.'' Ph.D. thesis, 7.4. Simulated Annealing, 7.4.2. Beschreibung des Algorithmus, Abb. 29, pp. 146 (German)</ref>. Several neighbor functions used to modify the weight vector were tried, where one randomly chosen element changed randomly performed well. The [https://en.wikipedia.org/wiki/Fitness_function fitness function] inside the inner loop is of course the most time consuming part. For [[Zugzwang (Program)|Zugzwang]], Mysliwietz used a database of 500 [[Test-Positions|test-positions]] with a [[Depth|search depth]] of one [[Ply|ply]], which took about three minutes on a [[Transputer|T 800 Transputer]] per iteration - the higher the hit rate of found expert moves, the fitter. The whole optimization used a tHight to tLow ratio of 100, a reduction factor r of 0.95, and n=40 inner iterations.
<pre>
/**
* simulatedAnnealing
* @author Peter Mysliwietz, slightly modified
* @param tHigh is the start temperature
* @param tLow is the minimal end temperature
* @param r is the temperature reduction factor < 1.0
* @param n number of iterations for each temperature
* @return best weight vector
*/
vector simulatedAnnealing(double tHigh, double tLow, double r, int n) {
vector currentWeights = randomWeights();
vector bestWeights = currentWeights;
double fittest = fitness(currentWeights);
for (double t = tHigh; t > tLow; t *= r) {
for (int i = 0; i < n; ++i) {
vector neighborWeights = neighbor(currentWeights);
if ( fitness(neighborWeights ) > fitness(currentWeights) ) {
currentWeights = neighborWeights;
if ( fitness(neighborWeights ) > fittest ) {
fittest = fitness(neighborWeights);
bestWeights = neighborWeights;
}
} else if (accept( fitness(currentWeights) - fitness(neighborWeights ), t) ) {
currentWeights = neighborWeights;
}
} /* for i */
} /* for t */
return bestWeights;
}
/**
* accept
* @param d is the energy difference >= 0
* @param t is the current temperature
* @return true with probability of Boltzmann factor e^(-d/kt)
*/
bool accept(double d, double t ) {
const double k = 1.38064852e−23; /* joule / kelvin */
double p = exp(-d / (k*t) );
double r = rand() / (RAND_MAX + 1.0);
return r < p;
}
</pre>
<ref>[https://en.wikipedia.org/wiki/Exponential_function Exponential function from Wikipedia]</ref> <ref>[https://en.wikipedia.org/wiki/C_mathematical_functions#Random_number_generation C mathematical functions - Random number generation from Wikipedia]</ref>
=See also=
* [[Automated Tuning]]
* [[Genetic Programming]]
* [[Iteration]]
* [[Learning]]
* [[SPSA]]
* [[Trial and Error]]
=Selected Publications=
<ref>[http://scienze-como.uninsubria.it/bressanini/montecarlo-history/ Monte Carlo History] by [http://scienze-como.uninsubria.it/bressanini/index.html Dario Bressanini]</ref>
==1948 ...==
* [[Mathematician#EFermi|Enrico Fermi]], [[Mathematician#RDRichtmyer|Robert D. Richtmyer]] ('''1948'''). ''Note on census-taking in Monte Carlo calculations''. [[Los Alamos National Laboratory]], [http://scienze-como.uninsubria.it/bressanini/montecarlo-history/fermi-1948.pdf pdf]
* [https://en.wikipedia.org/wiki/Nicholas_Metropolis Nicholas Metropolis], [[Stanislaw Ulam]] ('''1949'''). ''The Monte Carlo Method''. [https://en.wikipedia.org/wiki/Journal_of_the_American_Statistical_Association Journal of the American Statistical Association], Vol. 44, No. 247, [http://scienze-como.uninsubria.it/bressanini/montecarlo-history/metropolis-ulam-1949.pdf pdf]
==1950 ...==
* [https://en.wikipedia.org/wiki/Nicholas_Metropolis Nicholas Metropolis], [http://scitation.aip.org/content/contributor/AU0719025 Arianna W. Rosenbluth], [[Mathematician#MRosenbluth|Marshall N. Rosenbluth]], [https://commons.wikimedia.org/wiki/File:Augusta_H._Teller_Los_Alamos_ID.png Augusta H. Teller], [[Mathematician#ETeller|Edward Teller]] ('''1953'''). ''[https://en.wikipedia.org/wiki/Equation_of_State_Calculations_by_Fast_Computing_Machines Equation of State Calculations by Fast Computing Machines]''. [https://en.wikipedia.org/wiki/Journal_of_Chemical_Physics Journal of Chemical Physics], Vol. 21, No. 6
* [[Mathematician#MRosenbluth|Marshall N. Rosenbluth]], [http://scitation.aip.org/content/contributor/AU0719025 Arianna W. Rosenbluth] ('''1954'''). ''Further Results on Monte Carlo Equations of State''. [https://en.wikipedia.org/wiki/Journal_of_Chemical_Physics Journal of Chemical Physics], Vol. 22, No. 5, [http://scienze-como.uninsubria.it/bressanini/montecarlo-history/rosenbluth-1954.pdf pdf]
==1970 ...==
* [[Mathematician#WKHastings|W. Keith Hastings]] ('''1970'''). ''[http://biomet.oxfordjournals.org/content/57/1/97 Monte Carlo Sampling Methods Using Markov Chains and Their Applications]''. [[University of Toronto]], [https://en.wikipedia.org/wiki/Biometrika Biometrika], Vol. 57, No. 1, [http://www2.stat.duke.edu/~scs/Courses/Stat376/Papers/Basic/Hastings1970.pdf pdf]
==1980 ...==
* [[Mathematician#SKirkpatrick|Scott Kirkpatrick]], [[Mathematician#CDGelatt|C. Daniel Gelatt]], [https://www.linkedin.com/in/mariovecchi Mario P. Vecchi] ('''1983'''). ''[http://science.sciencemag.org/content/220/4598/671 Optimization by Simulated Annealing]''. [https://en.wikipedia.org/wiki/Science_(journal) Science], Vol. 220, No. 4598, [http://wexler.free.fr/library/files/kirkpatrick%20(1983)%20optimization%20by%20simulated%20annealing.pdf pdf]
* [https://sites.google.com/site/cernyv/Home Vlado Černý] ('''1985'''). ''[http://link.springer.com/article/10.1007%2FBF00940812 Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm]''. [http://www.springer.com/mathematics/journal/10957 Journal of Optimization Theory and Applications], Vol. 45, No. 1
* [[Mathematician#SBGelfand|Saul B. Gelfand]], [[Mathematician#SKMitter|Sanjoy K. Mitter]] ('''1985'''). ''Analysis of simulated annealing for optimization''. [http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4048220 24th IEEE Conference on Decision and Control]
* [[Mathematician#SBGelfand|Saul B. Gelfand]] ('''1987'''). ''Analysis of Simulated Annealing Type Algorithms''. Ph.D. thesis, [[Massachusetts Institute of Technology|MIT]], advisor: [[Mathematician##SKMitter|Sanjoy K. Mitter]], [http://www.mit.edu/~mitter/SKM_theses/87_2_Gelfand_PhD.pdf pdf]
* [https://en.wikipedia.org/wiki/Nicholas_Metropolis Nicholas Metropolis] ('''1987'''). ''The Beginning of the Monte Carlo Method''. [[Los Alamos National Laboratory|Los Alamos Science Special]], [http://library.lanl.gov/cgi-bin/getfile?00326866.pdf pdf]
* [https://scholar.google.com/citations?user=avq8-1QAAAAJ Rob A. Rutenbar] ('''1989'''). ''[https://scholar.google.com/citations?view_op=view_citation&hl=en&user=avq8-1QAAAAJ&citation_for_view=avq8-1QAAAAJ:u-x6o8ySG0sC Simulated Annealing Algorithms]''. [[IEEE]] Circuits and Devices Magazine, [http://www.cs.amherst.edu/~ccm/cs34/papers/rutenbar.pdf pdf]
==1990 ...==
* [[Mathematician#GDueck|Gunter Dueck]], [[Mathematician#TScheuer|Tobias Scheuer]] ('''1990'''). ''[http://adsabs.harvard.edu/abs/1990JCoPh..90..161D Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing]''. [https://en.wikipedia.org/wiki/Journal_of_Computational_Physics Journal of Computational Physics], Vol. 90, No. 1 <ref>[https://de.wikipedia.org/wiki/Schwellenakzeptanz Schwellenakzeptanz from Wikipedia.de] (German)</ref>
* [[Ingo Althöfer]], [[Klaus-Uwe Koschnick]] ('''1991'''). ''[http://link.springer.com/article/10.1007/BF01447741 On the convergence of “Threshold Accepting”]''. [http://link.springer.com/journal/245 Applied Mathematics and Optimization], Vol. 24, No. 1
* [[Andrey Grigoriev]] ('''1991'''). ''Artificial Intelligence or Stochastic Relaxation: Simulated Annealing Challenge''. [[2nd Computer Olympiad#Workshop|Heuristic Programming in AI 2]]
* [[Bernd Brügmann]] ('''1993'''). ''Monte Carlo Go''. [http://www.ideanest.com/vegos/MonteCarloGo.pdf pdf]
* [http://www.imm.dtu.dk/~rvvv/ René V. V. Vidal] (ed.) ('''1993'''). ''[http://link.springer.com/book/10.1007%2F978-3-642-46787-5 Applied Simulated Annealing]''. [http://www.springer.com/series/300 Lecture Notes in Economics and Mathematical Systems], Vol. 396, [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
* [[Robert Levinson]] ('''1994'''). ''Experience-Based Creativity''. Artificial Intelligence and Creativity: An Interdisciplinary Approach, Kluwer
* [[Peter Mysliwietz]] ('''1994'''). ''Konstruktion und Optimierung von Bewertungsfunktionen beim Schach.'' Ph.D. thesis (German)
* [[James C. Spall]] ('''1999'''). ''Stochastic Optimization: Stochastic Approximation and Simulated Annealing''. in [https://en.wikipedia.org/wiki/John_G._Webster John G. Webster] (ed.) ('''1999'''). [http://onlinelibrary.wiley.com/book/10.1002/047134608X Encyclopedia of Electrical and Electronics Engineering], Vol. 20, [https://en.wikipedia.org/wiki/John_Wiley_%26_Sons John Wiley & Sons], [http://www.jhuapl.edu/spsa/PDF-SPSA/Spall_Stochastic_Optimization.PDF pdf]
==2000 ...==
* [[Ari Shapiro]], [[Gil Fuchs]], [[Robert Levinson]] ('''2002'''). ''[http://www.arishapiro.com/researchportfolio/Learning%20Game%20Strategy/index.htm Learning a Game Strategy Using Pattern-Weights and Self-play]''. [[CG 2002]], [http://www.arishapiro.com//ShapiroA_CG2002.pdf pdf]
* [[Eric Triki]], [http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/c/Collette:Yann.html Yann Collette], [http://www.mirlabs.org/network/Europe/France/patrick.php Patrick Siarry] ('''2002'''). ''Empirical study of Simulated Annealing aimed at improved multiobjective optimization''. [http://uahost.uantwerpen.be/eume/workshops/momh/momh-9.pdf pdf]
* [http://cnls.lanl.gov/External/people/James_Gubernatis.php James Gubernatis] (ed.) ('''2003'''). ''[http://scitation.aip.org/content/aip/proceeding/aipcp/690 The Monte Carlo Method in Physical Sciences: Celebrating the 50th Anniversary of the Metropolis Algorithm]''. [http://scitation.aip.org/content/aip/proceeding/aipcp AIP Conference Proceedings] <ref>[http://cnls.lanl.gov/Conferences/MonteCarloMethods/ The Monte Carlo Method in Physical Sciences: Celebrating the 50th Anniversary of the Metropolis Algorithm]</ref>
* [[Daniel Walker]], [[Robert Levinson]] ('''2004'''). ''The MORPH Project in 2004''. [[ICGA Journal#27_4|ICGA Journal, Vol. 27, No. 4]]
* [http://cnls.lanl.gov/External/people/James_Gubernatis.php James Gubernatis] ('''2005'''). ''Marshall Rosenbluth and the Metropolis Algorithm''. [https://en.wikipedia.org/wiki/Physics_of_Plasmas Physics of Plasmas], Vol. 12, No. 5, [http://www.z-cam.es/historique/Gubernatis_on_Rosenbluth.pdf pdf]
==2010 ...==
* [http://sun.aei.polsl.pl/~zjc/ Zbigniew J. Czech], [http://sun.aei.polsl.pl/pub/wmikanik/index.html Wojciech Mikanik], [[Rafał Skinderowicz]] ('''2010'''). ''[http://link.springer.com/chapter/10.1007%2F978-3-642-14390-8_16?LI=true Implementing a Parallel Simulated Annealing Algorithm]''. [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science Lecture Notes in Computer Science], Volume 6067, [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
* [[Rafał Skinderowicz]] ('''2011'''). ''[http://www.researchgate.net/publication/220906163_Co-operative_Parallel_Simulated_Annealing_for_the_VRPTW Co-operative, Parallel Simulated Annealing for the VRPTW]''. Computational Collective Intelligence. Technologies and Applications, [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science Lecture Notes in Computer Science], [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer] <ref>[https://en.wikipedia.org/wiki/Vehicle_routing_problem Vehicle routing problem from Wikipedia]</ref>
* [[Mathematician#PRossmanith|Peter Rossmanith]] ('''2011'''). ''Simulated Annealing''. in [[Mathematician#BVoecking|Berthold Vöcking]] et al. (eds.) ('''2011'''). ''[http://www.springer.com/gp/book/9783642153273 Algorithms Unplugged]''. [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
* [[Ben Ruijl]], [[Jos Vermaseren]], [[Aske Plaat]], [[Jaap van den Herik]] ('''2013'''). ''Combining Simulated Annealing and Monte Carlo Tree Search for Expression Simplification''. [http://arxiv.org/abs/1312.0841 CoRR abs/1312.0841]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=38412&start=12 Re: Parameter tuning] by [[Rémi Coulom]], [[CCC]], March 23, 2011 » [[Automated Tuning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=31935 Idea for Automatic Calibration of Evaluation Function...] by [[Steve Maughan]], [[CCC]], January 22, 2010
=External Links=
==Simulated Annealing==
* [https://en.wikipedia.org/wiki/Simulated_annealing Simulated annealing from Wikipedia]
* [https://en.wikipedia.org/wiki/Adaptive_simulated_annealing Adaptive simulated annealing from Wikipedia]
* [http://mathworld.wolfram.com/SimulatedAnnealing.html Simulated Annealing] from [https://en.wikipedia.org/wiki/MathWorld Wolfram MathWorld]
* [http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo41.php Algorithmus der Woche - Informatikjahr 2006] by [[Mathematician#PRossmanith|Peter Rossmanith]], [https://en.wikipedia.org/wiki/RWTH_Aachen_University RWTH Aachen] (German)
* [http://apmonitor.com/me575/index.php/Main/SimulatedAnnealing Simulated Annealing Tutorial] by [https://scholar.google.com/citations?user=BD6fjEYAAAAJ John D. Hedengren], [https://en.wikipedia.org/wiki/Brigham_Young_University Brigham Young University]
* [http://katrinaeg.com/simulated-annealing.html The Simulated Annealing Algorithm] by [http://katrinaeg.com/ Katrina Ellison Geltman], February 20, 2014
==Related Topics==
* [https://en.wikipedia.org/wiki/Combinatorial_optimization Combinatorial optimization from Wikipedia]
* [https://en.wikipedia.org/wiki/Cross-entropy_method Cross-entropy method from Wikipedia]
* [https://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm Expectation–maximization algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Gibbs_sampling Gibbs sampling from Wikipedia]
* [https://en.wikipedia.org/wiki/Global_optimization Global optimization from Wikipedia]
* [https://en.wikipedia.org/wiki/Greedy_algorithm Greedy algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Hill_climbing Hill climbing from Wikipedia]
* [https://en.wikipedia.org/wiki/Local_search_(optimization) Local search (optimization) from Wikipedia]
* [https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo Markov chain Monte Carlo from Wikipedia]
* [https://en.wikipedia.org/wiki/Monte_Carlo_method Monte Carlo method from Wikipedia]
* [https://en.wikipedia.org/wiki/Quantum_annealing Quantum annealing from Wikipedia]
* [https://en.wikipedia.org/wiki/Simultaneous_perturbation_stochastic_approximation Simultaneous perturbation stochastic approximation from Wikipedia]
* [https://en.wikipedia.org/wiki/Stochastic_gradient_descent Stochastic gradient descent from Wikipedia]
* [https://en.wikipedia.org/wiki/Stochastic_optimization Stochastic optimization from Wikipedia]
* [https://en.wikipedia.org/wiki/Tabu_search Tabu search from Wikipedia]
==Misc==
* [https://en.wikipedia.org/wiki/Annealing_(metallurgy) Annealing (metallurgy) from Wikipedia]
* [[Videos#EsperanzaSpalding|Esperanza Spalding]] - [http://genius.com/Esperanza-spalding-good-lava-lyrics Good Lava], October 29, 2016 broadcast, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=9sOQ-YrGdyg|alignment=left|valignment=top}}
=References=
<references />
'''[[Algorithms|Up one Level]]'''
[[FILE:Bochumer Verein-23-50078.jpg|border|right|thumb| Glowing [https://en.wikipedia.org/wiki/Train_wheel train wheels] <ref>[https://en.wikipedia.org/wiki/Train_wheel train wheel production], [https://de.wikipedia.org/wiki/Bochumer_Verein Bochumer Verein], [https://en.wikipedia.org/wiki/Bochum Bochum], Germany, [https://de.wikipedia.org/wiki/ExtraSchicht ExtraSchicht] [http://www.ruhr-guide.de/freizeit/industriekultur/extraschicht-2010/16187,0,0.html 2010], [[Arts#IndustrialHeritageTrail|The Industrial Heritage Trail]], [https://commons.wikimedia.org/wiki/File:Bochumer_Verein-23-50078.jpg image] by [https://commons.wikimedia.org/wiki/User:Rainer_Halama Rainer Halama], June 19, 2010, [https://creativecommons.org/licenses/by-sa/3.0/deed.en CC BY-SA 3.0], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://de.wikipedia.org/wiki/Gl%C3%BChen Glühen from Wikipedia.de] (German)</ref> ]]
'''Simulated Annealing''', (SA)<br/>
a [https://en.wikipedia.org/wiki/Monte_Carlo_method Monte Carlo] based algorithm for [https://en.wikipedia.org/wiki/Combinatorial_optimization combinatorial optimization problems] inspired by [https://en.wikipedia.org/wiki/Statistical_mechanics statistical mechanics] in [https://en.wikipedia.org/wiki/Thermodynamics thermodynamics] with the [https://en.wikipedia.org/wiki/Statistical_ensemble_(mathematical_physics) statistical ensemble] of the [https://en.wikipedia.org/wiki/Probability_distribution probability distribution] over all possible [https://en.wikipedia.org/wiki/Thermodynamic_state states] of a [https://en.wikipedia.org/wiki/Thermodynamic_system system] described by a [https://en.wikipedia.org/wiki/Markov_chain Markov chain], where its [https://en.wikipedia.org/wiki/Stationary_distribution stationary distribution] converts to an optimal distribution during a [https://en.wikipedia.org/wiki/Cooling cooling process] after reaching the [https://en.wikipedia.org/wiki/Thermodynamic_equilibrium equilibrium]. Thus, the annealing algorithm simulates a nonstationary [https://en.wikipedia.org/wiki/Markov_chain#Finite_state_space finite state Markov chain] whose [https://en.wikipedia.org/wiki/State_space state space] is the domain of the [https://en.wikipedia.org/wiki/Loss_function cost function] called [https://en.wikipedia.org/wiki/Internal_energy energy] to be minimized <ref>[[Mathematician#SBGelfand|Saul B. Gelfand]], [[Mathematician#SKMitter|Sanjoy K. Mitter]] ('''1985'''). ''Analysis of simulated annealing for optimization''. [http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4048220 24th IEEE Conference on Decision and Control] </ref>.
=History=
The annealing algorithm is an adaptation of the [https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm Metropolis–Hastings algorithm] to generate sample states of a [https://en.wikipedia.org/wiki/Thermodynamic_system thermodynamic system], invented by [[Mathematician#MRosenbluth|Marshall Rosenbluth]] and published by [https://en.wikipedia.org/wiki/Nicholas_Metropolis Nicholas Metropolis] et al. in 1953 <ref>[https://en.wikipedia.org/wiki/Nicholas_Metropolis Nicholas Metropolis], [http://scitation.aip.org/content/contributor/AU0719025 Arianna W. Rosenbluth], [[Mathematician#MRosenbluth|Marshall N. Rosenbluth]], [https://commons.wikimedia.org/wiki/File:Augusta_H._Teller_Los_Alamos_ID.png Augusta H. Teller], [[Mathematician#ETeller|Edward Teller]] ('''1953'''). ''[https://en.wikipedia.org/wiki/Equation_of_State_Calculations_by_Fast_Computing_Machines Equation of State Calculations by Fast Computing Machines]''. [https://en.wikipedia.org/wiki/Journal_of_Chemical_Physics Journal of Chemical Physics], Vol. 21, No. 6</ref> <ref>[https://en.wikipedia.org/wiki/Nicholas_Metropolis Nicholas Metropolis] ('''1987'''). ''The Beginning of the Monte Carlo Method''. [[Los Alamos National Laboratory|Los Alamos Science Special]], [http://library.lanl.gov/cgi-bin/getfile?00326866.pdf pdf]</ref> , later generalized by [[Mathematician#WKHastings|W. Keith Hastings]] at [[University of Toronto]] <ref>[[Mathematician#WKHastings|W. Keith Hastings]] ('''1970'''). ''[http://biomet.oxfordjournals.org/content/57/1/97 Monte Carlo Sampling Methods Using Markov Chains and Their Applications]''. [[University of Toronto]], [https://en.wikipedia.org/wiki/Biometrika Biometrika], Vol. 57, No. 1, [http://www2.stat.duke.edu/~scs/Courses/Stat376/Papers/Basic/Hastings1970.pdf pdf]</ref>. According to [[Mathematician#RJlauber|Roy Glauber]] and [[Mathematician#ESegre|Emilio Segrè]], the original algorithm was invented by [[Mathematician#EFermi|Enrico Fermi]] and reinvented by [[Stanislaw Ulam]] <ref>[https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm Metropolis–Hastings algorithm from Wikipedia]</ref>.
SA was independently described by [[Mathematician#SKirkpatrick|Scott Kirkpatrick]], [[Mathematician#CDGelatt|C. Daniel Gelatt]] and Mario P. Vecchi in 1983 <ref>[[Mathematician#SKirkpatrick|Scott Kirkpatrick]], [[Mathematician#CDGelatt|C. Daniel Gelatt]], [https://www.linkedin.com/in/mariovecchi Mario P. Vecchi] ('''1983'''). ''[http://science.sciencemag.org/content/220/4598/671 Optimization by Simulated Annealing]''. [https://en.wikipedia.org/wiki/Science_(journal) Science], Vol. 220, No. 4598, [http://wexler.free.fr/library/files/kirkpatrick%20(1983)%20optimization%20by%20simulated%20annealing.pdf pdf]</ref>, at that time affiliated with [https://en.wikipedia.org/wiki/Thomas_J._Watson_Research_Center IBM Thomas J. Watson Research Center, Yorktown Heights], and by Vlado Černý from [https://en.wikipedia.org/wiki/Comenius_University Comenius University], [https://en.wikipedia.org/wiki/Bratislava Bratislava] in 1985 <ref>[https://sites.google.com/site/cernyv/Home Vlado Černý] ('''1985'''). ''[http://link.springer.com/article/10.1007%2FBF00940812 Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm]''. [http://www.springer.com/mathematics/journal/10957 Journal of Optimization Theory and Applications], Vol. 45, No. 1</ref>.
=Quotes=
In the 2003 conference proceedings ''Celebrating the 50th Anniversary of the Metropolis Algorithm'' <ref>[http://cnls.lanl.gov/Conferences/MonteCarloMethods/ The Monte Carlo Method in Physical Sciences: Celebrating the 50th Anniversary of the Metropolis Algorithm]</ref> <ref>[http://cnls.lanl.gov/External/people/James_Gubernatis.php James Gubernatis] (ed.) ('''2003'''). ''[http://scitation.aip.org/content/aip/proceeding/aipcp/690 The Monte Carlo Method in Physical Sciences: Celebrating the 50th Anniversary of the Metropolis Algorithm]''. [http://scitation.aip.org/content/aip/proceeding/aipcp AIP Conference Proceedings]</ref>, [[Mathematician#MRosenbluth|Marshall Rosenbluth]] describes the algorithm in the following beautifully concise and clear manner <ref>[http://cnls.lanl.gov/External/people/James_Gubernatis.php James Gubernatis] ('''2005'''). ''Marshall Rosenbluth and the Metropolis Algorithm''. [https://en.wikipedia.org/wiki/Physics_of_Plasmas Physics of Plasmas], Vol. 12, No. 5, [http://www.z-cam.es/historique/Gubernatis_on_Rosenbluth.pdf pdf]</ref>:
A simple way to do this [sampling configurations with the [https://en.wikipedia.org/wiki/Boltzmann_distribution Boltzmann weight]], as emerged after discussions with [[Mathematician#ETeller|Teller]], would be to make a trial move: if it decreased the energy of the system, allow it; if it increased the energy, allow it with [https://en.wikipedia.org/wiki/Probability probability] exp(−ΔE/kT) as determined by a comparison with a [[Pseudorandom number generator|random number]]. Each step, after an initial annealing period, is counted as a member of the ensemble, and the appropriate ensemble average of any quantity determined.
=Applications=
SA has multiple applications in discrete [https://en.wikipedia.org/wiki/NP-hardness NP-hard] optimization problems such as the [https://en.wikipedia.org/wiki/Travelling_salesman_problem Travelling salesman problem], in [[Learning|machine learning]], in training of [[Neural Networks|neural networks]], and in the domain of computer games and computer chess in [[Automated Tuning|automated tuning]] as elaborated by [[Peter Mysliwietz]] in his Ph.D. thesis <ref>[[Peter Mysliwietz]] ('''1994'''). ''Konstruktion und Optimierung von Bewertungsfunktionen beim Schach.'' Ph.D. thesis (German)</ref> to optimize the [[Evaluation|evaluation]] weight vector in [[Zugzwang (Program)|Zugzwang]]. In its variant of [[Temporal Difference Learning|temporal difference learning]] to adjust pattern weights in [[Morph]], [[Robert Levinson]] at al. used simulated annealing as [https://en.wikipedia.org/wiki/Metaheuristic metaheuristic] to set its own learning rate for each pattern, the more frequently a pattern is updated, the slower becomes its learning rate <ref>[[Robert Levinson]] ('''1994'''). ''Experience-Based Creativity''. Artificial Intelligence and Creativity: An Interdisciplinary Approach, Kluwer</ref> <ref>[[Ari Shapiro]], [[Gil Fuchs]], [[Robert Levinson]] ('''2002'''). ''[http://www.arishapiro.com/researchportfolio/Learning%20Game%20Strategy/index.htm Learning a Game Strategy Using Pattern-Weights and Self-play]''. [[CG 2002]], [http://www.arishapiro.com//ShapiroA_CG2002.pdf pdf]</ref> <ref>[[Johannes Fürnkranz]] ('''2000'''). ''Machine Learning in Games: A Survey''. [https://en.wikipedia.org/wiki/Austrian_Research_Institute_for_Artificial_Intelligence Austrian Research Institute for Artificial Intelligence], OEFAI-TR-2000-3, [http://www.ofai.at/cgi-bin/get-tr?download=1&paper=oefai-tr-2000-31.pdf pdf]</ref>.
=Algorithm=
==Description==
The [https://en.wikipedia.org/wiki/Control_flow control flow] of the algorithm is determined by two nested loops, the outer loop over decreasing [https://en.wikipedia.org/wiki/Temperature temperature] simulates the cooling, and an inner loop times n Monte Carlo [[Iteration|iterations]]. Each time a randomly picked neighbor state inside the inner loop provides a better energy or [https://en.wikipedia.org/wiki/Fitness_function fitness] than the current state, the neighbor becomes the new current and even new optimum if fitter than fittest so far. Otherwise, if the neighbor fitness does not exceed current, it might still become current depending on the positive fitness or energy difference ΔE, and [https://en.wikipedia.org/wiki/Kelvin absolute temperature] T, with a [https://en.wikipedia.org/wiki/Probability probability] p according to the [https://en.wikipedia.org/wiki/Boltzmann_distribution Boltzmann factor]:
: [[FILE:SimulatedAnnealingBoltzmannFactor.jpg|none|border|text-bottom]]
where k the [https://en.wikipedia.org/wiki/Boltzmann_constant Boltzmann constant], and [https://en.wikipedia.org/wiki/E_(mathematical_constant) e] base of the [https://en.wikipedia.org/wiki/Exponential_function exponential function] whose negative exponent ensures the [0, 1] probability interval. Accepting worse solutions is a primary feature of SA, and important to stop [https://en.wikipedia.org/wiki/Greedy_algorithm greedy] [https://en.wikipedia.org/wiki/Exploitation exploitation] a [https://en.wikipedia.org/wiki/Local_optimum local optimum] but to explore other areas - higher temperatures favor [https://en.wikipedia.org/wiki/Exploration exploration], while decreasing temperatures make the algorithm to behave greedier in favoring exploitation of the hopefully global optimum.
==Animation==
[[FILE:Hill_Climbing_with_Simulated_Annealing.gif|none|border|text-bottom|560px|link=https://commons.wikimedia.org/wiki/File:Hill_Climbing_with_Simulated_Annealing.gif]]
Simulated annealing - searching for a maximum. <ref>Start temperature: 25 step: 0.1 End temperature: 0 - 1,000,000 iterations at each temperature: [https://en.wikipedia.org/wiki/GIF Animated GIF] [https://commons.wikimedia.org/wiki/File:Hill_Climbing_with_Simulated_Annealing.gif Hill Climbing with Simulated Annealing] by [https://en.wikipedia.org/wiki/User:Kingpin13?rdfrom=commons:User:Kingpin13 Kingpin13], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Simulated_annealing Simulated annealing from Wikipedia]</ref><br/>With the high temprature, the numerous local maxima are left quickly through the strong noise movement - <br/>but the global maximum is reliably found because of cooling temperature is no longer sufficient to leave it.
==Pseudo Code==
The [[C]] like pseudo code is based on [[Peter Mysliwietz|Peter Mysliwietz']] description as given in his Ph.D. thesis <ref>[[Peter Mysliwietz]] ('''1994'''). ''Konstruktion und Optimierung von Bewertungsfunktionen beim Schach.'' Ph.D. thesis, 7.4. Simulated Annealing, 7.4.2. Beschreibung des Algorithmus, Abb. 29, pp. 146 (German)</ref>. Several neighbor functions used to modify the weight vector were tried, where one randomly chosen element changed randomly performed well. The [https://en.wikipedia.org/wiki/Fitness_function fitness function] inside the inner loop is of course the most time consuming part. For [[Zugzwang (Program)|Zugzwang]], Mysliwietz used a database of 500 [[Test-Positions|test-positions]] with a [[Depth|search depth]] of one [[Ply|ply]], which took about three minutes on a [[Transputer|T 800 Transputer]] per iteration - the higher the hit rate of found expert moves, the fitter. The whole optimization used a tHight to tLow ratio of 100, a reduction factor r of 0.95, and n=40 inner iterations.
<pre>
/**
* simulatedAnnealing
* @author Peter Mysliwietz, slightly modified
* @param tHigh is the start temperature
* @param tLow is the minimal end temperature
* @param r is the temperature reduction factor < 1.0
* @param n number of iterations for each temperature
* @return best weight vector
*/
vector simulatedAnnealing(double tHigh, double tLow, double r, int n) {
vector currentWeights = randomWeights();
vector bestWeights = currentWeights;
double fittest = fitness(currentWeights);
for (double t = tHigh; t > tLow; t *= r) {
for (int i = 0; i < n; ++i) {
vector neighborWeights = neighbor(currentWeights);
if ( fitness(neighborWeights ) > fitness(currentWeights) ) {
currentWeights = neighborWeights;
if ( fitness(neighborWeights ) > fittest ) {
fittest = fitness(neighborWeights);
bestWeights = neighborWeights;
}
} else if (accept( fitness(currentWeights) - fitness(neighborWeights ), t) ) {
currentWeights = neighborWeights;
}
} /* for i */
} /* for t */
return bestWeights;
}
/**
* accept
* @param d is the energy difference >= 0
* @param t is the current temperature
* @return true with probability of Boltzmann factor e^(-d/kt)
*/
bool accept(double d, double t ) {
const double k = 1.38064852e−23; /* joule / kelvin */
double p = exp(-d / (k*t) );
double r = rand() / (RAND_MAX + 1.0);
return r < p;
}
</pre>
<ref>[https://en.wikipedia.org/wiki/Exponential_function Exponential function from Wikipedia]</ref> <ref>[https://en.wikipedia.org/wiki/C_mathematical_functions#Random_number_generation C mathematical functions - Random number generation from Wikipedia]</ref>
=See also=
* [[Automated Tuning]]
* [[Genetic Programming]]
* [[Iteration]]
* [[Learning]]
* [[SPSA]]
* [[Trial and Error]]
=Selected Publications=
<ref>[http://scienze-como.uninsubria.it/bressanini/montecarlo-history/ Monte Carlo History] by [http://scienze-como.uninsubria.it/bressanini/index.html Dario Bressanini]</ref>
==1948 ...==
* [[Mathematician#EFermi|Enrico Fermi]], [[Mathematician#RDRichtmyer|Robert D. Richtmyer]] ('''1948'''). ''Note on census-taking in Monte Carlo calculations''. [[Los Alamos National Laboratory]], [http://scienze-como.uninsubria.it/bressanini/montecarlo-history/fermi-1948.pdf pdf]
* [https://en.wikipedia.org/wiki/Nicholas_Metropolis Nicholas Metropolis], [[Stanislaw Ulam]] ('''1949'''). ''The Monte Carlo Method''. [https://en.wikipedia.org/wiki/Journal_of_the_American_Statistical_Association Journal of the American Statistical Association], Vol. 44, No. 247, [http://scienze-como.uninsubria.it/bressanini/montecarlo-history/metropolis-ulam-1949.pdf pdf]
==1950 ...==
* [https://en.wikipedia.org/wiki/Nicholas_Metropolis Nicholas Metropolis], [http://scitation.aip.org/content/contributor/AU0719025 Arianna W. Rosenbluth], [[Mathematician#MRosenbluth|Marshall N. Rosenbluth]], [https://commons.wikimedia.org/wiki/File:Augusta_H._Teller_Los_Alamos_ID.png Augusta H. Teller], [[Mathematician#ETeller|Edward Teller]] ('''1953'''). ''[https://en.wikipedia.org/wiki/Equation_of_State_Calculations_by_Fast_Computing_Machines Equation of State Calculations by Fast Computing Machines]''. [https://en.wikipedia.org/wiki/Journal_of_Chemical_Physics Journal of Chemical Physics], Vol. 21, No. 6
* [[Mathematician#MRosenbluth|Marshall N. Rosenbluth]], [http://scitation.aip.org/content/contributor/AU0719025 Arianna W. Rosenbluth] ('''1954'''). ''Further Results on Monte Carlo Equations of State''. [https://en.wikipedia.org/wiki/Journal_of_Chemical_Physics Journal of Chemical Physics], Vol. 22, No. 5, [http://scienze-como.uninsubria.it/bressanini/montecarlo-history/rosenbluth-1954.pdf pdf]
==1970 ...==
* [[Mathematician#WKHastings|W. Keith Hastings]] ('''1970'''). ''[http://biomet.oxfordjournals.org/content/57/1/97 Monte Carlo Sampling Methods Using Markov Chains and Their Applications]''. [[University of Toronto]], [https://en.wikipedia.org/wiki/Biometrika Biometrika], Vol. 57, No. 1, [http://www2.stat.duke.edu/~scs/Courses/Stat376/Papers/Basic/Hastings1970.pdf pdf]
==1980 ...==
* [[Mathematician#SKirkpatrick|Scott Kirkpatrick]], [[Mathematician#CDGelatt|C. Daniel Gelatt]], [https://www.linkedin.com/in/mariovecchi Mario P. Vecchi] ('''1983'''). ''[http://science.sciencemag.org/content/220/4598/671 Optimization by Simulated Annealing]''. [https://en.wikipedia.org/wiki/Science_(journal) Science], Vol. 220, No. 4598, [http://wexler.free.fr/library/files/kirkpatrick%20(1983)%20optimization%20by%20simulated%20annealing.pdf pdf]
* [https://sites.google.com/site/cernyv/Home Vlado Černý] ('''1985'''). ''[http://link.springer.com/article/10.1007%2FBF00940812 Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm]''. [http://www.springer.com/mathematics/journal/10957 Journal of Optimization Theory and Applications], Vol. 45, No. 1
* [[Mathematician#SBGelfand|Saul B. Gelfand]], [[Mathematician#SKMitter|Sanjoy K. Mitter]] ('''1985'''). ''Analysis of simulated annealing for optimization''. [http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4048220 24th IEEE Conference on Decision and Control]
* [[Mathematician#SBGelfand|Saul B. Gelfand]] ('''1987'''). ''Analysis of Simulated Annealing Type Algorithms''. Ph.D. thesis, [[Massachusetts Institute of Technology|MIT]], advisor: [[Mathematician##SKMitter|Sanjoy K. Mitter]], [http://www.mit.edu/~mitter/SKM_theses/87_2_Gelfand_PhD.pdf pdf]
* [https://en.wikipedia.org/wiki/Nicholas_Metropolis Nicholas Metropolis] ('''1987'''). ''The Beginning of the Monte Carlo Method''. [[Los Alamos National Laboratory|Los Alamos Science Special]], [http://library.lanl.gov/cgi-bin/getfile?00326866.pdf pdf]
* [https://scholar.google.com/citations?user=avq8-1QAAAAJ Rob A. Rutenbar] ('''1989'''). ''[https://scholar.google.com/citations?view_op=view_citation&hl=en&user=avq8-1QAAAAJ&citation_for_view=avq8-1QAAAAJ:u-x6o8ySG0sC Simulated Annealing Algorithms]''. [[IEEE]] Circuits and Devices Magazine, [http://www.cs.amherst.edu/~ccm/cs34/papers/rutenbar.pdf pdf]
==1990 ...==
* [[Mathematician#GDueck|Gunter Dueck]], [[Mathematician#TScheuer|Tobias Scheuer]] ('''1990'''). ''[http://adsabs.harvard.edu/abs/1990JCoPh..90..161D Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing]''. [https://en.wikipedia.org/wiki/Journal_of_Computational_Physics Journal of Computational Physics], Vol. 90, No. 1 <ref>[https://de.wikipedia.org/wiki/Schwellenakzeptanz Schwellenakzeptanz from Wikipedia.de] (German)</ref>
* [[Ingo Althöfer]], [[Klaus-Uwe Koschnick]] ('''1991'''). ''[http://link.springer.com/article/10.1007/BF01447741 On the convergence of “Threshold Accepting”]''. [http://link.springer.com/journal/245 Applied Mathematics and Optimization], Vol. 24, No. 1
* [[Andrey Grigoriev]] ('''1991'''). ''Artificial Intelligence or Stochastic Relaxation: Simulated Annealing Challenge''. [[2nd Computer Olympiad#Workshop|Heuristic Programming in AI 2]]
* [[Bernd Brügmann]] ('''1993'''). ''Monte Carlo Go''. [http://www.ideanest.com/vegos/MonteCarloGo.pdf pdf]
* [http://www.imm.dtu.dk/~rvvv/ René V. V. Vidal] (ed.) ('''1993'''). ''[http://link.springer.com/book/10.1007%2F978-3-642-46787-5 Applied Simulated Annealing]''. [http://www.springer.com/series/300 Lecture Notes in Economics and Mathematical Systems], Vol. 396, [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
* [[Robert Levinson]] ('''1994'''). ''Experience-Based Creativity''. Artificial Intelligence and Creativity: An Interdisciplinary Approach, Kluwer
* [[Peter Mysliwietz]] ('''1994'''). ''Konstruktion und Optimierung von Bewertungsfunktionen beim Schach.'' Ph.D. thesis (German)
* [[James C. Spall]] ('''1999'''). ''Stochastic Optimization: Stochastic Approximation and Simulated Annealing''. in [https://en.wikipedia.org/wiki/John_G._Webster John G. Webster] (ed.) ('''1999'''). [http://onlinelibrary.wiley.com/book/10.1002/047134608X Encyclopedia of Electrical and Electronics Engineering], Vol. 20, [https://en.wikipedia.org/wiki/John_Wiley_%26_Sons John Wiley & Sons], [http://www.jhuapl.edu/spsa/PDF-SPSA/Spall_Stochastic_Optimization.PDF pdf]
==2000 ...==
* [[Ari Shapiro]], [[Gil Fuchs]], [[Robert Levinson]] ('''2002'''). ''[http://www.arishapiro.com/researchportfolio/Learning%20Game%20Strategy/index.htm Learning a Game Strategy Using Pattern-Weights and Self-play]''. [[CG 2002]], [http://www.arishapiro.com//ShapiroA_CG2002.pdf pdf]
* [[Eric Triki]], [http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/c/Collette:Yann.html Yann Collette], [http://www.mirlabs.org/network/Europe/France/patrick.php Patrick Siarry] ('''2002'''). ''Empirical study of Simulated Annealing aimed at improved multiobjective optimization''. [http://uahost.uantwerpen.be/eume/workshops/momh/momh-9.pdf pdf]
* [http://cnls.lanl.gov/External/people/James_Gubernatis.php James Gubernatis] (ed.) ('''2003'''). ''[http://scitation.aip.org/content/aip/proceeding/aipcp/690 The Monte Carlo Method in Physical Sciences: Celebrating the 50th Anniversary of the Metropolis Algorithm]''. [http://scitation.aip.org/content/aip/proceeding/aipcp AIP Conference Proceedings] <ref>[http://cnls.lanl.gov/Conferences/MonteCarloMethods/ The Monte Carlo Method in Physical Sciences: Celebrating the 50th Anniversary of the Metropolis Algorithm]</ref>
* [[Daniel Walker]], [[Robert Levinson]] ('''2004'''). ''The MORPH Project in 2004''. [[ICGA Journal#27_4|ICGA Journal, Vol. 27, No. 4]]
* [http://cnls.lanl.gov/External/people/James_Gubernatis.php James Gubernatis] ('''2005'''). ''Marshall Rosenbluth and the Metropolis Algorithm''. [https://en.wikipedia.org/wiki/Physics_of_Plasmas Physics of Plasmas], Vol. 12, No. 5, [http://www.z-cam.es/historique/Gubernatis_on_Rosenbluth.pdf pdf]
==2010 ...==
* [http://sun.aei.polsl.pl/~zjc/ Zbigniew J. Czech], [http://sun.aei.polsl.pl/pub/wmikanik/index.html Wojciech Mikanik], [[Rafał Skinderowicz]] ('''2010'''). ''[http://link.springer.com/chapter/10.1007%2F978-3-642-14390-8_16?LI=true Implementing a Parallel Simulated Annealing Algorithm]''. [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science Lecture Notes in Computer Science], Volume 6067, [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
* [[Rafał Skinderowicz]] ('''2011'''). ''[http://www.researchgate.net/publication/220906163_Co-operative_Parallel_Simulated_Annealing_for_the_VRPTW Co-operative, Parallel Simulated Annealing for the VRPTW]''. Computational Collective Intelligence. Technologies and Applications, [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science Lecture Notes in Computer Science], [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer] <ref>[https://en.wikipedia.org/wiki/Vehicle_routing_problem Vehicle routing problem from Wikipedia]</ref>
* [[Mathematician#PRossmanith|Peter Rossmanith]] ('''2011'''). ''Simulated Annealing''. in [[Mathematician#BVoecking|Berthold Vöcking]] et al. (eds.) ('''2011'''). ''[http://www.springer.com/gp/book/9783642153273 Algorithms Unplugged]''. [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
* [[Ben Ruijl]], [[Jos Vermaseren]], [[Aske Plaat]], [[Jaap van den Herik]] ('''2013'''). ''Combining Simulated Annealing and Monte Carlo Tree Search for Expression Simplification''. [http://arxiv.org/abs/1312.0841 CoRR abs/1312.0841]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=38412&start=12 Re: Parameter tuning] by [[Rémi Coulom]], [[CCC]], March 23, 2011 » [[Automated Tuning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=31935 Idea for Automatic Calibration of Evaluation Function...] by [[Steve Maughan]], [[CCC]], January 22, 2010
=External Links=
==Simulated Annealing==
* [https://en.wikipedia.org/wiki/Simulated_annealing Simulated annealing from Wikipedia]
* [https://en.wikipedia.org/wiki/Adaptive_simulated_annealing Adaptive simulated annealing from Wikipedia]
* [http://mathworld.wolfram.com/SimulatedAnnealing.html Simulated Annealing] from [https://en.wikipedia.org/wiki/MathWorld Wolfram MathWorld]
* [http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo41.php Algorithmus der Woche - Informatikjahr 2006] by [[Mathematician#PRossmanith|Peter Rossmanith]], [https://en.wikipedia.org/wiki/RWTH_Aachen_University RWTH Aachen] (German)
* [http://apmonitor.com/me575/index.php/Main/SimulatedAnnealing Simulated Annealing Tutorial] by [https://scholar.google.com/citations?user=BD6fjEYAAAAJ John D. Hedengren], [https://en.wikipedia.org/wiki/Brigham_Young_University Brigham Young University]
* [http://katrinaeg.com/simulated-annealing.html The Simulated Annealing Algorithm] by [http://katrinaeg.com/ Katrina Ellison Geltman], February 20, 2014
==Related Topics==
* [https://en.wikipedia.org/wiki/Combinatorial_optimization Combinatorial optimization from Wikipedia]
* [https://en.wikipedia.org/wiki/Cross-entropy_method Cross-entropy method from Wikipedia]
* [https://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm Expectation–maximization algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Gibbs_sampling Gibbs sampling from Wikipedia]
* [https://en.wikipedia.org/wiki/Global_optimization Global optimization from Wikipedia]
* [https://en.wikipedia.org/wiki/Greedy_algorithm Greedy algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Hill_climbing Hill climbing from Wikipedia]
* [https://en.wikipedia.org/wiki/Local_search_(optimization) Local search (optimization) from Wikipedia]
* [https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo Markov chain Monte Carlo from Wikipedia]
* [https://en.wikipedia.org/wiki/Monte_Carlo_method Monte Carlo method from Wikipedia]
* [https://en.wikipedia.org/wiki/Quantum_annealing Quantum annealing from Wikipedia]
* [https://en.wikipedia.org/wiki/Simultaneous_perturbation_stochastic_approximation Simultaneous perturbation stochastic approximation from Wikipedia]
* [https://en.wikipedia.org/wiki/Stochastic_gradient_descent Stochastic gradient descent from Wikipedia]
* [https://en.wikipedia.org/wiki/Stochastic_optimization Stochastic optimization from Wikipedia]
* [https://en.wikipedia.org/wiki/Tabu_search Tabu search from Wikipedia]
==Misc==
* [https://en.wikipedia.org/wiki/Annealing_(metallurgy) Annealing (metallurgy) from Wikipedia]
* [[Videos#EsperanzaSpalding|Esperanza Spalding]] - [http://genius.com/Esperanza-spalding-good-lava-lyrics Good Lava], October 29, 2016 broadcast, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=9sOQ-YrGdyg|alignment=left|valignment=top}}
=References=
<references />
'''[[Algorithms|Up one Level]]'''
