PAA 2007-2008, Petr Maj (majp1)
Protoze budu delat ulohu 6 pomoci genetickeho programovani, mym ukolem bylo udelat geneticky algoritmus ktery by resil problem batohu.
úplné zadání úlohyVzhledem k tomu ze jsem jiz v drive absolvovanych predmetech delal mnoho programu na informovane i neinformovane geneticke algoritmy i programovani, rozhodl jsem se na tomto prikladu vyzkouset pouze nejjednoduzsi neinformovany geneticky algoritmus. Pouzil jsem tedy pouze 2 operatory, mutaci a crossover. Pravdepodobnost mutace jsem experimentalne zvolil jako rovnou 1%.
Jedinec byl reprezentovan jako pole delky n (kde n je delka instance) kde pozice i urcovala zda vec i bude v batohu obsazena. Tato naivni reprezentace ma vyhodu ve sve jednoduchosti, rychlemu testu a stale delce. Naopak jeji vyrazna nevyhoda je predevsim fakt ze ne vsecha mozna reseni sou vhodna. Tento fakt byl sice vyresen tim, ze pokud jedinec rika ze i-ty prvek se ma do batohu vlozit, ale pro tento v nem jiz neni misto, prvek se nevlozi a okamzite se vrati vysledek dosud zpracovane casti jedince. Toto je samozrejme problem, protoze pri vyuziti mista batohu na ite pozici, na dalsich pozicich jiz nezalezi. Tedy pokud jsou tyto v crossoveru pouzity, vygeneruji se i kdyz geneticky jini, presto funkcne stejni jedinci, coz ubira crossoveru na sile. Tato reprezentace samozrejme neni idealni, pokud by napriklad nalezeni prvku co jiz nejde do batohu vlozit znamenalo jen nevlozeni toho prvku, ale pokracovani v ohodnoceni ostatnich, parametry by se vylepsily, ale jak jsem jiz napsal v uvodu, toto reseni jsem zvolil zamerne jako nejprimitivnejsi abych mohl porovnat primitivni naprosto neinformovany GA.
Velikost populace jsem vypocital tak, aby pravdepodobnost vyskytu libovolneho genu na alele byla alespon 0.999999, kde vzorec pro tento vypocet je nasledujici:
N=ceil(1+log2(-l/ln(P)))
Pro vyber jedince byl pouzit tournament selection ve kterem byl pocet kol nastaven experimentalne na 2 a pravdepodobnost vitezstvi slabsiho v kole na 1%. Zadne dalsi operatory nebyly pouzity a geneticky algoritmus byl elitisticky. Ukoncovaci kriterium bylo nastaveno bud na 200 generaci, nebo na 50 generaci bez zlepseni nejlepsiho jedince v populaci.
Vysledny geneticky algoritmus jsem testoval na 50ti vzorcich instanci od velikost 10 do velikosti 100 v krocich po deseti. Zajimal me pouze pocet vygenerovanych jedincu do nalezeni nejlepsiho jedince a samozrejme jeho optimalita, porovnavana jak s optimalnim resenim nalezenym pomoci dynamickeho programovani (algoritmus byl testovan na "nejnarocnejsich" datech pro B&B), tak s hodnotou Bounded Greedy algoritmu.
GA se projevil jako relativne schopny (rozhodne schopnejsi nez DFS a BFS) pro reseni problemu batohu. Na druhe strane vsak na mnou testovanych datech daval vysledky jen o malo lepsi nez omezeny greedy algoritmus v mnohem horsich casech. Navic jeho casy byly take horsi nez branch &bound algoritmu, ackoli na instancich degradujicich B%B z minuleho cviceni byla delka vypoctu zhruba stejna, ale vysledek nebyl vzdy optimalni. Z tohoto bych usuzoval ze GA se bude hodit vice na obrovske ulohy kde nam pujde o nalezeni ne nutne idealniho, ale pritom lepsiho reseni nez greedy algoritmus v nejakem "rozumnem" case.
Zajimave bylo ze jsem musel pro velikost instanci vetsi nez 80 upravit populaci, protoze popluace ktera byla nastavena pro velikosti instanci kolem 40 a proporcionalne upravena podle vyse uvedeneho vzorce jiz davala pro tyto delky instanci horsi vysledek nez greedy. Po uprave (koeficient nasobveni 1.5) vsak jiz GA daval vysledky lepsi.
| Instance Size | Tested Instances | Maximal Time | Minimal Time | Average Time | Maximal Visited States | Minimal Visited States | Average Visited States | Maximal Accuracy | Minimal Accuracy | Average Accuracy |
| 10 | 50 | 199.0 | 114.0 | 121.52 | 1445 | 240 | 413.0 | 1.0 | 1.0 | 1.0 |
| 20 | 50 | 289.0 | 232.0 | 255.44 | 4517 | 1254 | 2524.0 | 1.0 | 0.993614931238 | 0.999775680267 |
| 30 | 50 | 663.0 | 349.0 | 435.36 | 14055 | 2258 | 5084.0 | 1.0 | 0.996531062756 | 0.999891510858 |
| 40 | 50 | 1053.0 | 550.0 | 672.38 | 20096 | 4175 | 8136.0 | 1.0 | 0.991304347826 | 0.999483120473 |
| 50 | 50 | 1490.0 | 698.0 | 944.38 | 25316 | 4697 | 11096.0 | 1.0 | 0.997226624406 | 0.999757296184 |
| 60 | 50 | 2182.0 | 946.0 | 1319.04 | 33929 | 7046 | 15189.0 | 1.0 | 0.995024875622 | 0.99978726891 |
| 70 | 50 | 2976.0 | 1344.0 | 1813.54 | 42275 | 10839 | 20183.0 | 1.0 | 0.997069903725 | 0.999477165828 |
| 80 | 50 | 3696.0 | 1479.0 | 2463.16 | 47966 | 10568 | 27326.0 | 1.0 | 0.99744494464 | 0.999601705246 |
| 90 | 50 | 4560.0 | 2144.0 | 2921.92 | 54199 | 18427 | 29868.0 | 1.0 | 0.995107913669 | 0.998496553044 |
| 100 | 50 | 6135.0 | 2273.0 | 3656.72 | 69646 | 17072 | 35841.0 | 1.0 | 0.993272587925 | 0.997833111743 |
Algoritmus by sel samozrejme vylepsit o informovane metody typu greedy crossoveru, dalsich operatoru (greedy mutace,atd), pripadne nasazenim promenne delky populacem, nebo dokonce prolinani generaci. Prolinani generaci (tedy stav kdy je jen jedna populace do ktere se v kazdem kroku pridaji dva jedinci a dva spatni jedinci se odeberou) jsem zkusil implementovat, ale dosahovane vysledky nebyly lepsi. Mozna, ze prolinani generaci se sofistikovanejsimi operatory by jiz mohlo vest k lepsimu vysledku.
zdrojovy kod cele ulohy