Czym dokładnie są algorytmy genetyczne i do jakich problemów są przydatne?

Zauważyłem, że kilka pytań na tej stronie wspomina o algorytmach genetycznych i uświadomiłem sobie, że tak naprawdę niewiele o nich wiem.

Słyszałem już ten termin, ale nigdy nie używałem go, więc nie mam pojęcia o tym, jak działają i do czego są dobrzy. Wiem tylko, że dotyczą one ewolucji i losowo zmieniających się wartości.

Czy możesz podać mi krótkie wyjaśnienie, najlepiej zawierające praktyczny przykład ilustrujący podstawowe zasady?

Algorytmy ewolucyjne to rodzina algorytmów optymalizacyjnych opartych na zasadzie darwinowskiego doboru naturalnego . W ramach doboru naturalnego dane środowisko ma populację osób rywalizujących o przetrwanie i rozmnażanie. Zdolność każdej osoby do osiągnięcia tych celów decyduje o szansie na posiadanie dzieci, innymi słowy, na przekazanie genów następnemu pokoleniu osób, które ze względów genetycznych będą miały zwiększoną szansę na powodzenie, a nawet lepsze, w realizacji tych celów dwa cele.

Tę zasadę ciągłego doskonalenia na przestrzeni pokoleń przyjmują algorytmy ewolucyjne w celu optymalizacji rozwiązań problemu. W początkowym pokoleniu populacja złożona z różnych osobników jest generowana losowo lub innymi metodami. Jednostka jest rozwiązaniem problemu, mniej więcej dobrym: jakość jednostki w odniesieniu do problemu nazywa się kondycją , która odzwierciedla adekwatność rozwiązania problemu do rozwiązania. Im wyższa sprawność osobnika, tym bardziej prawdopodobne jest, że przekaże on część lub całość swojego genotypu osobnikom następnego pokolenia.

Osoba jest kodowana jako genotyp , który może mieć dowolny kształt, taki jak ** bitowy wektor ( algorytmy genetyczne ) lub wektor rzeczywisty (strategie ewolucji). Każdy genotyp przekształca się w fenotyp podczas oceny osobnika, tj. Przy obliczaniu jego sprawności. W niektórych przypadkach fenotyp jest identyczny z genotypem: nazywa się to kodowaniem bezpośrednim . W przeciwnym razie kodowanie nazywa się pośrednim. Załóżmy na przykład, że chcesz zoptymalizować rozmiar prostokątnego prostopadłościanu określonego przez jego długość, wysokość i szerokość. Aby uprościć przykład, załóżmy, że te trzy wielkości są liczbami całkowitymi od 0 do 15. Możemy następnie opisać każdą z nich za pomocą 4-bitowej liczby binarnej. Przykładem potencjalnego rozwiązania może być genotyp 0001 0111 01010. Odpowiednim fenotypem jest równoległościan o długości 1, wysokości 7 i szerokości 10.

Podczas przejścia ze starej do nowej generacji nazywa się operatorów wariacyjnych , których celem jest manipulowanie jednostkami. Istnieją dwa różne typy operatorów odmian:

• z mutacją podmioty , które są stosowane do wprowadzenia zmiany w tej samej osoby jak mutacji genetycznych;
• zwrotnica podmioty , które są stosowane do przejścia co najmniej dwóch różnych genotypów w krzyżówkach genetycznych z hodowli.

Algorytmy ewolucyjne sprawdziły się w różnych dziedzinach, takich jak badania operacyjne, robotyka, biologia, niuans lub kryptografia. Ponadto mogą optymalizować wiele celów jednocześnie i mogą być używane jako czarne skrzynki, ponieważ nie zakładają żadnych właściwości w modelu matematycznym do optymalizacji. Ich jedynym prawdziwym ograniczeniem jest złożoność obliczeniowa.

Algorytm genetyczny to algorytm, który losowo generuje szereg prób rozwiązania problemu. Ten zestaw próbowanych rozwiązań nazywa się „populacją”.

Następnie próbuje sprawdzić, jak dobrze te rozwiązania rozwiązują problem, korzystając z danej funkcji fitness . Próbowane rozwiązania o najlepszej kondycji wartości są wykorzystywane do generowania nowej populacji. Można tego dokonać, wprowadzając niewielkie zmiany w próbowanych rozwiązaniach (mutacja) lub łącząc istniejące próbowane rozwiązania (crossover).

Chodzi o to, że z czasem pojawia się próbowane rozwiązanie, które ma wystarczająco wysoką sprawność wartość aby rozwiązać problem.

Inspiracją do tego była teoria ewolucji; najlepsze rozwiązania przetrwają i rozrodzą się.

Przykład 1

Załóżmy, że szukałeś najbardziej wydajnego sposobu wycięcia wielu kształtów z kawałka drewna. Chcesz zmarnować jak najmniej drewna.

Próbowanymi rozwiązaniami byłyby losowe układanie tych kształtów na kawałku drewna. Sprawność określa się na podstawie tego, ile drewna pozostało po wycięciu kształtów po takim ustawieniu.
Im mniej drewna zostanie, tym lepsze będzie rozwiązanie.

Przykład 2

Załóżmy, że próbujesz znaleźć wielomian przechodzący przez kilka punktów. Twoje próbowane rozwiązania byłyby losowymi wielomianami.
Aby określić przydatność tych wielomianów, określ, jak dobrze pasują one do podanych punktów. (W tym konkretnym przypadku prawdopodobnie użyłbyś metody najmniejszych kwadratów, aby określić, jak dobrze wielomian pasuje do punktów). W trakcie szeregu prób otrzymujesz wielomian, który lepiej pasuje do punktów, dopóki nie uzyskasz wielomianu, który wystarczająco dokładnie pasuje do punktów.

Ta odpowiedź wymaga praktycznego przykładu, w jaki sposób można użyć jednego, który spróbuję podać oprócz innych odpowiedzi. Wydaje się, że dzięki bardzo dobrej pracy wyjaśniają, czym jest algorytm genetyczny. To da przykład.

Załóżmy, że masz sieć neuronową (chociaż nie są to jedyne jej zastosowania), która z niektórych danych wejściowych da pewne wyniki. Algorytm genetyczny może stworzyć ich populację, a sprawdzając, który wynik jest najlepszy, rozmnażaj i zabijaj członków populacji. Ostatecznie powinno to zoptymalizować sieć neuronową, jeśli jest wystarczająco skomplikowana.

Oto demonstracja, którą wykonałem, która pomimo złego kodowania może pomóc ci zrozumieć. http://khrabanas.github.io/projects/evo/evo.html Naciśnij przycisk ewolucji i zadzieraj z celami.

Wykorzystuje prosty algorytm genetyczny do rozmnażania, mutacji i decydowania, która z populacji przeżyje. W zależności od sposobu ustawienia zmiennych wejściowych sieć będzie w stanie zbliżyć się do nich na pewnym poziomie. W ten sposób populacja prawdopodobnie ostatecznie stanie się jednorodną grupą, której wyniki przypominają cele.

Algorytm genetyczny próbuje stworzyć swego rodzaju „sieć neuronową”, która poprzez przyjęcie RGB daje kolor wyjściowy. Najpierw generuje losową populację. Następnie bierze 3 losowych członków z populacji, wybiera tego o najniższej sprawności i usuwa go z populacji. Sprawność jest równa różnicy w kwadracie z górnej bramki + różnicy w dolnej bramce do kwadratu. Następnie rozmnaża pozostałe dwa razem i dodaje dziecko do tego samego miejsca w populacji, co martwy członek. Kiedy nastąpi kojarzenie, istnieje szansa, że ​​nastąpi mutacja. Ta mutacja zmieni losowo jedną z wartości.

Na marginesie, ze względu na to, jak jest skonfigurowany, w wielu przypadkach nie jest całkowicie poprawny, chociaż osiągnie względną bliskość.

Istnieje wiele dobrych odpowiedzi wyjaśniających, czym są algorytmy genetyczne i podających przykładowe aplikacje. Dodam kilka ogólnych wskazówek na temat tego, do czego są dobre, ale także przypadki, w których NIE powinieneś ich używać. Jeśli mój ton wydaje się ostry, to dlatego, że użycie GA w którymkolwiek z przypadków w sekcji Nieodpowiednia spowoduje, że twój artykuł zostanie natychmiast odrzucony z jakiegokolwiek dziennika najwyższego poziomu.

Po pierwsze, twój problem MUSI być problemem optymalizacji. Musisz zdefiniować „funkcję fitness”, którą próbujesz zoptymalizować i musisz mieć sposób na jej zmierzenie.

Dobry:

• Funkcje zwrotnic są łatwe do zdefiniowania i naturalne : w przypadku niektórych rodzajów danych funkcje crossover / mutacji mogą być łatwe do zdefiniowania. Na przykład ciągi (np. DNA lub sekwencje genów) można łatwo zmutować, łącząc dwa kandydujące ciągi, aby uzyskać nowy (dlatego natura używa algorytmów genetycznych!). Drzewa (takie jak drzewa filogenetyczne lub parsowane) można również splicować, zastępując gałąź jednego drzewa gałąź inną. Kształty (takie jak skrzydła samolotu lub kształty łodzi) można łatwo mutować, rysując siatkę na kształcie i łącząc różne sekcje siatki od rodziców, aby uzyskać dziecko. Zwykle oznacza to, że twój problem składa się z różnych części, a połączenie części z różnych rozwiązań jest właściwym rozwiązaniem kandydującym.
  • Oznacza to, że jeśli twój problem jest zdefiniowany w przestrzeni wektorowej, w której współrzędne nie mają żadnego specjalnego znaczenia, GA nie są dobrym wyborem. Jeśli trudno jest sformułować swój problem jako GA, nie warto.
• Ocena czarnej skrzynki : jeśli dla kandydata twoja funkcja fitness jest oceniana poza komputerem, GA są dobrym pomysłem. Na przykład, jeśli testujesz kształt skrzydła w tunelu powietrznym, algorytmy genetyczne pomogą Ci wygenerować dobre kształty kandydatów do wypróbowania.
  • Wyjątek: symulacje . Jeśli funkcja sprawności polega na mierzeniu skuteczności wykonania dyszy i wymaga symulacji dynamiki płynów dla każdego kształtu dyszy, GA mogą działać dobrze. Mogą również działać, jeśli symulujesz system fizyczny w czasie i jesteś zainteresowany wydajnością swojego projektu w trakcie operacji, np. modelowanie wzorców ruchowych . Jednak w literaturze opracowuje się metody wykorzystujące równania różniczkowe cząstkowe jako ograniczenia, np. Optymalizacja ograniczona przez PDE , więc może się to zmienić w przyszłości.

Nieodpowiednie:

• Możesz obliczyć gradient dla swojej funkcji: Jeśli masz dostęp do gradientu swojej funkcji, możesz wykonać spadek gradientu, który jest ogólnie znacznie bardziej wydajny niż GA. Spadek gradientu może mieć problemy z lokalnymi minimami (podobnie jak GA), ale zbadano wiele metod w celu złagodzenia tego.
• Znasz funkcję fitness w formie zamkniętej : prawdopodobnie możesz obliczyć gradient. Wiele języków ma biblioteki obsługujące automatyczne różnicowanie , więc nie musisz nawet robić tego ręcznie. Jeśli twojej funkcji nie można rozróżnić, możesz użyć zejścia subgradient .
• Twój problem optymalizacji ma znaną postać, taką jak program liniowy lub program kwadratowy : GA (i ogólnie metody optymalizacji czarnej skrzynki) są bardzo nieefektywne pod względem liczby kandydatów, których potrzebują do oceny, i najlepiej, jeśli to możliwe, unikać.
• Twoja przestrzeń rozwiązań jest niewielka : jeśli możesz efektywnie utworzyć siatkę swojej przestrzeni wyszukiwania, możesz zagwarantować, że znalazłeś najlepsze rozwiązanie, i możesz utworzyć wykresy konturowe przestrzeni rozwiązania, aby sprawdzić, czy istnieje region, który musisz zbadać dalej.

Wreszcie, jeśli rozważasz GA, rozważ nowszą pracę w Strategiach ewolucyjnych. Jestem stronniczy w stosunku do CMA-ES , który moim zdaniem jest dobrym prostym algorytmem, który przechwytuje pojęcie gradientu w krajobrazie fitness w sposób, w jaki tradycyjne GA nie.

Jak zaobserwowano w innej odpowiedzi, wystarczy zastosować algorytmy genetyczne (GA), aby przedstawić potencjalne rozwiązanie problemu w formie podlegającej krzyżowaniu i mutacji. Idealnie, funkcja fitness zapewni pewnego rodzaju płynną informację zwrotną na temat jakości rozwiązania, zamiast po prostu być „igłą w stogu siana”.

Oto niektóre cechy problemów, które są dobre dla Algorytmów Genetycznych (i ogólnie Metaheurystyki ):

• NP-complete - Liczba możliwych rozwiązań problemu jest wykładnicza, ale sprawdzanie sprawności rozwiązania jest stosunkowo tanie (technicznie z wielomianem czasowym w wielkości wejściowej).
• Czarna skrzynka - GA działają dość dobrze, nawet jeśli nie masz szczególnie świadomego modelu problemu do rozwiązania. Oznacza to, że takie podejścia są również przydatne jako podejście „szybkiego prototypowania” do rozwiązywania problemów.

Jednak pomimo ich powszechnego stosowania do tego celu, uwaga, że gaz faktycznie nie optymalizujące funkcyjnych - mechanizmy GA raczej nie do zbadania „odległych” Regiony przestrzeni poszukiwań w nadziei znalezienia jakiejś odległej wysokiej jakości rozwiązanie, ale raczej do klastra wokół więcej łatwo osiągalne szczyty w „krajobrazie fitness”.

Więcej szczegółów na temat zastosowania GA znajduje się w słynnym wczesnym artykule „Co sprawia, że ​​problem jest trudny dla algorytmu genetycznego?”