Skip to content

Instantly share code, notes, and snippets.

@ewarchul

ewarchul/gist-reveal.it-slides.html

Forked from ryanj/gist-reveal.it-slides.html
Last active May 28, 2020 15:45
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ewarchul/bd2ca3b07b38ceea740cd8aac1ce2ad9 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ewarchul/bd2ca3b07b38ceea740cd8aac1ce2ad9 to your computer and use it in GitHub Desktop.
Download ZIP
Gist-powered Revealjs slideshow presentations http://gist-reveal.it
Raw
gist-reveal.it-slides.html
<!doctype html>
<html>
<head>
<meta charset="utf-8">
<title>Prezentacja algorytmy ewolucyjne</title>
<meta name="description" content="Prezentacja na seminarium dyplomowe">
<meta name="author" content="Eryk Warchulski">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="stylesheet" href="dist/reset.css">
<link rel="stylesheet" href="dist/reveal.css">
<link rel="stylesheet" href="dist/theme/serif.css" id="theme">
<!-- Theme used for syntax highlighting of code -->
<link rel="stylesheet" href="plugin/highlight/monokai.css" id="highlight-theme">
</head>
<body>
<div class="reveal">
<div class="slides">
<section>
<h3>Modyfikacja reguły adaptacji macierzy kowariancji w strategiach ewolucyjnych</h3>
<p>
<h4><br>Eryk Warchulski</h4>
</p>
<p>
<small>Praca realizowana pod opieką <br> prof. PW dr hab. inż. Jarosława Arabasa</small>
</p>
</section>
<section>
<p style="text-align:left;"><h2>Plan prezentacji:</h2></p>
<ol>
<li>Optymalizacja</li>
<li>Strategie ewolucyjne</li>
<li>Adaptacja rozkładu</li>
<li>Ścieżka ewolucyjna oraz macierz kowariancji</li>
<li>Trudności z realizacją</li>
<li>Rozwiązania stosowane dotychczas</li>
<li>Idea realizowana w pracy </li>
<li>Weryfikacja</li>
<li>Dalsze plany</li>
<li>Bibliografia</li>
</ol>
</section>
<section>
<p style="text-align:center;">
Optymalizacja
</p>
</section>
<section>
<p style="text-align:left;">
Na problem optymalizacji statycznej składa się:
</p>
<br>
<ul>
<li> funkcja celu <br> $f\colon X \rightarrow Y$ <br> </li>
</ul>
</section>
<section>
<p style="text-align:left;">
Na problem optymalizacji statycznej składa się:
</p>
<br>
<ul>
<li> funkcja celu <br> $f\colon X \rightarrow Y$ <br> </li>
<li> algorytm optymalizacyjny <br> $A\left(\textbf{x}_{\small{0}}, f, \mathcal{P}\right)$ </li>
</ul>
</section>
<section>
<p style="text-align:left;">
Na problem optymalizacji statycznej składa się:
</p>
<br>
<ul>
<li> funkcja celu <br> $f\colon X \rightarrow Y$ <br> </li>
<li> algorytm optymalizacyjny <br> $A\left(\textbf{x}_{\small{0}}, f, \mathcal{P}\right)$ </li>
</ul>
<br>
<br>
\[ \small{\min_{x \in X}} \; \large{f}(\textbf{x}) \]
</section>
<section>
<p style="text-align:left;">
Gdzie można spotkać problemy statycznej optymalizacyjne?
</p>
<ul>
<li> Uczenie ze wzmocnieniem </li>
</ul>
<br>
<br>
</section>
<section>
<p style="text-align:left;">
Gdzie można spotkać problemy statycznej optymalizacyjne?
</p>
<ul>
<li> Uczenie ze wzmocnieniem </li>
<li> Konstrukcja modeli parametrycznych </li>
</ul>
<br>
<br>
</section>
<section>
<p style="text-align:left;">
Gdzie można spotkać problemy statycznej optymalizacyjne?
</p>
<ul>
<li> Uczenie ze wzmocnieniem </li>
<li> Konstrukcja modeli parametrycznych </li>
<li> Procesy technologiczne </li>
</ul>
<br>
<br>
</section>
<section>
Strategie ewolucyjne
</section>
<section>
<p style="text-align:left;">
Paradygmat wśród obliczeń ewolucyjnych (ang. evolutionary computation) poświęcony optymalizacji w przestrzeni rzeczywistoliczbowej.
</p>
<br>
<br>
</section>
<section>
<p style="text-align:left;">
Paradygmat wśród obliczeń ewolucyjnych (ang. evolutionary computation) poświęcony optymalizacji w przestrzeni rzeczywistoliczbowej.
</p>
$ X \equiv R^{n} $
<br>
$ Y \equiv R^{m} $
<br>
$x_{\small{0}} \equiv \big\{x_{i}\big\}_{i \in 1\dots\lambda}$
</section>
<section>
<p style="text-align:left;">
Paradygmat wśród obliczeń ewolucyjnych (ang. evolutionary computation) poświęcony optymalizacji w przestrzeni rzeczywistoliczbowej.
</p>
$ X \equiv R^{n} $
<br>
$ Y \equiv R^{m} $
<br>
$x_{\small{0}} \equiv \big\{x_{i}\big\}_{i \in 1\dots\lambda}$
<br>
<p style="text-align:left;">
Najczęsciej algorytmy z tej rodziny poświęcone są optymalizacji jednokryterialnej, tj. $m = 1$.
</p>
<br>
</section>
<section>
<p style="text-align:left;">
Często algorytmy strategii ewolucyjnych nazywane są algorytmami ostatniej szansy.
</p>
</section>
<section>
<img src="klee-minty.svg" height="390" width="900"/>
Rys. sześcian Klee-Minty'ego.
</section>
<section data-markdown>
<textarea data-template>
### (1+1)-ES
#### [I. Rechenberg, H. Schwefel, 1970]
```Haskell [1|4|5|6|7-8|10-11]
ustaw m(0), σ(0), α, β
t = 0
repeat
z(t) ~ N(0, I)
x(t) = m(t) + σ(t)*z(t)
if f[m(t)] ≥ f[x(t)] then
m(t+1) = x(t)
σ(t+1) = σ(t)*exp(α)
else
m(t+1) = m(t)
σ(t+1) = σ(t)*exp(β)
t = t + 1
```
</textarea>
</code></pre>
</section>
<section>
Adaptacja rozkładu
</section>
<section>
<p style="text-align:left;">
Na przestrzeni lat wprowadzano pewne
usprawnienia algorytmu dotyczące:
</p>
<ul>
</ul>
<p style="text-align:left;">
</p>
</section>
<section>
<p style="text-align:left;">
Na przestrzeni lat wprowadzano pewne
usprawnienia algorytmu dotyczące:
</p>
<ul>
<li> polityki sterowania zasięgiem mutacji $\sigma$ </li>
</ul>
<p style="text-align:left;">
</p>
</section>
<section>
<p style="text-align:left;">
Na przestrzeni lat wprowadzano pewne
usprawnienia algorytmu dotyczące:
</p>
<ul>
<li> polityki sterowania zasięgiem mutacji $\sigma$ </li>
<li> zwiększania rozmiaru populacji bazowej oraz potomnej </li>
</ul>
<p style="text-align:left;">
</p>
</section>
<section>
<p style="text-align:left;">
Na przestrzeni lat wprowadzano pewne
usprawnienia algorytmu dotyczące:
</p>
<ul>
<li> polityki sterowania zasięgiem mutacji $\sigma$ </li>
<li> zwiększania rozmiaru populacji bazowej oraz potomnej </li>
<li> sposobu rekombinacji osobników </li>
</ul>
<p style="text-align:left;">
</p>
</section>
<section>
<p style="text-align:left;">
Na przestrzeni lat wprowadzano pewne
usprawnienia algorytmu dotyczące:
</p>
<ul>
<li> polityki sterowania zasięgiem mutacji $\sigma$ </li>
<li> zwiększania rozmiaru populacji bazowej oraz potomnej </li>
<li> sposobu rekombinacji osobników </li>
<li> metody selekcji osobników z populacji potomnej.</li>
</ul>
<p style="text-align:left;">
</p>
</section>
<section>
<p style="text-align:left;">
Na przestrzeni lat wprowadzano pewne
usprawnienia algorytmu dotyczące:
</p>
<ul>
<li> polityki sterowania zasięgiem mutacji $\sigma$ </li>
<li> zwiększania rozmiaru populacji bazowej oraz potomnej </li>
<li> sposobu rekombinacji osobników </li>
<li> metody selekcji osobników z populacji potomnej.</li>
</ul>
<p style="text-align:left;">
Największą wartosć dodaną do działania algorytmu przyniosła adaptacja macierzy kowariancji wraz z ideą kumulacji.
</p>
</section>
<section>
Ścieżka ewolucyjna oraz macierz kowariancji
</section>
<section>
Idea stojąca za kumulacją:
\[
\mathcal{N}(0, 1)\textbf{x} \sim
\mathcal{N}(0, \textbf{x}\textbf{x}^{T})
\]
</section>
<section>
Idea stojąca za kumulacją:
\[
\mathcal{N}(0, 1)\textbf{x} \sim
\mathcal{N}(0, \textbf{x}\textbf{x}^{T})
\]
\[
\textbf{p} =
\mathcal{N}(0, 1)\textbf{x}_{1} +
\dots +
\mathcal{N}(0, 1)\textbf{x}_{K} \sim
\mathcal{N}(0, \sum^{K}_{i = 1}\textbf{x}_{i}\textbf{x}_{i}^{T})
\]
</section>
<section>
Idea stojąca za kumulacją:
\[
\mathcal{N}(0, 1)\textbf{x} \sim
\mathcal{N}(0, \textbf{x}\textbf{x}^{T})
\]
\[
\textbf{p} =
\mathcal{N}(0, 1)\textbf{x}_{1} +
\dots +
\mathcal{N}(0, 1)\textbf{x}_{K} \sim
\mathcal{N}(0, \sum^{K}_{i = 1}\textbf{x}_{i}\textbf{x}_{i}^{T})
\]
Ścieżka ewolucyjna (ang. evolution path) niesie informacje o kierunkach, w których prawdopodobieństwo sukcesu jest największe.
</section>
<section>
<p style="text-align:left;">
Pomysł został zrealizowany przez N. Hansena i A. Auger [1].
Autorzy opracowali algorytm $\textbf{CMA-ES}$.
Ścieżka ewolucyjna została osadzona w kontekście
wektora średniego populacji $\textbf{m}$, będącego efektem rekombinacji. <br>
Operator mutacji został wyposażony w macierz kowariancji różną od macierzy $I$.
</p>
</section>
<section>
Standardowa realizacja strategii ewolucyjnych została rozszerzona o:
\[
\textbf{z}^{(t)} = \mathcal{N}(\textbf{0}, I) \\
\textbf{d}^{(t)} = \textbf{m}^{t} + \sqrt{C^{(t)}}\textbf{z}^{(t)} \\
\]
</section>
<section>
Standardowa realizacja strategii ewolucyjnych została rozszerzona o:
\[
\textbf{z}^{(t)} = \mathcal{N}(\textbf{0}, I) \\
\textbf{d}^{(t)} = \textbf{m}^{t} + \sqrt{C^{(t)}}\textbf{z}^{(t)} \\
\textbf{p}^{(t)} = \frac{m^{(t+1)} - m^{(t)}}{\sigma^{(t)}} \\
\textbf{p}_{\sigma}^{(t)} = (C)^{-\frac{1}{2}}\frac{m^{(t+1)} - m^{(t)}}{\sigma^{(t)}} \\
\]
</section>
<section>
Standardowa realizacja strategii ewolucyjnych została rozszerzona o:
\[
\textbf{z}^{(t)} = \mathcal{N}(\textbf{0}, I) \\
\textbf{d}^{(t)} = \textbf{m}^{t} + \sqrt{C^{(t)}}\textbf{z}^{(t)} \\
\textbf{p}^{(t)} = \frac{m^{(t+1)} - m^{(t)}}{\sigma^{(t)}} \\
\textbf{p}_{\sigma}^{(t)} = (C)^{-\frac{1}{2}}\frac{m^{(t+1)} - m^{(t)}}{\sigma^{(t)}} \\
C^{(t+1)} = C^{(t)} + \textbf{p}^{(t+1)}(\textbf{p}^{(t+1)})^{T} + \sum^{\lambda}_{i = 1}w_{i}\textbf{d}_{i}^{(t+1)}(\textbf{d}_{i}^{(t+1)})^{T}
\]
</section>
<section>
Trudności z realizacją
</section>
<section>
\[
\sqrt{\star}\colon\; \mathbb{R} \rightarrow \mathbb{R}
\]
</section>
<section>
\[
\sqrt{\star}\colon\; \mathbb{R}^{n \times m} \rightarrow \mathbb{R^{n \times m}}
\]
</section>
<section>
\[
\sqrt{\star}\colon\; \mathbb{R}^{n \times m} \rightarrow \mathbb{R^{n \times m}} \Large{?}
\]
</section>
<section>
<p style="text-align:left;">
Pierwiastek kwadratowy liczby rzeczywistej jest dobrze zdefiniowane. <br>
Pierwiastek kwadratowy macierzy -- niekoniecznie. <br>
</p>
</section>
<section>
<ul>
<li> pierwiastkowanie macierzy z użyciem dekompozycji Choleskiego, $\mathcal{O}(N^{3})$ </li>
</ul>
</section>
<section>
<ul>
<li> pierwiastkowanie macierzy z użyciem dekompozycji Choleskiego, $\mathcal{O}(N^{3})$ </li>
<li> pierwiastkowanie macierzy z użyciem dekompozycji według wartości osobliwych, $\mathcal{O}(N^{3})$ </li>
</ul>
</section>
<section>
TODO: wykres na narzut czasowy
</section>
<section>
Rozwiązania stosowane dotychczas
</section>
<section>
Próby obejścia problemu dokonane przez innych:
<ul>
<li> $\textbf{LM-CMA-ES}$, I. Loshchilov [2] </li>
<li> $\textbf{(1+1)-CMA-ES}$, Ch. Igel [3] </li>
<li> $\textbf{MSR-CMA-ES}$, N. Hansen [4] </li>
<li> $\textbf{MA-ES}$, H. Beyer [5] </li>
</ul>
</section>
<section>
Idea realizowana w pracy
</section>
<section>
Okazuje się, że kontrola środka populacji w sensie średniej arytmetycznej pozwala usprawnić działanie algorytmu ewolucyjnego [6].
\[
\tilde{x} = \sum^{\lambda}_{i = 1}\textbf{x}_{i}
\]
</section>
<section>
<img src="ratios.svg" height="500" width="900"/>
<p style="text-align:center; font-size:20px; font-weight: bold">
Rys. Stosunek punktu średniego w populacji do punktu najlepszego. Rysunek własny.
</p>
</section>
<section>
<p style="text-align:left;">
Fakt ten skłania do skorzystania z informacji pozyskanej z punktu środkowego. <br>
Interesujące wydało się użycie tej informacji w kontekście polityki sterowania zasięgiem mutacji i opracowanie prostszej reguły, niż jest stosowana w algorytmie $\textbf{CMA-ES}$.
</p>
</section>
<section>
<p style="text-align:left;">
Jeden z pomysłów przyjął następującą postać:
</p>
\[
\sigma^{(t+1)} = \sigma^{(t)}*exp\left\{d^{-1}\frac{p_{s} - \alpha}{1 - \alpha}\right\}
\]
</section>
<section>
<p style="text-align:left;">
</p>
\[
\sigma^{(t+1)} = \sigma^{(t)}*exp\left\{\color{red} d^{-1}\frac{p_{s} - \alpha}{1 - \alpha}\right\}
\]
</section>
<section>
<p style="text-align:left;">
</p>
\[
\sigma^{(t+1)} = \sigma^{(t)}*exp\left\{d^{-1}\frac{\color{red} p_{\color{red} s} - \alpha}{1 - \alpha}\right\}
\]
</section>
<section>
<p style="text-align:left;">
</p>
\[
\sigma^{(t+1)} = \sigma^{(t)}*exp\left\{d^{-1}\frac{p_{s} - \color{red} \alpha}{1 - \color{red} \alpha}\right\}
\]
</section>
<section>
<p style="text-align:left;">
Ponadto, bazując na [5], reguła adaptująca macierz kowariancji może zostać zapisana w następującej formie:
</p>
\[
C^{(t+1)} =
C^{(t)}\left[I +
\left(\textbf{p}^{(t+1)} (\textbf{p}^{(t+1)})^{T} - I\right) +
\left(\sum^{\lambda}_{i = 1}w_{i}\textbf{z}_{i}^{(t)} (\textbf{z}_{i}^{(t)})^{T} - I\right)
\right]
\]
</section>
<section>
Weryfikacja
</section>
<section>
<dl>
<dt> IEEE CEC (ang. Congress on Computational Intelligence): </dt>
</dl>
</section>
<section>
<dl>
<dt> IEEE CEC (ang. Congress on Computational Intelligence): </dt>
<br>
<dd> $+$ łącznie 30 problemów optymalizacyjnych, a w tym 15 unikalnych </dd>
<dd> $+$ wymiarowość zadań $\{2, 5, 10, 30, 50, 100\}$ </dd>
<dd> $+$ kod źródłowy problemów udostępniony w $\texttt{C}$ </dd>
</dl>
</section>
<section>
<dl>
<dt> IEEE CEC (ang. Congress on Computational Intelligence): </dt>
<br>
<dd> $+$ łącznie 30 problemów optymalizacyjnych, a w tym 15 unikalnych </dd>
<dd> $+$ wymiarowość zadań $\{2, 5, 10, 30, 50, 100\}$ </dd>
<dd> $+$ kod źródłowy problemów udostępniony w $\texttt{C}$ </dd>
<br>
<dd> $-$ brak określenia procedury obsługi punktów niedopuszczalnych </dd>
<dd> $-$ niejednoznaczy opis problemów optymalizacyjnych </dd>
<dd> $-$ nieokreślony punkt startowy. </dd>
</dl>
</section>
<section>
<p style="text-align:left; font-size:20px; font-weight: bold">
Stosowany sposób agregacji wyników i porównywania badanych metod:
</p>
<img src="ecdf.svg" height="500" width="1000" class="center"/>
<p style="font-size:15px; font-weight: bold">
Rys. Krzywe ECDF uzyskane dla wszystkich problemów z konkursu CEC17.<br> Rysunek własny.
</p>
</section>
<section>
TODO: rysunek zbieżności na funkcji kwadratowej
</section>
<section>
Dalsze plany
</section>
<section>
<p style="text-align:left">
Bibliografia <br>
[1]<br>
[2]<br>
[3]<br>
[4]<br>
[5]<br>
</p>
</section>
<section>
Dziękuję.
</section>
</div>
</div>
<script src="dist/reveal.js"></script>
<script src="plugin/zoom/zoom.js"></script>
<script src="plugin/notes/notes.js"></script>
<script src="plugin/math/math.js"></script>
<script src="plugin/search/search.js"></script>
<script src="plugin/markdown/markdown.js"></script>
<script src="plugin/highlight/highlight.js"></script>
<script>
// Also available as an ES module, see:
// https://revealjs.com/initialization/
Reveal.initialize({
controls: true,
progress: true,
center: true,
hash: true,
math: {
mathjax: 'https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js',
config: 'TeX-AMS_HTML-full',
TeX: { Macros: { RR: "{\\bf R}" } }
},
// Learn about plugins: https://revealjs.com/plugins/
plugins: [ RevealZoom, RevealMath, RevealNotes, RevealSearch, RevealMarkdown, RevealHighlight ]
});
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment