Luus – Jaakola - Luus–Jaakola

v výpočetní inženýrství, Luus – Jaakola (LJ) označuje a heuristický pro globální optimalizace funkce se skutečnou hodnotou.[1] Ve strojírenském použití není LJ algoritmus která končí optimálním řešením; ani to není iterační metoda který generuje posloupnost bodů, která konverguje k optimálnímu řešení (pokud existuje). Při použití na dvakrát nepřetržitě diferencovatelnou funkci je však heuristika LJ správnou iterační metodou, která generuje sekvenci, která má konvergentní subsekvenci; pro tuto třídu problémů, Newtonova metoda je doporučeno a má kvadratickou míru konvergence, zatímco pro heuristiku LJ nebyla dána žádná analýza rychlosti konvergence.[1] V praxi byla LJ heuristika doporučena pro funkce, které nemusí být ani jedno, ani druhé konvexní ani rozlišitelný ani místně Lipschitz: Heuristika LJ nepoužívá a spád nebo subgradient když je k dispozici, což umožňuje jeho aplikaci na nediferencovatelné a nekonvexní problémy.

Navrhli Luus a Jaakola,[2] LJ generuje posloupnost iterací. Další iterace je vybrána ze vzorku z okolí aktuální pozice pomocí a rovnoměrné rozdělení. S každou iterací sousedství klesá, což nutí posloupnost iterací konvergovat do bodu klastru.[1]

Luus použil LJ v optimální ovládání,[3] [4] design transformátoru,[5] metalurgické procesy,[6] a chemické inženýrství.[7]

Motivace

Když je aktuální poloha X je daleko od optima je pravděpodobnost 1/2 pro nalezení zlepšení pomocí jednotného náhodného výběru vzorků.
Jak se přibližujeme k optimu, pravděpodobnost nalezení dalších vylepšení prostřednictvím jednotného vzorkování klesá směrem k nule, pokud je rozsah vzorkování d je udržována pevná.

V každém kroku heuristika LJ udržuje pole, ze kterého náhodně vzorkuje body, pomocí rovnoměrného rozdělení na poli. Pro unimodální funkce, pravděpodobnost snížení objektivní funkce klesá s přiblížením boxu k minimu. Obrázek zobrazuje jednorozměrný příklad.

Heuristický

Nechat F: ℝn → ℝ je funkce fitness nebo cena, kterou je třeba minimalizovat. Nechat X ∈ ℝn určit pozici nebo kandidáta na řešení ve vyhledávacím prostoru. Heuristika LJ iteruje následující kroky:

  • Inicializovat X ~ U(bhle,bnahoru) s náhodným jednotný pozice ve vyhledávacím prostoru, kde bhle a bnahoru jsou dolní a horní hranice.
  • Nastavte počáteční rozsah vzorkování tak, aby pokryl celý vyhledávací prostor (nebo jeho část): d = bnahoru − bhle
  • Dokud nebude splněno kritérium ukončení (např. Počet provedených iterací nebo dosaženo odpovídající kondice), opakujte následující kroky:
    • Vyberte náhodný vektor A ~ U(−d, d)
    • Přidejte toto k aktuální pozici X k vytvoření nové potenciální pozice y = X + A
    • Pokud (F(y) < F(X)), pak se přesuňte do nové polohy nastavením X = y, jinak zmenšete rozsah vzorkování: d = 0.95 d
  • Nyní X drží nejlépe nalezenou pozici.

Variace

Luus poznamenává, že dosud navržené algoritmy ARS (Adaptive Random Search) se liší v mnoha aspektech.[8]

  • Postup generování náhodných zkušebních bodů.
  • Počet interních smyček (NIL, počet náhodných vyhledávacích bodů v každém cyklu).
  • Počet cyklů (NEL, počet externích smyček).
  • Kontrakční koeficient velikosti oblasti vyhledávání. (Některé ukázkové hodnoty jsou 0,95 až 0,60.)
    • Zda je míra redukce oblasti stejná pro všechny proměnné nebo jiná rychlost pro každou proměnnou (tzv. Algoritmus M-LJ).
    • Zda je míra redukce oblasti konstantní nebo sleduje jiné rozdělení (např. Gaussian).
  • Zda má být začleněno řádkové vyhledávání.
  • Zda považovat omezení náhodných bodů za kritéria přijetí, nebo začlenit kvadratický trest.

Konvergence

Nair prokázal konvergenční analýzu. Pro dvakrát spojitě diferencovatelné funkce generuje heuristika LJ posloupnost iterací majících konvergentní subsekvenci.[1] Pro tuto třídu problémů je Newtonova metoda obvyklou optimalizační metodou a má kvadratická konvergence (bez ohledu na rozměr prostoru, kterým může být a Banachův prostor, podle Kantorovich analýza).

Podle analýzy Yudina a Nemirovského však nejhorší případ minimalizace třídy unimodálních funkcí exponenciálně roste v dimenzi problému. Z Yudin-Nemirovského analýzy vyplývá, že žádná metoda nemůže být rychlá u vysokodimenzionálních problémů, které postrádají konvexnost:

„Katastrofický růst [v počtu iterací potřebných k dosažení přibližného řešení dané přesnosti], protože [počet dimenzí se zvyšuje do nekonečna] ukazuje, že nemá smysl klást otázku konstruování univerzálních metod řešení ... problémů jakékoli znatelné dimenzionality „obecně“. Je zajímavé poznamenat, že stejný [závěr] platí pro ... problémy generované uni-extremálními [tj. unimodálními] (ale ne konvexními) funkcemi. “[9]

Když se použije na dvakrát kontinuálně diferencovatelné problémy, rychlost konvergence LJ heuristiky klesá s rostoucím počtem dimenzí.[10]

Viz také

Reference

  1. ^ A b C d Nair, G. Gopalakrishnan (1979). Msgstr "O konvergenci metody vyhledávání LJ". Journal of Optimization Theory and Applications. 28 (3): 429–434. doi:10.1007 / BF00933384. PAN  0543384.CS1 maint: ref = harv (odkaz)
  2. ^ Luus, R .; Jaakola, T.H.I. (1973). Msgstr "Optimalizace přímým vyhledáváním a systematické zmenšování velikosti vyhledávané oblasti". AIChE Journal. 19 (4): 760–766. doi:10,1002 / aic.690190413.
  3. ^ Bojkov, R .; Hansel, B .; Luus, R. (1993). "Aplikace přímé optimalizace vyhledávání na optimální problémy s řízením". Maďarský žurnál průmyslové chemie. 21: 177–185.
  4. ^ Heinänen, Eero (říjen 2018). Metoda automatického ladění PID regulátoru po optimalizaci Luus-Jaakola (PDF) (Diplomová práce ed.). Tampere, Finsko: Tampere University of Technology. Citováno 1. února 2019.
  5. ^ Spaans, R .; Luus, R. (1992). Msgstr "Důležitost redukce vyhledávací domény při náhodné optimalizaci". Journal of Optimization Theory and Applications. 75: 635–638. doi:10.1007 / BF00940497. PAN  1194836.
  6. ^ Papangelakis, V.G .; Luus, R. (1993). "Optimalizace reaktoru v procesu oxidace tlakem". Proc. Int. Symp. o modelování, simulaci a řízení metalurgických procesů. str. 159–171.
  7. ^ Lee, Y.P .; Rangaiah, G.P .; Luus, R. (1999). "Výpočty fázové a chemické rovnováhy přímou optimalizací vyhledávání". Počítače a chemické inženýrství. 23 (9): 1183–1191. doi:10.1016 / s0098-1354 (99) 00283-5.
  8. ^ Luus, Rein (2010). „Formulace a ilustrace optimalizačního postupu Luuse-Jaakoly“. V Rangalah, Gade Pandu (ed.). Stochastická globální optimalizace: techniky a aplikace v chemickém inženýrství. World Scientific Pub Co Inc. str. 17–56. ISBN  978-9814299206.
  9. ^ Nemirovsky & Yudin (1983, str. 7)

    Stránka 7 shrnuje pozdější diskusi o Nemirovsky & Yudin (1983, s. 36–39): Nemirovský, A. S .; Yudin, D. B. (1983). Složitost problému a účinnost metody v optimalizaci. Wiley-Interscience Series in Discrete Mathematics (Přeložil E. R. Dawson z (1979) Russian (Moscow: Nauka) ed.). New York: John Wiley & Sons, Inc., s. Xv + 388. ISBN  0-471-10345-4. PAN  0702836.CS1 maint: ref = harv (odkaz)

  10. ^ Nair (1979, str. 433)

Nemirovský, A. S .; Yudin, D. B. (1983). Složitost problému a účinnost metody v optimalizaci. Wiley-Interscience Series in Discrete Mathematics (Přeložil E. R. Dawson z (1979) Russian (Moscow: Nauka) ed.). New York: John Wiley & Sons, Inc., s. Xv + 388. ISBN  0-471-10345-4. PAN  0702836.