Prírodou inšpirované algoritmy

Klasifikačné systémy

Klasifikačné systémy

V doterajších úvahách sa o činnosti EA a konkrétne GA hovorilo najmä v súvislosti s riešením úloh (predovšetkým optimalizačných). Inou dôležitou oblasťou ich aplikácie je návrh efektívnych pravidliel orientovaných klasifikačných systémov (Goldberg, 1989). Jedná sa o špeciálny prípad strojového učenia, ktoré vychádza z jednej zo základných téz umelého života, podľa ktorej existuje dvojaká forma informácie:

• neinterpretovaná (genotyptická), ktorá sa prenáša na potomkov a vďaka genetickým operátorom je schopná evolúcie,
• interpretovaná (fenotypická), ktorá predstavuje vykonateľný kód.

Tento kód je tvorený pravidlami typu KEĎ situácia POTOM akcia. V chromozóme sú zakódované obe časti pravidla: situačná aj akčná. Hľadá sa pritom najefektívnejšia sada pravidiel, ktorými vyvíjajúci sa jedinec reaguje na rôzne situácie. Keď aplikácia nejakého pravidla prispieva v daných podmienkach k úspešnému správaniu sa, potom sa toto pravidlo v priebehu evolúcie posilní, v prípade neúspechu sa zoslabí. Silné pravidlá odpovedajú overenému správaniu sa systému v štandardných situáciách. Krížením silných pravidiel sa kumulujú ich úspešné stavebné bloky a vznikajú pravidlá nové, odpovedajúce síce sľubným ale ešte neovereným typom správania sa. Naznačený proces súťaže medzi pravidlami je jadrom efektívneho postupu, vďaka ktorému je systém schopný vysporiadať sa s neustále sa meniacimi podnetmi z okolia. Novovzniknuté, neoverené pravidlá sa môžu presadiť oproti silným overeným iba v neštandardných situáciách, v ktorých sú tie overené pravidlá "bezmocné".

Naznačený prístup, pri ktorom každý jedinec obsahuje kompletnú sadu pravidiel, býva označovaný ako „pittsburgský prístup“. Odlišný prístup, označovaný ako „michiganský“ inicioval sám Holland, ktorý ho pokladal za model myslenia. Pri tomto prístupe každý jedinec reprezentuje iba jedno pravidlo, pričom sadu pravidiel predstavuje celá populácia. Výsledné správanie sa systému vyplýva z kooperácie týchto jedincov a ich evolúcia zase zo súťaženia medzi nimi. Opis a porovnanie oboch uvedených prístupov je uvedený v (Michalewicz, 1992).

V (Holland, 1992) je uvedený jednoduchý príklad klasifikačného systému michiganského typu, ktorý riadi správanie žaby v závislosti na pozorovanom objekte. Je tvorený tromi pravidlami:

• A - ak sa objekt pohybuje, potom uteč,
• B - ak sa malý objekt pohybuje blízko vo vzduchu, potom ho prenasleduj,
• C - ak sa malý pruhovaný objekt pohybuje blízko vo vzduchu, potom nerob nič.

V nasledujúcej tabuľke sú chromozómy, kódujúce uvedené tri pravidlá (vľavo situačná časť a vpravo akčná časť). Význam symbolov: 1 - áno, 2 - nie, # - nezáleží na.

pravidlo	pohyblivé	na zemi	veľké	blízke	pruhované	uteč	prenasleduj
A	1	#	#	#	#	1	0
B	1	0	0	1	#	0	1
C	1	0	0	1	1	0	0

Tieto pravidlá tvoria hierarchiu, závislú na špecifičnosti situačnej časti: prioritu má vždy špecifickejšie pravidlo (s menším počtom # v situačnej časti).

Keď začne evolúcia klasifikačného systému, v prvých generáciách sa vyvinú pravidlá s jednoduchými podmienkami, pričom každé z nich rieši široký okruh situácií. V priebehu evolúcie získava systém "skúsenosti" a tie sa pretavia do stále zložitejších a špecifickejších pravidiel, ktoré sa čoskoro stávajú dostatočne silnými na to, aby sa presadili pri riešení jednotlivých konkrétnych situácií. Vzniká tak hierarchia pravidiel, z ktorej sa najprv pokúsi systém nájsť čo najšpecifickejšie pravidlo pre danú situáciu a v prípade neúspechu postupne hľadá použiteľné pravidlo na stále všeobecnejšej úrovni.

V zložitejších klasifikátoroch sú pravidlá zreťazené, t.j. majú všeobecnejší tvar AK podmienka POTOM správa. Podmienka na prvej úrovni obsahuje príznaky konkrétnej situácie, správa z výstupu tohoto pravidla postupuje do podmienky pravidla vyššej úrovne a až správa pravidla na najvyššej úrovni predstavuje nejakú konkrétnu akciu, resp. jej zložku. Nadväznosť použitých pravidiel nie je pevne stanovená, ale vyvíja sa v priebehu evolúcie prostredníctvom tzv. „bucket brigade“ algoritmu (Holland, 1985). Proces prebieha tak, že nie sú aktivované všetky pravidlá, ktorých situačná časť je splnená, ale iba tie s najväčšou vhodnosťou. Hodnotu vhodnosti ovplyvňujú dve zložky: špecifickosť (opísaná na príklade so žabou) a sila. Evolúcia sily pravidiel prebieha na „ekonomickom princípe“. Každé aktivované pravidlo „zaplatí“ istú čiastku pravidlám, ktorých správy vstúpili do jeho podmienkovej časti. Súčasne ale kompenzuje „náklady“ na svoju aktiváciu „poplatkami“, získanými od nadväzujúcich pravidiel, ktoré zase vo svojej podmienkovej časti použijú správu z jeho výstupu. Ak výsledkom uvedenej „transakcie“ je zisk, sila pravidla sa zvýši, ak je výsledkom strata, jeho sila sa zníži.

Je možné dosiahnuť aj toho, že sa vyššie ohodnotenie vhodnosti niektorého pravidla prejaví až s istým oneskorením. Vďaka tomu vývoj systému s takýmito pravidlami smeruje k schopnosti predvídať budúce následky terajších akcií.