Evoluční multimodální optimalizace - Evolutionary multimodal optimization

Část seriálu o
Evoluční algoritmus
Genetický algoritmus
Genetické programování

V aplikované matematice se multimodální optimalizace zabývá optimalizačními úkoly, které zahrnují nalezení všech nebo většiny z více (alespoň lokálně optimálních) řešení problému, na rozdíl od jediného nejlepšího řešení. Evoluční multimodální optimalizace je odvětví evolučních výpočtů , které úzce souvisí se strojovým učením . Wong poskytuje krátký průzkum, ve kterém kapitola Shir a kniha Preuss pokrývají toto téma podrobněji.

Motivace

Znalost několika řešení optimalizačního úkolu je obzvláště užitečná ve strojírenství, když kvůli fyzickým omezením (a / nebo nákladům) nemusí být vždy nejlepší výsledky realizovatelné. V takovém scénáři, pokud je známo více řešení (lokálně a / nebo globálně optimální), lze implementaci rychle přepnout na jiné řešení a stále získat nejlepší možný výkon systému. Lze také analyzovat více řešení, aby se zjistily skryté vlastnosti (nebo vztahy) podkladového optimalizačního problému, což je činí důležitými pro získání znalostí domény . Algoritmy pro multimodální optimalizaci navíc obvykle nejen lokalizují více optim v jednom běhu, ale také zachovávají jejich populační rozmanitost, což má za následek jejich schopnost globální optimalizace multimodálních funkcí. Kromě toho se techniky pro multimodální optimalizaci obvykle vypůjčují jako techniky údržby rozmanitosti pro jiné problémy.

Pozadí

Klasické techniky optimalizace by potřebovaly více bodů restartu a více běhů v naději, že při každém běhu může být objeveno jiné řešení, bez jakékoli záruky. Evoluční algoritmy (EA) díky svému populačnímu přístupu poskytují přirozenou výhodu oproti klasickým optimalizačním technikám. Udržují populaci možných řešení, která jsou zpracovávána každou generací, a pokud lze zachovat více řešení přes všechny tyto generace, pak při ukončení algoritmu budeme mít několik dobrých řešení, nikoli jen nejlepší řešení. Všimněte si, že je to proti přirozené tendenci klasických optimalizačních technik, které se vždy sblíží k nejlepšímu řešení nebo k neoptimálnímu řešení (v drsné, „špatně se chovající“ funkci). Nalezení a údržba více řešení spočívá v tom, že výzvou je použití EA pro multimodální optimalizaci. Niching je obecný termín označovaný jako technika hledání a zachování více stabilních výklenků nebo příznivých částí prostoru řešení, případně kolem více řešení, aby se zabránilo konvergenci k jednomu řešení.

Pole evolučních algoritmů zahrnuje genetické algoritmy (GA), evoluční strategii (ES), diferenciální evoluci (DE), optimalizaci roje částic (PSO) a další metody. Byly učiněny pokusy vyřešit multimodální optimalizaci ve všech těchto sférách a většina, ne-li všechny různé metody, implementují výklenky v nějaké formě.

Multimodální optimalizace pomocí genetických algoritmů / evolučních strategií

De Jongova metoda shlukování, Goldbergův přístup ke sdílení funkcí, Petrowskiho clearingová metoda, omezené páření, udržování více subpopulací jsou některé z populárních přístupů, které komunita navrhla. První dvě metody jsou obzvláště dobře studovány, nicméně neprovádějí explicitní rozdělení na řešení patřící do různých povodí přitažlivosti.

Aplikace multimodální optimalizace v rámci ES nebyla po mnoho let explicitní a byla prozkoumána teprve nedávno. Shir představil rámcový výklenek využívající derandomizovaný ES, který poprvé navrhl CMA-ES jako optimalizátor výklenku . Základem tohoto rámce byl výběr vrcholového jedince na subpopulaci v každé generaci, následovaný jeho vzorkováním za účelem následného rozptylu vyhledávacích bodů. Biologické analogie tohoto stroje je alfa-samec vítězný všechny uložené soutěží a následně dominoval jeho ekologické niky , které se pak získává všechny sexuální prostředky v nich pro vytvoření její potomstvo.

Nedávno byl navržen přístup s evoluční multiobjektivní optimalizací (EMO), ve kterém je k původně jednoúčelovému problému multimodální optimalizace přidán vhodný druhý cíl, takže několik řešení tvoří slabou paretooptimální frontu. Problém multimodální optimalizace lze tedy vyřešit u jeho více řešení pomocí algoritmu EMO. Stejní autoři vylepšili svou práci a přizpůsobili svůj algoritmus autopřizpůsobení, čímž eliminovali potřebu předběžného určování parametrů.

Přístup, který nepoužívá žádný poloměr k rozdělení populace na subpopulace (nebo druhy), ale místo toho využívá topologii prostoru, je navržen v.

Hledání více optim pomocí genetických algoritmů v úloze multimodální optimalizace. (Algoritmus předvedený v této ukázce je ten, který navrhl Deb, Saha v multiobjektivním přístupu k multimodální optimalizaci.)

Multimodální optimalizace pomocí DE

Metody specializace používané v GA byly také úspěšně prozkoumány v komunitě DE. Pokusy o lokální výběr a globální výběr založené na DE se také pokusily vyřešit multimodální problémy. DE spolu s místními vyhledávacími algoritmy (Memetic DE) byly prozkoumány jako přístup k řešení multimodálních problémů.

Pro komplexní léčbu metod multimodální optimalizace v DE viz Ph.D thesis Ronkkonen, J. (2009). Kontinuální multimodální globální optimalizace s metodami založenými na diferenciální evoluci .

Multimodální optimalizace pomocí algoritmu GSO založeného na inteligenci roje

Optimalizace roje Glowworm (GSO) je algoritmus založený na inteligenci rojů, který zavedli KN Krishnanand a D. Ghose v roce 2005 pro simultánní výpočet více optim multimodálních funkcí. Algoritmus sdílí několik funkcí s některými známějšími algoritmy, jako je optimalizace kolonií mravenců a optimalizace roje částic , ale s několika významnými rozdíly. Agenti v GSO jsou považováni za žhavé červy, které spolu s sebou nesou luminiscenční množství zvané luciferin. Žhaví červi kódují zdatnost jejich aktuálních poloh, hodnocených pomocí objektivní funkce, do hodnoty luciferinu, kterou vysílají svým sousedům. Žhavá červ identifikuje své sousedy a vypočítá své pohyby využitím adaptivního sousedství, které je výše ohraničeno rozsahem senzorů. Každá žhavka vybere pomocí pravděpodobnostního mechanismu souseda, který má hodnotu luciferinu vyšší než svou vlastní a pohybuje se směrem k němu. Tyto pohyby - založené pouze na místních informacích a selektivních interakcích sousedů - umožňují roj žhavých červů rozdělit se na nesouvislé podskupiny, které se sbíhají na více optimách dané multimodální funkce. Na rozdíl od většiny ostatních evolučních multimodálních optimalizačních algoritmů umožňuje vlastnost rozdělení do podskupin algoritmus simultánně konvergovat k lokálnímu optimu různých hodnot, což je činí vhodným pro řešení problémů s více zdroji signálu pomocí robotů.

Viz také

Reference

Bibliografie

externí odkazy