PSOptimizer

PSOptimizer je velice rychlý optimalizátor založený na metodě rojení částic (PSO, particle swarm optimization). Vstup i výstup jsou obecné a založené na datovém formátu PsoData, proto je PSOptimizer vhodný pro řešení libovolných úloh, jejichž kriteriální funkci (fitness function) lze definovat pomocí Matlab .m funkce. Jedná se o jednokriteriální multidimenzionální optimalizátor.

• psoptimizer1.3.zip
• nejnovější verze: 1.3
• dostupná verze: 1.3
• vývoj softwaru: 2008-2009, 2010-2011
• autoři: Miloslav Čapek, Pavel Hazdra (všichni K13117, katedra elektromagnetického pole)
• kontakt: miloslav.capek@fel.cvut.cz

Pro nekomerční využití je tento program zdarma. Tento kód je volně šiřitelný, avšak jeho užití je podmíněno souhlasem autorů.

Poznámka: V textu je popsán i postprocessing pomocí PSOpost. Tento nástroj není zatím volně šiřitelný - případní zájemci o aplikaci PSOpost nechť kontaktují autory.

V mnoha vědních oblastech je nezbytnou součástí návrhu systému jeho optimalizace. Důvodem je prostý fakt, že ne vše lze jednoduše spočítat. Pro funkci hledáme bod takový, že:



Hledáme-li maximum, invertujeme kritérium funkce. Předpokládáme neprázdnou množinu , funkci nazýváme objektivní funkcí (objective function), v souvislosti s PSO často též jako fitness funkci (fitness function, dále jen f.f.).

Obecně můžeme optimalizační techniky rozdělit do dvou skupin: deterministické a pravděpodobnostní. PSO patří do druhé skupiny, neboť pozice jednotlivých členů hejna je spoluurčena náhodně generovanými čísly (více dále). Tak lze efektivně odolat konvergenci do lokálního minima funkce.

Optimalizace vychází z rojové inteligence pozorované např. u včelstev a napodobuje jejich vzorce chování. V některých aspektech je PSO podobná ACO, v jiných můžeme nalézt paralelu s GA. Ve všech případech jde o samo se organizující systémy vykazující silné kolektivní chování. Zásadní rozdíl však spočívá v přístupu k členu hejna (agentovi), nad kterým jsou definovány určité operace a disponuje částí znalostí, které má celý roj. Tento princip je vysoce efektivní a dosahuje skvělých výsledků. Jistě ne nadarmo můžeme stejné vzorce chování odhalit u hejna ptáků, roje včel, ryb atp.

Vlastní algoritmus izoloval roku 1995 Eberhart na základě simulací které provedl J. Kennedy. Od té doby vznikla celá řada studií a výzkumů, které PSO využívají. Její význam dokládá i fakt, že byla zařazena jako optimalizační metoda do nové verze CST MWS. Mezi velké výhody patří zejm. rychlost, jednoduchost, robustnost, odolnost vůči uvíznutí v lokálním minimu, využitelnost na velký soubor problémů a malé režijní nároky na výpočet. Stejně jako jiné komplexní optimalizační metody je pro správnou funkci nutné vhodně nastavit jednotlivé parametry (na které je PSO velice citlivé, viz dále). Nyní se věnujme vlastnímu principu PSO.

Idea vychází z existence určitého počtu agentů, kteří jsou rozmístěni nad optimalizovanou funkcí. Plochu funkce, tedy na které její části budeme minimum hledat, stanoví uživatel. Tento prostor se nazývá solution space (dále jen s.s.). Situaci zobrazuje obrázek napravo. Agenti se snaží nalézt minimum kdekoliv v s.s. (v případě obr. maximum, totiž místo s nejvíce květy). V mnoho aplikacích nemá řešení mimo s.s. smysl (v našem případě by mohla být vedle definované louky např. řeka, kde sledovat hustoru květů nemá smysl), proto se snažíme udržet agenty v určeném prostoru. Způsoby jak toho dosáhnout probereme později.

Každý agent si pamatuje svůj dosavadní nejlepší objev pbest, proměnná v rovnici (1). Nejlepší objev celého hejna (gbest, ) je potom tím nejlepším ze všech osobních objevů. Chování jednotlivých agentů popisují následující dva vztahy. Nejprve uveďme výpočet rychlosti agenta. Rychlost je stanovena v každé iteraci pro každého agenta zvlášť a ovlivňuje směr, jímž se pohybuje. Počet složek tohoto vektoru je rovný dimenzi (index d) řešeného problému.

(1)

V Matlabu je potřeba vsadit tuto rovnici do for cyklu, čímž je zajištěno procházení celého hejna (index i označuje agenty). Zabalením do dalšího for cyklu umožníme iterování celého problému od do (paralela k jednotlivým generacím u GA). Dále je nutno objasnit význam zbylých proměnných a konstant.

Koeficient je často nazýván váhovací faktor (weighted factor). Může být po celou dobu optimalizace konstantní, nebo se může měnit (potom je zadávana dvojice parametrů a ). Klesající koeficient zabraňuje nepříjemným oscilacím a zároveň stimuluje hejno ke konvergenci nad nalezeným globálním minimem. Parametry a udávají, nakolik bude výsledná rychlost odvozena od osobního minima daného agenta a nakolik od společného globálního min. Jejich optimální velikost bude diskutována v dále. Bez komentáře zůstaly již pouze hodnoty a . V obou případech se jedná o náhodně generovaná čísla s normálním rozložením v rozsahu (0,1).

Víme-li již, jakým směrem a jak rychle se pohybují agenti, můžeme aktualizovat jejich pozici:

(2)

Rovnice (2) odpovídá pohybové rovnicí. Nové umístění agenta tedy získáváme jako součet koordinátů v minulé iteraci pozměněné o pohyb v současné iteraci. Protože může obecně nabývat libovolných hodnot, lze přiřadit (jednotkový, diskrétní čas).

Vztahy uvedené výše žádným způsobem neomezují pohyb agentů, mohou tedy opustit s.s. Z toho důvodu bylo navrženo několik technik, které zajistí, aby se agenti nerozběhli daleko za hranice s.s. Mezi nejcitovanější a nejužívanější patří následující:

• Omezení maximální rychlosti agenta ()

Ohraničující zdi:

• Absorbční zeď (Absorbing Wall)
• Odrazná zeď (Reflecting Wall)
• Neviditelná zeď (Invisible Wall)

První uvedená možnost, tedy omezení rychlosti agentů, není příliš vhodná. Rychlost je totiž omezena i uvnitř s.s. Lepším řešením je použití jedné ze zdí. Ty popisují způsob, jakým je naloženo s agentem, pokud překročí povolené hranice. Neovlivňují průběh optimalizace uvnitř s.s. a navíc, pokud již agent opustil prohledávaný prostor, ho efektivně nasměrují zpět.


V případě absorbční zdi je s.s. lemován pomyslným mantinelem. Ta složka rychlosti, která vede ven ze s.s. je nulována, agent se tedy pohybuje pouze podél ohraničení. Odrazná zeď uprostřed obrázku napravo též obsahuje stěnu. Namísto vynulování je však složce rychlosti v nežádnoucím směru obrácena orientace (znaménko) a agent se tedy od stěny odrazí. Tyto dvě zdi využívají stejného principu, a to úpravy rychlosti.

Užitím odrazné zdi umožníme agentům vyletět ze s.s., ovšem po jeho opuštění není vyhodnocována f.f. To zapříčíní pozvolný návrat agentů zpět do s.s. Velkou předností je výrazná úspora výpočetního času, poněvadž jsou vyhodnocována pouze ta schémata, o která se skutečně zajímáme. I z tohoto důvodu se jedná o pravděpodobně nejlepší řešení pro většinu inženýrských problémů. Tento typ zdi je implementován v PSOptimizeru.

Na závěr zrekapitujme důležité parametry PSO optimalizace v tabulce:

Parametr
	poznávací parametr (cognitive rate)
	sociální parametr (social rate)
	váhovací koeficient (na konci optimalizace)
	váhovací koeficient (na začátku optimalizace)
	časová konstanta, zpravidla jednotkový čas
iterace	počet iterací (vliv velikosti iterací viz níže)
počet agentů	počet agentů nad s.s. (viz níže)
	(současné) individiální nalezené minimum agenta ()
	(současné) globální nalezené minimum agenta ()

Na základě NFL (No Free Lunch) teorému můžeme tvrdit, že ne všechny optimalizační metody se hodí na všechny problémy (závěr tohoto tvrzení je mj. ten, že nelze jednotlivé metody porovnávat přímo pro vybraný problém). Půjdeme-li dále, lze tvrdit, že dokonce každá úloha je (statisticky) nejrychleji vyřešena s jiným nastavením a jinými parametry. Jaké jsou tedy tyto 'optimální' parametry (, , , , počet iterací a agentů, typ zdi atd.) v případě PSO?

Omezíme se zde na velice stručnou sadu doporučení, neboť komplexní odpověď je nad rámec tohoto textu. Pro konstanty a navrhoval Kennedy v roce 1998 hodnoty 2. Postupem času byla podmínka specifikována přesněji, totiž na rovnici: . Dvojice parametrů a by měla být dostatečně rozdílná, avšak respektovat poměry v rovnici (1). Počet agentů se doporučuje min. 10 a jednu dimenzi problému (tj. min. 10 pro minimalizaci kvadratické rovnice uvedené dále, min. 20 pro minimalizaci 2D funkce Levy5). Počet iterací závisí na požadované přesnosti řešení a na předpokládané složitosti fitness funkce. Defaultně jsou parametry v PSOptimizeru zvoleny následovně:

Parametr	defaultní hodnota	volitelné?
	2	ano
	2	ano
	0.4	ne
	0.9	ne
iterace	20	ano
počet agentů	50	ano
typ zdi	invisible	ne

Máme-li vytvořený optimalizační algoritmus, je vhodné otestovat jeho účinnost - tj. schopnost najít globální minimum různých funkcí pro daný počet iterací a agentů. V současné době existuje velké množství testovacích funkcí, u kterých jsou známa lokální i globální minima a jejich složitost. Můžeme tak jednoduše porovnat PSO algoritmus s ostatními.

Mezi nejčastěji využívané testovací funkce patří:

• Levy funkce č.3
• Levy funkce č.5
• Rosenbrockovo sedlo
• Rastriginova funkce
• Ranova funkce
• Schwefelova funkce
• Griewangkova funkce
• Ackleyho funkce č.2
• 4. de Jongova funkce
• 3. de Jongova funkce
• Mastersovo kosinus funkce
• celá řada 'patologických' funkcí
• a další…

Stále častěji jsou však pro testy využívány náhodně generované funkce, které lépe testují robustnost vybraného algoritmu. Následující obrázky zobrazují některé z klasických testovacích funkcí:
Levy3 funkce, s.s. 20×20


Levy5 funkce, s.s. 20×20

kde




Rosenbrockova funkce, s.s. 20×20



Rastrigrinova funkce, s.s. 10×10



3. de Jongova funkce, s.s. 2×2


Ackleyho II. funkce, s.s. 40×40



Natažená sinus-V vlna (Stretched V sin wave), s.s. 20×20

Funkce jsou zpravidla obecně popsány pro prostor, my však využíváme pouze 2-dimenzionální případy. Většina z vyjmenovaných funkcí je přiložena do balíku s PSOptimizerem, vč. vykreslení průběhu. Některé z uvedených funkcí jsou popsány v odstavci s vybranými příklady (dále).

GUI programu je navržen tak, aby byl jednoduchý, ale zároveň podrobně informoval o stávajícím stavu optimalizace. Text v levém rámu zobrazuje nastavené výchozí parametry, v pravé části potom aktuální průběh. Stupnice na ose y grafu zobrazujícího cost funkci je v (zde názornějším) logaritmickém měřítku. Tlačítko 'Exit' ukončuje optimalizaci, nejdříve však po dokončení dané iterace (tj. vypočte hodnotu fitness funkce pro zbylé agenty). I v tomto případě jsou do základního pracovního prostoru uloženy a vráceny výsledky, kterých bylo dosaženo.

Syntaxe volání PSOptimizeru je následující:

Kde PSOptimizer je název funkce, PsoData obsahuje veškerá data potřebná pro optimalizaci vybrané funkce, 'fitnessFunction' je název mfile souboru, který obsahuje fitness funkci a má hlavičku, která bude popsána dále. ag je celé kladné číslo, označující počet agentů optimalizace, it značí počet iterací. Parametry c1 a c2 není zpravidla potřeba zadávat, ale je to možné (viz 3 řádek tabulky). Parametry, jež uživatel přímo nezadá jsou dosazeny následovně: ag = 20, it = 50, c1 = 2, c2 = 2. Výsledek res potom obsahuje všechny informace o průběhu optimalizace, nalezené minumum a jeho parametry. Struktury PsoData i res mají složitější strukturu a jsou proto popsány samostatně dále.

Poznámka: Jak již bylo uvedeno, zvláštní pozornost si zaslouží hlavička fitness funkce, definovaná uživatelem. Její první parametr je 'eval' (tento příznak je určen pro větší mfily, které neslouží pouze pro vyhodnocení fitness funkce - tato situace nastavá například u našeho modálního řešiče EvalInFem, kde je tento příznak aktivně využíván). Data poslaná do fitness funkce obsahují, krom slotů data1-data3 s aktuálními daty rovněž pole .type s hodnotou 'psoRun'. Tato hodnota značí, že PSO právě běží a data pocházejí z funkce PSOptimizer. Těchto znalostí lze využít při efektivnějším psaní optimalizačních úloh.

Příklad krátké fitness funkce určené pro optimalizaci minima kvadratické funkce:

function fitnessValue = testedFunc_Levy5(sign, varargin)
%% inicializace vstupních dat (single/parallel řešení)
if strcmp(sign,'eval')
    x1 = varargin{1}.data1(1);
    x2 = varargin{1}.data1(2);
else
    fitnessValue = inf;
    return;
end

%% vlastní řešení kvadratické funkce
% minimum je v x1 = 0, jeho velikost je: -10
fitnessValue = x1^2 - 10;

Situace se zpřehlední po uvedení příkladů optimalizace níže.

Vstupní formát PsoData je zcela univerzální a zcela definuje danou optimalizační úlohu. Obsahuje následující pole:

Pole .data1-3 mohou obsahovat matice s parametry potřebnými pro výpočet volané úlohy. Některé (nebo všechny) z těchto parametrů mohou být optimalizované. Velikost matic je libovolná, vždy však musí být všechny tři matice definovány (alespoň jako prázdné). Počet slotů volíme tak, aby byl dostatečný pro řešení IFS antén (body základního útvaru, transformace a iterační matice). Dalším polem je PsoData.type, které je fixně zadáno string řetězcem 'psopt'. Pole je potřeba při identifikaci příchozích dat uvnitř funkce. PsoData.rank je nepovinný údaj, jenž koresponduje s dimenzí optimalizace. Na závěr zde figurují pole PsoData.bound, ve kterém jsou uloženy hranice definující s.s. a také PsoData.cond, určující, které z parametrů v slotech data1-3 mají být optimalizována. Způsob zápisu je následující:

ProData.bound{dimenze} = [min max],

a

ProData.cond{dimenze} = [Ai Bi Ci],

kde matice Ai, Bi a Ci jsou sloupcové o velikosti (i,1). Indexy Ai(i) obsahují čísla 1-3, odkazující na jeden ze slotů data1-3, matice Bi(i) ukazují na řádku daného slotu a konečně Ci(i) potom značí pozici na řádce (číslo sloupce). Hodnota na této pozici (pozici dimenze) je optimalizována pomocí PSO algoritmu v rozmezí [min a max]. Těchto hodnot může být více (dimenze = 1, dimenze = 2, atd.). Dokonce pro jedny meze (např. dimenze = 1) může být optimalizováno více hodnot najednou (velikost matic A,B a C je větší než 1, i > 1). Takto lze „svázat“ více parametrů do svazku, který se optimalizuje najednou s jednou dvojicí hranic [min max]. Tohoto využíváme zejm. při optimalizaci IFS struktur, viz dále.

Výstupní pole obsahuje opět sloty data1-3, patřičné hodnoty jsou ale optimalizovány. Hodnota fitness funkce pro tyto je uvedena v res.score. Pole res.done referuje o zdárném ukončení PSO; res.done = true/false (určeno jako návěstí pro nadřazené programy). res.options uvádí hodnoty, za kterých byla optimalizace dokončena a konečně res.history obsahuje většinu vnitřních stavů PSOptimizeru v každé iteraci. Tato pole lze využít např. pro vykreslení cost funkce nebo pro vykreslení pozice jednotlivých agentů v dané iteraci.

V souvislosti s optimalizací nás mnohdy nezajímá pouze vlastní výsledek (geometrie koláže s nejnižší rezonanční frekvencí, požadovaným VD atp.). Chceme znát i průběh optimalizace, chování jednotlivých agentů, jak vypadá prohledávaná funkce a míra efektivity celého hejna. Přirozeně, abychom tyto informace získali, musíme zahrnout do PSO další techniky.

Pro dynamické zobrazení průběhu optimalizace byl vytvořen program PSOPost. Náhled ukazuje obrázek napravo (vč. barevných isočár funkčních hodnot Griewangkovy funkce). V tuto chvíli je promítání optimalizace omezeno na dvě existující dimenze (PsoData.rank = 2). Počítáme však s rozšířením do 3D, kdy jednotlivé podmínky půjdou zvolit (neomezený počet podmínek). Do programu byl dodatečně připojen výpočet rozptylu agentů, později i výpočet všech, kteří překročili hranice s.s. Tyto hodnoty jsou i real-time vykreslovány do grafů vpravo. Je možné zobrazit i směrové vektory všech agentů.

Ovládací rozhraní je jednoduché. Obsahuje tlačítka na spuštění videa, jeho pauzu (opětovné spuštění restartuje video) a tlačítka na reset plátna a ukončení programu. Funkce může být volána s celou řadou parametrů a nastavení:

Následuje ukázka chování roje a optimalizace funkce Levy5 na prostoru 20×20. Jsou zobrazeny i skutečné funkční hodnoty, které byly pro tyto účely zvlášť vypočteny:

Vstupní proměnná PsoData může být generována jakýmkoliv způsobem. PSOptimizer lze proto zařadit do optimalizační smyčky s libovolným vhodně navrženým programem. Díky tomu lze propojit generování fraktálu ve formátu FRC s jeho optimalizací pro zvolené kritérium. Nastavení mezí optimalizace zajišťuje IFSLimiter (polí PsoData.bound a PsoData.cond, pole PsoData.data1 = FRC.base, PsoData.data2 = FRC.tran a PsoData.data3 = FRC.iter). Výstup optimalizace poskytuje aktuální data každou iteraci, i souhrnná data po jejím ukončení - lze tak analyzovat celý průběh a tomu přizpůsobit další strategii.

Dále viz:

• generátor IFS fraktálů (IFSMaker)
• nastavení mezí pro PSO (IFSLimiter)
• modální řešič TCMapp
• modální řešič EvalInFem

Schéma propojení jednotlivých programů:

Práce na této aplikaci byly pozastaveny, modul je plně funkční. Výhledově však počítáme s těmito úpravami:

1. hledání mnohonásobných globálních minim (doposud je nalezeno jen jedno)
2. rozšířit působnost algoritmu i pro GA (genetické algoritmy) a SOMA algoritmus
3. úprava / vytvoření nového multikriteriálního optimalizátoru (MOPSO)
4. přímé propojení s postprocessingovým nástrojem (vizualizace pohybu roje, rozptylu a efektivity pohybu roje)
5. rozšíření o absorbční (absorbing) odraznou (reflecting) zeď

— Miloslav Čapek 2012/01/03 23:03