Editing Global optimization (section)

== Stochastic methods ==
{{Main|Stochastic optimization}}

Several exact or inexact Monte-Carlo-based algorithms exist:

===Direct Monte-Carlo sampling===
{{Main|Monte Carlo method}}
In this method, random simulations are used to find an approximate solution.

Example: The [[traveling salesman problem]] is what is called a conventional optimization problem. That is, all the facts (distances between each destination point) needed to determine the optimal path to follow are known with certainty and the goal is to run through the possible travel choices to come up with the one with the lowest total distance. However, let's assume that instead of wanting to minimize the total distance traveled to visit each desired destination, we wanted to minimize the total time needed to reach each destination. This goes beyond conventional optimization since travel time is inherently uncertain (traffic jams, time of day, etc.). As a result, to determine our optimal path we would want to use simulation - optimization to first understand the range of potential times it could take to go from one point to another (represented by a probability distribution in this case rather than a specific distance) and then optimize our travel decisions to identify the best path to follow taking that uncertainty into account.

===Stochastic tunneling===
{{Main|Stochastic tunneling}}
'''Stochastic tunneling''' (STUN) is an approach to global optimization based on the [[Monte Carlo method]]-[[Sampling (signal processing)|sampling]] of the function to be objectively minimized in which the function is nonlinearly transformed to allow for easier tunneling among regions containing function minima. Easier tunneling allows for faster exploration of sample space and faster convergence to a good solution.

===Parallel tempering===
{{main|Parallel tempering}}
'''Parallel tempering''', also known as '''replica exchange MCMC sampling''', is a [[simulation]] method aimed at improving the dynamic properties of  [[Monte Carlo method]] simulations of physical systems, and of [[Markov chain Monte Carlo]] (MCMC) sampling methods more generally.  The replica exchange method was originally devised by Swendsen,<ref>Swendsen RH and Wang JS (1986) [https://www.researchgate.net/profile/Robert_Swendsen/publication/13255490_Replica_Monte_Carlo_Simulation_of_Spin-Glasses/links/0046352309b5f54715000000.pdf Replica Monte Carlo simulation of spin glasses] Physical Review Letters 57 : 2607–2609</ref> then extended by Geyer<ref>C. J. Geyer, (1991) in ''Computing Science and Statistics'', Proceedings of the 23rd Symposium on the Interface, American Statistical Association, New York, p. 156.</ref> and later developed, among others, by [[Giorgio Parisi]].,<ref>{{cite journal
 |author = Marco Falcioni and Michael W. Deem
 |year=1999
 |title = A Biased Monte Carlo Scheme for Zeolite Structure Solution
 |journal = J. Chem. Phys.
 |volume = 110 |issue = 3 |pages = 1754–1766
 |doi=10.1063/1.477812
|arxiv = cond-mat/9809085|bibcode = 1999JChPh.110.1754F|s2cid=13963102
 }}</ref><ref>David J. Earl and Michael W. Deem (2005) [http://www.rsc.org/Publishing/Journals/CP/article.asp?doi=b509983h "Parallel tempering: Theory, applications, and new perspectives"],  ''Phys. Chem. Chem. Phys.'',  7, 3910</ref>
Sugita and Okamoto formulated a [[molecular dynamics]] version of parallel tempering:<ref>{{cite journal
 |author = Y. Sugita and Y. Okamoto
 |year=1999
 |title = Replica-exchange molecular dynamics method for protein folding
 |journal = Chemical Physics Letters
 |volume = 314 |issue=1–2
 |pages = 141–151
 |doi=10.1016/S0009-2614(99)01123-9
|bibcode=1999CPL...314..141S}}</ref> this is usually known as replica-exchange molecular dynamics or REMD.

Essentially, one runs ''N'' copies of the system, randomly initialized, at different temperatures. Then, based on the Metropolis criterion  one exchanges configurations at different temperatures. The idea of this method
is to make configurations at high temperatures available to the simulations at low temperatures and vice versa.
This results in a very robust ensemble which is able to sample both low and high energy configurations.
In this way, thermodynamical properties such as the specific heat, which is in general not well computed in the canonical ensemble, can be computed with great precision.