Difference between revisions of "Simulated Annealing"

From Chessprogramming wiki
Jump to: navigation, search
 
(11 intermediate revisions by the same user not shown)
Line 13: Line 13:
 
=Quotes=
 
=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>:
 
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.  
+
A simple way to do this <nowiki>[</nowiki>sampling configurations with the [https://en.wikipedia.org/wiki/Boltzmann_distribution Boltzmann weight]<nowiki>]</nowiki>, 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=
 
=Applications=
Line 81: Line 81:
 
* [[Iteration]]
 
* [[Iteration]]
 
* [[Learning]]
 
* [[Learning]]
 +
* [[Monte-Carlo Tree Search]]
 
* [[SPSA]]
 
* [[SPSA]]
 
* [[Trial and Error]]
 
* [[Trial and Error]]
Line 109: Line 110:
 
* [[Robert Levinson]] ('''1994'''). ''Experience-Based Creativity''. Artificial Intelligence and Creativity: An Interdisciplinary Approach, Kluwer
 
* [[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)
 
* [[Peter Mysliwietz]] ('''1994'''). ''Konstruktion und Optimierung von Bewertungsfunktionen beim Schach.'' Ph.D. thesis (German)
 +
* [https://scholar.google.com/citations?user=-2E52C0AAAAJ&hl=en Olivier C. Martin], [[Steve Otto]] ('''1996'''). ''[https://www.semanticscholar.org/paper/Combining-simulated-annealing-with-local-search-Martin-Otto/379efcc32f7588f276830fca7310da094f2c624d Combining simulated annealing with local search heuristics]''. [https://en.wikipedia.org/wiki/Annals_of_Operations_Research Annals of Operations Research], Vol. 63, No. 1, [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
 
* [[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]
 
* [[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 ...==
 
==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]
 
* [[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]
+
* [[Eric Triki]], [https://dblp.uni-trier.de/pers/hd/c/Collette:Yann Yann Collette], [https://dblp.uni-trier.de/pers/hd/s/Siarry:Patrick Patrick Siarry] ('''2002'''). ''[https://www.researchgate.net/publication/265288492_Empirical_study_of_Simulated_Annealing_aimed_at_improved_multiobjective_optimization Empirical study of Simulated Annealing aimed at improved multiobjective optimization]''. Research Paper
 
* [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>
 
* [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]]
 
* [[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]
 
* [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]
 +
* [[Eric Triki]], [https://dblp.uni-trier.de/pers/hd/c/Collette:Yann Yann Collette], [https://dblp.uni-trier.de/pers/hd/s/Siarry:Patrick Patrick Siarry] ('''2005'''). ''[https://www.sciencedirect.com/science/article/abs/pii/S0377221704003388 A Theoretical Study on the Behavior of Simulated Annealing leading to a new Cooling Schedule]''. [https://en.wikipedia.org/wiki/European_Journal_of_Operational_Research European Journal of Operational Research], Vol. 166, No. 1
 
==2010 ...==
 
==2010 ...==
 +
* [[Todd W. Neller]], [https://dblp.uni-trier.de/pers/hd/p/Pilla:Christopher_J=_La Christopher J. La Pilla] ('''2010'''). ''[https://www.semanticscholar.org/paper/Decision-Theoretic-Simulated-Annealing-Neller-Pilla/a159e8642ccfc9c63ab1190899fca6e403bcbb21 Decision-Theoretic Simulated Annealing]''. [https://dblp.uni-trier.de/db/conf/flairs/flairs2010.html FLAIRS Conference 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]
 
* [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>
 
* [[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]
 
* [[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]
 +
* [[Alan J. Lockett]], [[Risto Miikkulainen]] ('''2011'''). ''[http://www.cs.utexas.edu/users/ai-lab/?lockett:gecco11 Real-Space Evolutionary Annealing]''. [https://dblp.uni-trier.de/db/conf/gecco/gecco2011.html GECCO 2011]
 +
* [[Alan J. Lockett]] ('''2012'''). ''General-Purpose Optimization Through Information Maximization''. Ph.D. thesis, [https://en.wikipedia.org/wiki/University_of_Texas_at_Austin University of Texas at Austin], advisor [[Risto Miikkulainen]], [http://www.alockett.com/static/pdf/lockett-thesis.pdf pdf]
 
* [[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]
 
* [[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]
 +
* [[Alan J. Lockett]], [[Risto Miikkulainen]] ('''2014'''). ''[http://nn.cs.utexas.edu/?lockett:jogo13 Evolutionary Annealing: Global Optimization in Arbitrary Measure Spaces]''. [https://www.springer.com/journal/10898 Journal of Global Optimization], Vol. 58
  
 
=Forum Posts=
 
=Forum Posts=
Line 152: Line 159:
 
==Misc==
 
==Misc==
 
* [https://en.wikipedia.org/wiki/Annealing_(metallurgy) Annealing (metallurgy) from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Annealing_(metallurgy) Annealing (metallurgy) from Wikipedia]
* [[:Category:Esperanza Spalding|Esperanza Spalding]] - [http://genius.com/Esperanza-spalding-good-lava-lyrics Good Lava], ([https://en.wikipedia.org/wiki/KINK 101.9 KINK]), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
+
* [[:Category:Esperanza Spalding|Esperanza Spalding]] - [http://genius.com/Esperanza-spalding-good-lava-lyrics Good Lava], [https://en.wikipedia.org/wiki/Emily%27s_D%2BEvolution Emily's D+Evolution], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=joq3teY9f1U|alignment=left|valignment=top}}
+
: {{#evu:https://www.youtube.com/watch?v=l4y3Gc07p5s|alignment=left|valignment=top}}
  
 
=References=  
 
=References=  
 
<references />
 
<references />
 
 
'''[[Algorithms|Up one Level]]'''
 
'''[[Algorithms|Up one Level]]'''
 +
[[Category:Quotes]]
 
[[Category:Industrial Heritage Trail]]
 
[[Category:Industrial Heritage Trail]]
 
[[Category:Esperanza Spalding]]
 
[[Category:Esperanza Spalding]]
 +
[[Category:Animation]]

Latest revision as of 12:16, 18 September 2020

Home * Programming * Algorithms * Simulated Annealing

Simulated Annealing, (SA)
a Monte Carlo based algorithm for combinatorial optimization problems inspired by statistical mechanics in thermodynamics with the statistical ensemble of the probability distribution over all possible states of a system described by a Markov chain, where its stationary distribution converts to an optimal distribution during a cooling process after reaching the equilibrium. Thus, the annealing algorithm simulates a nonstationary finite state Markov chain whose state space is the domain of the cost function called energy to be minimized [2].

History

The annealing algorithm is an adaptation of the Metropolis–Hastings algorithm to generate sample states of a thermodynamic system, invented by Marshall Rosenbluth and published by Nicholas Metropolis et al. in 1953 [3] [4] , later generalized by W. Keith Hastings at University of Toronto [5]. According to Roy Glauber and Emilio Segrè, the original algorithm was invented by Enrico Fermi and reinvented by Stanislaw Ulam [6].

SA was independently described by Scott Kirkpatrick, C. Daniel Gelatt and Mario P. Vecchi in 1983 [7], at that time affiliated with IBM Thomas J. Watson Research Center, Yorktown Heights, and by Vlado Černý from Comenius University, Bratislava in 1985 [8].

Quotes

In the 2003 conference proceedings Celebrating the 50th Anniversary of the Metropolis Algorithm [9] [10], Marshall Rosenbluth describes the algorithm in the following beautifully concise and clear manner [11]:

A simple way to do this [sampling configurations with the Boltzmann weight], as emerged after discussions with 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 probability exp(−ΔE/kT) as determined by a comparison with a 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 NP-hard optimization problems such as the Travelling salesman problem, in machine learning, in training of neural networks, and in the domain of computer games and computer chess in automated tuning as elaborated by Peter Mysliwietz in his Ph.D. thesis [12] to optimize the evaluation weight vector in Zugzwang. In its variant of temporal difference learning to adjust pattern weights in Morph, Robert Levinson at al. used simulated annealing as metaheuristic to set its own learning rate for each pattern, the more frequently a pattern is updated, the slower becomes its learning rate [13] [14] [15].

Algorithm

Description

The control flow of the algorithm is determined by two nested loops, the outer loop over decreasing temperature simulates the cooling, and an inner loop times n Monte Carlo iterations. Each time a randomly picked neighbor state inside the inner loop provides a better energy or 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 absolute temperature T, with a probability p according to the Boltzmann factor:

SimulatedAnnealingBoltzmannFactor.jpg

where k the Boltzmann constant, and e base of the exponential function whose negative exponent ensures the [0, 1] probability interval. Accepting worse solutions is a primary feature of SA, and important to stop greedy exploitation a local optimum but to explore other areas - higher temperatures favor exploration, while decreasing temperatures make the algorithm to behave greedier in favoring exploitation of the hopefully global optimum.

Animation

Hill Climbing with Simulated Annealing.gif

Simulated annealing - searching for a maximum. [16]
With the high temprature, the numerous local maxima are left quickly through the strong noise movement -
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' description as given in his Ph.D. thesis [17]. Several neighbor functions used to modify the weight vector were tried, where one randomly chosen element changed randomly performed well. The fitness function inside the inner loop is of course the most time consuming part. For Zugzwang, Mysliwietz used a database of 500 test-positions with a search depth of one ply, which took about three minutes on a 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.

/**
 * 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;
}

[18] [19]

See also

Selected Publications

[20]

1948 ...

1950 ...

1970 ...

1980 ...

1990 ...

2000 ...

2010 ...

Forum Posts

External Links

Simulated Annealing

Related Topics

Misc

References

  1. train wheel production, Bochumer Verein, Bochum, Germany, ExtraSchicht 2010, The Industrial Heritage Trail, image by Rainer Halama, June 19, 2010, CC BY-SA 3.0, Wikimedia Commons, Glühen from Wikipedia.de (German)
  2. Saul B. Gelfand, Sanjoy K. Mitter (1985). Analysis of simulated annealing for optimization. 24th IEEE Conference on Decision and Control
  3. Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, Edward Teller (1953). Equation of State Calculations by Fast Computing Machines. Journal of Chemical Physics, Vol. 21, No. 6
  4. Nicholas Metropolis (1987). The Beginning of the Monte Carlo Method. Los Alamos Science Special, pdf
  5. W. Keith Hastings (1970). Monte Carlo Sampling Methods Using Markov Chains and Their Applications. University of Toronto, Biometrika, Vol. 57, No. 1, pdf
  6. Metropolis–Hastings algorithm from Wikipedia
  7. Scott Kirkpatrick, C. Daniel Gelatt, Mario P. Vecchi (1983). Optimization by Simulated Annealing. Science, Vol. 220, No. 4598, pdf
  8. Vlado Černý (1985). Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications, Vol. 45, No. 1
  9. The Monte Carlo Method in Physical Sciences: Celebrating the 50th Anniversary of the Metropolis Algorithm
  10. James Gubernatis (ed.) (2003). The Monte Carlo Method in Physical Sciences: Celebrating the 50th Anniversary of the Metropolis Algorithm. AIP Conference Proceedings
  11. James Gubernatis (2005). Marshall Rosenbluth and the Metropolis Algorithm. Physics of Plasmas, Vol. 12, No. 5, pdf
  12. Peter Mysliwietz (1994). Konstruktion und Optimierung von Bewertungsfunktionen beim Schach. Ph.D. thesis (German)
  13. Robert Levinson (1994). Experience-Based Creativity. Artificial Intelligence and Creativity: An Interdisciplinary Approach, Kluwer
  14. Ari Shapiro, Gil Fuchs, Robert Levinson (2002). Learning a Game Strategy Using Pattern-Weights and Self-play. CG 2002, pdf
  15. Johannes Fürnkranz (2000). Machine Learning in Games: A Survey. Austrian Research Institute for Artificial Intelligence, OEFAI-TR-2000-3, pdf
  16. Start temperature: 25 step: 0.1 End temperature: 0 - 1,000,000 iterations at each temperature: Animated GIF Hill Climbing with Simulated Annealing by Kingpin13, Wikimedia Commons, Simulated annealing from Wikipedia
  17. 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)
  18. Exponential function from Wikipedia
  19. C mathematical functions - Random number generation from Wikipedia
  20. Monte Carlo History by Dario Bressanini
  21. Schwellenakzeptanz from Wikipedia.de (German)
  22. The Monte Carlo Method in Physical Sciences: Celebrating the 50th Anniversary of the Metropolis Algorithm
  23. Vehicle routing problem from Wikipedia

Up one Level