Przejdź do treści
Wróć do wyników wyszukiwania

Strategia Ewolucyjna (CMA-ES) — Adaptacja Macierzy Kowariancji

Autor metody
Nikolaus Hansen & Andreas Ostermeier
Rok
2001
Typ
Derivative-free continuous black-box optimizer

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

CMA-ES, skrót od Covariance Matrix Adaptation Evolution Strategy, jest nowoczesnym optymalizatorem ciągłych funkcji typu black-box, wprowadzonym przez Hansena i Ostermeiera w 2001 roku.

Utrzymuje on populację kandydatów na rozwiązania pobranych z wielowymiarowego rozkładu normalnego i iteracyjnie aktualizuje średnią, wielkość kroku oraz pełną macierz kowariancji rozkładu, aby skierować poszukiwania w lepsze rejony przestrzeni parametrów. Stał się on de facto standardem dla ciągłej optymalizacji typu black-box i jest szeroko stosowany w wyszukiwaniu architektur sieci neuronowych oraz optymalizacji polityk w uczeniu ze wzmocnieniem.

Intuicja stojąca za metodą

Wyobraźmy sobie, że szukamy najniższego punktu w pagórkowatym terenie, ale nie widzimy ukształtowania terenu — możemy jedynie badać poszczególne lokalizacje i poznawać ich wysokości. CMA-ES działa jak kierowana chmara: zrzuca chmurę punktów badawczych wokół aktualnie najlepszego przypuszczenia, mierzy, jak dobre jest każde z tych punktów, a następnie przekształca chmurę na potrzeby następnej rundy. Chmura nie jest prostą kulą — uczy się wydłużonego, nachylonego kształtu doliny, do której schodzi, zapamiętując, które kierunki doprowadziły do poprawy. W kolejnych generacjach chmura zwęża się i pochyla, dopasowując się do krzywizny powierzchni funkcji celu, co pozwala algorytmowi nawigować w długich, wąskich dolinach, które uwięziłyby prostsze metody.

Historia

Strategie ewolucyjne zostały wprowadzone w latach 60. i 70. XX wieku jako rodzina optymalizatorów opartych na populacji, inspirowanych ewolucją biologiczną. Mechanizm adaptacji macierzy kowariancji został opracowany przez Hansena i Ostermeiera i w pełni opisany w ich artykule z 2001 roku w Evolutionary Computation, który wykazał, że całkowicie zderandomizowana samo-adaptacja — uczenie się pełnej geometrii drugiego rzędu krajobrazu poszukiwań z historii udanych kroków — znacznie przewyższała wcześniejsze strategie ewolucyjne na problemach źle uwarunkowanych i nieodseparowanych. Samouczek Hansena z 2016 roku skonsolidował algorytm i jego właściwości teoretyczne, czyniąc CMA-ES standardową metodą referencyjną do benchmarkingu ciągłej optymalizacji typu black-box.

Kiedy stosować

CMA-ES jest odpowiedni, gdy funkcja celu jest ciągła, potencjalnie niewypukła, multimodalna lub zaszumiona, a informacje o gradiencie są niedostępne lub zbyt kosztowne do obliczenia. Optymalny zakres wymiarowości wynosi od około 10 do 1000 parametrów; poniżej 10 wymiarów prostsze metody są często wystarczające, a powyżej 1000 koszt pamięci kwadratowej macierzy kowariancji może stać się zaporowy. Nie ma minimalnego wymogu liczby próbek w sensie statystycznym — algorytm sam generuje własne punkty ewaluacji. CMA-ES naturalnie pasuje do strojenia hiperparametrów, wyszukiwania architektur sieci neuronowych, optymalizacji polityk w uczeniu ze wzmocnieniem oraz problemów projektowania inżynierskiego, gdzie symulator dostarcza jedynie wyjść typu black-box.

Ograniczenia i uwagi

  • Koszty pamięci kwadratowej i obliczeniowe na generację w zależności od liczby wymiarów ograniczają zastosowanie powyżej około 1000 parametrów bez wariantów redukcji wymiarowości.
  • Zbiega do lokalnego optimum w braku restartów; dla krajobrazów silnie multimodalnych potrzebne są wielokrotne restarty (IPOP-CMA-ES lub BIPOP-CMA-ES).
  • Nie nadaje się do dyskretnych lub kombinatorycznych przestrzeni poszukiwań — metoda jest z natury zdefiniowana dla ciągłych wektorów o wartościach rzeczywistych.

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Nie wymaga informacji o gradiencie — działa na dowolnej wywoływalnej funkcji celu, w tym na funkcjach zaszumionych lub opartych na symulacjach.
  • Uczy się lokalnej krzywizny krajobrazu poszukiwań poprzez adaptację kowariancji, co pozwala mu nawigować w wydłużonych i źle uwarunkowanych przestrzeniach poszukiwań, które pokonują metody bezgradientowe o stałych rozkładach poszukiwań.
  • Niezmienny względem transformacji zachowujących porządek funkcji celu i obrotów przestrzeni poszukiwań, co czyni go odpornym w szerokiej gamie geometrii problemów.
  • Dobrze nadaje się do problemów ciągłych o umiarkowanej do wysokiej wymiarowości (10–1000 parametrów) z jednym dostrajanym hiperparametrem — początkową wielkością kroku.

Zastosowania

  • Strojenie hiperparametrów dla modeli uczenia maszynowego, w tym architektur sieci neuronowych i agentów uczenia ze wzmocnieniem.
  • Wyszukiwanie architektur sieci neuronowych — optymalizacja dyskretnie zakodowanych parametrów architektury poprzez ciągłą relaksację.
  • Optymalizacja polityk w uczeniu ze wzmocnieniem, gdy polityka jest parametryzowana przez wektor ciągły.
  • Optymalizacja projektowania inżynierskiego, taka jak optymalizacja kształtu aerodynamicznego i dopasowanie parametrów strukturalnych, gdzie dostępne są jedynie wyniki symulatora.
  • Kalibracja modeli naukowych — dopasowanie modeli symulacyjnych do danych eksperymentalnych, gdy funkcja wiarygodności jest niedyferencjowalna lub kosztowna obliczeniowo.

Jak to działa

Jak to działa

1

Algorytm jest inicjowany wektorem początkowego rozwiązania i początkową wielkością kroku (sigma). Macierz kowariancji zaczyna jako macierz jednostkowa — idealnie kulista chmura poszukiwań. Ustawiany jest rozmiar populacji, zazwyczaj około 4 + floor(3 * ln(wymiar)).

2

W każdej generacji populacja kandydatów na rozwiązania jest próbkowana z bieżącego wielowymiarowego rozkładu normalnego zdefiniowanego przez wektor średniej, wielkość kroku i macierz kowariancji. Ponieważ rozkład jest wielowymiarowy normalny, próbki odzwierciedlają zarówno bieżące najlepsze oszacowanie, jak i nauczony kształt przestrzeni poszukiwań.

3

Każdy kandydat na rozwiązanie jest przekazywany do funkcji celu i otrzymuje ocenę jakości. Nie są wymagane żadne informacje o gradiencie — potrzebna jest jedynie skalarna wartość celu w każdym próbkowanym punkcie. To sprawia, że CMA-ES nadaje się do celów zaszumionych, niedyferencjowalnych i opartych na symulacjach.

4

Średnia jest przesuwana w kierunku lepiej ocenionych rozwiązań. Macierz kowariancji i wielkość kroku są aktualizowane za pomocą dwóch uzupełniających się ścieżek adaptacji — aktualizacji typu rank-one i rank-mu — tak, aby kierunki, które przyniosły dobre poprawy, stały się bardziej prawdopodobne w następnej generacji. Jest to kluczowy mechanizm, dzięki któremu CMA-ES uczy się lokalnej geometrii krajobrazu funkcji celu.

5

Algorytm powtarza cykl próbkowania–oceny–aktualizacji do momentu spełnienia kryterium zatrzymania: maksymalnej liczby ewaluacji funkcji, tolerancji na zmianę średniej lub wielkości kroku, lub wykrytego degeneracji macierzy kowariancji. Zwracane jest najlepsze rozwiązanie znalezione we wszystkich generacjach.

Częste pułapki

  • Ustawienie zbyt małej początkowej wielkości kroku uwięzi poszukiwania w wąskim sąsiedztwie i uniemożliwi eksplorację; zbyt duża spowoduje, że wczesne generacje zmarnują ewaluacje z dala od optimum. Powszechną zasadą jest ustawienie sigma tak, aby optimum znajdowało się w odległości trzech sigma od punktu startowego.
  • Stosowanie CMA-ES do problemów o bardzo niskiej wymiarowości (mniej niż pięć parametrów) jest zazwyczaj nieopłacalne — prostsze przeszukiwanie siatkowe lub metoda Neldera-Meada są wystarczające, a narzut związany z populacją w CMA-ES nie przynosi korzyści.
  • Uruchomienie tylko jednej instancji CMA-ES na multimodalnym krajobrazie grozi pominięciem globalnego optimum; należy stosować strategie wielokrotnego startu lub restartów opartych na populacji (IPOP/BIPOP), gdy wiadomo, że krajobraz jest silnie multimodalny.
  • Traktowanie zwróconego najlepszego rozwiązania jako prawdziwego globalnego optimum bez weryfikacji restartem jest częstym błędem — zawsze należy potwierdzić wielokrotnymi niezależnymi przebiegami, gdy cel jest silnie niewypukły.

Najczęściej zadawane pytania

Czym CMA-ES różni się od prostego algorytmu genetycznego?

Klasyczny algorytm genetyczny utrzymuje populację i stosuje krzyżowanie oraz mutację ze stałymi operatorami. CMA-ES zamiast tego modeluje populację jako próbki z wielowymiarowego rozkładu normalnego i stale adaptuje ten rozkład — jego średnią, wielkość kroku i pełną macierz kowariancji — w oparciu o to, które rozwiązania były udane. Pozwala to CMA-ES na naukę kształtu krajobrazu funkcji celu i nawigację w skorelowanych, źle uwarunkowanych przestrzeniach znacznie wydajniej niż algorytm genetyczny ze stałymi operatorami.

Czy CMA-ES gwarantuje znalezienie globalnego optimum?

Nie. CMA-ES jest metodą lokalnego przeszukiwania w tym sensie, że pojedynczy przebieg może zbiec do lokalnego optimum. Dla krajobrazów multimodalnych zaleca się wielokrotne niezależne restarty — być może z rosnącymi rozmiarami populacji (IPOP-CMA-ES) — w celu poprawy pokrycia przestrzeni poszukiwań.

Jaki jest najważniejszy hiperparametr do ustawienia?

Początkowa wielkość kroku sigma jest pojedynczym, najbardziej wpływowym hiperparametrem. Dobrą heurystyką jest ustawienie jej tak, aby oczekiwane optimum znajdowało się w odległości około trzech sigma od punktu startowego. Rozmiar populacji i maksymalna liczba ewaluacji są drugorzędnymi kontrolkami; domyślny wzór na rozmiar populacji (4 + floor(3 * ln(wymiar))) dobrze sprawdza się w praktyce.

Czy CMA-ES może obsługiwać zaszumione funkcje celu?

Tak. Ponieważ CMA-ES wykorzystuje jedynie informacje o kolejności rang w populacji — a nie absolutne wartości funkcji — jest stosunkowo odporny na szum. W przypadku wysoce zaszumionych ewaluacji, zwiększenie rozmiaru populacji lub uśrednienie wielu ewaluacji na kandydata może dodatkowo poprawić odporność.

Pokrewne metody

Źródła

  1. Hansen, N. & Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolutionary Strategies. Evolutionary Computation, 9(2), 159-195.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.

    Otwórz odnośnik do publikacji
    Skopiowano.