Minimalizácia CSS genetickým algoritmom
Ako súvisí Darwinova evolučná teória a genetické algoritmy s CSS a čo som s tým dosiahol v mojom malom experimente.
Genetický algoritmus v prírode
Nieje to tak dávno čo som o genetický algoritmoch ešte nič nevedel. Väčšina ľudí, ktorím som to povedal sa v prvom momente zhrozila a v druhom momente kapitulovala s tým, že to asi nikdy nepochopia. Princíp je však podľa mňa úplne jednoduchý.
Základom je akýsi genóm. Tento genóm je predpis, ktorý určuje správanie, vlastnosti či výzor opisovaného problému. Napríklad si zoberme genóm takej dážďovky. Je v ňom zakódované kedy má žrať, ako sa má hýbať keď prší,… Neviem či sa dážďovky časom učia a či majú nejakú pamäť ale predpokladajme, že nie. Bude to tak jednoduchšie.
To čo ďalej potrebujeme je evolúcia. Aby sa totiž dážďovky "zlepšovali" treba tie lepšie nejako zvýhodniť pred tími horšími. V prírode je to jednoduché: Ten kto žije dlhšie má lepšiu šancu zabezpečiť väčšie množstvo potomstva. Toto potomstvo vzniká spojením dvoch jedincov a to tak, že genómy rodičov sa na náhodných miestach prekrížia a tak vznikne nový genóm, ktorý má isté črty otca a iné črty matky. (Dážďovka je hermafrodit takže toto berte s rezervou.) Taktiež môže dôjsť k mutáciám, čo sú náhodné zmeny v genóme. Takto dostaneme ďalšiu generáciu dáždoviek a tým, že zvýhodneňovaní sú tí lepší ma každá ďaľšia generácia tendenciu sa zlepšovať.
Genetický algoritmus a CSS
Zadanie môjho problému je asi takéto:
Zober existujúci CSS stylesheet a poprehadzuj pravidlá tak aby bol výsledný súbor čo najmenší ale aby sa výzor stránky, na ktorú bol tento stylesheet aplikovaný nezmenil.
Prvým problémom bolo to ako zakódovať pravidlá CSS do genómu, ktorý by sa jednoducho mutoval a krížil. Urobil som to tak, že ku každému pravidlu som pridal pole selektorov, na ktoré sa pravidlo aplikuje. (V podstate je to pole všetkých selektorov a tie, ktoré sa majú aplikovať majú hodnotu true.)
Ďaľším a asi najväčším problémom je úprava genómu tak aby nemenil výzor stránky. Ja som si to navyše zjednodušil tak, že som nebral v úvahu špecifičnosť selectorov ale iba ich poradie čo značne obmedzuje použitie ale pre demonštráciu to úplne stačí.
Zvýhodňovanie "jedincov" je úplne zrejmé. Vygenerujeme predpisy CSS z genómu a zistíme aký je dlhý a podľa toho ich budeme uprednostňovať. Kratšie sú lepšie a dlhšie sú horšie. Uprednostňujeme ich tak, že pri výbere genómu na mutáciu či kríženie má najväčšiu šancu ten najlepší. Robil som to pomocou lineárneho preškálovania čiže ak mám 100 genómov tak prvý najlepší má šancu výberu 100, druhý 99, tretí 98,… Každý kto vie niečo o aritmetických radoch si ostatné ľahko domyslí.
Modelový prípad
Môjmu programu som zadal takéto jednoduché pravidlá:
.left {
text-align: left;
color: green;
margin: 10em;
float: left;
}
.right {
color: green;
margin: 10em;
float: right;
text-align: right;
font-weight: bold;
}
Program pracoval s populáciou 300 genómov pričom 2% najlepších sa automaticky prenášajú do ďaľšej generácie (elitárstvo), 20% prejde iba mutáciou, 77% prejde krížením a 1% vzniká náhodne. Pravdepodobnosť mutácie na úrovni jednej položky v genóme bola 15% čo je relatívne vysoká hodnota.
Nasledujúci výsledný optimálny stylesheet vznikol v priemere za 50 generácii. Pričom dĺžka bola rovnaká a dochádzalo len k rozdielom v poradí jednotlivých pravidiel.
.left, .right {
margin: 10em;
color: green;
text-align: left;
float: left;
}
.right {
font-weight: bold;
text-align: right;
float: right;
}
Problémy genetických algoritmov
Závažným problémom genetických algoritmov je uviaznutie v lokálnom maxime. Znamená to asi toľko, že genóm nedokáže "prežiť" mutácie, ktoré sú potrebné na to aby sa dostal do lepšieho stavu. Toto sa do istej miery prejavilo aj v mojom experimente kde je potrebná veľká zmena genómu na malú zmenu k lepšiemu výsledku. Týmto sa vysvetľuje už spomenutá veľká hodnota pravdepodobnosti mutácie.
Ešte väčšie hodnoty pravdepodobnosti mutácie by mali za účinok destabilizáciu populácie genómov a tak by sa z genetického algoritmu stal náhodný generátor genómov, ktoré majú len malú šancu na zlepšovanie.
(17. január 2004)