This shows you the differences between two versions of the page.
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. | + | |
- | + | ||
- | < | + | |
- | def genetic_alg(iterat, | + | |
- | 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/ | + | |
- | 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, | + | |
- | 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, | + | |
- | + | ||
- | # 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, | + | |
- | 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, | + | |
- | + | ||
- | # ci uz reprodukovany alebo povodny, pridam ich do q | + | |
- | q.append(a) | + | |
- | q.append(b) | + | |
- | + | ||
- | # zapisem staru generaciu do suboru | + | |
- | write_pop(fit, | + | |
- | + | ||
- | # vykreslim data | + | |
- | graph_data(fit, | + | |
- | + | ||
- | # zakillujem staru generaciu a nahradim novou | + | |
- | pop = q | + | |
- | </code> | + | |
- | + | ||
- | ==== Procedury ==== | + | |
- | + | ||
- | Procedury pouzivane v genetic_alg sa nachadzaju tu. Najdolezitejsie su ruleta (vyber jedincov do reprodukcie), | + | |
- | + | ||
- | === Ruleta === | + | |
- | + | ||
- | < | + | |
- | + | ||
- | # Ruleta 2 | + | |
- | def roulette2(fit, | + | |
- | a = random.sample(grad, | + | |
- | b = random.sample(grad, | + | |
- | 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, | + | |
- | bb = random.sample(b_pool, | + | |
- | return (aa,bb) | + | |
- | + | ||
- | # Ruleta 1 | + | |
- | def roulette(fit, | + | |
- | 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 === | + | |
- | + | ||
- | < | + | |
- | + | ||
- | def fitness((count, | + | |
- | if halt: | + | |
- | return float((float(count*count) | + | |
- | 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 == | + | |
- | + | ||
- | < | + | |
- | + | ||
- | def reproduce(a, | + | |
- | 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[: | + | |
- | state_bb = state_b[: | + | |
- | else: | + | |
- | num = int(random.random()*lena) | + | |
- | state_aa = state_a[: | + | |
- | state_bb = state_b[: | + | |
- | + | ||
- | # ak nahodne cislo mensie ako pravdepodobnost mutacie, | + | |
- | # tak este ideme krizenych jedincov zmutovat | + | |
- | if (random.random() < mut_prob): | + | |
- | (state_aa, | + | |
- | aa="" | + | |
- | bb="" | + | |
- | for state in state_aa: | + | |
- | aa = aa + state + ";" | + | |
- | for state in state_bb: | + | |
- | bb = bb + state + ";" | + | |
- | return (aa,bb) | + | |
- | + | ||
- | </ | + | |
- | + | ||
- | == Mutacia == | + | |
- | + | ||
- | < | + | |
- | + | ||
- | def mutate(a, | + | |
- | 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, | + | |
- | b[rndb] = random.sample(states, | + | |
- | + | ||
- | ### - 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, | + | |
- | if (what == 1): | + | |
- | read = random.sample(abc, | + | |
- | if (what == 2): | + | |
- | writ = random.sample(abc, | + | |
- | if (what == 3): | + | |
- | next = random.sample(stavy, | + | |
- | if (what == 4): | + | |
- | move = random.sample(mov, | + | |
- | 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, | + | |
- | if (what == 1): | + | |
- | read = random.sample(abc, | + | |
- | if (what == 2): | + | |
- | writ = random.sample(abc, | + | |
- | if (what == 3): | + | |
- | next = random.sample(stavy, | + | |
- | if (what == 4): | + | |
- | move = random.sample(mov, | + | |
- | bb = init + " " + str(read) + " " + str(writ) + " " + next + " " + move | + | |
- | b[rnda] = bb | + | |
- | + | ||
- | return (a,b) | + | |
- | + | ||
- | </ | + | |
- | + | ||
- | 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 " | + | |
- | + | ||
- | 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, | + | |
- | + | ||
- | < | + | |
- | + | ||
- | def penalize(pop, | + | |
- | imagos = [] | + | |
- | pop_perc = float(len(pop))/ | + | |
- | 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 | + | |
- | + | ||
- | </ | + | |
- | + | ||
- | 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, | + | |
- | 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: | + | |
- | * mutation: 0.6 | + | |
- | * penalize | + | |
- | * roulette1 | + | |
- | * :::: generacia 440 - najvyssi TS: 0.25 | + | |
- | + | ||
- | ---- | + | |
- | + | ||
- | + | ||
- | **laptop: | + | |
- | + | ||
- | * populacia: 100 | + | |
- | * radical mutation: 0.9 | + | |
- | * reproduction: | + | |
- | * mutation: 0.65 | + | |
- | * penalize | + | |
- | * roulette1 | + | |
- | * // | + | |
- | + | ||
- | {{: | + | |
- | + | ||
- | ---- | + | |
- | + | ||
- | **laptop:** | + | |
- | * populacia: 100 | + | |
- | * radical mut:0.9 | + | |
- | * repro: | + | |
- | * mut:0.65 | + | |
- | * penalize | + | |
- | * roulette1 | + | |
- | * // | + | |
- | + | ||
- | {{: | + | |
- | + | ||
- | ---- | + | |
- | + | ||
- | **laptop:** | + | |
- | + | ||
- | * populacia: 100 | + | |
- | * radical mut:0.9 | + | |
- | * repro: | + | |
- | * mut:0.65 | + | |
- | * NO penalize | + | |
- | * roulette1 | + | |
- | * // | + | |
- | + | ||
- | {{: | + | |
- | + | ||
- | ---- | + | |
- | + | ||
- | + | ||
- | **laptop:** | + | |
- | * populacia: 100 | + | |
- | * radical mut:0.9 | + | |
- | * repro: | + | |
- | * mut:0.8 | + | |
- | * NO penalize | + | |
- | * roulette1 | + | |
- | * // | + | |
- | + | ||
- | {{: | + | |
- | + | ||
- | ---- | + | |
- | + | ||
- | + | ||
- | **laptop:** | + | |
- | * populacia: 100 | + | |
- | * radical mut:0.9 | + | |
- | * repro: | + | |
- | * mut:0.8 | + | |
- | * NO penalize | + | |
- | * roulette1 | + | |
- | * // | + | |
- | + | ||
- | {{: | + | |
- | + | ||
- | ---- | + | |
- | + | ||
- | **laptop:** | + | |
- | * populacia: 100 | + | |
- | * radical mut:0.9 | + | |
- | * repro: | + | |
- | * mut:0.8 | + | |
- | * penalize | + | |
- | * roulette2 OPRAVENA! | + | |
- | * // | + | |
- | + | ||
- | 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. | + | |
- | + | ||
- | + | ||
- | {{: | + | |
- | + | ||
- | ---- | + | |
- | + | ||
- | **laptop:** | + | |
- | * populacia: 100 | + | |
- | * radical mut:0.9 | + | |
- | * repro: | + | |
- | * mut:0.8 | + | |
- | * penalize | + | |
- | * roulette2 | + | |
- | * // | + | |
- | + | ||
- | podivne je ze 0.64 TS sa objavili a hned vyhynuli .. az na druhy krat sa presadili. | + | |
- | + | ||
- | Nove vizualizacie. | + | |
- | + | ||
- | {{: | + | |
- | + | ||
- | ---- | + | |
- | + | ||
- | **laptop 2.12 01:30** | + | |
- | * populacia: 100 | + | |
- | * radical mut:0.9 | + | |
- | * repro: | + | |
- | * mut:0.8 | + | |
- | * penalize | + | |
- | * roulette2 | + | |
- | * // | + | |
- | + | ||
- | Nova mutacia. Dvojbitova. Rychlejsie dospievam ku komplexnejsim TS. Stale nestaci na preskakovanie medzi roznymi vetvami vyvoja. | + | |
- | + | ||
- | {{: | + | |
- | + | ||
- | ---- | + | |
- | + | ||
- | **laptop 2.12 02:17** | + | |
- | * populacia: 100 | + | |
- | * radical mut:0.9 | + | |
- | * repro: | + | |
- | * mut:0.8 | + | |
- | * penalize | + | |
- | * roulette2 | + | |
- | * // | + | |
- | + | ||
- | {{: | + | |
- | + | ||
- | ---- | + | |
- | + | ||
- | **laptop 2.12 07:48** | + | |
- | * populacia: 100 | + | |
- | * radical mut:0.9 | + | |
- | * repro:0.9 | + | |
- | * mut:0.2 | + | |
- | * penalize | + | |
- | * roulette2 | + | |
- | * // | + | |
- | + | ||
- | {{: | + | |
- | + | ||
- | {{: | + | |
- | + | ||
- | 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 | + | |
- | * // | + | |
- | + | ||
- | Vysoka mutacia, nizka reprodukcia, | + | |
- | + | ||
- | {{: | + | |
- | + | ||
- | ---- | + | |
- | + | ||
- | **laptop 2.12 11:42** | + | |
- | * populacia: 100 | + | |
- | * radical mut: 0.7 | + | |
- | * repro:0.9 | + | |
- | * mut:0.6 | + | |
- | * penalize | + | |
- | * roulette2 | + | |
- | * // | + | |
- | + | ||
- | {{: | + | |
- | + | ||
- | ---- | + | |
- | + |