1,359
edits
Changes
Jump to navigation
Jump to search
Line 49:
Line 49: − + + + + + +
Temperature Scheduling in Simulated Annealing (view source)
Revision as of 07:21, 21 December 2007
, 07:21, 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).
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, 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 [2], the ParSA library suggests that convergence speed is governed by the following equation:
<math>P(X_n \not\in Cost_{min})=\left(\frac{K}{n}\right)^{\alpha}</math>
Where P is the convergence speed, n is the subchain length and "''K'' and α are constants specific to the problem." [7].
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:
<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>