Prírodou inšpirované algoritmy

Algoritmus GARP

Indukcia pravidiel použitím genetického algoritmu (GARP)

Algoritmus GARP bol vytvorený Davidom Stockwellom z ERIN Unit of Environment v Austrálii a v pôvodnom návrhu je súčasťou komplexného modelovacieho systému GMS (GARP modelling system), ktorý okrem samotnej predikcie vykonáva predspracovanie, inicializáciu dát ako aj formátovanie výstupu. GMS sa skladá z ôsmich modulov, ktoré sú navrhnuté ako komponenty v systéme kaskádneho spracovania dát . To znamená, že jednotlivé moduly majú presne definované rozhranie a je teda možné ich ľahko doplniť popr. rozšíriť novými prvkami.

GMS

• rasterize - konvertuje bodové dáta na priestorový ráster dátových vrstiev (layers)
• presample - zjednocuje dáta na uniformnú veľkosť, normalizuje pravdepodobnosti a pokrytie. Vytvára trénovaciu a testovaciu množinu.
• initial - vytvára základný (prvý) model, inicializuje model
• explain - aplikuje genetický algoritmus na tento model, jeho výstupom je množina najlepších modelov
• verify - vyhodnocuje modely z predchádzajúceho výstupu
• predict - aplikuje model na vstupné dáta
• image - vytvára obrázok na základe predikčných dát
• translate - poskytuje vysvetlenie (interpretáciu nájdeného modelu)

Dátové formáty a predspracovanie.

Predspracovanie pozostáva z transformácie geografických dát na sériu vrstiev (layers) a ich rozdelenie do trénovacej a testovacej množiny. Úlohou biologického modelovania je spracovať jednotlivé lokálne dáta výskytu daného druhu a na ich základe vytvoriť čo možno najpresnejšiu mapu potenciálnej distribúcie. Dáta z jednotlivych lokalít (tzv.lokálne dáta) sú zväčša sériou bodov ( daných geogragfickou polohou) kde sa daný druh vyskytuje resp. nevyskytuje.

Dátový súbor taktiež nazývaný bodové pokrytie (point coverage popr. geocoded flat file) je ASCII súbor kde prvé dva stĺpce sú geografické dáta ( stupeň zemepisnej širky a dľžky) a ďalšie sú početnosť výskytu daného druhu popr. hodnoty parametrov napr.:

150.775 -35.005 0 0 1178 195 169 0

148.005 -35.005 1 3 824 204 138 5

...

Zdrojom týchto dát sú zväčša databázy a GIS aplikácie (geographical information systems). Ďalším súborom je súbor parametrov, ktorý úchováva informáciu o jednotlivých premenných ( min, max hodnotu, typ, jednotky, formát).

Modul rasterize použije ako vstup parametrický a dátový súbor a vytvorí sériu vrstiev (obrázkov). V danom obrázku množina bodov (1 bod = 1 byte) reprezentuje svojím umiestnením nejaké geografické miesto a svojou hodnotou výskyt druhu popr. hodnotu parametra. Keďže hodnota môže nadobúdať hodnoty v rozmedzi 0 až 255 je nutné všetky dáta normalizovať do tohoto intervalu. Pre výskyt daného druhu bod nadobúda hodnotu ak pre dané miesto existuje jeden alebo viacero výskytov, pri spojitých a reálnych dátach bod nadobúda normalizovanú strednú hodnotu. Príklad jednotlivých vrstiev je možné vidieť na obrazku ( výstup modulu rasterize)

Reprezentácia a vhodnosť.

Modul presample vytvára trénovaciu a testovaciu množinu. Trénovacia množina je použitá na indukciu modelu, testovacia na overenie kvality nájdeného modelu. Do modulu je možné zahrnúť aj náhradu, čo sa využíva hlavne v prípade nedostaku dát popr. pri takmer vyhynutých druhoch kedy počet výskytov je veľmi nízky. Modul initial vytvára prvý model, ktorý je vlastne len množinou pravidiel, ktorá sa nasledné spracuje genetickým algoritmom. Každé pravidlo je pravidlom typu ak-potom (if-then), logika predikcie pri pravidle je :

Pre pravidlo , ak A je splnene predikuj B, pričom A je predpoklad pravidla a B je následok.

Presnosť pravidla je daná pravdepodobnosťou. Keďže predpoklad ohraničuje vstupný priestor, pravdepodobnosť je potom možné vyrátať ako podiel výskytu jedinca v tomto subpriestore k veľkosti daného subpriestoru. Príklad výstupu modulu initial je:

Prvý stĺpec obsahuje inidikátor použitia/nepoužitia daného pravidla. Ďalej je uvedený typ pravidla (r - logistic, m - bioclim, d - range, a - atomic viď. ďalej), hodnota prvej premennej (závislej), minimum parametra alebo hodnota ( v závislosti na type pravidla), maximum parametra atď. Závislá premenná môźe byť vyjadrená dvoma hodnotami, ak typ pravidla je d alebo m potom ide o minimum, maximum. Ak typ pravidla je r potom prvá hodnota je koeficient, druhá je irelevantná, ak typ pravidla je a potom prvá hodnota je presnou hodnotou a druhá je irelevantná. V prípade, že rozmedzie hodnôt je 0 255 potom pravidlo je splnené pre všetky hodnoty parametra.

Následne je uvedených desať hodnotiacich parametrov pre dané pravidlo:

1. Vhodnosť (signifikancia)
2. Primárna sila = pXs/n. Určuje pre akú časť subpriestoru je možné aplikovať toto pravidlo.
3. Primárna pravdepodobnosť = pYs/n. Určije akú časť ma predikovaná trieda v trénovacej množine.
4. Primárna vzdialenosť = pYcs/n
5. Sekundárna (posteriórna) sila = pXSs/no
6. Sekundárna pravdepodobnosť = pXYs/no
7. Sekundárna vzdialenosť = pYcXs/no
8. Pokrytie = no/n
9. Signifikancia = (pXYs-no*pYs/n)/sqrt(no*pYs*(1-pYs/n)/n)
10. Chyba = Signifikancia * sqrt (( pXYs/no)*(1-pXYs/no))/no

pričom:

pXs - aplikačný potenciál pravidla (sila). Ak daný bod splňuje predpoklad je rovný 1, ak nie 0
• pYs - určitosť pravidla. Ak predikovaná hodnota splňuje následok pravidla potom 1, inak 0
• no - počet bodov selektovaných predpokladom
• pXSs - suma pXs po aplikácii pravidla
• pXYs - suma pYs po aplikácii pravidla

posledných šesť hodnôt sú :

1. počet generácií
2. indikátor, či pravidlo už bolo vyhodnotené
3. koľkokrát bolo pravidlo vyhodnotené
4. heuristická hodnota
5. monitorovacia hodnota
6. dĺžka pravidla

Jednou z výhod GMS je schopnosť pracovať s viacerými pravidlami a tým schopnosť lepšieho popisu daného modelu. V súčasnosti sa používajú štyri typy pravidiel a to : atomické (atomic), BIOCLIM pravidlá, logit pravidlá (Logit) a range pravidlá. Atomické pravidlá maju formu :

patria k najjednoduchším pravidlám, v predpokladovej časti majú len jednu hodnotu pre každý parameter. BIOCLIM pravidlá sú založené na pravidlách použitých v programe BIOCLIM. Pravidlá sa vytvarajú na základe obálky (envelope, súboru podmienok pre parametre), tak aby predpokladová časť vypĺňala aspoň 95% priestoru v ktorom sa daný druh vyskytuje. V GMS sa tieto pravidlá vypočítajú štatisticky. Príklad takéhoto pravidla je:

Na rozdiel od atomických predpokladová časť obsahuje rozsahy hodnôt parametrov ( použiva sa symbolika množín, otvorená, uzavretá množina ). Pravidlo môže predikovať buď výskyt alebo absenciu druhu. Range pravidlá sú zovšeobecnené BIOCLIM pravidlá. Počet parametrov je irelevantný, neuvedené parametre môžu nadobúdať ľubovolné hodnoty. Príkladom takéhoto pravidla môže byť pravidlo:

Tento typ pravidiel je užitočný keď druhy sa správajú na základe tolerancie a limít voči prostrediu. Logit pravidlá sú adaptáciou logistických regresných pravidiel. Logistická regresia je regresná rovnica v ktorej výstup je transformovaný na pravdepodobnosť ( p = 1/(exp(-y)+1, kde y je predpokladová časť). Napr:

Genetický algoritmus.

GMS používa trochu modifikovaný genetický algoritmus. Reprezentácia jedinca je ekvivalentná reprezentácii pravidla. Jedna iterácia GMS pozostáva z týchto krokov:

1. štart, čas t
2. inicializuj populáciu P(t)
3. náhrada
4. vypočítaj hodnotiacu funkciu (fitness) populácie
5. umiestni najlepších a vynimočných jedincov do archívu
6. testuj podmienku ukončenia
7. vyber novú populáciu z archívu
8. aplikuj operátory (crossover, mutácia, join)
9. t = t + 1
10. skok na 3

Archív je vytváraný za účelom vyhnutia sa konvergencie k jednomu pravidlu. Algoritmus začína inicializáciou (2) t.j. načítaním pravidiel vytvorených modulom initial. V ďalšom kroku je vybraná náhodná subpopulácia jedincov (3) a vypočíta sa ich fitness (4), čo je akákoľvek funkcia (utility) zadaná uživateľom resp. signifikancia. Následne sú najlepší a vynimočný jedinci presunutí do archívu (5) a testuje sa stop pravidlo. Stop pravidlo je zisťované na základe zmeny jedincov v archíve, v prípade, že sa nezmenilo viac ako 5 pravidiel zo 100 algoritmus končí. Operátory použité v 8. kroku sú:

• join ( zlúčenie predpokladov dvoch pravidiel),
• mutácia - náhodná zmena hodnoty parametra, buď v rozmedzí 1-254 (random mutation) alebo inkrementáciou (incremental mutation)
• crossover - výmena časti dvoch pravidiel v náhodnom bode

GMS taktiež vyratáva úspešnosť použitia daného operátora a na jej základe mení pravdepodobnosť aplikácie operátora. Signifikancia je použitá ako hodnotiaca funkcia ale je možné aplikovať bias ako napr. sekundárna pravdepodobnosť, selekčný tlak, ekologický priestor ( čo najväčšie pokrytie predpokladom), negácia dĺžky pravidla. Ten je potom použitý pri vyberaní jedincov z archívu.

Modul verify testuje presnosť predikcie vzniknutého modelu na testovacej množine. Výstupom je kontingečná tabuľka, napr. :

Modul predict aplikuje odtestovaný predikčný model na vrstvy (layers), pričom hodnota predikcie môže nadobúdať 256 hodnôt. Vzhľadom k tomu, že množstvo dát z tohoto modulu je veľkosť danej vrstvy * 256 (* počet vrstiev) najednoduchším spôsobom prezentácie sú obrázky (raw, miff, bmp, grid, pnm,mesh). Modul translate zjednodušuje množinu pravidiel tak, že vynecháva z predpokladovej časti parametre ktoré môžu nadobúdať ľubovolné hodnoty. Týmto prístupom je výsledok ľahšie zrozumiteľný a jednoduchšie interpretovateľný.