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.)