Optimalizačné algoritmy

V technickej praxi sa vyskytuje množstvo úloh, ktoré možno nazvať optimalizačné. Optimalizáciou chápeme proces zamera...


V technickej praxi sa vyskytuje množstvo úloh, ktoré možno nazvať
optimalizačné. Optimalizáciou chápeme proces zameraný na nájdenie určitého
vyhovujúceho riešenia nejakej úlohy. MÖže ísť napríklad o nájdenie parametrov
aproximovanej funkcie, nájdenie správnych konštánt na reguláciu výrobného
procesu, či nájdenie optimálneho rozloženia strojov vo výrobnej hale tak, aby
zaberali čo možno najmenej miesta.
Podobných príkladov je možné nájsť veía tak v technickej praxi, ako aj vo vede
a výskume. Možno si všimnúť časté použitie odvodenín slova "nájsť", ako aj
použitie superlatívov "najmenej miesta", "najmenší presun medziproduktov" apod.
Tieto slová vystihujú úlohu každého optimalizačného algoritmu: "nájsť extrém" v
určitom stavovom priestore. Obtiažnosť úlohy vyplýva z viacerých faktov.
Zvyčajne je nemožné rozhodnúť, či od nájdeného "najlepšieho" riešenia existuje
riešenie lepšie alebo nie. Preto sa spravidla úloha nájsť najlepšie riešenie
redukuje na úlohu nájsť riešenie vyhovujúce. To však nie je jedná nástraha
číhajúca na pri optimalizácii. Ďalšími sú napríklad časová náročnosť
optimalizačného procesu, klamlivosť daného problému, či nebezpečenstvo
uviaznutia v lokálnom extréme. O týchto a iných problémoch optimalizácie si
niečo bližšie povieme pri jednotlivých optimalizačných metódach.

Funkcia vhodnosti
Na tomto mieste je potrebné definovať tzv. "funkciu vhodnosti" (angl. "fitness
function") daného riešenia. Exaktnej matematickej definícii sa vyhneme; pre
potreby nasledujúceho textu je potrebné vedieť iba to, že fitness funkcia
každému riešeniu jednoznačne priraďuje ohodnotenie v podobe nezáporného
reálneho čísla. Toto číslo je tým väčšie, čím dané riešenie lepšie vyhovuje
úlohe. Optimalizačná úloha sa potom definuje ako snaha o maximalizáciu funkcie
vhodnosti.

Vzorový príklad
Predstavme si nasledujúcu úlohu: máme nula-jednotkový reťazec dížky 100 bitov,
pričom funkcia vhodnosti je definovaná ako súčet jednotiek v tomto reťazci.
Ideálne riešenie, ktoré budeme híadať, je teda reťazec zložený zo samých
jednotiek. Pre niektoré optimalizačné algoritmy si ukážeme, ako by daná metóda
konvergovala k požadovanému výsledku. Parametre pri jednotlivých metódach boli
volené tak, aby bolo podía možnosti vyskúšané približne rovnaké množstvo
riešení; v danom prípade 10 000.

Náhodné prehíadávanie
Najjednoduchším spÖsobom híadania optimálneho riešenia je jeho náhodné
(stochastické) híadanie. Vygeneruje sa náhodné riešenie (sada koeficientov pre
PID regulátor, poradie navštívených miest pre obchodného cestujúceho, alebo v
našom prípade nula-jednotkový reťazec dížky 100 bitov) a toto riešenie sa
vyskúša, t.j. vyhodnotí sa jeho fitness funkcia. Ak je toto riešenie prvé
vyskúšané alebo ak je jeho fitness väčšia ako fitness najlepšieho doteraz
nájdeného riešenia, odpamätá sa toto riešenie ako najlepšie nájdené a pokračuje
sa generovaním ďalšieho riešenia a jeho vyskúšania. DÖležitým faktom je tu
náhodnosť každého riešenia: počas skúšania generovaných riešení sa nezískava
žiadna znalosť o vzťahu parametrov a fitness každé riešenie je vytvorené bez
súvislosti s predchádzajúcimi riešeniami.
Mohlo by sa zdať, že optimalizácia v tomto najjednoduchšom tvare nemá praktické
uplatnenie. Je pravda, že tejto metóde chýba cielenosť vývoja (tzv. "selekčný
tlak", bude spomínaný neskÖr), avšak stochastické prehíadávanie sa úspešne
vyhýba problému uviaznutia v lokálnom minime, ktorý je typický pre gradientné
metódy. Vyhovujúce riešenie mÖže byť týmto spÖsobom nájdené na niekoíko málo
pokusov, rovnako ako nemusí byť (zvlášť pri viacrozmernej úlohe) nájdené ani po
veíkom počte krokov. Preto sa stochastické prehíadávanie stavového priestoru
pri optimalizácii používa zvyčajne na inicializáciu niektorých iných metód,
najmä metód založených na množine ("populácii") riešení.
Horolezecké algoritmy
Horolezecké (angl. "hillclimbing") algoritmy sú gradientnou metódou híadania
extrému v lokálnom okolí nejakého bodu. Je to stochastické prehíadávanie
doplnené o usmernenie generovaných riešení. Základným princípom horolezeckého
algoritmu je prehíadanie lokálneho okolia najlepšieho nájdeného riešenia (alebo
náhodne vygenerovaného riešenia na začiatku procesu optimalizácie). Namiesto
náhodného ďalšieho riešenia sa použije najlepšie doposiaí nájdené riešenie, v
ktorom sa urobí určitá malá zmena (napr. sa zmení 5 % parametrov tohto
riešenia). Toto nové riešenie sa prijme, ak je lepšie ako to, z ktorého
vzniklo; ak je horšie, opäť sa urobí iná malá zmena najlepšieho riešenia.
Závislosť nového riešenia od predchádzajúceho je v tomto algoritme silná.
Horolezecké algoritmy zvyčajne dokážu rýchlo nájsť lokálny extrém, v ktorom
uviaznu, ak sa v prehíadávanom okolí nenachádza lepšie riešenie. Preto sa
horolezecké metódy pri optimalizácii používajú na "dotiahnutie do
extrému" (obrazne aj doslovne) riešenia nájdeného inou metódou.

Zakázané híadanie
Metóda zakázaného híadania (angl. "tabu search") je určitým zlepšením
horolezeckého algoritmu. Zlepšenie spočíva v odstránení možnosti nastatia
cyklických zmien pri prehíadávaní okolia bodu v stavovom priestore. Kým
horolezecký algoritmus sa mÖže dostať do niektorého z predchádzajúcich stavov
(mÖže generovať také riešenia, ktoré už v minulosti boli vyskúšané), metóda
zakázaného híadania obsahuje krátkodobú pamäť (angl. "short-term memory")
obsahujúcu určitý počet posledne vyskúšaných riešení a tieto sú v ďalšom
prehíadávaní zakázané ("tabu").

Metropolisov algoritmus
Tento algoritmus je inšpirovaný fyzikálnym javom, keď sa pri postupnom
(dostatočne pomalom) znižovaní teploty látky jej kmitajúce častice ustaíujú v
rovnovážnych polohách. Kmitaniu častíc zodpovedá náhodná malá zmena riešenia
(angl. "perturbation"), podobne ako pri horolezeckom algoritme. Metropolisov
algoritmus sa snaží na rozdiel od horolezeckého algoritmu zabrániť uviaznutiu v
lokálnom extréme tým, že za určitých podmienok prijíma za lepšie riešenie aj
to, ktoré má mierne nižšiu fitness ako predchádzajúce najlepšie riešenie.
"Ochladzovanie" v tejto metóde znamená postupné znižovanie pravdepodobnosti, s
ktorou sa do ďalšieho kroku prijme horšie riešenie.

Simulované žíhanie Algoritmus simulovaného žíhania (angl. "simulated
annealing") je zlepšenou verziou predchádzajúcej metódy. Je to sekvencia
Metropolisových algoritmov s postupne sa znižujúcou teplotou, pričom výstup
predchádzajúceho behu Metropolisovho algoritmu je vstupom behu nasledujúceho.
Dá sa povedať, že na začiatku optimalizačného procesu sa táto metóda podobá
stochastickému prehíadávaniu stavového priestoru (t.j. rovnomerne prehíadáva
celý stavový priestor), ale na konci je to takmer horolezecký algoritmus (t.j.
rýchlo konverguje do lokálneho minima), pričom prechod medzi týmito dvomi
stavmi je plynulý. Metropolisov algoritmus, ale najmä simulované žíhanie patrí
medzi veími silné metódy optimalizácie. Vznikajú tu ale nové problémy, a to s
voíbou parametrov samotného optimalizačného algoritmu. Akú voliť konečnú
"teplotu" (t.j. kedy algoritmus zastaviť)? Ako rýchlo znižovať "teplotu"? Je
potrebné híadať kompromis medzi možným uviaznutím v lokálnom extréme stavového
priestoru (rýchle "ochladzovanie") a neúmerne dlhým časom potrebným na
optimalizáciu (pomalé "ochladzovanie"). Vzniká potreba optimalizovať
optimalizačný algoritmus. Na to sú potrebné explicitné znalosti o riešenej
úlohe.

Genetické algoritmy
V tomto prípade ide o biologicky motivovanú metódu. V každom kroku sa pracuje
nie s jediným riešením, ale z celou množinou riešení, tzv. "populáciou".
Jednotlivé riešenia sa v kontexte genetických algoritmov nazývajú "jedince". V
základnom tvare genetického algoritmu je jedinec nula-jednotkový reťazec
určitej dížky. Nová populácia jedincov sa tvorí genetickými operátormi
"selekcie" (angl. "selection") a prekríženia (angl. "crossover"). Dva jedince z
aktuálnej populácie sa vyberú za rodičov, pričom sa uprednostnia jedince s
vyššou hodnotou fitness (vzniká tzv. "selekčný tlak"). Vymenia sa časti ich
nula-jednotkových reťazcov, čím vzniknú dva nové jedince potomkovia. Títo sa
prípadne mierne pozmenia (mutácia) a zaradia sa do novej populácie. Genetické
algoritmy umožňujú mnohé zlepšenia a modifikácie, čo ich robí jednou z
najsilnejších metód optimalizácie. Dokážu sa úspešne vyhýbať uviaznutiu v
lokálnom extréme, dostatočne prehíadávajú celý stavový priestor, ale rovnako
dokážu rýchlo skonvergovať. Napriek tomu existujú úlohy (tzv. "klamlivé" alebo
"deceptívne"), ktoré sú aj pre genetické algoritmy stále veíkým problémom.

Ďalšie metódy
Existujú aj ďalšie optimalizačné metódy, ktoré sa dokážu vysporiadať aj s
najťažšími úlohami. Pre ich pochopenie je však potrebná bližšia znalosť
genetických algoritmov, z ktorých väčšinou vychádzajú. Sú to metódy
diferenciálnej evolúcie (DE), ich obdoba metóda SADE, a najmä metóda SOMA,
ktorá je napriek svojej jednoduchosti (alebo práve vďaka nej?) veími úspešná aj
pri najťažších úlohách. Za zmienku stojí fakt, že posledne menovaná metóda
vznikla nie tak dávno práve v Českej republike.

Dalšie informácie na WWW
http://www.mat.univie.ac.at/~neum/glopt.html na tejto stránke je možné nájsť o
globálnej optimalizácii takmer všetko. Optimalizačné algoritmy sú rozdelené do
jedenástich tried. Je tu aj prehíad softwaru na optimalizáciu, linky a odkazy
na súvisiace témy. Rovnako tu možno nájsť zoznam odkazov na vyše 150 íudí
zaoberajúcich sa optimalizáciou. http://www.icsi.berkeley.edu/~storn/code.html
domovská stránka Diferenciálnej evolúcie (DE), jedného z najvýkonnejších
optimalizačných algoritmov a jej aplikácia na aproximáciu spojitých funkcií.
Obsahuje históriu, teoretické základy, praktické rady a implementáciu algoritmu
v jazykoch Java, C, MatLab, SciLab, PSather, C++, Fortran a Python.
http://klobouk.fsv.cvut.cz/~ondra/sade/sade.html pojednanie o vysokorozmerných
úlohách, problémoch s lokálnymi extrémami a o algoritme SADE, ktorý má za cieí
zjednodušiť a sprehíadniť algoritmus DE.
http://www.ft.utb.cz/people/zelinka/soma/ SOMA (Self-Organizing Migrating
Algorithm) je veími výkonný optimalizačný algoritmus, ktorý vznikol relatívne
nedávno (1999) v Čechách. Na tejto domovskej stránke možno nájsť jeho
teoretický popis, zdrojové kódy, testovacie funkcie a pripravuje sa aj on-line
demo.
http://alife.fei.tuke.sk/projekty/gen_alg/ stránka o genetických algoritmoch,
ich histórii, fungovaní, modifikáciách a aplikáciách.
http://alife.fei.tuke.sk/projekty/gen_prog/ stránka o genetickom programovaní
ako o špeciálnom prípade evolučných algoritmov.
http://www.genetic-programming.com/ okrem štúdie zameranej na výskum
genetických programov schopných produkovať výsledky porovnateíné s tými, ktoré
objavili íudia tu možno nájsť i popis 1 000uzlového Beovulf-style paralelného
počítača.









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