This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
cogsci:ui [2009/06/21 21:28] kik |
cogsci:ui [2009/06/23 23:02] (current) |
||
---|---|---|---|
Line 298: | Line 298: | ||
vyhodnocovacia funkcia f(u) = g(u) + h(u) | vyhodnocovacia funkcia f(u) = g(u) + h(u) | ||
+ | |||
g(u) - cena cesty | g(u) - cena cesty | ||
+ | |||
h(u) - odhad vzdialenosti k cielu | h(u) - odhad vzdialenosti k cielu | ||
Line 1397: | Line 1399: | ||
Typy evolučných algoritmov | Typy evolučných algoritmov | ||
- | * Genetické algoritmy | + | * Genetické algoritmy |
- | * Genetické programovanie | + | * Genetické programovanie |
- | * Evolučné programovanie | + | * Evolučné programovanie |
- | * Evolučné stratégie | + | * Evolučné stratégie |
=== Genetické algoritmy === | === Genetické algoritmy === | ||
- | najpopulárnejší typ EA, využívaný pri riešení problémov a optimalizácií | + | Najpopulárnejší typ EA, využívaný pri riešení problémov a optimalizácií. V skratke a kusok vulgarne ide o to, ze mame nejaku populaciu rieseni, a robime umelu evoluciu na rieseniach s cielom najst lepsie riesenia. Riesenia je mozne chapat aj ako stavy/body vo fazovom priestore. Stav/ |
- | každý stav sa označuje pojmom chromozóm, je reprezentovaný binárnym reťazcom x dĺžky N | + | Nejakym sposobom si teda zvolime dlzku n chromozomu, vacsinou |
- | pracujeme | + | |
- | každému chromozómu x ktorý patrí do P sa priraďuje funkcia | + | |
- | podstatou genetického algoritmu je nájsť globálne maximum fitness | + | |
- | riešenie problému prebieha pomocou simulovanej evolúcie | + | * Zvolime si nejaku velkost populacie P (povedzme 100) |
- | čas t je diskrétna premenná označujúca epochu, alebo generáciu | + | * Nahodne inicializujeme populaciu |
- | P< | + | * Spustime algoritmus |
- | === Postup reprodukcie: === | + | Algoritmus: |
- | == Selekcia == | + | |
- | do procesu reprodukcie vstupujú dvojice chromozómov x, x' patriace do P | + | |
- | existuje viacero selekčných metód pre výber populácie určenej na reprodukciu | + | |
- | * náhodne | + | |
- | * v závislosti od úspešnosti, | + | |
- | == Kríženie | + | **1.** Ohodnot pomocou fitness funkcie populaciu P\\ |
- | proces, pri ktorom si vybraté chromozómy vymieňajú | + | **2.** Z populacie P vyber pomocou nejakej metody selekcie jedincov ktori sa budu rozmnozovat\\ |
- | skrížením dostaneme dva nové chromozómy. | + | **3.** Rozmnoz jedincov pomocou krizenia a mutacie\\ |
+ | **4.** Novych jedincov pridaj do populacie P\\ | ||
+ | **5.** Ak hotovo tak hotovo, ak nie tak chod na 1.\\ | ||
+ | |||
+ | === 1. Fitness funkcia === | ||
+ | |||
+ | Fitness funkcia je mrte dolezita, bez dobrej fitness nevieme porovnavat medzi roznymi rieseniami a vybrat to silnejsie. Neexistuje ziadna vseobecna fitness funkcia - vzdy nejaku vymyslime pre dany problem. Vacsinou je fitness funkcia nejake daco co chromozomu priradi nejake cislo - povedzme cim vyssie cislo, tym lepsi chromozom. | ||
+ | |||
+ | === 2. Metody selekcie === | ||
+ | |||
+ | Najpouzivanejsie su Ruleta a Tournament. | ||
+ | |||
+ | |||
+ | Ruleta funguje ako ruleta :) Ked uz mame ohodnotene chromozomy pomocou fitness funkcie, tak im (zjednodusene) pridelime policka rulety v zavislosti od toho ako silne su dane chromozomy. Priklad: mame v populacii jeden chromozom A so silou 0.6 a styri chromozomy B,C,D,E so silou 0.1. Najprv si urcime " | ||
+ | |||
+ | Tournament funguje tak ze si vyberieme k nahodnych chromozomov, | ||
+ | |||
+ | === 3. Krizenie a mutacia === | ||
+ | |||
+ | Proces, pri ktorom si do rozmnozovania | ||
+ | Single point crossover je jednoducho urcenie si miesta i na chromozome, kde sa chromozomy " | ||
< | < | ||
i=4 | i=4 | ||
- | x = 000[00111] | + | A = 000[00111] |
- | x' | + | B |
- | z = 00011001 | + | Decko 1 = 00011001 |
- | z' | + | Decko 2 |
</ | </ | ||
+ | Multiple point crossover je take, ze tych bodov je viacej a povedzme sa vymienaju len useky medzi dvoma bodmi .. | ||
+ | |||
+ | Mutacia je jednoducho pravdepodobnost s ktorou sa nejaky bit chromozomu preklopi. Teda jednotka na nulku alebo nulka na jednotku. Vacsinou byva mutacia malinke cislo, nieco ako 0.02 (teda dva pripady zo sto). Vyssia mutacia prinasa viacej novosti do populacie ale rovnako dokaze nicit dobre riesenia. Ako pri vsetkych parametroch - ide najdenie tej spravnej hodnoty pre danu aplikaciu. | ||
+ | |||
+ | === 4. Pridavanie novych jedincov do populacie === | ||
+ | |||
+ | Tuna existuje zase mrte moznosti, ale najbeznejsia je ze rodicov zmazeme a pridame naspat ich deti. Takto zostane zachovana velkost populacie P. | ||
+ | Ine metody su take, ze deti ohodnotime cez fitness funkciu a vyberieme len tych najsilnejsich spomedzi deti & rodicov a to tiez tak aby zostala zachovana velkost P. | ||
+ | |||
+ | === 5. Kedy koniec === | ||
- | Okrem popísaného jednobodového kríženia existujú aj iné typy (dvoj- či viac- bodové) | + | GA skonci ked: |
+ | * sa našlo riešenie ktoré uspokojuje dopredu zadefinovane kritéria | ||
+ | * bol prekročený stanovený počet epoch (kazdy navrat ku 1. je akoby nova epocha) | ||
+ | * uviazli sme v lokálnom extréme, alebo na plošine (viď. cyklické prehľadávanie v 3) -- toto sa tazko detekuje ale napriklad ak sme sa pocas x epoch nikam nepohli a najsilnejsie chromozomy maju stale rovnaku fitness | ||
- | == Mutácia | + | === Dajake poznamky === |
- | pri mutácií sa preklopia dvom chromozómom (pozn. podľa mna nie je nutné, aby dvom, opravte ma ak sa mylim) náhodne vybraté bity z reťazca, tj 0->1, alebo 1->0. | + | |
- | Pravdepodobnosť mutácie by mala byť dosť malá, približne 10< | + | |
- | dôvodom pre vytvorenie možnosti mutácie je snaha vyhnúť sa uviaznutiu v lokálnom extréme | + | |
- | kríženie a mutácia sú **genetické operátory** | + | Keby sa Markosova pytala ako sa zvoli optimalna dlzka chromozomu - to zavysi od aplikacie. Kedze chromozomy su vacsinou vlastne prirodzene cisla zapisane v binarnom kode, tak ak mame nejaky spojity priestor ktory chceme prehladavat tak by sme mali dlzku n zvolit tak aby tento priestor chromozomy rozdelili na dostatocne jemny pocet casti. Priklad: mame hladat maximum nejakej sialenej funkcie na < |
- | proces reprodukcie sa končí ak: | + | Keby sa Markosova pytala |
- | * sa našlo riešenie ktoré uspokojuje kritéria | + | |
- | * bol prekročený stanovený počet generácií | + | |
- | * uviazli | + | |
+ | A tak... | ||
===Zdroje: === | ===Zdroje: === | ||
Návrat, P. a kol., Umelá inteligencia, | Návrat, P. a kol., Umelá inteligencia, | ||
+ | Gonda z hlavy a z wikipedie. |