DokuWiki

User Tools

Site Tools

Trace:
beaver

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision 		Previous revision
Next revision Both sides next revision
beaver [2006/12/02 15:15]
admin 		beaver [2006/12/18 01:47]
admin
Line 1: Line 1:
 ====== Priprava Busy Beaver v domacom prostredi ====== ====== Priprava Busy Beaver v domacom prostredi ======
 +
 +=== Logbook ;) ===
 +
 +vsetko fici, az nato ze ked uz evolucia dospeje ku nejakemu rieseniu stale mam pocit ze je to len lokalne maximum - velka uniformita populacie a malo cudzich genov, mozno je to problem hamingovskej bariery, mozno toho ze mutacie TS, ktore su uz na hrane riesenia (napr. 10 alebo 9) ich len nicia a ze vyssie riesenia su umiestnene v priestore moznosti niekde inde. preto som sa rozhodol zmenit ruletu (aby vyberala nie to coho je najviac) ale aby vyberala podla pseudonahodnej funkcie (ako by mala v skutocnosti). takisto som zaviedol penalizaciu ktora tresta prilis rovnake ts a berie im fitness body. nakoniec som pridal mutaciu ktora v istom pripade vygeneruje ts cely novy stav nemiesto zmeny pismena.
 +
 +zmenil som roulette na roulette 2, z nejakeho dovodu sa cela populacia sprava ako totalny hnoj a chaos - aj ked sa objavi prevratne riesenie (napr. 0.64) nepresadi sa a vsetko sa straca v priemere. skusil som to pustit zo starou roulette - je to lepsie ale stali nic moc. urcite ma natom najvacsi vplyv ruleta, mozno aj penalizacia ktora sposobuje ze je potom viacej oblasti kde pada kocka s tym istym vysledkom (napr. 0.64 - 0.6312 0.64 - 0.6228 pre dve rozne 8 jednotkove ts) mutacia sa asi ukazala prilis hrubou nato aby z vyssich ts spravila nejake lepsie riesenia.. ked vygeneruje cely stav nahodne, jasne ze to vo vacsine pripadov cely ts odjebe. 
 +
 +Roulette2 som uz opravil - bola v nej chyba.. skusim vypocty s roulette1 a roulette2 ako sa spravaju.
 +
 +**2.12.2006**
 +
 +Spravil som novu vizualizaciu pre evoluciu, vidiet na nej ake rozne chromozomy sa nachadzaju v populacii a aj ich pomer a ich vyvoj v case. Premyslal som o mutacii, ktora je jednobitova a preto sposobuje to ze z jedneho typu TS rovnakej sily na druhy je tazke prejst, pretoze jednobitova mutacia hociaj spravnym smerom tento TS oslabi a preto sa nebude dalej rozmnozovat. Prepisal som mutacie tak, aby sa diali naraz dve bitove zmeny (bit - rozumej pismenko v stave). Hned tretia evolucia mi strasne rychlo nasla 11 jednotkovy TS !!! Zrusil som ju kvoli akejsi chybe vo vykreslovani, pustil zase a cela populacia stagnuje okolo 10 jednotkoveho TS. Ked som porovnaval rozdiely medzi 0.64 TS z ktorej sa vyvinul 1.21 TS a 0.64 TS z ktorej vzisiel 1.0 (aby bolo jasno - 8 jednotkovy TS ma fitness 0.64, teda x jednotkovy bude mat X^2/100) zistil som ze tie dve rozne 0.64 su fakt uplne rozdielne a ze mutaciami nieje mozne prejst z jednej vetvy evolucie do druhej. Toto sa vola hammingova bariera ?? Fook. Dalsia nepekna vec je, ze akonahle sa uz vyvinu nejake silnejsie TS (0.64 a vyssie), ich chromozomy sa casom uz vobec nemenia! Ved proti tomu som spravil penalizaciu pre rovnake TS v generacii. Aj ked penalizacia ich odlisuje maximalne o stotiny... Dalsi napad je, nechat evoluciu na zaciatku bezat len tak ze do zasoby naskrabe rozlicne TS - napriklad prvych 100 generacii bude kazdych 20 generacii slachtit TS do sily 0.64 (alebo 0.36, alebo 0.25,, neviem) a potom si ich zapamata, a zacne odznovu. Ak zisti ze ide uz vyslapanou cestou zrusi evoluciu a zase zacne. Takto po 100 prvych generaciach bude mat zasobu roznych chodnickov ktorymi sa evolucia moze uberat a tu vaznu evoluciu zacne s co najroznorodejsou, a najsilnejsou populaciou zlozenou z toho co bolo predslachtene. Takto to nebude evolucia len jednej vetvy, ale superenie viacerych vetiev, ktore na seba inaksie kvoli hammingovej bariere nedosiahnu. 
 +Dalsia zaujimava vec je, ze cca 40% populacie zabera shit - teda menejcenne automaty (0.25 a menej). Tie najlepsie su v hornych 15 percentach ;)
 +
 +bezim evolucie na smecnete aj na laptope. na laptope su s grafmi priebehu fitness funkcie (spriemerovanej). 
 +
 +**17.12.2006** 
 +
 +No tymto to asi padne, netusil som ze 5 a 6 stavove su uz take huste na vypocty. heh. Zacal som v pondelok (11.12) s tym ze som len prepisal 4stavovy kod pre 5stavove automaty. Este nejaky tinkering aby to bezalo na servri a aby som videl results (http://smecnet.itchybit.org/evolucia/). Rozdiel vo fitness funkcii - kym pre 4stavove bezala simulacia 5000 krokov a dost, tuna bezi na lubovolny pocet krokov, s tym ze horna hranica napisanych jednotiek je 10000 (som si povedal ze preco si mysliet ze najdeny 4098 TS bol strop ;).. ukazala sa cela plejada TS, co vedela zapisat 4 jednotky a bezat donekonecna , etc etc.. spravil som funkciu co checkuje historiu poctu jednotiek a stavov a ked je poslednych 300 stavov rovnakych asi to bude nejaky loop.. etc.. nechal bezat do piatku.,. potom zase strasne casu zozrali TS ktore idu ako husenica zlava doprava a donekonecna pridavaju po jednotke vzdy na jednej ci druhej strane, tie fakt pokial napisu 10000 jednotiek tak zanikne vesmir. som to zoptimalizoval tak ze ked robim simulaciu, tak strasne vela jednotiek v stave co sa hybe po jednotkach a zapisuje jednotky proste preskocim.. super.. hned vzapati sa ukaze napri. toto: **q0 0 1 A R ;D 1 1 B N ;A 0 0 B L ;C 1 0 B R ;B 0 1 A N ;A 1 0 q0 R ;D 0 0 A R ;B 1 0 C N ;C 0 1 A L ;** co uz sa hore-dole hybe cez cyklus zlozeny z dvoch stavov. Robi to na paske taku striedacku 010101 a strasne pomaly rastie pocet zapisanych jednotiek. No a na nejaky vseobecnejsi algorytmus co by sam rozoznal nejake bazalne formy loopov a preskocil ich som uz cas nemal.. 
 +ved toto necham dobezat, aspon som sa nieco naucil, nasiel som aj 11 jednotkovy 4TS a uz mam aj napad ako evoluciu pouzit na jeden plagat co mam spravit do konca decembra.. hmm kod dole je outdated,, keby niekto chcel poskytnem sucasny stav :)
  
 ==== Evolucia ==== ==== Evolucia ====
Line 5: Line 25:
 Evoluciu robim v pythone, asi je to pomale oproti c-cku ale easy sa v tom kodi. Tu je kod gentickeho algoritmu, doplnil som do neho poznamky. Procedury a funkcie ktore vola su nizsie. Evoluciu robim v pythone, asi je to pomale oproti c-cku ale easy sa v tom kodi. Tu je kod gentickeho algoritmu, doplnil som do neho poznamky. Procedury a funkcie ktore vola su nizsie.
  
-<code>+<code python>
 def genetic_alg(iterat,repro_prob,mut_prob,filename): def genetic_alg(iterat,repro_prob,mut_prob,filename):
     t = 0     t = 0
Line 90: Line 110:
 === Ruleta === === Ruleta ===
  
-<code>+<code python>
  
 # Ruleta 2 # Ruleta 2
Line 138: Line 158:
 === Fitness funkcia === === Fitness funkcia ===
  
-<code>+<code python>
  
 def fitness((count,halt)): def fitness((count,halt)):
Line 156: Line 176:
 == Krizenie == == Krizenie ==
  
-<code>+<code python>
  
 def reproduce(a,b,mut_prob): def reproduce(a,b,mut_prob):
Line 194: Line 214:
 == Mutacia == == Mutacia ==
  
-<code>+<code python>
  
 def mutate(a,b): def mutate(a,b):
Line 272: Line 292:
 Vymyslel som si penalizaciu, ktora pokutuje prilis rozsirenych jedincov a tym padom dava vacsiu sancu mutantom ktory maju tu istu fitness ale je ich menej.  Vymyslel som si penalizaciu, ktora pokutuje prilis rozsirenych jedincov a tym padom dava vacsiu sancu mutantom ktory maju tu istu fitness ale je ich menej. 
  
-<code>+<code python>
  
 def penalize(pop,fit): def penalize(pop,fit):
Line 299: Line 319:
 Penalizacia proste vypocita percentualny podiel jedinca na populacii, obrati ho (100 - podiel) a prenasobi ho tak aby vysledne cislo bolo z intervalu 0.8 az 1. Tym padom sa nemoze stat ze schopnejsi jedinec ma mensiu fitness ako menej schopny.  Penalizacia proste vypocita percentualny podiel jedinca na populacii, obrati ho (100 - podiel) a prenasobi ho tak aby vysledne cislo bolo z intervalu 0.8 az 1. Tym padom sa nemoze stat ze schopnejsi jedinec ma mensiu fitness ako menej schopny. 
  
-==== Vysledky ==== 
  
-=== Logbook ;) === 
  
-vsetko fici, az nato ze ked uz evolucia dospeje ku nejakemu rieseniu stale mam pocit ze je to len lokalne maximum - velka uniformita populacie a malo cudzich genov, mozno je to problem hamingovskej bariery, mozno toho ze mutacie TS, ktore su uz na hrane riesenia (napr. 10 alebo 9) ich len nicia a ze vyssie riesenia su umiestnene v priestore moznosti niekde inde. preto som sa rozhodol zmenit ruletu (aby vyberala nie to coho je najviac) ale aby vyberala podla pseudonahodnej funkcie (ako by mala v skutocnosti). takisto som zaviedol penalizaciu ktora tresta prilis rovnake ts a berie im fitness body. nakoniec som pridal mutaciu ktora v istom pripade vygeneruje ts cely novy stav nemiesto zmeny pismena.+==== Vysledky ====
  
-zmenil som roulette na roulette 2, z nejakeho dovodu sa cela populacia sprava ako totalny hnoj a chaos - aj ked sa objavi prevratne riesenie (napr. 0.64) nepresadi sa a vsetko sa straca v priemere. skusil som to pustit zo starou roulette - je to lepsie ale stali nic moc. urcite ma natom najvacsi vplyv ruleta, mozno aj penalizacia ktora sposobuje ze je potom viacej oblasti kde pada kocka s tym istym vysledkom (napr. 0.64 - 0.6312 0.64 - 0.6228 pre dve rozne 8 jednotkove ts) mutacia sa asi ukazala prilis hrubou nato aby z vyssich ts spravila nejake lepsie riesenia.. ked vygeneruje cely stav nahodne, jasne ze to vo vacsine pripadov cely ts odjebe. +Pre 4 stavove TS som nasiel najlepsi TS taky, ktory zapise 11 jednotiek a skonci: 
  
-Roulette2 som uz opravil - bola v nej chyba.. skusim vypocty s roulette1 a roulette2 ako sa spravaju.+**q0 0 1 A R;A 0 1 C R;B 0 1 A L;C 0 1 B L;B 1 1 B L;q0 1 0 q0 L;C 1 0 q0 R;**
  
-**2.12.2006**+vypocet:
  
-Spravil som novu vizualizaciu pre evoluciu, vidiet na nej ake rozne chromozomy sa nachadzaju v populacii a aj ich pomer a ich vyvoj v case. Premyslal som o mutacii, ktora je jednobitova a preto sposobuje to ze z jedneho typu TS rovnakej sily na druhy je tazke prejst, pretoze jednobitova mutacia hociaj spravnym smerom tento TS oslabi a preto sa nebude dalej rozmnozovat. Prepisal som mutacie tak, aby sa diali naraz dve bitove zmeny (bit - rozumej pismenko v stave). Hned tretia evolucia mi strasne rychlo nasla 11 jednotkovy TS !!! Zrusil som ju kvoli akejsi chybe vo vykreslovani, pustil zase a cela populacia stagnuje okolo 10 jednotkoveho TS. Ked som porovnaval rozdiely medzi 0.64 TS z ktorej sa vyvinul 1.21 TS a 0.64 TS z ktorej vzisiel 1.0 (aby bolo jasno - 8 jednotkovy TS ma fitness 0.64, teda x jednotkovy bude mat X^2/100) zistil som ze tie dve rozne 0.64 su fakt uplne rozdielne a ze mutaciami nieje mozne prejst z jednej vetvy evolucie do druhej. Toto sa vola hammingova bariera ?? Fook. Dalsia nepekna vec je, ze akonahle sa uz vyvinu nejake silnejsie TS (0.64 a vyssie), ich chromozomy sa casom uz vobec nemenia! Ved proti tomu som spravil penalizaciu pre rovnake TS v generacii. Aj ked penalizacia ich odlisuje maximalne o stotiny... Dalsi napad je, nechat evoluciu na zaciatku bezat len tak ze do zasoby naskrabe rozlicne TS - napriklad prvych 100 generacii bude kazdych 20 generacii slachtit TS do sily 0.64 (alebo 0.36, alebo 0.25,, neviem) a potom si ich zapamata, a zacne odznovu. Ak zisti ze ide uz vyslapanou cestou zrusi evoluciu a zase zacne. Takto po 100 prvych generaciach bude mat zasobu roznych chodnickov ktorymi sa evolucia moze uberat a tu vaznu evoluciu zacne s co najroznorodejsou, a najsilnejsou populaciou zlozenou z toho co bolo predslachtene. Takto to nebude evolucia len jednej vetvy, ale superenie viacerych vetiev, ktore na seba inaksie kvoli hammingovej bariere nedosiahnu.  +['1', '1', '1']\\ 
-Dalsia zaujimava vec je, ze cca 40% populacie zabera shit - teda menejcenne automaty (0.25 a menej). Tie najlepsie su v hornych 15 percentach ;) +[0, '1', '1', '1']\\ 
- +[0, '1', '1', '1', '1']\\ 
-bezim evolucie na smecnete aj na laptope. na laptope su s grafmi priebehu fitness funkcie (spriemerovanej). +['1', '0', '1', '1', '1']\\ 
 +['1', '0', '0', '1', '1']\\ 
 +['1', '1', '1', '0', '1']\\ 
 +['1', '1', '1', '0', '0']\\ 
 +['1', '1', '1', '1', '1', '1']\\ 
 +['1', '1', '1', '1', '1', '1']\\ 
 +['1', '1', '1', '1', '1', '1']\\ 
 +['1', '1', '1', '1', '1', '1']\\ 
 +[0, '1', '1', '1', '1', '1', '1']\\ 
 +[0, '1', '1', '1', '1', '1', '1', '1']\\ 
 +['1', '0', '1', '1', '1', '1', '1', '1']\\ 
 +['1', '0', '0', '1', '1', '1', '1', '1']\\ 
 +['1', '1', '1', '0', '1', '1', '1', '1']\\ 
 +['1', '1', '1', '0', '0', '1', '1', '1']\\ 
 +['1', '1', '1', '1', '1', '0', '1', '1']\\ 
 +['1', '1', '1', '1', '1', '0', '0', '1']\\ 
 +['1', '1', '1', '1', '1', '1', '1', '0', 0]\\ 
 +['1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1']\\ 
 +['1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1']\\ 
 +['1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1']\\ 
 +['1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1']\\ 
 +['1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1']\\ 
 +['1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1']\\ 
 +['1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1']\\ 
 +['1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1']\\ 
 +['1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1']\\ 
 +['1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1']\\ 
 + \\ 
 +Pre 5 a 6 stavove som uz nestihol vela.\\
  
 === Data === === Data ===
Line 514: Line 560:
 ---- ----
  
 +**laptop 2.12 12:30** 
 +  * populacia: 100
 +  * radical mut: 0.9 - 1
 +  * 2bit mut: 0.4 - 0.9
 +  * 1bit mut: 0 - 0.4
 +  * repro:0.9
 +  * mut:0.6
 +  * penalize
 +  * roulette2 
 +  * //Vysledok:// najvyssi TS: 0.64, 500 generacii.
 +
 +Nova mutacia - radical mutation vytvori novy stav ale s rovnakym initom, podla nahodneho cisla est aj 2bitova alebo jednobitova mutacia, 2bitova je najpravdepodobnejsia..
 +
 +{{:population_2_12_12-30.jpg|:population_2_12_12-30.jpg}}
 +
 +----
 +
 +**laptop 2.12 12:30** 
 +  * populacia: 100
 +  * radical mut: 0.9 - 1
 +  * 2bit mut: 0.4 - 0.9
 +  * 1bit mut: 0 - 0.4
 +  * repro:0.9
 +  * mut:0.6
 +  * penalize
 +  * roulette2 
 +  * //Vysledok:// najvyssi TS: 0.64, 500 generacii.
 +
 +Nova mutacia - radical mutation vytvori novy stav ale s rovnakym initom, podla nahodneho cisla est aj 2bitova alebo jednobitova mutacia, 2bitova je najpravdepodobnejsia..
 +
 +{{:population_2_12_12-30.jpg|:population_2_12_12-30.jpg}}
 +
 +----
 +
 +**laptop 2.12 12:30** 
 +  * populacia: 100
 +  * radical mut: 0.9 - 1
 +  * 2bit mut: 0.4 - 0.9
 +  * 1bit mut: 0 - 0.4
 +  * repro:0.9
 +  * mut:0.6
 +  * penalize
 +  * roulette2 
 +  * //Vysledok:// najvyssi TS: 0.64, 500 generacii.
 +
 +Nova mutacia - radical mutation vytvori novy stav ale s rovnakym initom, podla nahodneho cisla est aj 2bitova alebo jednobitova mutacia, 2bitova je najpravdepodobnejsia..
 +
 +{{:population_2_12_12-30.jpg|:population_2_12_12-30.jpg}}
 +
 +----
 +
 +**laptop 2.12 13:40** 
 +  * populacia: 100
 +  * radical mut: 0.9 - 1
 +  * 2bit mut: 0.4 - 0.9
 +  * 1bit mut: 0 - 0.4
 +  * repro:0.9
 +  * mut:0.6
 +  * penalize
 +  * roulette2 
 +  * //Vysledok:// najvyssi TS: 1.0, 1500 generacii.
 +
 +stale ten isty problem, akonahle dospeje povedzme po 0.64 uz iba mlati prazdne zito s tym istym genomom. nic nove sa uz neobjavi..
 +
 +{{:population_2_12_13-40.jpg|:population_2_12_13-40.jpg}}
 +
 +----
  
 +dalsie (new) vysledky [[http://smecnet.itchybit.org/evolucia/|tuna]]
beaver.txt · Last modified: 2007/04/17 12:58 (external edit)

Page Tools

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 4.0 International
CC Attribution-Noncommercial-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki