Algorytmy genetyczne - wprowadzenie
Algorytm genetyczny (GA) to technika optymalizacji oparta na wyszukiwaniu, oparta na zasadach Genetics and Natural Selection. Jest często używany do znajdowania optymalnych lub prawie optymalnych rozwiązań trudnych problemów, których rozwiązanie w innym przypadku zajęłoby całe życie. Jest często używany do rozwiązywania problemów optymalizacyjnych, w badaniach i uczeniu maszynowym.
Wprowadzenie do optymalizacji
Optymalizacja to proces making something better. W każdym procesie mamy zestaw danych wejściowych i zestaw wyjść, jak pokazano na poniższym rysunku.
Optymalizacja polega na znalezieniu wartości wejść w taki sposób, aby uzyskać „najlepsze” wartości wyjściowe. Definicja „najlepszego” różni się w zależności od problemu, ale w kategoriach matematycznych odnosi się do maksymalizacji lub minimalizacji jednej lub więcej funkcji celu poprzez zmianę parametrów wejściowych.
Zbiór wszystkich możliwych rozwiązań lub wartości, które dane wejściowe mogą zająć przestrzeń poszukiwań. W tej przestrzeni poszukiwań znajduje się punkt lub zbiór punktów, który daje optymalne rozwiązanie. Celem optymalizacji jest znalezienie tego punktu lub zbioru punktów w przestrzeni poszukiwań.
Co to są algorytmy genetyczne?
Natura zawsze była wielkim źródłem inspiracji dla całej ludzkości. Algorytmy genetyczne (GA) to algorytmy oparte na wyszukiwaniu, oparte na pojęciach 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 GA mamy pool or a population of possible solutionsdo zadanego 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, ale 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 funkcje ciągłe i dyskretne, a także 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ż cierpią z powodu kilku 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 osiągnąć optymalnego rozwiązania.
GA - Motywacja
Algorytmy genetyczne są w stanie dostarczyć „wystarczająco dobre” rozwiązanie „wystarczająco szybko”. To sprawia, że algorytmy genetyczne są atrakcyjne 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. Ale w większości rzeczywistych sytuacji mamy bardzo złożony problem zwany krajobrazami, które składają 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 z podróżującym sprzedawcą (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 i dlatego wymagane jest „wystarczająco dobre” rozwiązanie, które jest dostarczane „szybko”.