Luus–Jaakola

Inom beräkningsteknik betecknar Luus–Jaakola (LJ) en heuristik för global optimering av en verkligt värderad funktion. Vid ingenjörsbruk är LJ inte en algoritm som slutar med en optimal lösning; Det är inte heller en iterativ metod som genererar en sekvens av punkter som konvergerar till en optimal lösning (när en sådan finns). Men när den tillämpas på en två gånger kontinuerligt differentierbar funktion är LJ-heuristiken en korrekt iterativ metod, som genererar en sekvens som har en konvergent undersekvens; för denna klass av problem Newtons metod och har en kvadratisk konvergenshastighet, medan ingen konvergenshastighetsanalys har givits för LJ-heuristiken. I praktiken har LJ-heuristiken rekommenderats för funktioner som varken behöver vara konvexa eller differentierbara eller lokalt . .

Föreslagit av Luus och Jaakola genererar LJ en sekvens av iterater. Nästa iteration väljs från ett urval från en grannskap av den aktuella positionen med hjälp av en enhetlig fördelning . Med varje iteration minskar grannskapet, vilket tvingar en undersekvens av iterationer att konvergera till en klusterpunkt.

Luus har tillämpat LJ inom optimal styrning , transformatordesign , metallurgiska processer och kemiteknik .

Motivering

När den aktuella positionen x är långt ifrån den optimala är sannolikheten 1/2 för att hitta en förbättring genom enhetligt slumpmässigt urval.

När vi närmar oss det optimala minskar sannolikheten för att hitta ytterligare förbättringar genom enhetlig sampling mot noll om samplingsintervallet d hålls fast.

Vid varje steg upprätthåller LJ-heuristiken en ruta från vilken den tar punkter slumpmässigt, med hjälp av en enhetlig fördelning på lådan. För en unimodal funktion minskar sannolikheten för att reducera objektivfunktionen när boxen närmar sig ett minimum. Bilden visar ett endimensionellt exempel.

Heuristisk

Låt f : ℝ ⁿ → ℝ vara fitness- eller kostnadsfunktionen som måste minimeras. Låt x ∈ ℝ ⁿ beteckna en position eller en kandidatlösning i sökutrymmet. LJ-heuristiken itererar följande steg:

Initiera x ~ U ( b _lo , b _up ) med en slumpmässig enhetlig position i sökutrymmet, där b _lo och b _up är de nedre respektive övre gränserna.
Ställ in det initiala urvalsintervallet så att det täcker hela sökutrymmet (eller en del av det): d = b _upp − b _lo
Tills ett avslutningskriterium är uppfyllt (t.ex. antal utförda iterationer, eller tillräcklig kondition uppnåtts), upprepa följande:
- Välj en slumpmässig vektor a ~ U (− d , d )
- Lägg till detta till den aktuella positionen x för att skapa den nya potentiella positionen y = x + a
- Om ( f ( y ) < f ( x )) flytta sedan till den nya positionen genom att ställa in x = y , annars minskar samplingsintervallet: d = 0,95 d
Nu har x den bäst hittade positionen.

Variationer

Luus noterar att ARS-algoritmer (Adaptive Random Search) som hittills föreslagits skiljer sig åt i många aspekter.

Procedur för att generera slumpmässiga provpunkter.
Antal interna loopar (NIL, antalet slumpmässiga sökpunkter i varje cykel).
Antal cykler (NEL, antal externa slingor).
Sammandragningskoefficient för sökregionens storlek. (Vissa exempelvärden är 0,95 till 0,60.)
- Om regionreduktionshastigheten är densamma för alla variabler eller en annan hastighet för varje variabel (kallad M-LJ-algoritmen).
- Om regionreduktionshastigheten är en konstant eller följer en annan fördelning (t.ex. Gauss).
Om en radsökning ska införlivas.
Om man ska betrakta begränsningar av de slumpmässiga poängen som acceptanskriterier, eller att införliva ett kvadratiskt straff.

Konvergens

Nair bevisade en konvergensanalys. För två gånger kontinuerligt differentierbara funktioner genererar LJ-heuristiken en sekvens av iterationer med en konvergent undersekvens. För denna klass av problem är Newtons metod den vanliga optimeringsmetoden, och den har kvadratisk konvergens ( oavsett storleken på rummet, vilket kan vara ett Banach-rum , enligt Kantorovichs analys).

Den värsta tänkbara komplexiteten av minimering av klassen av unimodala funktioner växer exponentiellt i problemets dimension, enligt Yudins och Nemirovskys analys. Yudin-Nemirovsky-analysen antyder att ingen metod kan vara snabb på högdimensionella problem som saknar konvexitet:

"Den katastrofala tillväxten [i antalet iterationer som behövs för att nå en ungefärlig lösning med en given noggrannhet] när [antalet dimensioner ökar till oändlighet] visar att det är meningslöst att ställa frågan om att konstruera universella metoder för att lösa ... problem av någon märkbar dimensionalitet 'allmänt'. Det är intressant att notera att samma [slutsats] gäller för ... problem som genereras av uni-extrema [det vill säga unimodala] (men inte konvexa) funktioner."

När den tillämpas på två gånger kontinuerligt differentierbara problem, minskar LJ-heuristikens konvergenshastighet när antalet dimensioner ökar.

Se även

Slumpmässig optimering är en relaterad familj av optimeringsmetoder som samplar från allmänna distributioner, till exempel den enhetliga fördelningen.
Slumpmässig sökning är en relaterad familj av optimeringsmetoder som samplar från allmänna distributioner, till exempel en enhetlig fördelning på enhetssfären .
Mönstersökning används på bullriga observationer, särskilt inom responsytmetodik inom kemiteknik . De kräver inte att användare programmerar gradienter eller hessians.