Tilfeldig optimalisering - Random optimization

Tilfeldig optimalisering (RO) er en familie med numeriske optimaliseringsmetoder som ikke krever at gradienten av problemet skal optimaliseres og RO kan følgelig brukes på funksjoner som ikke er kontinuerlige eller differensierbare . Slike optimaliseringsmetoder er også kjent som direktesøk, derivatfrie eller black-box-metoder.

Navnet tilfeldig optimalisering tilskrives Matyas som tidlig presenterte RO sammen med grunnleggende matematisk analyse. RO fungerer ved iterativt å flytte til bedre posisjoner i søkeområdet som blir samplet ved hjelp av f.eks. En normalfordeling rundt den nåværende posisjonen.

algoritme

La f : ℝ ⁿ  → ℝ være egnethets- eller kostnadsfunksjonen som må minimeres. La x  ∈ ℝ ⁿ utpeke en stilling eller kandidatløsning i søkeområdet. Den grunnleggende RO-algoritmen kan deretter beskrives som:

• Initialiser x med en tilfeldig plassering i søkeområdet.
• Inntil et avslutningskriterium er oppfylt (f.eks. Antall iterasjoner som er utført eller oppnådd tilstrekkelig egnethet), gjenta følgende:
  • Prøv en ny posisjon y ved å legge til en normalt distribuert tilfeldig vektor til den nåværende posisjonen x
  • Hvis ( f ( y ) <  f ( x )), flytter du til den nye stillingen ved å stille inn x  =  y
• Nå innehar x den best funnet posisjonen.

Denne algoritmen tilsvarer en (1 + 1) evolusjonsstrategi med konstant trinnstørrelse.

Konvergens og varianter

Matyas viste den grunnleggende formen for RO konvergerer til det optimale for en enkel unimodal funksjon ved å bruke et grensesikkert som viser at konvergens til det optimale er sikkert å oppstå hvis et potensielt uendelig antall iterasjoner blir utført. Dette beviset er imidlertid ikke nyttig i praksis fordi et begrenset antall iterasjoner bare kan utføres. Faktisk vil en slik teoretisk grensesikkerhet også vise at rent tilfeldig prøvetaking av søkeområdet uunngåelig vil gi en prøve vilkårlig nær det optimale.

Matematiske analyser blir også utført av Baba og Solis og Wets for å fastslå at konvergens til et område som omgir det optimale er uunngåelig under noen milde forhold for RO-varianter ved bruk av andre sannsynlighetsfordelinger for prøvetakingen. Et estimat på antall iterasjoner som kreves for å nærme seg det optimale er avledet av Dorea. Disse analysene blir kritisert gjennom empiriske eksperimenter av Sarma som brukte optimeringsvariantene av Baba og Dorea på to problemer i den virkelige verden, og viser at det optimale å bli nærmet veldig sakte og dessuten at metodene faktisk ikke var i stand til å finne en løsning med tilstrekkelig egnethet, med mindre prosessen ble startet tilstrekkelig nær det optimale til å begynne med.

Se også

• Tilfeldig søk er en nær beslektet familie av optimaliseringsmetoder som prøver fra en hypersfære i stedet for en normalfordeling.
• Luus – Jaakola er en nær beslektet optimaliseringsmetode som bruker en enhetlig distribusjon i prøvetakingen og en enkel formel for eksponentielt å redusere prøvetakingsområdet.
• Mønstersøk tar skritt langs aksene i søkeområdet ved å bruke eksponentielt reduserende trinnstørrelser.
• Stokastisk optimalisering

referanser