File: Simulated-Annealing-algorithm.html

package info (click to toggle)
gsl-ref-html 2.3-1
  • links: PTS
  • area: non-free
  • in suites: bullseye, buster, sid
  • size: 6,876 kB
  • ctags: 4,574
  • sloc: makefile: 35
file content (107 lines) | stat: -rw-r--r-- 4,818 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 The GSL Team.

Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with the
Invariant Sections being "GNU General Public License" and "Free Software
Needs Free Documentation", the Front-Cover text being "A GNU Manual",
and with the Back-Cover Text being (a) (see below). A copy of the
license is included in the section entitled "GNU Free Documentation
License".

(a) The Back-Cover Text is: "You have the freedom to copy and modify this
GNU Manual." -->
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Scientific Library &ndash; Reference Manual: Simulated Annealing algorithm</title>

<meta name="description" content="GNU Scientific Library &ndash; Reference Manual: Simulated Annealing algorithm">
<meta name="keywords" content="GNU Scientific Library &ndash; Reference Manual: Simulated Annealing algorithm">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Function-Index.html#Function-Index" rel="index" title="Function Index">
<link href="Simulated-Annealing.html#Simulated-Annealing" rel="up" title="Simulated Annealing">
<link href="Simulated-Annealing-functions.html#Simulated-Annealing-functions" rel="next" title="Simulated Annealing functions">
<link href="Simulated-Annealing.html#Simulated-Annealing" rel="previous" title="Simulated Annealing">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>


</head>

<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="Simulated-Annealing-algorithm"></a>
<div class="header">
<p>
Next: <a href="Simulated-Annealing-functions.html#Simulated-Annealing-functions" accesskey="n" rel="next">Simulated Annealing functions</a>, Up: <a href="Simulated-Annealing.html#Simulated-Annealing" accesskey="u" rel="up">Simulated Annealing</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Simulated-Annealing-algorithm-1"></a>
<h3 class="section">26.1 Simulated Annealing algorithm</h3>

<p>The simulated annealing algorithm takes random walks through the problem
space, looking for points with low energies; in these random walks, the
probability of taking a step is determined by the Boltzmann distribution,
</p>
<div class="example">
<pre class="example">p = e^{-(E_{i+1} - E_i)/(kT)}
</pre></div>

<p>if 
<em>E_{i+1} &gt; E_i</em>, and 
<em>p = 1</em> when 
<em>E_{i+1} &lt;= E_i</em>.
</p>
<p>In other words, a step will occur if the new energy is lower.  If
the new energy is higher, the transition can still occur, and its
likelihood is proportional to the temperature <em>T</em> and inversely
proportional to the energy difference 
<em>E_{i+1} - E_i</em>.
</p>
<p>The temperature <em>T</em> is initially set to a high value, and a random
walk is carried out at that temperature.  Then the temperature is
lowered very slightly according to a <em>cooling schedule</em>, for
example: <em>T -&gt; T/mu_T</em>
where <em>\mu_T</em> is slightly greater than 1. 
<a name="index-cooling-schedule"></a>
<a name="index-schedule_002c-cooling"></a>
</p>
<p>The slight probability of taking a step that gives higher energy is what
allows simulated annealing to frequently get out of local minima.
</p>



</body>
</html>