Galerija

Slepi Sajdžija i programeri

Kad krenete Internetom znate odakle ste krenuli, a ne znate kuda ćete stići ako se prepustite njegovim strujama. Sve je počelo za večerom sa prijateljima, pre neko veče, razgovarali smo, između ostalog, o visoko tehnološkim karakteristikama paukove mreže koju ni najsposobniji inženjeri današnjice nisu u stanju ni da shvate ni da naprave. Pa se tu onda postavila ona poznata teza, kako je priroda savršena, da sve što je prirodno je najbolje itd… Da, možda, ali sam nekoliko dana kasnije hteo da se pozabavim tom temom i da vidim gde je kvaka. I ne znam zašto, ali me je zanimalo šta o tome misli poznati evolucioni biolog Ričard Dokins (Richard Dawkins), jer sam negde iz svoje polu-tame, polu-svesti iskopao polu-sećanje, da je Dokins pisao već o tome. I, na moje ne tako veliko iznenađenje, ispostavilo se da je tako. U svojoj knjizi „Penjanje uz planinu neverovatnoće“ (Climbing Mount Improbable), govorio je o tome, ali tu se već radilo o kompleksnijim teorijama. Onda sam malo prošvrćkao po Internetu i naleteo na jednostavnije misaone eksperimente „Teorema o beskonačnom majmunu“ (infinite monkey theorem) i „Izgleda mi da to liči na lasicu“. (Methinks it is like a weasel) i koje obrađuje u svojoj knjizi „Slepi sajdžija“ (The blind watchmaker).

Evolucioni biolog i po malo informatičar, Ričard Dokins

Evolucioni biolog i po malo informatičar, Ričard Dokins

Dokins je naravno jedan od poznatijih i istaknutijih istraživača i učvršćivača teorije o evoluciji koja je počela sa Darvinom (o kome sam već pisao), a danas nalazi sve veći broj dokaza o tome da je sav živi svet posledica sabiranja malih slučajnih genetskih mutacija i potpuno namerne i veoma rigidne prirodne selekcije koja održava u životu samo one jedinke koje se najbolje prilagođavaju trenutnim prirodnim okolnostima. Ali, ono što je povod ovom tekstu je da je Dokins ne samo biolog, već i programer, dakle kolega. I, Dokins je i lično napisao pre više od dvadeset godina jedan program po genetičkom algoritmu. Na dnu Vikipedijine stranice naišao sam na pregršt već napisanih reimplementacija originalnog algoritma u najrazličitijim programskim jezicima, no, kako je algoritam bio zaista trivijalan, odlučio sam da i sam napišem jednu njegovu varijantu, ovog puta u programskom jeziku „Wolframa Mathematica“.  Moglo je i u bilo čemu drugome C++, JavaScript, pa čak i Kobol, potpuno je svejedno. Wolfram mi se našao pod rukom. Pa, evo šta stoji iza svega toga.

Sve ovo je u svrhu misaone borbe između kreacionista i evolucionista. Dokins se mišlju poigrao sa kreacionistima kada nas je podsetio na priču o hipotetičkom majmunu kome bi dali pisaću mašinu i teoretisalo se o tome, koliko bi njemu bilo potrebno vremena da napiše sva Šekspirova dela. Da je Dokins Balkanac, eksperiment bi bio o tome koliko bi svinji trebalo da napiše „Gorski Vijenac“. I jedno i drugo teorijski nije nemoguće, kako i jedno i drugo, ako bi im se dalo dovoljno vremena mogli bi pukim lupanjem po tasterima, za trilijardi triliona trilenijuma (mada je broj zaista mnogo veći od toga) da slučajno ubodu pravi sadržaj knjige. No, to vreme, iako moguće, je daleko duže od svog trajanja cele Vaseljene od postanka do danas, čak iako bi životinje kucale milione slova po minutu. Dakle, kreacionisti su u pravu, koristeći analogiju, i čovek nije mogao slučajno nastati? Naravno da nisu, zato što je samo deo evolucione teorije baziran na slučajnosti, a to je mutacija. Ali drugi deo, je apsolutno nameran, radi se o ostavljanju u životu samo onih koji su mutarli na pravi način. U tome nema ni malo slučajnosti, već samo nemilosrdne sigurnosti.

Evo jednog genetskog algoritma čiji cilj je da stvori neku željenu, zadatu, rečenicu počevši od neke potpune nesuvisle, koja čak nema nikakvo značenje ni u jednom jeziku, jednostavano sačinjena je od slučajno izabranih slova poređanim jedno iza drugog. Na primer početna rečenica je:

„ETCU DYDEJPTSWBJG NFDNYOZTVUYPXPTFHW IFLSIRFOUTQP XWRKZFYERJXVLXDMTROS  YRC“,
a kranja zadata rečenica je:
„EVOLUCIJA JE ZBIR SLUCAJNIH GENETSKIH MUTACIJA I RIGIDNE PRIRODNE SELEKCIJE“
jedino što ove dve rečenice na početku imaju zajedničko je broj slova: 75. Pravila algoritma su sledeća:

1.) Počni sa slučajnom rečenicom od 75 slova
2.) Neka se „rodi“ 100 potomaka, iz početne rečenice sa šansom od 3% po slovu da se ono promeni nekim drugim slučajnim slovom u procesu nasleđivanja
3.) Uporedi svakog novorođenog potomka sa željenom rečenicom, i izračunaj njen nivo sličnosti (broj slova koja su na istoj pozicija jednaka originalu)
4.) Ako je bilo koji od potomaka jednak originalu, zaustavi proces, evolucija je proizvela traženi rezultat
5.) U obrnutom slučaju, izaberi potomka sa najvećim nivoom sličnosti, odbaci ostale i neka on bude novi roditelj novim potomcima i ponovo se vrati na korak 2.)

Dakle, algoritam je banalan u svom mehanizmu, ali je maestralan u svom dubljem smislu. Naravno da u prirodi ne postoji neka zadata rečenica, neki krajnji cilj do koga se mora doći (ili barem nije poznato da postoji takav cilj), ali se to može jednostavnije zamisliti kao neka vrsta, neka rečenica koji postoji nakon neke druge, neka vrsta koja odgovara nekim prirodnim uslovima. Setimo, se, ne preživljaju uvek ni najjači, ni najpametniji, ni najpokvareniji, ni najduhovitiji, već oni koji su podobniji trenutnom stanju prirode, a priroda se u zadnjih 4.5 milijardi godina, barem na našoj planeti promenila toliko puno, da jednostavno život koji je tada postojao, danas bi imao malo ili nimalo šanse da preživi ili obrnuto. Štaviše, 99.99% svih živih vrsta koje su ikada postojale su sve izumrle. Ono što je bitno u ovoj simulaciji je to da postoji neki objektivni kriterijum. Umesto rečenice sa smislom koju sam naveo, traženi rezultat bi mogla biti bilo koja druga rečenica bez smisla za nas na našem jeziku u 21. veku. Opet bi isti mehanizam savršeno tačno pre ili kasnije stvorio zadatu rečenicu. Zato što je zadata rečenica samo kriterijum merenja rezultata procesa, bilo šta može biti izabrano kao izlazni kriterijum. Kao što od čoveka može ponovo nastati bakterija ili obrnuto. No, najlepši deo ovog fenomena su 3 sledeća aspekta:

1.) Algoritam (proces) je u stanju da stvori bilo šta od bilo kog početnog stanja
2.) Za to mu nije potrebno preterano puno iteracija, dakle, mnogo više od jedne generacije, ali daleko manje od vremena od Big Benga do danas.
3.) Stvaranje smila od besmisla, složenosti od jednostavnosti može da ne zahteva višu inteligenciju, ako ikakvog dizajna i ima, to je samo u ovom procesu. Čovek jeste primer koji uspeva da transformiše dalje prirodu namernim dizajnom, ali to nije jedini mehanizam promene

Ovaj algoritam nije formalni dokaz evolucije, već dobra simulacija dokaza koji već postoje, a zasnovani su na mnogim elementima koje ćete bolje pročitati u Dokinsovim knjigama.

Evo par rezultata: Za 100 potomaka po generaciji, i verovatnoći mutacije od 3% po slovu, potrebno je 310 generacija, i evo koraka, kako se do toga došlo (radi sažetosti samo potomak svake 10 generacije je izlistan):

000, ETCU DYDEJPTSWBJG NFDNYOZTVUYPXPTFHW IFLSIRFOUTQP XWRKZFYERJXVLXDMTROS YRC
010, EJHJ LYJG PTSZBJG SFRNYXNTD LPXPTFHW IFFSIWFOUAQP IGIKZEYPRJQVLXEMOR SR YRC
020, EJLLTLIJA JTBZBJJ SFRNYXNTD LPNKTSHW IFPSIWFOVAQVXIGIKGE PRJQVMYERSR ER IJC
030, EJOLTCIJA JUBZBIJ STRNAXNTD LENKTSAW IKUSACVOVAQVVIGIKPE PRSQVMSERSRLER IJC
040, EIOLTCIJA JUBZBIJ SWUNAONID NENKTSAWEIKUEACVJAATVRIGIDZE PRSQOLSEISRLERCIJC
050, EVOL CIVA JSBZBIR SWUNAONIL GENJTSAKW MUEACVJAATVRIGIDNE PRSROLSEISRLERCIJE
060, EVOLUCIVA JS ZBIR SWUNAONIL GENJTSJZW MUEACVJAAI RIGIDNE PRSRONSEJSRLERCIJE
070, EVOLUCIVA JE ZBIR SWUCAJNIL GENJTSHZW MUMACVJAWI RIGIDNE PRSRODOEJSRLERCIJE
080, EVOLOCIVA JE ZBIR SWUCAJNIL GENXTSHIW MUMACVJA I RIGIDNE PRSRODOEJSRLERCIJE
090, EVOLOCILAHJE ZBIR SHUCAJNIG GENETSHIH MUTACVJA I RIGIDNE PRIRODOE SGLEBCIJE
100, EVOLOCILAHJE ZBIR SHUCAJNIG GENETSKIH MUTACVJA I RIGIDNE PRIRODOE SGLEBCIJE
110, EVOLKCILAHJE ZBIR SHUCAJNIB GENETSKIH MUTACVJA I RIGIDNE PRIRODIE SGLEMCIJE
120, EVOLKCIJAZJE ZBIR SHUCAJNIB GENETSKIH MUTACRJA I RIGIDNE PRIRODDE SULEFCIJE
130, EVOLKCIJANJE ZBIR SHUCAJNIB GENETSKIH MUTACNJA I RIGIDNE PRIRODEE SULEFCIJE
140, EVOLKCIJANJE ZBIR SUUCAJNIB GENETSKIH MUTACNJA I RIGIDNE PRIRODEE SULEPCIJE
150, EVOLKCIJANJE ZBIR SUUCAJNIN GENETSKIH MUTACIJA I RIGIDNE PRIRODEE SULEKCIJE
160, EVOLDCIJALJE ZBIR SUUCAJNIN GENETSKIH MUTACIJA I RIGIDNE PRIRODNE SULEKCIJE
170, EVOLDCIJALJE ZBIR SUUCAJNIH GENETSKIH MUTACIJA I RIGIDNE PRIRODNE SULEKCIJE
180, EVOLRCIJALJE ZBIR SMUCAJNIH GENETSKIH MUTACIJA I RIGIDNE PRIRODNE SELEKCIJE
190, EVOLTCIJA BE ZBIR SUUCAJNIH GENETSKIH MUTACIJA I RIGIDNE PRIRODNE SELEKCIJE
200, EVOLUCIJA BE ZBIR SUUCAJNIH GENETSKGH MUTACIJA I RIGIDNE PRIRODNE SELEKCIJE
210, EVOLUCIJA VE ZBIR SUUCAJNIH GENETSKGH MUTACIJA I RIGIDNE PRIRODNE SELEKCIJE
220, EVOLUCIJA VE ZBIR SKUCAJNIH GENETSKIH MUTACIJA I RIGIDNE PRIRODNE SELEKCIJE
230, EVOLUCIJA VE ZBIR SKUCAJNIH GENETSKIH MUTACIJA I RIGIDNE PRIRODNE SELEKCIJE
240, EVOLUCIJA E ZBIR SRUCAJNIH GENETSKIH MUTACIJA I RIGIDNE PRIRODNE SELEKCIJE
250, EVOLUCIJA E ZBIR SOUCAJNIH GENETSKIH MUTACIJA I RIGIDNE PRIRODNE SELEKCIJE
260, EVOLUCIJA E ZBIR STUCAJNIH GENETSKIH MUTACIJA I RIGIDNE PRIRODNE SELEKCIJE
270, EVOLUCIJA E ZBIR STUCAJNIH GENETSKIH MUTACIJA I RIGIDNE PRIRODNE SELEKCIJE
280, EVOLUCIJA E ZBIR STUCAJNIH GENETSKIH MUTACIJA I RIGIDNE PRIRODNE SELEKCIJE
290, EVOLUCIJA E ZBIR STUCAJNIH GENETSKIH MUTACIJA I RIGIDNE PRIRODNE SELEKCIJE
300, EVOLUCIJA E ZBIR STUCAJNIH GENETSKIH MUTACIJA I RIGIDNE PRIRODNE SELEKCIJE
310, EVOLUCIJA JE ZBIR SLUCAJNIH GENETSKIH MUTACIJA I RIGIDNE PRIRODNE SELEKCIJE

Iz ovog primera se ne vidi dobro, jer je prekratak, ali iz eksperimenata sam video da postoje i degeneracijske evolucije. Recimo reč ZBIR, se u nekoj nekonačnoj generaciji može već pojaviti, da zatim nestane, pa da se ponovo pojavi, čak više nego jednom, što je više generacija, to je broj oscilacijskih progresa/regresa veći. Algoritam ne garantuje stabilnost bilo kog dela rečenice sve do kraja. Dakle, algoritam je krajnje rudimentalan, ali upravo zato je autentičniji kao simulacija prirode.

Ako, krenete da menjate parametere, recimo, smanjite broj potamaka na 10, broj generacija naglo skače. Ako povećate broj potomaka, broj potrebnih generacija se smanjuje. Eto, jedne analogije sa prirodom, zašto tako obiluje velikim brojem vrsta koje imaju tako puno potomaka.

Ili ako krenete da menjate verovatnoću mutacije. Za vrednosti u opsegu od 1% do 4%, broj generacija se smanjuje, no samo ako dignete na 5%, sistem postaje daleko nestabilniji, desetine hiljada generacija su potrebne. Ako se digne na 10% ili 20% i trilioni generacija bi bili potrebni, ali bi se opet moglo stići do zadatog cilja. Ali, ako krenete da smanjujete previše verovatnoću, recimo pređete na promile, opet su potrebne mnogobrojne generacije, zato što je sistem premalo promenljiv. Dakle, samo prava kombinacija broja potomaka i verovatnoća mutacije omogućuje mali broj generacija.

Naravno, siguran sam, tu opet uskaču, neo-kreacionisti, koji iznose svoje nove teorije o pametnom dizajnu gde, priznaju da je evolucija postojeći mehanizam, ali je neki „Viši Autor“, neko „Jako pametan izvan sistema“, dobro podesio početne parametre. Kao i obično, smela izjava koja traži jake dokaze. Šta je to viši autor, šta to znači iznad sistema, i tako dalje? Ali šta ćemo, valjda će uvek postojati ljudi, kojima čak iako nacrtate, crno slovo na belom papiru, postavljaće pitanje šta je to papir, ili da je relativno šta je to crno. Bilo šta se može pretpostaviti, ali samo mali deo toga donosi neki napredak u našem poimanju sveta u kome živimo. Želim vam dobru zabavu u ekperimentisanju sa ovim algoritmom, barem onoliko koliko je to meni bilo. A ja sam zaista uživao.

Evo i listina u programskom jeziku Wolfram Mathematica (oprostite što su promenljive napisane na Engleskom jeziku, ali radi se o profesionalnoj deformaciji):

NatureSentence = „EVOLUCIJA JE ZBIR SLUCAJNIH GENETSKIH MUTACIJA I RIGIDNE PRIRODNE SELEKCIJE“
ElligbleLetters = Join[{32}, Table[x, {x, 65, 65 + 25}]];
RandomLetter[] := ElligbleLetters [[IntegerPart[Random[]*27 + 1]]]
StartSentence =
FromCharacterCode[
Table[RandomLetter[], {x, 1, StringLength[NatureSentence]}]]
MutationProbability = 3/100
NumberOfDesendants = 100

CreateDescendant[sentence_] :=
StringJoin[
Table[If[Random[] < MutationProbability,
FromCharacterCode[RandomLetter[]],
StringTake[sentence, {x, x}]], {x, 1, StringLength[sentence]}] ]

CalculateFitness[candidate_, target_] :=
Block[{i, equals = 0},
For[i = 1, i <= StringLength[candidate], i++,
If[StringTake[candidate, {i, i}] == StringTake[target, {i, i}],
equals++]]; equals]

CreateGeneration[sentence_] :=
Block[{i, WinnerFitness = 0, CandidateFitness,
WinnerSentence = „nobody“, CandidateSentence},
For[i = 1, i <= NumberOfDesendants, i++,
CandidateSentence = CreateDescendant[sentence];
CandidateFitness =
CalculateFitness[CandidateSentence, NatureSentence];
If[CandidateFitness > WinnerFitness,
WinnerFitness = CandidateFitness;
WinnerSentence = CandidateSentence]]; WinnerSentence]

Block[{sentence = StartSentence,
LastGenerationWinnerSentence = StartSentence,
NumberOfGenerations = 0},
While[sentence != NatureSentence,
If[Mod[NumberOfGenerations, 10] == 0,
Print[NumberOfGenerations, „, „, LastGenerationWinnerSentence]];
LastGenerationWinnerSentence = CreateGeneration[sentence];
NumberOfGenerations++;
sentence = LastGenerationWinnerSentence;
]; {NumberOfGenerations, LastGenerationWinnerSentence}]

Ako želite da odslušate, prilog počinje na 44 min 50 sek

Ja pišem vama, a vi meni recite šta mislite. Voleo bih da saznam o…

Advertisements
od Markus Maki Objavljeno u nauka

One comment on “Slepi Sajdžija i programeri

  1. Povratni ping: Dozvolite mi da se predstavim, ja sam između ostalog čovek | Markus Maki

Zatvoreno za komentare.