Sztuczna sieć neuronowa - algorytm genetyczny

Natura zawsze była wielkim źródłem inspiracji dla całej ludzkości. Algorytmy genetyczne (GA) to algorytmy oparte na wyszukiwaniu, oparte na koncepcjach doboru naturalnego i genetyki. GA są podzbiorem znacznie większej gałęzi obliczeń znanej jakoEvolutionary Computation.

GA zostały opracowane przez Johna Hollanda oraz jego studentów i współpracowników z University of Michigan, w szczególności Davida E. Goldberga, i od tego czasu były testowane z dużym powodzeniem w różnych problemach optymalizacyjnych.

W AH mamy pulę lub populację możliwych rozwiązań danego problemu. Następnie roztwory te ulegają rekombinacji i mutacji (podobnie jak w genetyce naturalnej), rodząc nowe dzieci, a proces ten powtarza się przez różne pokolenia. Każdej osobie (lub proponowanemu rozwiązaniu) przypisywana jest wartość przystosowania (oparta na wartości funkcji celu), a sprawniejsze osobniki mają większą szansę na kojarzenie się i wydanie bardziej „sprawniejszych” osobników. Jest to zgodne z darwinowską teorią „przetrwania najsilniejszych”.

W ten sposób nieustannie „rozwijamy” lepsze jednostki lub rozwiązania przez pokolenia, aż osiągniemy kryterium zatrzymania.

Algorytmy genetyczne mają wystarczająco losowy charakter, jednak działają znacznie lepiej niż losowe wyszukiwanie lokalne (w którym po prostu próbujemy różnych losowych rozwiązań, śledząc najlepsze do tej pory), ponieważ wykorzystują również informacje historyczne.

Zalety GA

GA mają różne zalety, dzięki którym są niezwykle popularne. Należą do nich -

Nie wymaga żadnych informacji pochodnych (które mogą nie być dostępne w przypadku wielu rzeczywistych problemów).
Jest szybszy i wydajniejszy w porównaniu do metod tradycyjnych.
Posiada bardzo dobre możliwości równoległe.
Optymalizuje zarówno funkcje ciągłe i dyskretne, jak i problemy z wieloma celami.
Zawiera listę „dobrych” rozwiązań, a nie tylko pojedyncze rozwiązanie.
Zawsze otrzymuje odpowiedź na problem, która z czasem staje się coraz lepsza.
Przydatne, gdy przestrzeń wyszukiwania jest bardzo duża i występuje duża liczba parametrów.

Ograniczenia GA

Jak każda technika, GA również ma kilka ograniczeń. Należą do nich -

GA nie są dostosowane do wszystkich problemów, zwłaszcza problemów, które są proste i dla których dostępne są informacje pochodne.
Wartość sprawności jest obliczana wielokrotnie, co może być kosztowne obliczeniowo w przypadku niektórych problemów.
Będąc stochastycznym, nie ma gwarancji co do optymalności ani jakości rozwiązania.
Jeśli nie zostanie prawidłowo wdrożony, GA może nie doprowadzić do osiągnięcia optymalnego rozwiązania.

GA - Motywacja

Algorytmy genetyczne są w stanie dostarczyć „wystarczająco dobre” rozwiązanie „wystarczająco szybko”. To sprawia, że Gas jest atrakcyjny do wykorzystania w rozwiązywaniu problemów optymalizacyjnych. Powody, dla których potrzebne są GA, są następujące -

Rozwiązywanie trudnych problemów

W informatyce istnieje wiele problemów, którymi są NP-Hard. W istocie oznacza to, że rozwiązanie tego problemu nawet w przypadku najpotężniejszych systemów komputerowych zajmuje bardzo dużo czasu (nawet lata!). W takim scenariuszu GA okazują się skutecznym narzędziem dostarczaniausable near-optimal solutions w krótkim czasie.

Niepowodzenie metod opartych na gradientach

Tradycyjne metody oparte na rachunku różniczkowym działają na zasadzie startu w losowym punkcie i poruszania się zgodnie z kierunkiem nachylenia, aż osiągniemy szczyt wzgórza. Ta technika jest wydajna i działa bardzo dobrze w przypadku funkcji celu z pojedynczym szczytem, takich jak funkcja kosztu w regresji liniowej. Jednak w większości rzeczywistych sytuacji mamy bardzo złożony problem zwany krajobrazami, składający się z wielu szczytów i wielu dolin, co powoduje, że takie metody zawodzą, ponieważ cierpią z powodu nieodłącznej tendencji do utknięcia w lokalnych optymach, jak pokazano na poniższym rysunku.

Szybkie uzyskanie dobrego rozwiązania

Niektóre trudne problemy, takie jak problem komiwojażera (TSP), mają zastosowania w świecie rzeczywistym, takie jak wyszukiwanie ścieżek i projektowanie VLSI. Teraz wyobraź sobie, że korzystasz z systemu nawigacji GPS i obliczenie „optymalnej” ścieżki od źródła do celu zajmuje kilka minut (lub nawet kilka godzin). Opóźnienia w takich rzeczywistych zastosowaniach są nie do przyjęcia, dlatego wymagane jest „wystarczająco dobre” rozwiązanie, które jest dostarczane „szybko”.

Jak używać Google Analytics do rozwiązywania problemów z optymalizacją?

Wiemy już, że optymalizacja to działanie mające na celu uczynienie czegoś takiego jak projekt, sytuacja, zasoby i system tak efektywnymi, jak to tylko możliwe. Proces optymalizacji przedstawia poniższy diagram.

Etapy mechanizmu GA dla procesu optymalizacji

Poniżej przedstawiono etapy mechanizmu GA używanego do optymalizacji problemów.

Generuj losowo początkową populację.
Wybierz początkowe rozwiązanie z najlepszymi wartościami sprawności.
Ponownie połącz wybrane rozwiązania za pomocą operatorów mutacji i krzyżowania.
Wstaw potomstwo do populacji.
Teraz, jeśli warunek zatrzymania jest spełniony, zwróć rozwiązanie z najlepszą wartością dopasowania. W przeciwnym razie przejdź do kroku 2.