Kiedy algorytmy genetyczne są dobrym wyborem do optymalizacji?

20

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:

Antena ST5

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

Gus
źródło
7
+1 dla przykładu, znalazłem oryginalny artykuł: alglobus.net/NASAwork/papers/Space2006Antenna.pdf
Tim

Odpowiedzi:

19

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 i 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.

Lacerbi
źródło
2

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.

manu190466
źródło
Ok, aby głosować negatywnie, ale czy mógłbyś wyjaśnić, gdzie się mylę?
manu190466
5
Ta strona ceni odpowiedzi, które zapewniają kontekst i tło. Zobacz tę stronę pomocy, aby znaleźć odpowiedzi, które dodadzą do naszego repozytorium przydatnych odpowiedzi na interesujące pytania. Wyjaśnienie odpowiedzi jest również dobrym sposobem na sprawdzenie własnego zrozumienia. Na przykład w tym przypadku możesz chcieć rozwinąć kwestię tego, w jaki sposób algorytmy genetyczne „dobrze nadają się do optymalizacji wielokryterialnej”, ponieważ strona Wikipedii wydaje się sugerować funkcje fitness o jednej wartości jako cele algorytmów genetycznych.
EdM,
0

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.

Joseph Yourine
źródło
Głównym założeniem tego argumentu wydaje się być to, że algorytmy genetyczne są optymalizatorami czarnej skrzynki. Ale istnieje wiele optymalizatorów czarnej skrzynki. Dlaczego miałoby to być lepsze niż inne wybory? Ponadto nie sądzę, że tak naprawdę GA mogą łatwo poradzić sobie z ograniczeniami. Na przykład, jeśli funkcja jest niezdefiniowana, z wyjątkiem podprzestrzeni 3D w świecie 4D, z pewnością waniliowa GA zawiodłaby.
Cliff AB,
@CliffAB W rzeczywistości nic o tym nie powiedziałem, a może wręcz przeciwnie. W GA masz dużą kontrolę nad obliczeniami rdzenia, GA sam w sobie jest sekwencją kroków i porządkowania światła. Kiedy definiujesz funkcje kosztów, możesz obsłużyć wszystko w funkcji, nawet zewnętrzne ograniczenia, które możesz zapytać. Moje główne argumenty to: radzenie sobie z wieloma problemami, nie musisz się martwić kompatybilnością z frameworkiem (musisz tylko zwrócić koszty), wymyślić przyzwoite rzeczywiste rozwiązanie w większości przypadków biznesowych NAWET, jeśli nie zawsze najlepsze
Joseph Yourine