Modyfikacja reguły adaptacji macierzy kowariancji w strategiach ewolucyjnych


Eryk Warchulski

Praca realizowana pod opieką
prof. PW dr hab. inż. Jarosława Arabasa

Plan prezentacji:

  1. Optymalizacja
  2. Strategie ewolucyjne
  3. Adaptacja rozkładu
  4. Ścieżka ewolucyjna oraz macierz kowariancji
  5. Trudności z realizacją
  6. Rozwiązania stosowane dotychczas
  7. Idea realizowana w pracy
  8. Weryfikacja
  9. Dalsze plany
  10. Bibliografia

Optymalizacja

Na problem optymalizacji statycznej składa się:


  • funkcja celu
    $f\colon X \rightarrow Y$

Na problem optymalizacji statycznej składa się:


  • funkcja celu
    $f\colon X \rightarrow Y$
  • algorytm optymalizacyjny
    $A\left(\textbf{x}_{\small{0}}, f, \mathcal{P}\right)$

Na problem optymalizacji statycznej składa się:


  • funkcja celu
    $f\colon X \rightarrow Y$
  • algorytm optymalizacyjny
    $A\left(\textbf{x}_{\small{0}}, f, \mathcal{P}\right)$


\[ \small{\min_{x \in X}} \; \large{f}(\textbf{x}) \]

Gdzie można spotkać problemy statycznej optymalizacyjne?

  • Uczenie ze wzmocnieniem


Gdzie można spotkać problemy statycznej optymalizacyjne?

  • Uczenie ze wzmocnieniem
  • Konstrukcja modeli parametrycznych


Gdzie można spotkać problemy statycznej optymalizacyjne?

  • Uczenie ze wzmocnieniem
  • Konstrukcja modeli parametrycznych
  • Procesy technologiczne


Strategie ewolucyjne

Paradygmat wśród obliczeń ewolucyjnych (ang. evolutionary computation) poświęcony optymalizacji w przestrzeni rzeczywistoliczbowej.



Paradygmat wśród obliczeń ewolucyjnych (ang. evolutionary computation) poświęcony optymalizacji w przestrzeni rzeczywistoliczbowej.

$ X \equiv R^{n} $
$ Y \equiv R^{m} $
$x_{\small{0}} \equiv \big\{x_{i}\big\}_{i \in 1\dots\lambda}$

Paradygmat wśród obliczeń ewolucyjnych (ang. evolutionary computation) poświęcony optymalizacji w przestrzeni rzeczywistoliczbowej.

$ X \equiv R^{n} $
$ Y \equiv R^{m} $
$x_{\small{0}} \equiv \big\{x_{i}\big\}_{i \in 1\dots\lambda}$

Najczęsciej algorytmy z tej rodziny poświęcone są optymalizacji jednokryterialnej, tj. $m = 1$.


Często algorytmy strategii ewolucyjnych nazywane są algorytmami ostatniej szansy.

Rys. sześcian Klee-Minty'ego.
Adaptacja rozkładu

Na przestrzeni lat wprowadzano pewne usprawnienia algorytmu dotyczące:

Na przestrzeni lat wprowadzano pewne usprawnienia algorytmu dotyczące:

  • polityki sterowania zasięgiem mutacji $\sigma$

Na przestrzeni lat wprowadzano pewne usprawnienia algorytmu dotyczące:

  • polityki sterowania zasięgiem mutacji $\sigma$
  • zwiększania rozmiaru populacji bazowej oraz potomnej

Na przestrzeni lat wprowadzano pewne usprawnienia algorytmu dotyczące:

  • polityki sterowania zasięgiem mutacji $\sigma$
  • zwiększania rozmiaru populacji bazowej oraz potomnej
  • sposobu rekombinacji osobników

Na przestrzeni lat wprowadzano pewne usprawnienia algorytmu dotyczące:

  • polityki sterowania zasięgiem mutacji $\sigma$
  • zwiększania rozmiaru populacji bazowej oraz potomnej
  • sposobu rekombinacji osobników
  • metody selekcji osobników z populacji potomnej.

Na przestrzeni lat wprowadzano pewne usprawnienia algorytmu dotyczące:

  • polityki sterowania zasięgiem mutacji $\sigma$
  • zwiększania rozmiaru populacji bazowej oraz potomnej
  • sposobu rekombinacji osobników
  • metody selekcji osobników z populacji potomnej.

Największą wartosć dodaną do działania algorytmu przyniosła adaptacja macierzy kowariancji wraz z ideą kumulacji.

Ścieżka ewolucyjna oraz macierz kowariancji
Idea stojąca za kumulacją: \[ \mathcal{N}(0, 1)\textbf{x} \sim \mathcal{N}(0, \textbf{x}\textbf{x}^{T}) \]
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}) \]
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.

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.
Operator mutacji został wyposażony w macierz kowariancji różną od macierzy $I$.

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)} \\ \]
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)}} \\ \]
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} \]
Trudności z realizacją
\[ \sqrt{\star}\colon\; \mathbb{R} \rightarrow \mathbb{R} \]
\[ \sqrt{\star}\colon\; \mathbb{R}^{n \times m} \rightarrow \mathbb{R^{n \times m}} \]
\[ \sqrt{\star}\colon\; \mathbb{R}^{n \times m} \rightarrow \mathbb{R^{n \times m}} \Large{?} \]

Pierwiastek kwadratowy liczby rzeczywistej jest dobrze zdefiniowane.
Pierwiastek kwadratowy macierzy -- niekoniecznie.

  • pierwiastkowanie macierzy z użyciem dekompozycji Choleskiego, $\mathcal{O}(N^{3})$
  • pierwiastkowanie macierzy z użyciem dekompozycji Choleskiego, $\mathcal{O}(N^{3})$
  • pierwiastkowanie macierzy z użyciem dekompozycji według wartości osobliwych, $\mathcal{O}(N^{3})$
TODO: wykres na narzut czasowy
Rozwiązania stosowane dotychczas
Próby obejścia problemu dokonane przez innych:
  • $\textbf{LM-CMA-ES}$, I. Loshchilov [2]
  • $\textbf{(1+1)-CMA-ES}$, Ch. Igel [3]
  • $\textbf{MSR-CMA-ES}$, N. Hansen [4]
  • $\textbf{MA-ES}$, H. Beyer [5]
Idea realizowana w pracy
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} \]

Rys. Stosunek punktu średniego w populacji do punktu najlepszego. Rysunek własny.

Fakt ten skłania do skorzystania z informacji pozyskanej z punktu środkowego.
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}$.

Jeden z pomysłów przyjął następującą postać:

\[ \sigma^{(t+1)} = \sigma^{(t)}*exp\left\{d^{-1}\frac{p_{s} - \alpha}{1 - \alpha}\right\} \]

\[ \sigma^{(t+1)} = \sigma^{(t)}*exp\left\{\color{red} d^{-1}\frac{p_{s} - \alpha}{1 - \alpha}\right\} \]

\[ \sigma^{(t+1)} = \sigma^{(t)}*exp\left\{d^{-1}\frac{\color{red} p_{\color{red} s} - \alpha}{1 - \alpha}\right\} \]

\[ \sigma^{(t+1)} = \sigma^{(t)}*exp\left\{d^{-1}\frac{p_{s} - \color{red} \alpha}{1 - \color{red} \alpha}\right\} \]

Ponadto, bazując na [5], reguła adaptująca macierz kowariancji może zostać zapisana w następującej formie:

\[ 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] \]
Weryfikacja
IEEE CEC (ang. Congress on Computational Intelligence):
IEEE CEC (ang. Congress on Computational Intelligence):

$+$ łącznie 30 problemów optymalizacyjnych, a w tym 15 unikalnych
$+$ wymiarowość zadań $\{2, 5, 10, 30, 50, 100\}$
$+$ kod źródłowy problemów udostępniony w $\texttt{C}$
IEEE CEC (ang. Congress on Computational Intelligence):

$+$ łącznie 30 problemów optymalizacyjnych, a w tym 15 unikalnych
$+$ wymiarowość zadań $\{2, 5, 10, 30, 50, 100\}$
$+$ kod źródłowy problemów udostępniony w $\texttt{C}$

$-$ brak określenia procedury obsługi punktów niedopuszczalnych
$-$ niejednoznaczy opis problemów optymalizacyjnych
$-$ nieokreślony punkt startowy.

Stosowany sposób agregacji wyników i porównywania badanych metod:

Rys. Krzywe ECDF uzyskane dla wszystkich problemów z konkursu CEC17.
Rysunek własny.

TODO: rysunek zbieżności na funkcji kwadratowej
Dalsze plany

Bibliografia
[1]
[2]
[3]
[4]
[5]

Dziękuję.