-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathchapter_4.tex
193 lines (162 loc) · 9.02 KB
/
chapter_4.tex
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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
\chapter{Heuristieken en metaheuristieken}
\section{Introductie}
Heuristieken zijn informele methoden die \emph{voldoende goede} oplossingen kunnen opleveren voor complexe problemen.
Hierbij worden twee soorten onderscheiden: constructieve en perturbatieve heuristieken.
Constructieve heuristieken bouwen een oplossing op en de groep van perturbatieve heuristieken maken wijzigingen aan een al bestaande oplossing.
\section{Modelleringen}
Een modellering dient om een oplossing voor te stellen, waarbij deze aan de volgende voorwaarden moet voldoen:
\begin{itemize}
\item Volledigheid: alle mogelijke oplossingen kunnen voorgesteld worden in de modellering
\item Connectiviteit: er bestaat een (indirect) pad tussen 2 oplossingen
\item Effici\"entie: snel een eenvoudig te manipuleren en evalueren
\end{itemize}
\paragraph{Binaire codering}
Deze codering houdt voor ieder object een eigenschap bij.
Bijvoorbeeld in geval van het knapzakprobleem, waarbij 0 voorstelt dat het item niet in de knapzak zit en 1 wel.
%
\begin{table}[!h]
\centering
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
1 & 0 & 0 & 1 & 1 & 1 & 0 \\ \hline
\end{tabular}
\end{table}
%
\paragraph{Geheeltallige codering}
Deze codering kan meerdere eigenschappen toekennen aan een enkel object dan de binaire codering, wat voor toekennings- en locatieproblemen nuttig is.
Deze codering kan ook gebruikt worden om permutatie- en volgordeproblemen te weerspiegelen.
Hierbij kunnen nummers uiteraard geen twee keer voorkomen, tenzij de probleemstelling dat toelaat.
%
\begin{table}[!h]
\centering
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
4 & 7 & 8 & 1 & 2 & 6 & 5 \\ \hline
\end{tabular}
\end{table}
%
\paragraph{Floating-point voorstelling}
Voor continue optimalisatieproblemen kan een voorstelling met zwevende komma's gebruikt worden.
Toepassingen zijn bijvoorbeeld het bepalen van samenstellingen of het optimaliseren vna parameters.
%
\begin{table}[!h]
\centering
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
2.5 & 0.8 & 10.3 & 1.0 & 2.3 & 4.6 & 0.1 \\ \hline
\end{tabular}
\end{table}
%
\paragraph{Niet-lineaire voorstelling}
Mocht gekozen worden voor een niet-lineaire voorstelling van de oplossing, is dit in veel gevallen een graaf- of boomstructuur.
\subsection{Directe en indirecte voorstelling}
Bij de modellering kan er gekozen worden om met een \emph{directe} voorstelling te werken, waarbij alle informatie direct beschikbaar is. Indien dit niet het geval is, en er dus een decoder nodig is om de oplossing te interpreteren, wordt gesproken van een \emph{indirecte} voorstelling.
\section{Lokale zoekmethoden}
Lokale zoekmethoden werken op basis van een initi\"ele oplossing, waarbij getracht wordt een lokaal minimum te bereiken.
Deze algoritmen bestaan dus altijd uit twee stappen:
%
\begin{enumerate}
\item Stap 1: construeer een initi\"ele oplossing.
\item Stap 2: vervang de huidige oplossing door een betere buur.
\item Stap 3: stoppen.
\end{enumerate}
%
Het bepalen van een valide initi\"ele oplossing kan op verschillende manieren gebeuren.
Zo kan er vertrokken worden van een al gekende oplossing.
Een andere strategie is om met een eenvoudigere heuristiek of zelfs willekeurig een oplossing te genereren.
De tweede stap is het vervangen van een oplossing door een betere uit de \emph{neighbourhood}.
De strategie om deze oplossing te kiezen, bepaalt de performantie en het eindelijke resultaat.
Tenslotte moet er ook een stop-voorwaarde voorzien worden.
Een eenvoudige voorwaarde is om de uitvoertijd te beperken, wat als nadeel heeft dat de oplossing mogelijks niet lokaal optimaal is.
Dit kan beter---maar ook niet gegarandeerd---bereikt worden door een timer te starten na de laatste verbetering.
Door een vast aantal iteraties te gebruiken in plaats van een timer, is dit wel mogelijk; dat aantal is echter afhankelijk van de probleemgrootte.
Daarnaast hebben beide strategi\"en als nadeel dat ze minder duidelijk zijn naar de gebruiker toe.
\paragraph{Steepest descent}
Hierbij wordt uit een omgeving de beste verbetering gekozen.
Deze strategie heeft als nadeel dat deze snel vast komt te zitten in een lokaal optimum. Een voordeel is wel dat de stop-voorwaarde duidelijk is: wanneer er geen betere buren meer zijn. Daarnaast convergeert deze heuristiek ook snel, wat wilt zeggen dat het lokale optimum snel bereikt wordt.
\paragraph{Hill climbing}
Hier wordt niet de beste, maar eerste verbetering uit een omgeving aanvaard, wat uitaard dezelfde nadelen heeft als steepest descent.
\TODO delta-evaluatie
\section{Metaheuristieken}
Een metaheuristiek is een methode die een probleem optimaliseert door iteratief te proberen een kandidaatoplossing te verbeteren met betrekking tot een gegeven kwaliteitsmaat.
Metaheuristieken zijn niet probleemspecifiek.
Ze zijn in staat om grote ruimten met kandidaatoplossingen te doorzoeken, maar bieden geen garantie op het vinden van een optimale oplossing.
\subsection{Simulated annealing}
Simulated annealing behoort tot de groep van \emph{drempelalgoritmen}, waarbij een slechtere oplossing soms aanvaard wordt op basis van een \emph{threshold}.
Dit wordt gerealiseerd door de oplossing te beschouwen als een kristallijne smelt, die langzaam afkoelt.
De temperatuur $T$ is staat voor de energie en heeft een invloed op de acceptatie-functie.
%%%%%%%%%%%%%%%%%%
% Indien dit gekopieerd wordt, zie: https://en.wikibooks.org/wiki/LaTeX/Algorithms
%%%%%%%%%%%%%%%%%%
\begin{algorithm}
\caption{Pseudocode voor simulated annealing.}
\label{algo:SimulatedAnnealing}
\begin{algorithmic}
\Require $s_0$: Initial solution
\Require $T_0$: Initial temperature
\Require $T_{min}$: Temperature of stopping condition
\Function{SimulatedAnnealing}{$s_0$, $T_0$, $T_{min}$}
\State $s \gets s_0$
\State $T \gets T_0$
\Repeat
\Repeat
\State{$s' \gets$ random neighbour}
\State{$\Delta E \gets f(s') - f(s)$}
\State{$r \gets$ random number between 0 and 1}
\If{$\Delta E \leq 0$ \Or $r < e^{ \frac{- \Delta E}{T}} $}
\State{$s \gets s'$}
\EndIf
\Until{$T < T_{min}$} \Comment{Equilibrium condition}
\State{$T = g(T)$} \Comment{Cooling scheme}
\Until{$T < T_{min}$} \Comment{Stopping condition}
\State \Return $s$
\EndFunction
\end{algorithmic}
\end{algorithm}
\paragraph{Acceptatiefunctie}
De waarschijnlijkheid om een slechtere oplossing te aanvaarden zal afnemen in functie van de temperatuur $T$.
In lijn met de koeling-analogie, is de acceptatiefunctie de Maxwell-Boltzmannverdeling waarbij een willekeurig getal $r$ tussen 0 en 1 groter zal moeten zijn.
\begin{equation}
r < e^{ \frac{- \Delta E}{T}}
\end{equation}
\paragraph{Koeling}
In algoritme~\ref{algo:SimulatedAnnealing} is de koelingstrategie $T \gets g(T)$ open gelaten, aangezien er verschillende strategi\"en bestaan.
Enkele voorbeelden:
\begin{enumerate}
\item \textbf{Lineair}: $T_i = T_0 - i \cdot \beta$ met $i$ het aantal iteraties
\item \textbf{Geometrisch}: $T = \alpha \cdot T$ met $\alpha$ vaak tussen 0,5 en 0,99.
\item \textbf{Logaritmisch}: $T_i = \frac{T_0}{\log(i)}$ Dit is in de praktijk onbruikbaar traag.
\item \textbf{Niet-monotoon}: hierbij wordt er aan \emph{reheating} gedaan, waarbij de temperatuur $T$ terug stijgt.
\end{enumerate}
\paragraph{Threshold accepting}
Dit is een deterministische variant op simulated annealing, waarbij de acceptatiefunctie vervangen wordt door een iteratie-afhankelijke drempelwaarde $Q$.
\paragraph{Old bachelor}
Hierbij wordt de drempel $Q$ aangepast in functie van de historiek: bij een recent geaccepteerde slechtere oplossing zal de drempel lichtjes verhoogd worden en verlaagd bij het aanvaarden van een betere oplossing. Hiervoor wordt de leeftijd (aantal iteraties sinds laatste aanvaardde oplossing) bijgehouden.
\subsection{Tabu search}
%%%%%%%%%%%%%%%%%%
% Indien dit gekopieerd wordt, zie: https://en.wikibooks.org/wiki/LaTeX/Algorithms
%%%%%%%%%%%%%%%%%%
\begin{algorithm}
\caption{Pseudocode voor tabu search.}
\label{algo:TabuSearch}
\begin{algorithmic}
\Require $s_0$: Initial solution
\Function{SimulatedAnnealing}{$s_0$}
\State $best \gets s_0$
\State{Initialize tabu list, intermediate and long term memory}
\Repeat
\State{$s \gets $ best allowed solution in neighbourhood}
\If{$f(s) < f(best)$}
\State{$s \gets best$}
\EndIf
\State{Update tabu list, aspiratation conditions, and memory}
\State{...}
\Until{stopping condition}
\State \Return $s$
\EndFunction
\end{algorithmic}
\end{algorithm}
\paragraph{Kortetermijngeheugen}
Het kortetermijngeheugen houdt een lijst bij van bezochte oplossingen om lussen te vermijden.
Alle oplossingen bijhouden neemt echter teveel ruimte en rekentijd in beslag, dus kan de lengte van deze \emph{tabu-lijst} beperkt worden.
Een alternatief is om \emph{hashes} op te slaan of kenmerken van de \emph{moves}, waarbij de inverse move verboden wordt.