PAA 2007-2008, Petr Maj (majp1)
Naprogramovat geneticky algoritmus, ktery bude resit WSAT-3 problem. WSAT 3 je jako normalni SAT-3 (tedy splnitelnost booleovske formule), pouze s tim rozdilem ze pro reseni neni dulezity pouze pocet splnenych klauzuli, ale take vaha reseni, tedy soucet vah promennych v reseni nastavenych na 1.
Jako testovaci data jsem bral instance se 100 promennymi a poctem klauzuli 430, ktere jsem ziskal na strankach University of British Columbia. Tyto instance SAT problemu by mely byt obtizne. K nim jsem nahodne doplnil vahy promennych z intervalu 0 az 100.
uplne zadani ulohy pro PAA testovaci instanceJedinec je reprezentoval velice jednoduse jako bistring delky n, kde n je pocet promennych dane instance.
Nejprve jsem implementoval fitness funkci ktera kazdemu jedinci prirazovala fitness rovnou:
F(i) = (Wmax*pocet_splnenych_klauzulii)+Wi
Takto formulovanou fitness funkci v obecnejsim realnem tvaru jsem take navrhl v pocatku prace. Behem experimentovani se vsak ukazalo ze tato funkce davala velice spatne vysledky. Konkretne reseni vsech klauzuli nebylo vetsinou nalezeno, a pokud nalezeno bylo, jeho vaha nebyla prakticky vubec vylepsena. Toto chovani je logicke, protoze SAT problem neni lokalne optimalni, tedy napriklad mame-li reseni ktere nesplnuje pouze 1 klauzuli, nemusi to vubec znamenat ze reseni splnujici vsechny klauzule bude nekde "blizko" (napriklad Hammingovou vzdalenosti). Je tedy nutne vytvorit fitness funkci tak, aby podporovala diverzitu na nizsich stupnich, cehoz jsem docilil vytvorenim dvoustupnove fitness funkce. Pro jedince kteri nesplnovali vsechny klauzule byla jejich fitness rovna poctu klauzuli ktere splnili, pro jedince splnujici vsechny klauzule se pak jeste pripocitavala vaha jedince. Tato funkce tedy udrzovala relativni diverzitu na nizsich hladinach a umoznovala vylepsovat idealni reseni. Algoritmus jsem vsak musel updavit tak, ze pokud se neporadi najit uplne reseni, musi se jeste vahove vyladit nejlepsi nalezene reseni. Nalezeni idealniho prvku je proto kratsi nez nalezeni neoptimalniho prvku.
Populaci jsem zacal na velikosti 200. Potom jsem zkusil predpripravit si vzorky v nekolika oddelenych bazenech na zacatku a ty potom nakrizit dohromady. Toto reseni se mi bohuzel moc neosvedcilo. Bylo vyhodnejsi pro male populace, pro populace kolem 300 a vyse vsak jiz nedochazelo k zadne vyhode. Vsechny populace byly vzdy elitisticke s prechodem nejlepsiho jedince do dalsi populace automaticky beze zmen.
Nejprve jsem zacinal s 1X a 2X crossoverem. Potom jsem pridal informovany greedy crossover ktery postupoval tak ze vzdy pro dane jedince vybral pozici a zvolil do potomka tu hodnotu, ktera pomohla splnit vetsi mnozstvi jeste nesplnenych klauzuli. Krome toho ze tento crossover byl mnohem pomalejsi, ukazalo se ze diky vyse zminenene lokalni neoptimalite toho reseni bylo krajne nevhodne. Mozna ze by bylo lepsi pokud by se pozice volily nahodne, toto reseni jsem vsak nezkousel. Ve vyslednem algoritmu je proto pouzit pouze 2X crossover.
Algoritmus pouziva normalni mutaci s pravdepodobnosti 10%. Ukazalo se ze mutace ma relativne zlepsujici vliv na populaci kde jeste nebyl nalezen jedinec splnujici vsechny klauzule, naopak po jeho nalezeni byla jiz mutace ciste skoro vyhradne destruktivni. Zkusil jsem jeste experimentovat s progresivni mutaci (mira mutace je umerna rozdilu mezi fitness jedince a fitness nejlepsiho), ale potom co jsem zjistil ze mutace neni nijak efektivni, tuto jsem vypnul.
V konecne podobne algoritmu se jedna o jediny pouzity informovany operator. tento operator vezme jedince, najde klauzuli kterou nesplnuje a tuto splni nahodnou zmenou jedne promenne v ni obsazene. Jak vyplyva z nize uvedenych grafu, tento operator se spolu s fitness a tournament selekci stal "hnacim motorem" algoritmu. Ukazalo se ze je idealni je-li pokus o vylepseni jedince proveden vzdy (tedy s pravdepodobnosti 100%).
Druhym krokem je vytvoreni prvotni populace (nahodne) a jeji evoluce. Evoluce probiha do doby dokud neubehne x generaci bez vylepseni nejlepsiho jedince. Pak se vezme nejlepsi jedinec a pokud splnuje vsechny klauzule, je vracen jako nalezene reseni. Pokud vsechny klauzule nesplnuje, upravi se fitness funkce podle stare fitness a nejlepsi nalezene reseni se jeste upravi vahove s podobnou ukoncovaci podminkou, po jejimz skonceni je vracen.
Ackoli jsem provedl s programem mnoho experimentu, jejich statisticke vyhodnoceni je velmi narocne. Napriklad pro 1X a 2X crosoover byla presnost programu o 1% lepsi pro 2X. Toto ale rozhodne neni zachytitelny rozdil pro 100 testovacich instanci. Krome pravdepodobnosti informovaneho vylepseni, fitness funkce, velikosti populace a pocet kol turnaje se vsak vsechna dalsi nastaveni chovala zhruba stejne. Vytvoreni grafu z relevantnich dat je opet narocne diky relativne dlouhemu casu pro zpracovani instanci. Tyto experimenty budou tedy uvedeny pouze v textove podobe.
Zakladni algoritmus dosahoval velice podprumernych vysledku (tedy uspesnost horsi nez 50%). Naopak s lepsi fitness, informovanym vylepsenim a vicekolovym tournamentem se uspesnost pohybovala v radu 70% a vyssi. Pro populaci o velikosti 200 jedincu bylo reseni splnujici vsechny klauzule nalezeno s pravdepodobnosti 76% v prumernem case 4 vteriny procesoroveho casu. Pro velikost populace 1000 a pocet kol tournamentu 7 pak byla uspesnost 98% (na 100 testovanych vzorcich) a prumerny procesorovy cas 10.4 vterin. Na druhe strane za vsechny provedene testy nebyl nikdy nalezen jedinec horsi nez 428 (a ik 428 jen velice vyjimecne).
U grafu jsem pouzil tri serie, prvni je pro pripad kdy bylo spravne reseni nalezeno velice rychle (radove 10. generace), druhy kde k jeho nalezeni doslo mnohem pozdeji (40. generace) a posledni kdy nejlepsi jedinec nebyl nalezen nikdy.
U rychle konvergujiciho jedince je zajimave jednak velice rychle nalezeni spravneho jedince (v 10. generaci), potom jeho relativne male vylepseni, ke kteremu doslo v 12 a 13 generaci, tedy relativne velice rychle po jehol nalezeni. Skok ve fitness funcki je zpusoben pridanim informace o vaze jedince. Zajimavy je vsak graf uspesnosti operatoru. Zde je videt ze v dobe kdy se hledal nejlepsi jedinec co do poctu splnenych klauzuli byli crossover, mutace i vylepsovaci operator relativne stejne uspesni. Velka zmena ale nastala po nalezeni spravneho jedince. Zatimco mutace okamzite zacala nicit nalezene jedince (mutace jedince splnujiciho vsechno vetsinou vedla k jeho posunu do nizsi fitness a tutiz nezapocitani jeho vahy). Crossover se relativne stabilne drzi na prumeru s malym vylepsenim ihned po nalezeni jedince (vylepsovani nejlepsiho) a zajimave je sledovat informovane vylepseni. Zde je dulezite si uvedomit ze neni mozne vylepsit jedince splnujici vsechny, naopak vylepsenim jedince na vsechny splnene klauzule znamena zapocitani vahy k fitness a proto tak veliky skok.
Tyto grafy jsou velice podobne rychle konvergujicimu jedinci, hlavnim rozdilem je mnohem lepsi vylepseni reseni co se tyce vahy, diky tomu ze v populaci se diky pomale konvergenci nahromadilo vice kvalitnich jedincu schopnych toto reseni vylepsit. Zajimave je opet sledovat male zvyseni uspesnosti crossoveru po nalezeni nejlepsiho jedince stejne jako obrovsky pokles mutace a vzrust informovaneho zlepseni.
Zde je videt veliky skok kde doslo k ukonceni hledani optimalniho reseni a soustredeni se na aktualni reseni ve fitness funkci kolem 50te generace. Naopak vylepseni tohoto jedince trva relativne velice dlouhou dobu (prakticky az do 200te generace). Naopak z operatoru jediny kdo si podrzel diky skokove fitness funkci dobrou uspesnost byl crossover. Mutace i informovane vylepseni se propadly pod uroven 1.0. U informovaneho vylepseni je to castecne proto, ze tento operator se porad jeste snazil splnit vsechny klauzule. Glitch u uspesnosti crossoveru je v jinem meritku a ilustruje prechod od fitness poctu splnenych klauzuli k stare fitness.
Narozdil od predchozich uloh jsem se rozhodl implementovat tyto ulohu v C++, hlavne diky jeho rychlosti, protoze jsem vedel ze se bude jednat o casove narocnejsi ulohu.
Pote co jsem slysel od kolegu z minuleho rocniku jsem byl prekvapen uspesnosti algoritmu a castecne i jeho rychlosti, ackoli verim ze na B&B algoritmus na ne uplne spatnych instancich rozhodne mit nebude. U GA navic neexistuje zaruka nalezeni nejoptimalnejsiho reseni, specielne vahove vylepseni optimalniho reseni je velice problematicke. Na druhe strane myslim ze uspesnost 98% a 10 vterin na vypocet neni z nejhorsich. I tak bych ale myslel ze WSAT-3 neni problemem nejvhodnejsim pro reseni GA (pareve diky male lokalnosti optimality).
zdrojovy kod ulohy zdrojovy kod hlavicky zdrojovy kod knihovny zkomprimovany C++ zdrojovy kod dokumentace ke kodu