Programowanie genetyczne [zamknięte]

Niedawno przeglądałem Reddit i natrafiłem na post prowadzący do przykładu „algorytmu genetycznego JavaScript”. Naprawdę byłem zafascynowany koncepcjami algorytmów genetycznych i programowania, jednak nawet po pewnym Googlingu wciąż jestem trochę zdezorientowany. Jak to działa?

Podejrzewam, że terminy słownictwa mnie dezorientują bardziej niż cokolwiek innego. Byłbym wdzięczny za krótkie przykłady i być może wyjaśnienia. Po prostu koncepcja programowania genetycznego i jak mogę ją wdrożyć w swoich projektach i dlaczego?

Wygląda na to, że mówisz o algorytmach genetycznych bardziej niż o programowaniu genetycznym, ale oto mój wkład w twoje zrozumienie.

Przydatne może być myślenie o GA w kategoriach części, z których są złożone.

Powiedzmy, że masz jakiś problem. Pierwszą rzeczą, której potrzebujesz, jest sposób wyrażenia, jak będzie wyglądało rozwiązanie. Jeśli miałeś problem z podróżującym sprzedawcą w miastach A, B, C, D, E, to wiesz już, jak mogłoby wyglądać rozwiązanie, tablica nazw miast [B, C, A, D, E].

To jest gen .

W przeciwnym razie znany jako potencjalne rozwiązanie problemu. Jak wspomina Steven A. Lowe, ciągi bitów są powszechnym sposobem kodowania genów, ale nie jest to konieczne; to po prostu ułatwia pewne rzeczy. Ważną częścią jest to, że masz sposób na reprezentację rozwiązania w taki sposób.

Teraz. Skąd wiesz, czy rozwiązanie jest dobre? Potrzebujesz funkcji, która może ci powiedzieć i ocenić rozwiązanie. Zatem ponownie dla TSP możesz mieć funkcję mierzącą odległość przebytą za pomocą ścieżki [B, C, A, D, E]. Przypisywaną „oceną” może być po prostu przebyta odległość, ale w bardziej skomplikowanych problemach można uwzględnić takie rzeczy, jak koszt podróży i inne rzeczy.

To jest funkcja fitness .

Teraz możesz wybrać potencjalne rozwiązanie i dowiedzieć się, czy jest ono dobre. Co dalej?

Następnie musimy rozpocząć naszą pierwszą generację. Generujemy więc kilka losowych rozwiązań. Nie ma znaczenia, czy są dobre, czy nie. To twoja początkowa populacja. Możesz nazwać to swoją pulą genów.

Więc bierzesz początkową pulę genów i stosujesz dla nich wszystkie funkcje fitness i dajesz im ocenę. Teraz musisz wziąć dwa z nich i stworzyć z nich nową populację - dla następnego pokolenia. Kogo wybierasz Cóż, nie musisz wybierać tylko najodpowiedniejszego dopasowania, co może prowadzić do pewnych problemów. Zamiast tego potrzebujesz funkcji wyboru .

Jednym ze sposobów wyboru, który jest łatwy do wizualizacji, jest użycie pewnego rodzaju koła: każdy gen jest wycinkiem na kole, a ich ocena sprawności wskazuje, jak duży jest ich wycinek (im lepsza sprawność, tym większy wycinek). Przyłóż szpilkę do koła i obróć go (tj. Wygeneruj losową liczbę). Szpilka wskazuje pierwszego rodzica. Zrób to ponownie dla drugiego rodzica.

Teraz musisz stworzyć nowe dzieci. Chcesz połączyć rodziców, aby stworzyć nową populację. Można to zrobić na różne sposoby, ale wszystkie nazywane są funkcją crossover . Możesz podzielić je na pół i zamienić połówki między rodzicami lub zrobić coś w rodzaju przeplotu. Jest to bardzo analogiczne do rodzicielskich ssaków rodzących nowe dzieci -> oboje wnoszą swój gen do nowego dziecka.

Kiedy masz już nowe pokolenie, rzucasz losową, ale rzadką mutację każdemu dziecku. Często widziałem częstość mutacji mniejszą niż 1%. Funkcja mutacji losowo zmieni coś w zakodowanym genie. Jeśli twój gen jest nieco ciągiem, może trochę zamienić, jeśli jest to tablica miast, może zamienić 2 miasta na liście. Ważną częścią jest to, że jest to stosunkowo rzadkie zjawisko i miesza wszystko.

Powtarzaj ten proces do pożądanej liczby pokoleń lub do momentu, gdy twoja funkcja fitness zapewni rodzicom niezmiennie wysokie wyniki fitness i uzyskasz rozwiązanie, które (mam nadzieję, że zrobisz wszystko dobrze) jest optymalne.

To było trochę nieporadne, więc podsumuję metaforą:

1. Geny to ludzie: ludzie rozwiązują problemy
2. Funkcje fitness to stopnie: ludzie otrzymują ocenę na podstawie tego, jak dobrze rozwiązali problem
3. Wybierasz 2 osoby do wyhodowania nowej populacji: dajesz osobom z lepszymi ocenami większe szanse na rozmnażanie
4. Kiedy rodzice się rozmnażają, łączą się, aby rodzić dzieci.
5. Rzadko i losowo mutujesz ich dzieci
6. Oceniasz dzieci nowej populacji
7. Wypłukać i powtórzyć

Mam nadzieję że to pomoże.

koduj rozwiązanie problemu jako ciąg bitów

napisz funkcję (zwaną funkcją „fitness”), która ocenia, jak „dobre” zakodowane rozwiązanie otrzymuje ciąg bitów - zwykle wynikiem jest liczba od 0 do 1

losowo wygeneruj kilka tych ciągów bitów i oceń ich kondycję

wybierz kilka z nich - zazwyczaj te bardziej dopasowane - i pokrój je na pół i zamień połówki, aby uzyskać nowe ciągi bitów (crossover)

następnie czasami losowo przerzuć kilka bitów w niektórych nowych ciągach bitów (mutacja)

powtarzaj, aż rozwinie się dobre rozwiązanie

po co to robić: niektóre problemy mają ogromne możliwe przestrzenie rozwiązań, tak duże, że ocena wszystkich możliwości jest niepraktyczna (por. problem Podróżujący sprzedawca)

Bardzo polecam książkę Algorytmy genetyczne w wyszukiwaniu, optymalizacji i uczeniu maszynowym

Programowanie genetyczne pozwala komputerowi pisać programy dla Ciebie!

Nie myśl „programów” jak MS Word, myśl o „programach” w następujący sposób:

function(x){ return x*2; }

Ta funkcja (lub program) sama w sobie nie ma powodu do istnienia. Szukamy rozwiązań problemów. Jeśli chcesz znaleźć sumę dwóch liczb, wystarczy otworzyć kalkulator i wykonać matematykę. Co się stanie, jeśli ktoś poda Ci poniższą tabelę i poprosi o ustalenie związku między resulti xa y:

x   y   result
99  1   (3.02)
79  88   2.01 
21  62   5.01 
84  52  (6.58)
12  70   5.54 
67  18   0.73 

Te dane to Twoje dane „szkoleniowe”. Twój komputer wykorzysta te dane do wygenerowania pewnej hipotezy, a następnie przetestujesz je na rzeczywistych danych.

Załóżmy, że nie znasz statystyk i uważasz, że ten problem jest zbyt trudny do samodzielnego rozwiązania, więc dostaniesz komputer, aby go rozwiązać.

Niech komputer losowo generuje dzikie domysły

Komputer generuje milion odpowiedzi i sprawdza, czy któraś z nich się trzyma (zgadnij ... milion razy!). Oto przykład kilku domysłów:

function(x,y){ return x+y; } // wrong
function(x,y){ return x/1*1*1*1*1*1+y; } //wrong, silly

Możesz to wiedzieć lub nie, ale funkcje lub programy mogą być również reprezentowane jako drzewa, na przykład druga funkcja to:

(+ (/ x (* 1 (* 1 (* 1 (* 1 (* 1 1)))) y)

Możesz sprawić, by wyglądał bardziej jak drzewo, wcinając go w ten sposób (przy okazji, sprawdź odwrotną polską notację i składnię lisp ... ale zrozumiesz, dlaczego wkrótce reprezentujemy takie programy):

(+ 
    (/ x 
        (* 1 
            (* 1 
                (* 1 
                    (* 1 
                        (* 1 1)))) 
    y)

( +znajduje się na górze z dwoma „liśćmi” /i y. /sam ma kilkoro dzieci itp.)

Dlatego tak dużo czytasz o „drzewach” w programowaniu genetycznym. W każdym razie podłączamy wartości xi ydo tej funkcji, co daje nam ZŁĄ odpowiedź. Nic dziwnego, ponieważ losowo to wygenerowaliśmy.

Teraz decydujesz się wygenerować milion takich rozwiązań. Wszystkie są w błędzie. Jednak zauważasz, że niektóre odpowiedzi są bliższe właściwej odpowiedzi niż inne. Innymi słowy, niektóre rozwiązania są bardziej „dopasowane” niż inne. Pamiętaj, że komputer nie wie, co jest „dobre”, a co „złe”, dlatego musisz zapewnić własną funkcję „fitness”. Ta funkcja otrzymuje potencjalne rozwiązanie, dane treningowe i odpowiada za poinformowanie systemu GP o tym, jak „pasuje” to rozwiązanie. Jak możesz sobie wyobrazić, ta funkcja jest uruchamiana miliony razy.

Co wyróżnia GP?

Oto, co odróżnia programowanie genetyczne od zgadywanek. Postanawiasz zrobić kolejną rundę milionów zgadnięć; robisz to jednak trochę inteligentniej. Bierzesz 10% domysłów (tych, które były bliskie faktycznym wartościom) i czynisz je częścią drugiej generacji. Bierzesz także wiele z tych rozwiązań (być może te same 10% ... nie pamiętam) i decydujesz się je „pomieszać”.

Losowo wybierasz dwa rozwiązania, losowo wybierasz poddrzewa i zaczynasz je zamieniać. Tak więc część rozwiązania A kończy się na roztworze B i odwrotnie - właśnie je „skrzyżowałeś”. Ty też bierzesz kilka rozwiązań i po prostu „mutujesz” je ... weź trochę poddrzewa i trochę spieprz je (hej, jeśli rozwiązanie jest okropne, „pieprzenie się z nim bez powodu” może faktycznie go poprawić).

Dobry sposób myślenia o tym jest następujący: twoja mama i tata mają pewne atrybuty - kolor włosów, wzrost, prawdopodobieństwo choroby itp. Ty, jako dziecko, dziedziczysz różne atrybuty od obojga rodziców. Jeśli oboje twoi rodzice byli sportowcami olimpijskimi, będziesz również super sportowcem, prawda? Cóż, biolodzy, socjologowie, a nawet historycy mogą kwestionować ten pomysł, ale informatyków nie interesuje moralność eugeniki. Właśnie zobaczyli „system” wykonujący całkiem dobrą robotę dostarczającą rozwiązania, więc postanowili modelować go w oprogramowaniu.

Jeśli tak naprawdę nie pasuje do biologii, ale nadal zapewnia dobre odpowiedzi ... wielu informatyków wspólnie mówi „cokolwiek, koleś, i dziękuję za terminologię”. Zauważ też, że wszyscy twoi bracia i siostry, a NIE DOKŁADNIE tacy sami ... nawet dzięki tym samym rodzicom. Każda osoba ma geny, które mutują z jakiegokolwiek powodu (proszę, nie pokazuj tego biologowi, chodzi o zrozumienie motywacji leżącej u podstaw dużej terminologii).

Teraz komputer generuje miliony programów i mierzy ich sprawność. Najlepsze rozwiązania przetrwają w kolejnej generacji. „Mutujemy” i krzyżujemy „populację” (zauważ, jak używany jest język genetyki i biologii). Po utworzeniu drugiej generacji sprawność mierzona jest ponownie. Ponieważ to pokolenie ma najlepsze rozwiązania z poprzedniego pokolenia ORAZ przeszliśmy i zmutowaliśmy najlepsze rozwiązania (wraz ze mierną populacją - aby zachować różnorodność), to pokolenie powinno być co najmniej trochę lepsze niż poprzednie pokolenie.

Kontynuujemy to przez bardzo dużą liczbę pokoleń. Każde pokolenie (miejmy nadzieję) zapewnia coraz lepsze rozwiązania, dopóki nie otrzymamy właściwej odpowiedzi. Na przykład:

(+ (- 2.2 (/ x 11) (* 7 (cos y))))

Spójrz na to, to prawda!
(Skopiowałem to z http://en.wikipedia.org/wiki/Genetic_programming , który również ma graficzną reprezentację tego drzewa)

Szanse i zakończenia

Istnieje kilka ważnych kwestii, takich jak to, jak decydujesz, które „terminale” ( +, -, *, /, cos, sin, tan) są dostępne dla twojego systemu GP, jak piszesz funkcję fitness i jak system obsługuje niesensowne programy, takie jak (1 + cos)lub (2 / "hello")(wiele innych).

Rozwijanie równań jest dość nudne. Staje się bardziej interesujący, jeśli twój zestaw terminali wygląda następująco: (ogień, wyczuj wroga, ruszaj się, ...), a twoja funkcja fitness mierzy twoje zdrowie i liczbę martwych ciał martwych potworów.

Większość tego napisałem z pamięci, ale to jest podstawowa idea. Zrobiłem kilka GP na studiach. Zdecydowanie powinieneś się z tym bawić. Nie martw się o zrozumienie całej terminologii, po prostu pobierz kilka darmowych systemów GP, przejrzyj kilka przykładów, aby się zorientować i wymyśl własne ciekawe przykłady (znajdź relacje między różnymi zestawami danych, spróbuj połączyć je z grą API itp.)

Survival of the Fittest: Natural Selection with Windows Forms to sposób, w jaki zapoznałem się z programowaniem genetycznym. To łatwy odczyt z kodem dostępnym do pobrania. Minusem jest to, że GP wymaga środków do wykonania kodu utworzonego w czasie wykonywania, a w momencie pisania artykułu C # nie był dobrze przystosowany do tego zadania. Dlatego w przykładzie użyto CodeDOM do generowania, kompilowania i uruchamiania kodu w czasie wykonywania, co samo w sobie dodaje kolejną warstwę złożoności.

Od tamtej pory wszystko się zmieniło, ponieważ .NET ma teraz własny interfejs API ExpressionTree, co prawdopodobnie pozwoliłoby na bardziej elegancką implementację GP w C # niż ta opisana w tym artykule. Ale to wystarczy, aby zrozumieć, jak działa GP.

Tutaj możesz pobrać darmowy ebook na GP, który zawiera również bardzo krótki przykład kodu Java, który może być również interesujący.

Algorytmy genetyczne i programowanie genetyczne są powiązane, ale różne koncepcje.

Algorytmy genetyczne (GA) to algorytmy wyszukiwania dla złożonych problemów optymalizacji. W GA kodujesz parametry rozwiązania jakiegoś problemu w łańcuchu bitowym „DNA”, a następnie losowo „rozmnażasz” te łańcuchy bitowe: poproś o ich odtworzenie poprzez połączenie ich części i zastosuj „przetrwanie najsilniejszych” poprzez usunięcie wszystkich łańcuchów bitowych masz oprócz tych, które najlepiej rozwiązują Twój problem.

Programowanie genetyczne (GP) jest jeszcze bardziej skomplikowane: tutaj nie reprezentujesz programów według ich DNA (ciągów bitów), ale przez parsowanie drzew, które hodujesz i wybierasz.