Algoritmus SOMA - najlepšie, čo doma máme

VComputerworlde 6/2003 sme sa podrobne pozreli na oblasť genetických algoritmov. Optimalizačný algoritmus SOMA (Self-Organ...


VComputerworlde 6/2003 sme sa podrobne pozreli na oblasť genetických
algoritmov. Optimalizačný algoritmus SOMA (Self-Organizing Migrating Algorithm,
SamoOrganizujúci sa Migračný Algoritmus) využíva ku svojej funkcii niektoré
podobné prístupy, predovšetkým prácu s populáciou riešení.
Pri behu algoritmu SOMA sa však nevytvárajú žiadni noví jedinci, dochádza iba k
ich premiestňovaniu v stavovom priestore. Samoorganizácia (viď názov algoritmu)
vzniká vzájomným ovplyvňovaním sa jedincov populácie pri pohybe. Výhodou tohto
algoritmu proti GA je veími dobrá geometrická interpretovateínosť a tým aj
pochopiteínosť činnosti algoritmu.
Kým pri GA hodnoty parametrov z híadiska algoritmu predstavujú genóm jedinca a
tak je s nimi aj zaobchádzané (operácie kríženia a mutácie), pri algoritme SOMA
tieto parametre znamenajú iba to, čo v skutočnosti sú: súradnice jedinca
riešenia v stavovom priestore. Poloha najlepšieho riešenia v populácii
ovplyvňuje zmenu polohy ostatných jedincov v nasledujúcom kroku.

Jedinec a populácia
Na začiatku sa náhodne vygeneruje určitý počet jedincov. Vyhodnotí sa ich
funkcia vhodnosti (fitness) a určí sa najlepší jedinec líder. Potom sa vytvorí
ďalšia populácia, v ktorej sa každý jedinec okrem najlepšieho pokúsi nájsť si
vhodnejšiu polohu v priestore a to tak, že sa "skokmi" určitej dížky pohybuje
po priamke smerom k lídrovi, prípadne po tejto priamke pokračuje ešte ďalej za
polohu lídra. Navyše jedinec na tejto ceste mÖže urobiť menšie "odbočky",
nepohybuje sa po celkom presnej priamke, ale miestami sa od nej trochu odchýli;
toto zvyšuje diverzitu v populácii. Keď jedinec prejde celú opísanú trasu, v
ďalšej populácii sa usadí na mieste, ktoré bolo na celej trase najvhodnejšie.
Celý proces je pre jedného jedinca nakreslený na obrázku: PÖvodnú populáciu
tvoria modré body a červený líder. Jedinec A sa pohybuje skokmi po naznačenej
trajektórii k lídrovi L, pričom sa ohodnotia všetky riešenia predstavované tými
skokmi (na obr. prázdne krúžky). Z nich sa vyberie najlepšie riešenie, v ktorom
sa jedinec "usadí" na obrázku fialový bod B. Je možné nahliadnuť že ak sa
takýmto spÖsobom budú pohybovať všetci jedinci (samozrejme okrem lídra), dÖjde
k "rezaniu" stavového priestoru a v skutočnosti bude prehíadané oveía väčšie
množstvo riešení, ako je jedincov v populácii.

Zastavovanie
Na zastavovanie algoritmu SOMA sa používa rozdiel vhodností medzi najlepším a
najhorším jedincom v populácii ak je tento rozdiel dostatočne malý, algoritmus
sa mÖže zastaviť. Tento spÖsob je podobný ako princíp zastavovania GA pomocou
parametra usporiadania (ordering), ale je oveía menej výpočtovo náročný. (Ide o
nájdenie najhoršieho jedinca a porovnanie, jeho vhodnosti s vhodnosťou nového
lídra, pričom pri zastavovaní pomocou parametra usporiadania je potrebné tento
parameter osobitne vypočítať, čo je operácia v pohyblivej rádovej čiarke nad
vhodnosťami všetkých jedincov v populácii. Navyše, počet jedincov v populácii
by musel byť pri GA rádovo vyšší ako je počet jedincov v populácii algoritmu
SOMA pre tú istú úlohu.) V praxi sa samozrejme aj pri algoritme SOMA stanovuje
určitá horná hranica počtu populácií, pri ktorej sa algoritmus násilne zastaví.

Memetické algoritmy
Pokiaí bol v úvode článku algoritmus SOMA klasifikovaný ako evolučný, so
znalosťou jeho fungovania sa mÖžeme naň dívať aj ako na algoritmus memetický.
V podstate sú memetické algoritmy charakterizované ako stratégie súťaže a
spolupráce prejavujúce atribúty synergetiky. Významným synergetickým efektom
algoritmu SOMA je, že jedinci sa navzájom ovplyvňujú a vďaka tomu často menia
smer pohybu. Ich celková trajektória nie je daná žiadnym presným pravidlom, ale
iba ich vzájomnou interakciou.

Variácie algoritmu SOMA
All-To-One alebo "všetci k jednému". Táto variácia bola opísaná vyššie a je
možné ju považovať za základnú variáciu algoritmu SOMA. Ako hovorí názov,
všetci jedinci z populácie migrujú k lídrovi; samozrejme okrem neho samotného.
All-To-All alebo "všetci ku všetkým". V tejto variácii neexistuje líder; každý
jedinec migruje ku všetkým ostatným. Táto stratégia je výpočtovo veími náročná,
ale na druhej strane prehíadáva primerane väčšiu časť stavového priestoru a
zvyšuje pravdepodobnosť nájdenia globálneho, nie lokálneho extrému.
All-To-One-Rand alebo "všetci k jednému náhodne". Každý jedinec migruje len k
jednému náhodne vybranému jedincovi. Pri tejto stratégii sa priam núkajú ďalšie
možné zlepšenia týkajúce sa nahradenia náhodného výberu lídra výberom založeným
na vhodnosti, ako je to pri selekcii v GA.
All-To-All-Adaptive alebo "adaptívne všetci ku všetkým". Táto variácia je
založená na stratégii All-To-All s tým rozdielom, že aktuálne migrujúci jedinec
sa nepresúva do novej pozície až po migrácii smerom ku všetkým jedincom, ale
bezprostredne po dokončení svojej migrácie ku každému z jedincov a v migrácii k
ďalším jedincom pokračuje už z tejto novej polohy.
Clusters alebo "zväzky". Algoritmus SOMA s vytváraním zväzkov je úprava, ktorú
je možné použiť spolu s ktoroukoívek predchádzajúcou variáciou. "Zväzok"
znamená, že jedinci v populácii sú rozdelení do zhlukov a v každom zhluku
prebieha samostatná migrácia. V GA existuje podobný prístup a nazýva sa
"udržiavanie subpopulácií"; implementuje sa zvyčajne za účelom zvýšenia
diverzity populácie. Je ale potrebné podotknúť, že pri algoritme SOMA
clusterizácia nepriniesla žiadne výrazné zlepšenie.

Záver
Hoci je algoritmus SOMA relatívne nový, bol už úspešne použitý aj pri riešení
reálnych úloh. Pre porovnanie s inými optimalizačnými algoritmami, najmä s
algoritmom diferenciálnej evolúcie, bol algoritmus SOMA testovaný
mnohorozmernými funkciami. Na obrázku sú ilustračne uvedené príklady dvoch z
použitých testovacích funkcií. Kým na obrázku sú funkcie uvedené v
trojrozmernom priestore, pri skutočnom testovaní algoritmu bol použitý
storozmerný priestor.
Ďalšie informácie o algoritme možno nájsť na stránkach jeho autora Ivana
Zelinku, ktoré nájdete na http: //www.ft.utb.cz/people/zelinka/soma/.

Plazmový reaktor
Niekoíko experimentov na porovnanie optimalizačných algoritmov SOMA,
diferenciálnej evolúcie a simulovaného žíhania bolo urobených na The Open
University Oxford vo Veíkej Británii na tamojšom plazmovom reaktore (viď
obrázok na strane 25).
Správanie sa reaktora je silne nelineárne a vyskytujú sa v ňom náhodné
fluktuácie, preto nájsť všetkých 14 správnych parametrov (7 periód a 7 amplitúd
riadiacich signálov) bolo veími ťažké.
Ako vyplýva z výsledkov uverejnených na http://www.ft.utb cz/people/zelinka
/soma/, algoritmus SOMA dokázal nájsť tieto parametre s vysokou presnosťou
oproti napr. algoritmu simulovaného žíhania, ktorý našiel iba veími približné
riešenie. Na grafoch porovnávajúcich všetky tri spomínané algoritmy uvedených
na vyššie spomínanej stránke je možné pozorovať aj ďalšiu veími dÖležitú
vlastnosť algoritmu SOMA, ktorou je odolnosť voči náhodným šumom vyskytujúcim
sa v reaktore. Práve tieto fluktuácie predstavovali prekážku pre nájdenie
presného riešenia algoritmom simulovaného žíhania.









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.