User Tools

Site Tools


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
beaver [2006/12/02 15:15]
admin
beaver [2007/04/17 12:58] (current)
Line 1: Line 1:
-====== Priprava Busy Beaver v domacom prostredi ====== +[[http://smecnet.itchybit.org/wiki/gnd/beaver|moved here]]
- +
-==== Evolucia ==== +
- +
-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> +
-def genetic_alg(iterat,repro_prob,mut_prob,filename): +
-    t = 0 +
- +
-    # pop je pole pre sucasnu populaciu +
-    pop = [+
- +
-    # fit je pole kde sa drzi fitness kazdeho jedinca +
-    fit = [+
- +
-    # fit_c je pole kde mam kolko jednotiek^2/100 vygeneroval TS +
-    fit_c = [] +
-    stop = False; +
- +
-    # nahodne si vygenerujem 100 TS, pridam do pop, a do fit a fit_c popridavam nuly +
-    for i in range(100): +
-        pop.append(generate_random()) +
-        fit.append(0) +
-        fit_c.append(0) +
-    # samotna evolucia sa zacina tu. konci sa zatial len po dosiahnuti isteho poctu generacii +
-    while (t < iterat): +
-        t+=1 +
- +
-        # g je pole kde davam potomkov generacie pop +
-        q=[] +
-        i=0 +
-         +
-        # gradient je pole v ktorom si pamatam,  +
-        # kolko roznych stupnov fitness mam +
-        gradient=[] +
- +
-        # pre kazdy TS vypocitam je fitness funkciu.  +
-        # Najprv ho simulujem v eval_TS  +
-        # potom vysledok prepocitam a hodim do fit a fit_c +
-        for ts in pop: +
-            fit_c[i] = fitness(eval_TS(ts,5000)) +
-            fit[i] = fit_c[i] +
-            i+=1 +
- +
-        # Penalizaciu som si vymyslel tak  +
-        # aby sa v populacii rovnako vykonnych TS  +
-        # presadili nove, a menej rozsirene formy +
-        #fit = penalize(pop,fit) +
- +
-        # Pozriem na vsetky rozne fitness hodnoty  +
-        # a pridam ich po jednej do gradient +
-        for ts_fit in fit: +
-            if (ts_fit not in gradient): +
-                gradient.append(ts_fit) +
- +
-        # Tu sa zacina reprodukcia +
-        # Bezi to pokial je nova populacia q mensia ako populacia pop +
-        while (len(q) < len(pop)): +
- +
-            # Vyberiem v rulete alebo rulete2 dvoch jedincov z populacie +
-            (ai,bi)= roulette(fit,gradient) +
-            a = pop[ai] +
-            b = pop[bi] +
- +
-            # pokial nahodne cislo je mensie  +
-            # ako pravdepodobnost reprodukcie tak sa idu reprodukovat +
-            # reprodukcia ma svoju (globalnu) pravdepodobnost mutacie +
-            if (random.random() < repro_prob): +
-                (a,b) = reproduce(a,b,mut_prob) +
- +
-            # ci uz reprodukovany alebo povodny, pridam ich do q +
-            q.append(a) +
-            q.append(b) +
- +
-        # zapisem staru generaciu do suboru +
-        write_pop(fit,fit_c,pop,filename,t) +
-     +
-        # vykreslim data +
-        graph_data(fit,fit_c,"e:/evolution.jpg",iterat) +
- +
-        # zakillujem staru generaciu a nahradim novou +
-        pop = q +
-</code> +
- +
-==== Procedury ==== +
- +
-Procedury pouzivane v genetic_alg sa nachadzaju tuNajdolezitejsie su ruleta (vyber jedincov do reprodukcie), fitness funkcia (ohodnotnie jedincov) a reprodukcia. +
- +
-=== Ruleta === +
- +
-<code> +
- +
-# Ruleta 2 +
-def roulette2(fit,grad): +
-    a = random.sample(grad,1)[0] +
-    b = random.sample(grad,1)[0] +
-    a_pool = [] +
-    b_pool = [] +
-    for i in range(len(fit)): +
-        if (fit[i] == a): +
-            a_pool.append(i) +
-        if (fit[i] == b): +
-            b_pool.append(i) +
-    aa = random.sample(a_pool,1)[0] +
-    bb = random.sample(b_pool,1)[0] +
-    return (aa,bb) +
- +
-# Ruleta 1 +
-def roulette(fit,grad): +
-    add = sum(fit) +
-    all = len(fit) +
-    a = random.random()*add +
-    b = random.random()*add +
-    aa = int(random.random()*all) +
-    bb = int(random.random()*all) +
-    line = 0 +
-    first_a = True +
-    first_b = True +
-    for i in range(len(fit)): +
-        line += fit[i] +
-        if ((a < line) & (first_a)): +
-            first_a = False +
-            aa = i +
-        if ((b < line) & (first_b)): +
-            first_b = False +
-            bb = i +
-    return (aa,bb) +
- +
-</code> +
- +
-Mam dve rulety. Ruleta 1 je povodna, ktora vybera jedincov tak ze sa urci nahodne cislo v rozpati od nula po sucet vsetkych fitness hodnot. potom sa ku nule postupne pripocitavaju jednotlive fitness jedincov,a ktory jedinec prvy prekroci nahodne cislo je jedinec ktory sa do reprodukcie vybral. Da sa to predstavit ako interval nasekany na 100 ciastociek, kazda velka ako fitness daneho jedinca, a nahodne cislo padne do nejakej ciastocky, ktorej jedinec bude vybrany. +
- +
-Ruleta2 funguje tak ze sa zoberie gradient fitness hodnot, a z nich sa vyberie jedna fitness hodnota. AH! a teraz ma napadlo preco je ruleta2 tak nedobra. Velkost fitness hodnot pri nahodnom vybere nezohrava rolu ! aaargh.. no super :) +
- +
-Dovod na spravenie rulety2 bol taky ze ked je interval nasekany na 90 malinkych casti a 10 vacsich tak je aj tak najvacsia sanca ze nahodne cislo padne do 90 malinkych casti. teda ze ruleta1 uprednostnovala najpocetnejsich jedincov v populacii. (pricom je ale sranda ze ked sa objavil schopnejsi, tak sa aj tak hned rozmnozil a kompletne nahradil slabsiu populaciu) +
- +
-=== Fitness funkcia === +
- +
-<code> +
- +
-def fitness((count,halt)): +
-    if halt: +
-        return float((float(count*count) float(100))) +
-    else: +
-        return 0 +
- +
-</code> +
- +
-Velmi jednoducha. Eval_TS vracia tuple - teda dve hodnoty - count je pocet jednotiek na paske, a halt je ci sa v danom intervale (v sucasnosti 5000 krokov) zastavil. Ak sa TS nezastavil, dostava nulu, ak sa zastavil, dostava count^2 / 100. Teda TS co napise 9 jednotiek na pasku dostane 0.81 +
- +
-=== Reprodukcia === +
- +
-Sa sklada z reprodukcie (krizenia) a mutacie. +
- +
-== Krizenie == +
- +
-<code> +
- +
-def reproduce(a,b,mut_prob): +
-    state_a = a.split(";"+
-    state_b = b.split(";"+
-    state_a.pop() +
-    state_b.pop() +
-    lenb = len(state_b) +
-    lena = len(state_a) +
- +
-    # krizenie zavysi od toho ktory automat je dlhsi.  +
-    # (bullshit, oba su rovnako dlhe, myslel som ze mozno vzniknu aj kratke automaty) +
-    # urci sa bod a za bodom si automaty vymenia genom +
-    if (lena > lenb): +
-        num = int(random.random()*lenb) +
-        state_aa = state_a[:num+ state_b[num:] +
-        state_bb = state_b[:num] + state_a[num:+
-    else: +
-        num = int(random.random()*lena) +
-        state_aa = state_a[:num] + state_b[num:+
-        state_bb = state_b[:num] + state_a[num:+
-     +
-    # ak nahodne cislo mensie ako pravdepodobnost mutacie,  +
-    # tak este ideme krizenych jedincov zmutovat +
-    if (random.random() < mut_prob): +
-        (state_aa,state_bb) = mutate(state_aa,state_bb) +
-    aa="" +
-    bb="" +
-    for state in state_aa: +
-        aa = aa + state + ";" +
-    for state in state_bb: +
-        bb = bb + state + ";" +
-    return (aa,bb) +
- +
-</code> +
- +
-== Mutacia == +
- +
-<code> +
- +
-def mutate(a,b): +
-    lena = len(a) +
-    lenb = len(b) +
-    rnda = int(lena*random.random()) +
-    rndb = int(lenb*random.random()) +
-     +
-    ### - Less probable but generates a random new state +
-    if (random.random() > 0.90): +
-         +
-        a[rnda] = random.sample(states,1)[0].replace(";"," ") +
-        b[rndb] = random.sample(states,1)[0].replace(";"," ") +
-         +
-    ### - More probable, changes one bit in a state +
-    else: +
-         +
-        # A - mutation +
-        init =  a[rnda].split()[0] +
-        read =  a[rnda].split()[1] +
-        writ =  a[rnda].split()[2] +
-        next =  a[rnda].split()[3] +
-        move =  a[rnda].split()[4] +
-        what = int(random.random()*5) +
-        if (what == 0): +
-            init = random.sample(stavy,1)[0] +
-        if (what == 1): +
-            read = random.sample(abc,1)[0] +
-        if (what == 2): +
-            writ = random.sample(abc,1)[0] +
-        if (what == 3): +
-            next = random.sample(stavy,1)[0] +
-        if (what == 4): +
-            move = random.sample(mov,1)[0] +
-        aa = init + " " + str(read) + " " + str(writ) + " " + next + " " + move +
-        a[rnda] = aa +
-     +
-        # B - mutation +
-        init =  b[rndb].split()[0] +
-        read =  b[rndb].split()[1] +
-        writ =  b[rndb].split()[2] +
-        next =  b[rndb].split()[3] +
-        move =  b[rndb].split()[4] +
-        what = int(random.random()*5) +
-        if (what == 0): +
-            init = random.sample(stavy,1)[0] +
-        if (what == 1): +
-            read = random.sample(abc,1)[0] +
-        if (what == 2): +
-            writ = random.sample(abc,1)[0] +
-        if (what == 3): +
-            next = random.sample(stavy,1)[0] +
-        if (what == 4): +
-            move = random.sample(mov,1)[0] +
-        bb = init + " " + str(read) + " " + str(writ) + " " + next + " " + move +
-        b[rnda] = bb +
- +
-    return (a,b)    +
-  +
-</code> +
- +
-Mutacia ma dva druhy: jeden je viacej pravdepodobny a v zapise TS zmeni jedno pismenko pre kazdeho z dvoch jedincov. Druhy sposob mutacie je menej pravdepodobny - zavysi od pravdepodobnosti "radikalnej mutacie" ;) - a TS nahradi jeden prechod uplne novym a nahodnym. +
- +
-Teda: +
-a = q0 0 1 A R;A 1 1 A L;C 1 1 C L;C 0 1 B R;A 0 1 C R;B 0 1 q0 L;q0 1 0 B N; +
- +
-Po normalnej mutacii sa napr nahradi posledne N za L: +
-a = q0 0 1 A R;A 1 1 A L;C 1 1 C L;C 0 1 B R;A 0 1 C R;B 0 1 q0 L;q0 1 0 B **L**; +
- +
-po radikalnej mutacii sa napr. vygeneruje cely novy predposledny stav: +
-a = q0 0 1 A R;A 1 1 A L;C 1 1 C L;C 0 1 B R;A 0 1 C R;**A 1 1 C R**;q0 1 0 B L; +
- +
-==== Ine ==== +
- +
-=== Penalizacia === +
- +
-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> +
- +
-def penalize(pop,fit): +
-    imagos = [] +
-    pop_perc = float(len(pop))/float(100) +
-    for ts in pop: +
-        if (ts not in imagos): +
-            imagos.append(ts) +
-     +
-    for imago in imagos: +
-        count = 0 +
-        for ts in pop: +
-            if (imago == ts): +
-                count+=1 +
-        penale = float(100 - float(count) / float(pop_perc)) / float(500) + 0.8 +
-        i=0 +
-        for ts in pop: +
-            if (ts == imago): +
-                fit[i] = fit[i] * penale +
-            i+=1 +
-         +
-    return fit +
- +
-</code> +
- +
-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. +
- +
-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).  +
- +
-=== Data === +
- +
-Grafy su trojfarebne:  +
- +
-  * Zelena je spriemerovana fitness funkcia celej populacie, AJ S NULOVYMI fitness. +
-  * Cervena je spriemerovana fitness funkcia celej populacie, BEZ NULOVYCH fitness +
-  * Modra je hodnota penalizovanej spriemerovanej fitness, BEZ NULOVYCH fitness. V pripadoch kde je penalizacia vypnuta, modra prekryva cervenu. +
- +
-Ciary su postupne po desatinach, teda prva je 0.1, druha 0.2, etc.. +
- +
- +
-**Smecnet:**  +
-  * populacia: 100 +
-  * radical mutation: 0.85 +
-  * reproduction: 0.7 +
-  * mutation: 0.6 +
-  * penalize +
-  * roulette1 +
-  * :::: generacia 440 - najvyssi TS: 0.25 +
- +
----- +
- +
- +
-**laptop:** +
- +
-  * populacia: 100 +
-  * radical mutation: 0.9 +
-  * reproduction: 0.6 +
-  * mutation: 0.65 +
-  * penalize +
-  * roulette1  +
-  * //Vysledok:// generacia 300 - najvyssi TS: 0.49 (obrazok ts001.jpg) +
- +
-{{:ts001.jpg|:ts001.jpg}} +
- +
----- +
- +
-**laptop:**  +
-  * populacia: 100 +
-  * radical mut:0.9 +
-  * repro:0.65 +
-  * mut:0.65 +
-  * penalize +
-  * roulette1 +
-  * //Vysledok:// najvyssie TS: 0.49, 500 generacii  +
- +
-{{:ts002.jpg|:ts002.jpg}} +
- +
----- +
- +
-**laptop:**  +
- +
-  * populacia: 100 +
-  * radical mut:0.9 +
-  * repro:0.65 +
-  * mut:0.65 +
-  * NO penalize +
-  * roulette1 +
-  * //Vysledok:// najvyssi TS: 0.49, 500 generacii  +
- +
-{{:ts003.jpg|:ts003.jpg}} +
- +
----- +
- +
- +
-**laptop:**  +
-  * populacia: 100 +
-  * radical mut:0.9 +
-  * repro:0.65 +
-  * mut:0.8 +
-  * NO penalize +
-  * roulette1 +
-  * //Vysledok:// najvyssi TS: 0.49, 500 generacii +
- +
-{{:ts004.jpg|:ts004.jpg}} +
- +
----- +
- +
- +
-**laptop:**  +
-  * populacia: 100 +
-  * radical mut:0.9 +
-  * repro:0.65 +
-  * mut:0.8 +
-  * NO penalize +
-  * roulette1 +
-  * //Vysledok:// najvyssi TS: 1.0, 1500 generacii. 1.0 sa nasiel pocas 370 generacie, zvysnych 1200 generacii sa uz nic neudialo. +
- +
-{{:ts005.jpg|:ts005.jpg}} +
- +
----- +
- +
-**laptop:**  +
-  * populacia: 100 +
-  * radical mut:0.9 +
-  * repro:0.65 +
-  * mut:0.8 +
-  * penalize +
-  * roulette2 OPRAVENA! +
-  * //Vysledok:// najvyssi TS: 1.0, 500 generacii. 1.0 sa nasiel pocas cca 150 generacie, zvysnych 350 generacii sa uz nic neudialo. +
- +
-zda sa ze ruleta2 uz funguje lepsie a dovoluje aj slabsim jedincom prezit, co spolu z penalizaciou ma za nasledok to ze geneticky pool je bohatsi. +
- +
- +
-{{:ts006.jpg|:ts006.jpg}} +
- +
----- +
- +
-**laptop:**  +
-  * populacia: 100 +
-  * radical mut:0.9 +
-  * repro:0.65 +
-  * mut:0.8 +
-  * penalize +
-  * roulette2  +
-  * //Vysledok:// najvyssi TS: 0.81, 500 generacii. +
- +
-podivne je ze 0.64 TS sa objavili a hned vyhynuli .. az na druhy krat sa presadili. +
- +
-Nove vizualizacie. +
- +
-{{:ts007.gif|:ts007.gif}} +
- +
----- +
- +
-**laptop 2.12 01:30**  +
-  * populacia: 100 +
-  * radical mut:0.9 +
-  * repro:0.65 +
-  * mut:0.8 +
-  * penalize +
-  * roulette2  +
-  * //Vysledok:// najvyssi TS: 1.0, 500 generacii. +
- +
-Nova mutacia. Dvojbitova. Rychlejsie dospievam ku komplexnejsim TS. Stale nestaci na preskakovanie medzi roznymi vetvami vyvoja. +
- +
-{{:population_2_12_1-30.jpg|:population_2_12_1-30.jpg}} +
- +
----- +
- +
-**laptop 2.12 02:17**  +
-  * populacia: 100 +
-  * radical mut:0.9 +
-  * repro:0.65 +
-  * mut:0.8 +
-  * penalize +
-  * roulette2  +
-  * //Vysledok:// najvyssi TS: 0.81, 500 generacii. +
- +
-{{:population_2_12_2-17.jpg|:population_2_12_2-17.jpg}} +
- +
----- +
- +
-**laptop 2.12 07:48**  +
-  * populacia: 100 +
-  * radical mut:0.9 +
-  * repro:0.9 +
-  * mut:0.2 +
-  * penalize +
-  * roulette2  +
-  * //Vysledok:// najvyssi TS: 0.81, 500 generacii. +
- +
-{{:evolution_2_12_7-48.jpg|:evolution_2_12_7-48.jpg}} +
- +
-{{:population_2_12_7-48.jpg|:population_2_12_7-48.jpg}} +
- +
-Nizsia uroven mutacie a vyssia reprodukcia - znizili pomer shitnych TS na populacii. mozno treba skusit nechat bezat na 1000 generacii aby sa to niekam dopracovalo.  +
- +
----- +
- +
-**laptop 2.12 10:52**  +
-  * populacia: 100 +
-  * radical mut:0.7 +
-  * repro:0.9 +
-  * mut:0.9 +
-  * penalize +
-  * roulette2  +
-  * //Vysledok:// najvyssi TS: 1.0, 500 generacii. +
-  +
-Vysoka mutacia, nizka reprodukcia, vysoka radikalna mutacia. Shitne TS vyskocili az na 80% populacie. Neda sa povedat ze by sa 1.0 TS objavili nejako velmi skoro, vzapati vyhynuli. +
- +
-{{:population_2_12_10-52.jpg|:population_2_12_10-52.jpg}} +
- +
----- +
- +
-**laptop 2.12 11:42**  +
-  * populacia: 100 +
-  * radical mut: 0.7 +
-  * repro:0.9 +
-  * mut:0.6 +
-  * penalize +
-  * roulette2  +
-  * //Vysledok:// najvyssi TS: 1.0, 500 generacii. +
-  +
-{{:population_2_12_11-42.jpg|:population_2_12_11-42.jpg}} +
- +
----- +
- +
beaver.1165068943.txt.gz · Last modified: 2007/04/17 12:58 (external edit)