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?
Odpowiedzi:
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:
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:
Nieodpowiednie:
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 ):
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?”