Dowód teoretyczno-krzemowy na skuteczność ewolucji
Na początku było źródło. A potem /me skompilował je i zobaczył, że to było dobre. I tak upłynęły wieczór i poranek, dzień pierwszy. Drugiego dnia /me wgrał XOrg i KDE i zobaczył że to było dobre. Tak upłynął wieczór i poranek, dzień drugi.
Fanów Gnome’a, LXDE i innych środowisk/windowmanagerów proszę o bycie cicho i nie sianie zamętu!
Fast Forward.
/me założył sobie: niech będzie dana boska funkcja g(x)=sin(x) g od god
I tak się stało
/me zażyczył sobie: niech powstanie funkcja wielomianowa najbliższa boskiej funkcji!
I tak się stało.
/me stworzył f(x)=costam na swój wzór, znaczy się na wzór boskiej funkcji. Ale po kolei.
Trochę teorii.
Załóżmy sobie, że jest prosta funkcja y=x. Możemy teraz poddać ją ocenie i zobaczyć, że dla małych x jest ona bliska boskiej funkcji, znaczy się ideałowi. Dla niedowiarków, ateistów czy fanów dyskalkulii polecam sprawdzenie tablic trygonometryczynch lub zmuszenie się i przyjęcie tego na wiarę.
Dla małych X sprawa jest jasna, ale gdy X jest większe? Temat się sypie. Może by to jakoś zoptymalizować?
Ustalmy sobie zbiór powiedzmy dziesięciu tysięcy różnych funkcji wielomianowych. No któraś z nich pewnie będzie bliższa sin(x) niż f(x)=x! Dodajmy do tego funkcje kwadratowe i wyższego rzędu! f(x)=ðx2+đx albo chociażby takie f(x) = 0, żeby tematu nie komplikować, będzie lepsze bo dla f(dużo) będzie zero a nie dużo. Sinus będzie najwyżej -1 lub 1 więc odległość od boskości mniejsza. Fachowo mówiąc, wynik tego eksperymentu będzie pijacką realizacją szeregu Maclaurina.
Wróćmy do zbioru „dużo różnych funkcji”. Załóżmy że jesteśmy noga z analizy matematycznej i lenie patentowane – ograniczmy sobie zbiór operacji w funkcjach do mnożenia, dzielenia, dodawania, odejmowania i potęgowania. Argumenty do iksów i liczb rzeczywistych. No i jeszcze nawiasy.
Informatycy mają taki fajny zapis zwany odwrotną notacją polską ale nie chcę tu zanudzać by go tłumaczyć. Załóżmy sobie, że mamy takie działanie: a + b. Te literki po bokach plusa to wyrażenia. Całość też jest wyrażeniem. To znaczy że możemy zrobić tak: (a+b)+c. Całość da się zapisać w postaci drzewa, informatycy przez to przechodzili pewnie pod nazwą teoretyczne podstawy informatyki, pomińmy szczegóły, jeśli kogoś to interesuje, proszę o komć.
Also, mamy te drzewa czy tam funkcje. To nazwijmy sobie te drzewa genotypem. Funkcje osobnikami. Następnie będziemy te osobniki krzyżować i dokonywać na nich mutacji.
Krzyżowanie to wymiana losowo wybranych gałęzi drzewa, mutacja to losowa zmiana w losowym miejscu drzewa. Zastąpienie operacji lub argumentu. Mutować będzie losowo wybrane 5% populacji.
Do krzyżowania wybierzemy sobie losowe grupy po 20 funkcji i w nich będziemy wybierać najlepszą funkcję a następnie ją krzyżować z resztą z tej grupy, albo nawet podwójnie (raz w wyniku będzie lewa strona pierwszej i prawa strona drugiej, kolejnym razem odwrotnie). Dopuśćmy do populacji 20% starych osobników i pozwólmy im się dowolnie krzyżować, a co! Rozmaite religie przymykają oko na kaziorodztwo w niekŧórych przypadkach, my też możemy.
Ostatnie pytanie – skąd wiadomo który osobnik jest lepszy? Zróbmy tak: lepszy jest ten który jest krótszy i ten który jest dokładniejszy. Dokładność to może być całka oznaczona od -1000 do 1000 z fit(x)=abs(egz(x)-sin(x)) a jak nie umiemy całkować, to policzymy sobie pola 2000 trapezów utworzonych przez wysokość tych funkcji. Ja bym tego zaprogramować nie umiał, więc zostańmy przy metodzie trapezowej (tę powinien znać maturzysta na maturze z informatyki, sprawdź arkusz z roku 2006).
I sru! Niech eksperyment leci! To co opisaliśmy wyżej, to wcale nie taki prosty algorytm genetyczny. Taki program który prowadzi ewolucję ukierunkowaną pseudoorganizmu. Niestety nie mam czasu by to zaprogramować ale jeśli ktoś ma ochotę – czemu nie? Efektem powinno być dobre przybliżenie sin(x), zbiegające do zera tam gdzie kończy się miejsce na zwiększanie stopnia wielomianu.
Ale o co w tym chodzi?
Algorytmy genetyczne wykorzystuje się do obliczania rzeczy które ciężko jest policzyć, książkowy przykład to problem komiwojażera (najkrótsza trasa pomiędzy wieloma punktami), mniej sztandarowy to zapisanie obrazu w sieci neuronowej (mapowanie x,y=>r,g,b; nie mogę znaleźć źródła) czy wektoryzacja obrazu (genetyczne programowanie mony lisy). Różne problemy optymalizacyjne, w tym ważenie sieci neuronowych, czy rozpoznawanie obrazów to dobre przykłady na zastosowanie algorytmów gentycznych. Ale nie o tym chciałem ewangelizować.
Nasza ewolucja to przykład ewolucji ukierunkowanej, to znaczy mamy założony cel wedle którego oceniamy egzemplarze. Założyliśmy też bardzo uproszczony model genetyczny. Na prawdę genotyp to dwa drzewa, a nie jedno (w DNA są dwie nitki białek a nie jedna). Na podstawie genotypu tworzony jest fenotyp (czyli to, że mając geny włosów blond i ciemnych będziemy mieć fenotyp włosów ciemnych). Dochodzi jeszcze wpływ środowiska/otoczenia, czyli możemy kupić farbę do włosów. W naturze czynników jest znacznie więcej – zdecydowanie nie do odwzorowania w prostej symulacji komputerowej.
Algorytmy genetyczne dla wytrwałych
Chochoł zegara
AG może być wykorzystany do rozmontowania i obalenia chochołowego argumentu przeciwko ewolucji mówiącego że gdy rozmontujemy zegar i włożymy części do pudełka, to nie wyjdzie zegar.
Mario
Ewentualnie algorytm genetyczny może być zatrudniony do przejścia mario:
Tetris
Albo grania w tetris:
Framsticks
W sieci znalazłem też staruteńki program framsticks pozwalający symulować żyjątka sterowane siecią neuronową. Same żyjątka, jak i sterująca nimi sieć – może ewoluować. Ewolucja może być ukierunkowana na coś (np średnią szybkość zwierzaka) ale też nieukierunkowana (wtedy kryterium jest długość życia i „inteligencja”). Zainteresowanych odsyłam do Framsticks CTF (ppt) czyli prezentacji o zmuszeniu tych żyjątek do grania w „przechwyć flagę” znane z gier komputerowych. 🙂
Wnioski z eksperymentu
Założona przeze mnie symulacja (i inne podlinkowane) pokazała, że „życie” poddawane losowym zmianom może ewoluować by stworzyć „lepszy” organizm, nawet bez „aktu bożej woli”.
Fanom teorii o bożej woli sprawczej polecam rozważenie dlaczego da się za pomocą rzutów kostką policzyć liczbę pi, zwie się to metodą monte carlo. Skoro da się policzyć tak pi, to w dostatecznie długim czasie i odpowiednio dużej liczbie szalek petriego – da się wytworzyć życie. Może być tak że jest gazylion planet na których jest życie. Gazylion planet w zylionie wszechświatów.
Znowu ściana tekstu wyszła, no!