Prírodou inšpirované algoritmy

Optimalizácia particle swarm-om

V tejto kapitole je predstavená metodológia optimalizácia nelineárnej funkcie použitím techniky particle swarm. Je tu načrtnutý vývoj niekoľkých prístupov a podrobnejšie je rozobratý jeden z nich. Takisto táto kapitola popisuje testy tohto prístupu a aplikácie. Popisuje takisto vzťahy medzi particle swarm-om, umelým životom a genetickými algoritmami.

Metóda bola vytvorená simuláciou zjednodušeného sociálneho modelu, preto sa tu preberá sociálna metafora, keďže algoritmus je postavený bez podpory sociálnej metafory. Algoritmus je popísaný v intenciách jeho predchodcov, v skratke popisujúc jednotlivé kroky jeho vývoja od sociálnej simulácie k optimalizácii.

Optimalizácia particle swarm-om má korene v dvoch hlavných komponentových metodológií. Asi najzrejmejšia je jeho spojitosť s A-life a s modelovaním kŕdľov vtákov, húfov rýb a celkovo húfov. Je takisto spojený s evolučnými výpočtami a má väzby aj ku genetickým algoritmom a evolučnému programovaniu. Optimalizácia particle swarm-om zahŕňa veľmi jednoduchý koncept a jej paradigmy môžu byť implementované niekoľkými riadkami počítačového kódu. Vyžaduje len jednoduché matematické operátory a je výpočtovo nenáročná. Skoršie testy ukázali, že je efektívna pri riešení viacerých druhov problémov. V tejto práci sa rozoberá použitie algoritmu na trénovanie váh umelých neurónových sietí. Ale bola použitá aj pre potreby výpočtu testovacej funkcie genetických algoritmov.

Viacero vedcov sa zaoberalo počítačovou simuláciou rôznych interpretácií skupinového pohybu organizmov. Zaujímali ich vnútorné procesy, ktoré ovplyvňujú nepredvídateľnú dynamiku pohybu a s tým spojené sociálne správanie organizmov. Modely ich správania sa zväčša spoliehali na manipuláciu so vzdialenosťou medzi indivíduami, keďže sa predpokladalo, že synchronizácia je založená na úsilí o optimálnu vzdialenosť jedincov medzi sebou.

Jedným z motívov bolo aj vytvorenie modelu sociálneho správania sa ľudí, ktorý je samozrejme odlišný od modelov správania sa iných organizmov. Podstatná odlišnosť je jeho abstraktnosť. Ľudia nerozlišujú len fyzické pohyby, ale aj kongnitívne a experimentálne hodnoty. Riadime sa podľa sociálnych vzťahov, postojov a pod. Aj napriek tomu je tu snaha o zmenu modelovania ľudského správania sa na modelovanie podobné pohybu vtákov alebo rýb. Mení sa pohyb v 3D priestore na pohyb v abstraktnom multidimenzionálnom svete. Táto navigácia si žiada psychologické skúsenosti a informačné vstupy. Ľudia sa naučia vyhýbať sa kolízii vo veľmi mladom veku ale pohyb v psychologickom svete si vyžaduje roky praxe a zdá sa, že niektorí z nás pre toto nikdy nedosiahnu potrebnú zručnosť.

Základný simulátor pohybu sa opiera o dva parametre: rozdiel v rýchlosti najbližšieho suseda a náhodnosť. Populácia vtákov bola náhodne inicializovaná na mriežke s pozíciou a x-ovou a y-ovou rýchlosťou. V každej iterácii program určil pre každého agenta jeho najbližšieho suseda a jeho zložky rýchlosti. Toto jednoduché pravidlo vytvorilo synchronizovaný pohyb, avšak pohyb húfu po krátkom čase ustal. Preto bolo nutné pridať stochastický parameter náhodnosti. V každej iterácii sa o niečo zmenia zložky rýchlosti agentov. Táto zmena dodala simulácii dostatočnú variáciu a potrebný vzhľad, aj keď zmena bola úplne umelá.

Inou variáciou riešenia bolo zadefinovanie útočiska, kam sa celá skupina snaží dostať. Je to určitá forma atraktora, čo odbúralo nutnosť použitia stochastického parametra, za predpokladu pohybu tohto bodu. Táto idea bola využitá aj pri optimalizácii, kde stádo hľadá takýto atraktor. Výsledky boli povzbudzujúce. Skupina agentov veľmi rýchlo nájde atraktor v 2D priestore a začne okolo neho krúžiť, pričom sa stále zmenšuje vzdialenosť medzi jednotlivcami.

Keď bolo jasne ukázané, že tento algoritmus dokáže optimalizovať 2D funkciu, bolo potrebné identifikovať ktoré časti paradigmy sú aj naďalej potrebné pre algoritmus. Zistilo sa napríklad, že algoritmus pracuje práve tak dobre aj bez stochastického parametra náhodnosti, takže bol odstránený. Ďalej sa ukázalo, že je lepšie nezohľadňovať v porovnávaní rýchlostí najbližšieho suseda jednotlivca. Stratil sa tak efekt kŕdľa, ale prispelo to k rýchlosti algoritmu, ktorý sa teraz viac podobá na rojenie častíc (particle swarm).

Keďže väčšina problémov optimalizácie nieje lineárneho charakteru a ani nie sú dvojdimenzionálne, bolo potrebné testovať algoritmus na takýchto problémoch. Zdá sa, že algoritmus pracuje rovnako dobre aj na viacdimenzionálnych doménach, ako napríklad nastavenie váh doprednej neurónovej siete. Jeden z testovacích problémov bolo nastavenie váh neurónovej siete riešiacej XOR problém, čo bol problém nastavenia trinástich parametrov váh siete. Algoritmus sa ukázal ako veľmi výkonný. Tento problém vyriešil do stavu kritéria e < 0,05 v priemere na 30,7 iteráciách s 20-timi agentmi. Väčšia neurónová sieť by bola samozrejme náročnejším problémom so zdĺhavejším riešením ale výsledky v skorých aplikáciách sa ukázali ako sľubné. Bolo vypracované aj množstvo variácií tohto algoritmu, ktoré viac či menej prispievajú k jeho zrýchleniu.

Autori používajú termín swarm (kŕdeľ) v súlade s prácou, ktorú publikoval Millonas, ktorý vytvoril vlastný model pre aplikáciu v umelom živote a vyslovil päť základných princípov inteligencie krdľa.

• Princíp blízkosti – populácia by mala byť schopná fungovať na jednoduchých priestorových a časových výpočtoch.
• Princíp kvality – populácia by mala byť schopná odpovedať na kvalitatívne faktory v prostredí.
• Princíp rozdielneho účinku – populácia by nemala vykonávať svoje aktivity pozdĺž príliš rovných kanálov.
• Princíp stability – populácia by nemala meniť model svojho správania zakaždým, keď sa zmení prostredie.
• Princíp adaptability – populácia by mala byť schopná zmeniť model svojho správania sa, ak je to vhodné z hľadiska výpočtovej náročnosti.

Všimnite si, že štvrtý a piaty princíp sú navzájom opačné. Základom tejto konkrétnej paradigmy sú n-rozmerné priestorové výpočty vykonávané v sérii časových krokov. Termín častica bol vybraný ako kompromis, keďže príslušníci populácie sú modelovaní ako body bez objemu a hmotnosti, a preto ich možno nazvať častice. Ako bolo povedané, tento optimalizačný algoritmus bol použitý pre trénovanie váh neurónovej siete s efektivitou porovnateľnou s klasickým algoritmom spätného šírenia chyby a bol použitý aj na klasifikačnú úlohu s podobnou efektivitou.

Algoritmus optimalizácie pomocou particle swarm-u je veľmi jednoduchý a zdá sa vhodný pre optimalizáciu širokého rozsahu rôznych funkcií. Pozeráme sa naň ako na medziúrovňovú formu A-life alebo biologicky odvodený algoritmus, ktorý zaberá priestor medzi evolučným prehľadávaním a prirodzeným spracovávaním. Sociálna optimalizácia sa objavuje v časovom rámci prirodzenej skúsenosti – v podstate je to aj prirodzená skúsenosť. Aj keď má množstvo podobných čŕt s evolučným programovaním a genetickými algoritmami, je to skôr stochastický proces. Jeho jedinečnými vlastnosťami sú prelietavanie medzi riešeniami a akcelerácia k „lepšiemu“ riešeniu.

Tento algoritmus slúži rovnako dobre v sociálnej aj inžinierskej doméne. Sociálne správanie je tak často pozorovateľné v ríši zvierat práve preto že optimalizuje. Preto je to sľubný prístup aj v inžinierskej praxi.

Zdroj:
http://www.engr.iupui.edu/~shi/Coference/psopap4.html