Kiedy algorytmy genetyczne są dobrym wyborem do optymalizacji?

Algorytmy genetyczne są jedną z metod optymalizacji. Często stochastyczne zejście gradientu i jego pochodne są najlepszym wyborem do optymalizacji funkcji, ale algorytmy genetyczne są nadal stosowane. Na przykład antena statku kosmicznego ST5 NASA została stworzona za pomocą algorytmu genetycznego:

Kiedy metody optymalizacji genetycznej są lepszym wyborem niż bardziej popularne metody spadku gradientu?

Algorytmy genetyczne (GA) to rodzina heurystyk, które są empirycznie dobre w zapewnianiu przyzwoitej odpowiedzi w wielu przypadkach, chociaż rzadko są najlepszą opcją dla danej domeny.

Wspominasz o algorytmach pochodnych, ale nawet przy braku pochodnych istnieje wiele algorytmów optymalizacji bez pochodnych, które działają znacznie lepiej niż GA. Zobacz tę i tę odpowiedź, aby uzyskać kilka pomysłów.

Wiele wspólnych standardowych algorytmów optymalizacji (nawet metody bez pochodnych) to założenie, że podstawowa przestrzeń jest gładkim kolektorem (być może z kilkoma dyskretnymi wymiarami), a funkcja optymalizacji jest dość dobrze zachowana.

Jednak nie wszystkie funkcje są zdefiniowane na gładkim kolektorze. Czasami chcesz zoptymalizować na podstawie wykresu lub innych dyskretnych struktur (optymalizacja kombinatoryczna) - tutaj są dedykowane algorytmy, ale GA również by działały.

Im bardziej zbliżasz się do funkcji zdefiniowanych w złożonych, dyskretnych strukturach, tym więcej GA może być użyteczna, szczególnie jeśli możesz znaleźć reprezentację, w której operatorzy genetyczni pracują najlepiej (co wymaga dużo ręcznego dostrajania i wiedzy w dziedzinie).

Oczywiście, przyszłość może doprowadzić do całkowitego zapomnienia GA i opracowania metod mapowania dyskretnych przestrzeni na ciągłą przestrzeń i wykorzystania mechanizmów optymalizacji, które mamy na ciągłej reprezentacji.

Metody genetyczne dobrze nadają się do optymalizacji wielokryterialnej, gdy spadek gradientu jest poświęcony optymalizacji monokryterialnej. Zejście gradientowe pozwala znaleźć minimum funkcji, gdy istnieją pochodne i istnieje tylko jedno optymalne rozwiązanie (jeśli nie liczymy lokalnych minimów). Algorytm genetyczny może być stosowany w problemach wielokryterialnych i prowadzić do ciągłości rozwiązań, z których każda stanowi jednostkę populacji, która ewoluowała od populacji początkowej. Wartości, które należy zoptymalizować, to fenotypy poszczególnych osób i może istnieć kilka fenotypów. Ogólnie rzecz biorąc, żadna z osób nie ma jednocześnie lepszej wartości każdego fenotypu, więc nie ma tylko jednego rozwiązania. Osoby w końcowej populacji, które są wszystkimi rozwiązaniami optymalizacji, są częścią „frontu Pareto” i oznaczone jako „ranga Pareto pierwsza” osoby fizyczne. Oznacza to, że w porównaniu do wszystkich innych osób mających taką samą wydajność dla każdego fenotypu, są one przynajmniej lepsze dla jednego fenotypu niż dla innych.

Najlepszy w jakim sensie?

Z mojego doświadczenia wynika, że ​​GA są jednym z najbardziej pragmatycznych optymalizatorów. Podczas gdy wiele bardziej precyzyjnych algorytmów wymaga czasu i wysiłku, aby sformalizować rzeczywiste problemy w świecie matematycznym, GA mogą obsługiwać każdą funkcję kosztów ze złożonymi regułami i ograniczeniami (GA są powiązane w końcu z podejściem wykonawczym, a nie z konkretnymi obliczeniami). Ten proces jest prosty i można wypróbować wiele metod pracy eksploracyjnej.

Doceniam także możliwość wprowadzenia wcześniejszych rozwiązań algorytmu dla przyszłych przebiegów, co jest dobre dla powtarzanego zadania.

Koncepcyjnie algorytm genetyczny może być reprezentowany przez zestaw funkcji i kolorów, tak więc języki funkcjonalne, takie jak Clojure, który jest także językiem, w którym można bardzo szybko osiągnąć duże wyniki.

Algorytmy genetyczne można również zagnieżdżać: funkcją kosztu jednego GA może być GA! Algorytmy te wykorzystują nowoczesny sprzęt i infrastrukturę, które pozwalają im obliczyć bardzo dużą populację, dzięki czemu - nawet przy prostych operacjach mutacji / selekcji - możesz nadal osiągać dobre wyniki.

Nawet w przypadku prostych problemów, takich jak znalezienie minimum funkcji falowej, GA nie są tak złe i mogą osiągnąć przyzwoitą precyzję w akceptowalnym czasie.

Tak, rozwiązania analityczne mogą mieć szybszy czas wykonania i większą precyzję, ale czas potrzebny do wytworzenia ich przeważa często oczekiwane korzyści! Więc kiedy ? Niemal za każdym razem, przynajmniej w przypadku metaoptymalizacji.