09 · Wzmocnienie · 4 min czytania · aktualizacja
Czym są algorytmy ewolucyjne i do czego służą w uczeniu maszynowym?
W skrócie
Algorytm ewolucyjny optymalizuje bez gradientu: ocenia populację, zostawia najlepszych (selekcja), łączy ich geny (krzyżowanie) i losowo je zmienia (mutacja).
Co to jest
Algorytmy ewolucyjne (genetyczne, strategie ewolucyjne) to metody optymalizacji inspirowane doborem naturalnym. Utrzymują populację kandydatów, oceniają każdego funkcją przystosowania (fitness), wybierają lepszych do rozmnażania, tworzą potomstwo przez krzyżowanie i mutację i powtarzają to przez wiele pokoleń.
Nie potrzebują gradientu, więc radzą sobie z parametrami dyskretnymi i funkcjami nieróżniczkowalnymi. W uczeniu maszynowym stosuje się je do strojenia hiperparametrów, przeszukiwania architektur (NAS), wyboru cech i polityk w uczeniu ze wzmocnieniem — zwykle nie do uczenia wag dużych modeli.
Mechanizm — dlaczego tak działa
Selekcja: osobniki o wyższym fitness mają większą szansę zostać rodzicami (turniej, ruletka). Przy powtarzaniu rozkład populacji przesuwa się w stronę lepszych rozwiązań — to statystyczna wspinaczka po funkcji przystosowania bez liczenia pochodnych.
Krzyżowanie: potomek dostaje część genów od każdego z rodziców. Jeśli dobre rozwiązania składają się z dobrych bloków (np. dobry learning rate i dobra szerokość sieci), krzyżowanie łączy bloki znalezione osobno. Mutacja: losowa zmiana genu z małym prawdopodobieństwem. Utrzymuje różnorodność i pozwala wyjść z lokalnych optimów — bez niej populacja szybko zbiega do kopii jednego osobnika i przestaje szukać.
Koszt: każda ocena to pełne uruchomienie (np. trening sieci do końca), a populacja z dziesiątek osobników przez dziesiątki pokoleń to tysiące uruchomień. Ewolucja ma więc sens, gdy parametrów jest mało, oceny da się zrównoleglić, a gradientu nie ma. Dla milionów wag sieci spadek gradientu jest nieporównanie wydajniejszy: jeden backprop daje informację o wszystkich wagach naraz, a ewolucja z każdej oceny dostaje jedną liczbę.
Wyjątki istnieją. Strategie ewolucyjne rozproszone na tysiące rdzeni trenują polityki RL konkurencyjnie z metodami gradientowymi (Salimans i in. 2017), bo tam gradient i tak jest szumny, a oceny tanie. Regularized evolution dobrze wypada w przeszukiwaniu architektur (Real i in. 2019), a Population Based Training (Jaderberg i in. 2017) łączy ewolucję hiperparametrów z gradientowym treningiem wag.
Zastrzeżenie: selekcja działa tylko tak dobrze, jak pomiar fitness. Przy szumnej ocenie (kilka epizodów, mała walidacja) selekcja nagradza szczęście, a nie geny, i populacja dryfuje zamiast się poprawiać.
Na przykładzie
Na zbiorze Breast Cancer Wisconsin (podział 70/30, random_state=0, cechy po standaryzacji) ewoluowaliśmy 31 wag klasyfikatora liniowego (30 cech i wyraz wolny), a fitness była po prostu trafność na treningu — funkcja schodkowa, której gradientem nie da się optymalizować. Populacja 50 osobników, turniej trzech, krzyżowanie jednostajne, mutacja 10% genów szumem o odchyleniu 0,3, najlepszy osobnik przechodzi do kolejnego pokolenia; NumPy, seed 0.
Najlepszy z losowej populacji miał 88% trafności, po 10 pokoleniach — 99,0%, po 100 pokoleniach — 99,5% na treningu i 94,2% na teście. Bez mutacji ewolucja utknęła na 99,0%, a różnorodność populacji (średnie odchylenie genów) spadła do 0,08 wobec 0,32 z mutacją. Dla porównania regresja logistyczna potrzebowała 17 iteracji optymalizatora i miała 95,9% na teście; ewolucja zużyła 5000 ocen. Wyższy wynik treningowy nie przełożył się na test, bo trafność treningowa jest przy tak małej liczbie wierszy szumną miarą.
Dane: Breast Cancer Wisconsin (diagnostyka raka piersi)
W praktyce
- Hiperparametry: biblioteki DEAP, Nevergrad, Optuna (
CmaEsSampler); dla kilku ciągłych hiperparametrów CMA-ES to mocny wybór. - NAS: regularized evolution jako punkt odniesienia; w praktyce częściej metody gradientowe lub losowe przeszukiwanie.
- RL: strategie ewolucyjne jako alternatywa dla PPO przy tanich symulatorach i wielu rdzeniach.
- Wagi sieci: nie — użyj gradientu. Parametry dyskretne (liczba warstw, wybór cech, kolejność operacji): tak.
- Typowy błąd: fitness z jednego seeda lub jednego krótkiego epizodu — selekcja wybiera szczęściarzy.
Najczęstsze pytania
- Czy algorytmy genetyczne mogą trenować sieci neuronowe?
- Małe — tak (neuroewolucja, NEAT). Duże — zwykle się nie opłaca: spadek gradientu dostaje informację o wszystkich wagach z jednego przejścia wstecz, ewolucja z każdej oceny tylko jedną liczbę. Wyjątkiem są polityki RL przy tanich, zrównoleglonych symulacjach.
- Ewolucja czy optymalizacja bayesowska do hiperparametrów?
- Przy kilku ciągłych hiperparametrach i drogiej ocenie — optymalizacja bayesowska, bo potrzebuje mniej uruchomień. Przy wielu parametrach dyskretnych, równoległym sprzęcie i tanich ocenach — ewolucja lub losowe przeszukiwanie, które jest zaskakująco mocnym punktem odniesienia.
- Po co w algorytmie ewolucyjnym mutacja, skoro jest krzyżowanie?
- Krzyżowanie tylko miesza geny już obecne w populacji; po kilku pokoleniach selekcja usuwa różnorodność i wszyscy stają się podobni. Mutacja wprowadza nowe wartości i pozwala uciec z lokalnego optimum. Za silna mutacja zamienia jednak ewolucję w losowe błądzenie.
Źródła
- Eiben, A. E., Smith, J. E. (2015). Introduction to Evolutionary Computing, 2nd ed., Springer, rozdz. 3 "What is an evolutionary algorithm?".
- Salimans, T., Ho, J., Chen, X., Sidor, S., Sutskever, I. (2017). "Evolution strategies as a scalable alternative to reinforcement learning". arXiv:1703.03864
- Real, E., Aggarwal, A., Huang, Y., Le, Q. V. (2019). "Regularized evolution for image classifier architecture search". AAAI. arXiv:1802.01548
- Jaderberg, M. i in. (2017). "Population based training of neural networks". arXiv:1711.09846
- Goodfellow, I., Bengio, Y., Courville, A. (2016). Deep Learning, MIT Press, rozdz. 11.4 "Selecting hyperparameters" (kontekst strojenia).