Optimalizace roje částic (anglicky particle swarm optimization, PSO) je v informatice výpočetní metoda, která optimalizuje problém tím, že se iterativně snaží vylepšit kandidátní řešení s ohledem na danou míru kvality. PSO optimalizuje problém tím, že má populaci kandidátních řešení, zde nazývaných částice, a pohybuje těmito částicemi ve vyhledávacím prostoru podle jednoduchých matematických vzorců přes pozici a rychlost částice. Pohyb každé částice je ovlivněn její místní nejznámější pozicí a je také veden k nejznámějším pozicím ve vyhledávacím prostoru, které jsou aktualizovány tak, jak jsou lepší pozice nalézány jinými částicemi. Očekává se, že to posune roj k nejlepším řešením.
PSO je původně připisováno Kennedymu, Eberhartovi a Shi a původně bylo určeno pro simulaci sociálního chování, jako stylizované znázornění pohybu organismů v hejnu ptáků nebo rybí škole. Algoritmus byl zjednodušen a bylo pozorováno, že provádí optimalizaci. Kniha Kennedyho a Eberharta popisuje mnoho filozofických aspektů PSO a inteligence rojů. Rozsáhlý průzkum aplikací PSO provádí Poli.
PSO je metaheuristika, protože vytváří jen málo nebo vůbec žádné předpoklady o optimalizovaném problému a může prohledávat velmi velké prostory kandidátních řešení. Metheuristiky jako PSO však nezaručují, že se někdy najde optimální řešení. Přesněji řečeno, PSO nepoužívá gradient optimalizovaného problému, což znamená, že PSO nevyžaduje, aby byl optimalizační problém diferencovatelný, jak to vyžadují klasické optimalizační metody, jako je gradientní sestup a kvazi-newtonové metody. PSO lze proto použít i na optimalizační problémy, které jsou částečně nepravidelné, hlučné, mění se v čase atd.
Základní varianta algoritmu PSO funguje tak, že má populaci (tzv. roj) kandidátních řešení (tzv. částice). Tyto částice se pohybují v prohledávaném prostoru podle několika jednoduchých vzorců. Pohyby částic jsou řízeny jejich vlastní nejznámější pozicí v prohledávaném prostoru a také nejznámější pozicí celého roje. Když jsou objeveny vylepšené pozice, tyto pak přijdou usměrnit pohyby roje. Proces se opakuje a tím se doufá, ale není zaručeno, že nakonec bude objeveno uspokojivé řešení.
Formálně nechť f: ℝn → ℝ je nákladová funkce, která musí být minimalizována. Funkce bere jako argument kandidátní řešení v podobě vektoru reálných čísel a produkuje reálné číslo jako výstup, který udává objektivní hodnotu funkce daného kandidátního řešení. gradient f není znám. Cílem je najít řešení a pro které f(a) ≤ f(b) pro všechna b ve vyhledávacím prostoru, což by znamenalo, že a je globální minimum. Maximalizaci lze provést tak, že místo toho vezmeme v úvahu funkci h = -f.
Parametry ω, φp a φg volí aplikující lékař a kontroluje chování a účinnost metody PSO, viz níže.
Performance landscape zobrazující, jak si jednoduchá varianta PSO vede v souhrnu při několika benchmarkových problémech při změně dvou parametrů PSO.
Volba parametrů PSO může mít velký vliv na optimalizační výkon. Výběr parametrů PSO, které přinášejí dobrý výkon, byl proto předmětem mnoha výzkumů.
Parametry PSO lze také vyladit pomocí dalšího překryvného optimalizátoru, což je koncept známý jako meta-optimalizace. Parametry byly také vyladěny pro různé optimalizační scénáře.
Sousedství a topologie
Základní PSO se snadno zachytí do lokálního minima. Této předčasné konvergenci se lze vyhnout tím, že se nepoužije nejznámější poloha celého roje g, ale jen nejznámější poloha l dílčího roje „kolem“ pohybující se částice. Takovým dílčím rojem může být geometrický – například „m nejbližší částice“ – nebo častěji sociální, tj. množina částic, která nezávisí na žádné vzdálenosti. V takovém případě se o variantě PSO říká, že je lokální nejlepší (vs globální nejlepší pro základní PSO).
Předpokládáme-li, že mezi každou částicí a jejími sousedy existuje informační vazba, sestaví soubor těchto vazeb graf, komunikační síť, která se nazývá topologie varianty PSO. Běžně používanou sociální topologií je prstenec, ve kterém má každá částice jen dva sousedy, ale existuje mnoho dalších. Topologie není nutně pevná a může být adaptivní (SPSO, stochastická hvězda, TRIBES, Cyber Swarm, C-PSO).
Existuje několik myšlenkových proudů, proč a jak může algoritmus PSO provádět optimalizaci.
Mezi výzkumníky je rozšířená víra, že chování roje se liší mezi průzkumným chováním, tedy hledáním v širší oblasti hledaného prostoru, a vykořisťovatelským chováním, tedy lokálně orientovaným vyhledáváním, aby se přiblížilo (možná místnímu) optimu. Tento myšlenkový směr převládá již od vzniku ZVS. Tento myšlenkový směr tvrdí, že algoritmus ZVS a jeho parametry musí být zvoleny tak, aby byla správně vybrána rovnováha mezi průzkumem a využíváním, aby se zabránilo předčasné konvergenci k místnímu optimu, ale přesto byla zajištěna dobrá míra konvergence k optimu. Tato víra je předchůdcem mnoha variant ZVS, viz níže.
Jinou myšlenkovou školou je, že chování roje PSO není dobře pochopeno z hlediska toho, jak ovlivňuje skutečný výkon optimalizace, zejména u problémů s vyhledáváním vyšších dimenzí a optimalizací, které mohou být nespojité, hlučné a časově proměnlivé. Tato myšlenková škola se pouze snaží najít algoritmy a parametry PSO, které způsobují dobrý výkon bez ohledu na to, jak lze chování roje interpretovat ve vztahu např. k průzkumu a využití. Takové studie vedly ke zjednodušení algoritmu PSO, viz níže.
Ve vztahu k ZVS slovo konvergence obvykle znamená jednu ze dvou věcí, i když často není objasněno, která definice je myšlena a někdy jsou mylně považovány za totožné.
V literatuře existuje několik pokusů o matematickou analýzu konvergence PSO. Výsledkem těchto analýz byly pokyny pro výběr parametrů PSO, o kterých se předpokládá, že způsobují konvergenci, divergenci nebo oscilaci částic roje, a z analýz také vzešlo několik variant PSO. Nicméně analýzy byly Pedersenem kritizovány za příliš zjednodušené, protože předpokládají, že roj má pouze jednu částici, že nepoužívá stochastické proměnné a že body přitažlivosti, tedy nejznámější poloha částice p a nejznámější poloha roje g, zůstávají konstantní po celou dobu procesu optimalizace. Některé analýzy navíc umožňují nekonečný počet optimalizačních iterací, což není ve skutečnosti možné. To znamená, že určení konvergenčních schopností různých algoritmů a parametrů PSO proto stále závisí na empirických výsledcích.
Vzhledem k tomu, že základní ZVS pracuje dimenzi po dimenzi, bod řešení se snadněji najde, když leží na ose vyhledávacího prostoru, na úhlopříčce, a ještě snadněji, když je přímo uprostřed.
Prvním přístupem, jak se vyhnout tomuto zkreslení, a pro spravedlivé srovnání, je právě použití neobjektivních benchmarkových problémů, které jsou posunuty nebo rotovány.
Dalším přístupem je modifikace samotného algoritmu tak, aby nebyl citlivější na systém souřadnic.
Možné jsou četné varianty i základního PSO algoritmu. Například existují různé způsoby inicializace částic a rychlostí (např. místo toho začít s nulovými rychlostmi), jak rychlost utlumit, pouze aktualizovat pí a g po aktualizaci celého roje atd. Některé z těchto možností a jejich možný dopad na výkon byly diskutovány v literatuře.
Neustále jsou také zaváděny nové a sofistikovanější varianty PSO ve snaze zlepšit výkonnost optimalizace. V tomto výzkumu existují určité trendy; jedním z nich je vytvoření hybridní optimalizační metody pomocí PSO v kombinaci s dalšími optimalizátory, např. začlenění efektivní metody učení. Dalším výzkumným trendem je snaha o zmírnění předčasné konvergence (tedy stagnace optimalizace), např. zvrácením nebo rušením pohybu částic PSO, dalším přístupem k řešení předčasné konvergence je využití více rojů (optimalizace více rojů). Přístup více rojů lze také použít k realizaci multiobjektivní optimalizace. A konečně dochází k vývoji v adaptaci behaviorálních parametrů PSO během optimalizace.
Dalším myšlenkovým proudem je, že PSO by mělo být co nejvíce zjednodušeno, aniž by došlo ke zhoršení jeho výkonu; obecný koncept je často označován jako Occamova břitva. Zjednodušení PSO bylo původně navrženo Kennedym a bylo zkoumáno obsáhleji, kde se ukázalo, že optimalizační výkon byl zlepšen, parametry se snáze ladily a fungovaly konzistentněji napříč různými optimalizačními problémy.
Dalším argumentem ve prospěch zjednodušení PSO je, že metaheuristiky mohou mít svou účinnost prokázanou empiricky pouze provedením výpočetních experimentů na konečném počtu optimalizačních problémů. To znamená, že metaheuristika jako PSO nemůže být prokázána jako správná a to zvyšuje riziko vzniku chyb v jejím popisu a implementaci. Dobrým příkladem toho byla slibná varianta genetického algoritmu (další populární metaheuristika), ale později bylo zjištěno, že je vadná, protože byla silně zaujatá při optimalizačním hledání podobných hodnot pro různé rozměry ve vyhledávacím prostoru, což bylo shodou okolností optimální ze zvažovaných benchmarkových problémů. Toto zaujatí bylo způsobeno programovací chybou a nyní bylo opraveno.
Inicializace rychlostí může vyžadovat dodatečné vstupy. Jednodušší variantou je optimalizace zrychleného částicového roje (APSO), která vůbec nemusí používat rychlost a může zrychlit konvergenci v mnoha aplikacích. K dispozici je jednoduchý demo kód APSO
Multi-objektivní optimalizace
PSO bylo také aplikováno na multiobjektivní problémy, ve kterých objektivní srovnání funkcí bere při přesunu částic PSO v úvahu dominanci pareta a nedominovaná řešení jsou uložena tak, aby se přiblížila čelu pareta.
Binární, diskrétní a kombinační PSO
Vzhledem k tomu, že výše uvedené rovnice PSO fungují na reálných číslech, běžně používanou metodou řešení diskrétních problémů je mapování diskrétního vyhledávacího prostoru na spojitou doménu, aplikace klasického PSO a následná demarkace výsledku. Takové mapování může být velmi jednoduché (například pouhým použitím zaokrouhlených hodnot) nebo sofistikovanější.
Lze však poznamenat, že rovnice pohybu využívají operátory, které provádějí čtyři činnosti:
Obvykle je pozice a rychlost reprezentována n reálnými čísly, a tyto operátory jsou jednoduše -, *, +, a znovu +. Ale všechny tyto matematické objekty mohou být definovány úplně jiným způsobem, aby se vypořádaly s binárními problémy (nebo obecněji diskrétními), nebo dokonce kombinatorickými
. Jedním z přístupů je redefinovat operátory na základě množin.