1,359
edits
Changes
Jump to navigation
Jump to search
Line 86:
Line 86: − + − + − + + Line 98:
Line 99: + − + − + +
Temperature Scheduling in Simulated Annealing (view source)
Revision as of 08:54, 21 December 2007
, 08:54, 21 December 2007→Convergence and Prospective strategies
==Convergence and Prospective strategies==
==Convergence and Prospective strategies==
Convergence when spoken in the context of simulated annealing refers to how (if at all) a particular algorithm will approach the correct solution (or for very difficult problems a close to correct solution). There are many proofs of convergence that are given for certain types of simulated annealing algorithms ([[#References|[3]]] and [[#References|[7]]]), each with there own twist on cooling and other aspects of the algorithm's implementation. To understand fully (in a mathematical sense) the subject of convergence one must look into the properties of Markov chains and there connections to Monte Carlo-like algorithms. This topic is reserved for another wiki page. However, citing the article by [[#References|[2]]], the ParSA library suggests that convergence speed is governed by the following equation:
Convergence when spoken in the context of simulated annealing refers to how (if at all) a particular algorithm will approach the correct solution (or for very difficult problems a close to correct solution). There are many proofs of convergence that are given for certain types of simulated annealing algorithms ([[#References|[3]]] and [[#References|[7]]]), each with there own twist on cooling and other aspects of the algorithm's implementation. To understand fully (in a mathematical sense) the subject of convergence one must look into the properties of Markov chains and there connections to Monte Carlo-like algorithms. This topic is reserved for another wiki page. However, citing the article by [[#References|[2]]], the ParSA library suggests that convergence speed is governed by the following equation:
{align="center
{|width="50%"
{|width="50%"
|align="center"|
|align="right"|
<math>P(X_n \not\in Cost_{min})=\left(\frac{K}{n}\right)^{\alpha}</math>
<math>P(X_n \not\in Cost_{min})=\left(\frac{K}{n}\right)^{\alpha}</math>
|align="right" width="80"|(1)
|align="center" width="80"|(1)
|}
|}
|}
The primary objective for potential cooling strategies lies in the determination of the α and ''K'' factors given in the ParSA section on improving solution quality in a lesser amount of time. By tracking both the chain length ''n'' and speed of convergence P(X<sub>n</sub> ∉ Cost<sub>min</sub>), one can find a linear plot relating all four of the quantities through the following relationship:
The primary objective for potential cooling strategies lies in the determination of the α and ''K'' factors given in the ParSA section on improving solution quality in a lesser amount of time. By tracking both the chain length ''n'' and speed of convergence P(X<sub>n</sub> ∉ Cost<sub>min</sub>), one can find a linear plot relating all four of the quantities through the following relationship:
{|align="center"
{|width="50%"
{|width="50%"
|align="center"|
|align="right"|
<math>\ln{P(X_n \not\in Cost_{min})} = \alpha \ln{K} - \alpha \ln{n}</math>
<math>\ln{P(X_n \not\in Cost_{min})} = \alpha \ln{K} - \alpha \ln{n}</math>
|align="right" width="80"|(2)
|align="center" width="80"|(2)
|}
|}
|}