-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
178 lines (178 loc) · 11.4 KB
/
index.html
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
<!DOCTYPE html>
<html lang="en">
<head>
<script src="https://d3js.org/d3.v7.min.js"></script>
<script src="https://code.jquery.com/jquery-3.6.0.min.js" integrity="sha256-/xUj+3OJU5yExlq6GSYGSHk7tPXikynS7ogEvDej/m4=" crossorigin="anonymous"></script>
<script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
<link rel="stylesheet" type="text/css" href="style.css">
<script async defer src="https://buttons.github.io/buttons.js"></script>
<script src="utils.js" defer></script>
<script src="simulated_annealing.js" defer></script>
<script>
window.MathJax = {
tex: {
inlineMath: [['$', '$'], ['\\(', '\\)']]
}
};
</script>
<!-- Place this tag in your head or just before your close body tag. -->
<script async defer src="https://buttons.github.io/buttons.js"></script>
<meta charset="utf-8" />
</head>
<body onload="updateCode()">
<!-- <h1>Simulated Annealing Visualization</h1> -->
<div style="display: flex">
<div style="width: 30%;">
<div style="display: flex; line-height: 10px; background-color: burlywood;">
<img src="https://i.imgur.com/8heu0x7.png">
<h1>Simulated Annealing</h1>
<!-- Place this tag where you want the button to render. -->
</div>
<!-- Place this tag where you want the button to render. -->
<a class="github-button" href="https://github.com/vgarciasc/simulated-annealing-viz" data-icon="octicon-star" data-size="large" data-show-count="true" aria-label="Star vgarciasc/simulated-annealing-viz on GitHub">Star</a>
<p>The <b>Simulated Annealing</b> (SA) algorithm is a meta-heuristic, that is, a technique for approximating the global optimum of a function $J(x)$. SA is inspired by the annealing process in metallurgy, where a metal is molded by carefully altering its temperature over time. In this page, you can find a visualization of SA being applied in a clustering application.</p>
<p>Informally, <b>this is how SA works</b>: the algorithm starts with a high temperature and a initial solution $x$. Each iteration, this solution is randomly modified in some way, and the resulting solution is evaluated. If it is better than what we currently have, then great!, just use that instead. However, if the resulting solution is worse than what we currently have, then we still have <i>some</i> probability of accepting that candidate as our current solution; in particular, this probability is affected by the current temperature of the algorithm. Over time, this temperature gets reduced and we become more and more conservative (only accepting better solutions). It is useful to think about the two extremes: if the temperature is $0$, then only better solutions are accepted; if the temperature is $\infty$, then any solution is accepted, no matter how bad.</p>
<p>More formally, the algorithm is divided into inner and outer loops. In each of the $N$ <b>inner loop</b> iterations (<span class="line-number">line 3</span>), we apply a random perturbation to the current solution $x$ (<span class="line-number">line 5</span>) and obtain a candidate solution $\hat{x}$. Then, we compare $x$ and $\hat{x}$ (<span class="line-number">line 6</span>): if $\hat{x}$ is <i>better</i> than $x$ (i.e. if $J(\hat{x}) \leq J(x)$), then we accept $\hat{x}$ as our new current solution $x$ (<span class="line-number">line 7</span>). But if $\hat{x}$ is <i>worse</i> than $x$, then we only accept $\hat{x}$ with a probability that is proportional to the relative quality of the new solution (i.e. the worse the solution, the lower the probability) and also proportional to a parameter $T$ called <i>temperature</i> (i.e. the higher the temperature, the higher the probability). This probability is captured by the term $e^{(J(x) - J(\hat{x})) / T}$ in <span class="line-number">line 6</span> (notice that if $\hat{x}$ is better than $x$, then $J(\hat{x}) \leq J(x)$ and the probability check always returns true).</p>
<p>In each of the $k_{\max}$ <b>outer loop</b> iterations (<span class="line-number">line 1</span>), the temperature $T$ is reduced in a process called <i>cooling</i> (<span class="line-number">line 2</span>). This has the effect of making the algorithm more conservative over time: in the beginning the temperature is high, so worse solutions are occasionally accepted; however as the execution progresses, the temperature is reduced and it becomes hard to accept worse solutions.</p>
<p>Finally, the algorithm always checks if a solution $x$ is the <b>best one yet</b> (<span class="line-number">line 8</span>). If it is, then it is stored as $x_{\min}$ (<span class="line-number">line 9</span>). This is what the algorithm returns at the end of its execution.</p>
<!-- <h2>To-do:</h2>
<ul>
<li><s>botar diversas configurações: temperatura inicial, k_max, N, tipo de resfriamento, quantidade de clusters, dispersão dos clusters, talvez o tipo de disposição inicialdos clusters (e se for uniforme ao inves de gaussiano?), epsilon, etc</s></li>
<li><s>adicionar opção: colorir os pontos de acordo com o cluster mais proximo</s></li>
<li><s>definir uma forma melhor de definir os clusters iniciais (as vezes eles ficam muito juntos)</s></li>
<li>adicionar uma coluna no final com texto sobre simulated annealing</li>
<li><s>testar perturbações diferentes (todas as componentes, ao inves de apenas uma?)</s></li>
<li><s>pensar numa forma melhor de mostrar o x_min</s></li>
<li><s>o que fazer com os pontos que saem da tela?</s></li>
<li>adicionar distinção entre 'reset clusters' e 'reset solution'</li>
<li>adicionar fast simulated annealing?</li>
</ul> -->
</div>
<div style="width: 35%;">
<br><br>
<div style="padding: 10px; border: dashed 1px black; height: fit-content; margin-left: 10px">
<svg id="main-view"></svg>
</div>
</div>
<div style="margin-left: 10px; width: 35%">
<h2>Options:</h2>
<div style="margin-left: 1em;">
<!-- <b>1. Cluster quantity (1-5):</b> <label for="cluster-quantity" id="cluster-quantity-label">2</label>
<br> -->
<!-- <input style="margin-left: 1em;" type="range" id="cluster-quantity" name="cluster-quantity" min="1" max="5" value="2" step="1" oninput="$('#cluster-quantity-label').text($(this).val())"> -->
<!-- <br> -->
<b>1. $\# \text{clusters}$:</b> <input type=number id="cluster-quantity" min=1 max=5 step=1 value=2 style="width:50px">,
$T_0$:</b> <input type=number id="initial-temperature" min=0 max=10 step=0.1 value=1.0 style="width:50px">,
$k_\text{max}$:</b> <input type=number id="kmax" min=1 max=100 step=1 value=10 style="width:50px">,
$N$:</b> <input type=number id="Nmax" min=1 max=1000 step=1 value=100 style="width:50px">
<br>
<b>2. Should restart clusters that become empty?</b> <input type=checkbox id="should-restart-empty-clusters" onclick="updateCode()">
<br>
<b>3. Random perturbation type:</b>
<br>
<input type=radio name="random-perturbation-type" value="single-cluster-single-coordinate" checked>Single cluster, single coordinate
<br>
<input type=radio name="random-perturbation-type" value="single-cluster-all-coordinates">Single cluster, all coordinates
<br>
<input type=radio name="random-perturbation-type" value="all-clusters-all-coordinates">All clusters, all coordinates
</div>
<hr>
<button id="step-btn">> Step</button>
<button id="play-btn">>> Play</button>
<button id="play-btn" onclick="reset_algorithm()">[] Restart</button>
<button id="reset-btn" onclick="reset_points()">[] Generate new points</button>
<br><br>
<div style="width: 100%; border: solid 1px black;">
<div id="code-line-0" class="code-line">
<span class="line-number">0.</span> Initialize $x \leftarrow \mathbf{0}$, $x_\text{min} = x$
</div>
<div id="code-line-1" class="code-line">
<span class="line-number">1.</span> For $k = 1 \ldots k_\text{max}$:
<span id="code-line-1-comment" class="code-comment">
<!-- #0.23 <= 0.47 -->
</span>
</div>
<div id="code-line-2" class="code-line depth-1">
<span class="line-number">2.</span> $T \leftarrow T_0 / \log_2(k + 1)$
</div>
<div id="code-line-3" class="code-line depth-1">
<span class="line-number">3.</span> For $n = 1 \ldots N$:
<span id="code-line-3-comment" class="code-comment">
<!-- #0.23 <= 0.47 -->
</span>
</div>
<div id="code-line-3-1" condition="should-restart-empty-clusters" class="code-line conditional-code-line depth-2">
<span class="line-number">4.</span> Restart empty clusters
</div>
<div id="code-line-4" class="code-line depth-2">
<span class="line-number">5.</span> Randomly perturb $x$ to obtain $\hat{x}$
</div>
<div id="code-line-5" class="code-line depth-2">
<span class="line-number">6.</span> If $\text{unif}(0, 1) \leq e^{(J(x) - J(\hat{x})) / T}$:
<span id="code-line-5-comment" class="code-comment">
<!-- #0.23 <= 0.47 -->
</span>
</div>
<div id="code-line-6" class="code-line depth-3">
<span class="line-number">7.</span> $x \leftarrow \hat{x}$
</div>
<div id="code-line-7" class="code-line depth-3">
<span class="line-number">8.</span> If $J(x) \leq J(x_\text{min})$:
<span id="code-line-7-comment" class="code-comment">
<!-- #0.23 <= 0.47 -->
</span>
</div>
<div id="code-line-8" class="code-line depth-4">
<span class="line-number">9.</span> $x_\text{min} \leftarrow x$
</div>
</div>
<br>
<table style="width: 100%">
<colgroup>
<col span="1" style="width: 15%;">
<col span="1" style="width: 45%;">
<col span="1" style="width: 20%;">
<col span="1" style="width: 20%;">
</colgroup>
<tbody>
<tr>
<td colspan=1>$T$</td>
<td colspan=1 id="table-values-T">0</td>
</tr>
<tr>
<td>
<div style="display: flex; justify-content: end; align-items: center;">
<svg width="1em" height="1em"><circle class="solution-point" r="5" cx="0.5em" cy="0.5em"></circle></svg>
$x$
</div>
</td>
<td class="font-small coordinates" id="table-values-x">0</td>
<td>$J(x)$</td> <td id="table-values-Jx">0</td>
</tr>
<tr>
<td>
<div style="display: flex; justify-content: end; align-items: end;">
<svg width="20" height="20"><polygon class="best-solution-point" points="10,0,12.938926261462367,5.954915028125263,19.510565162951536,6.9098300562505255,14.755282581475768,11.545084971874736,15.877852522924732,18.090169943749473,10,15,4.12214747707527,18.090169943749473,5.244717418524233,11.545084971874738,0.4894348370484636,6.909830056250527,7.061073738537633,5.954915028125264"></polygon></svg>
$x_{\text{min}}$
</div>
</td>
<td class="font-small coordinates" id="table-values-xmin">0</td>
<td>$J(x_{\text{min)}}$</td><td id="table-values-Jxmin">0</td>
</tr>
<tr>
<td>
<div style="display: flex; justify-content: end; align-items: end;">
<svg width="1em" height="1em"><circle class="proposed-solution-point" r="5" cx="0.5em" cy="0.5em"></circle></svg>
$\hat{x}$
</div>
</td>
<td class="font-small coordinates" id="table-values-xhat">0</td>
<td>$J(\hat{x})$</td><td id="table-values-Jxhat">0</td>
</tr>
</tbody>
</table>
</div>
</div>
</body>
</html>