Slumpmässig sökning - Random search
Slumpmässig sökning (RS) är en familj av numeriska optimeringsmetoder som inte kräver att problemets gradient ska optimeras, och RS kan därför användas på funktioner som inte är kontinuerliga eller differentierbara . Sådana optimeringsmetoder är också kända som direktsökningsmetoder, derivatfria eller svarta rutor.
Namnet "slumpmässig sökning" tillskrivs Rastrigin som gjorde en tidig presentation av RS tillsammans med grundläggande matematisk analys. RS fungerar genom att iterativt flytta till bättre positioner i sökutrymmet, som samplas från en hypersfär som omger den aktuella positionen.
Algoritmen som beskrivs häri är en typ av lokal slumpmässig sökning, där varje iteration är beroende av den tidigare iterationens kandidatlösning. Det finns alternativa slumpmässiga sökmetoder som samplar från hela sökutrymmet (till exempel ren slumpmässig sökning eller enhetlig global slumpmässig sökning), men dessa beskrivs inte i denna artikel.
Algoritm
Låt f : ℝ n → ℝ vara fitness- eller kostnadsfunktionen som måste minimeras. Låt x ∈ ℝ n utse en position eller kandidatlösning i sökutrymmet. Den grundläggande RS-algoritmen kan sedan beskrivas som:
- Initiera x med en slumpmässig position i sökutrymmet.
- Tills ett uppsättningskriterium är uppfyllt (t.ex. antal utförda iterationer eller tillräcklig träning har uppnåtts), upprepa följande:
- Exempel på en ny position y från hypersfären av en given radie som omger den aktuella positionen x (se t.ex. Marsaglias teknik för provtagning av en hypersfär.)
- Om f ( y ) < f ( x ) flyttar du till den nya positionen genom att ställa in x = y
Varianter
Ett antal RS-varianter har introducerats i litteraturen:
- Fixed Step Size Random Search (FSSRS) är Rastrigins grundläggande algoritm som samplar från en hypersfär med fast radie.
- Optimal stegstorlek slumpmässig sökning (OSSRS) av Schumer och Steiglitz är främst en teoretisk studie om hur man optimalt kan justera hypersfärens radie för att möjliggöra snabb konvergens till det optimala. En faktisk implementering av OSSRS måste approximera denna optimala radie genom upprepad provtagning och är därför dyr att utföra.
- Adaptive Step Size Random Search (ASSRS) av Schumer och Steiglitz försöker heuristiskt anpassa hypersfärens radie: två nya kandidatlösningar genereras, en med den aktuella nominella stegstorleken och en med en större stegstorlek. Den större stegstorleken blir den nya nominella stegstorleken om och bara om det leder till en större förbättring. Om inget av stegen för flera iterationer leder till en förbättring minskas den nominella stegstorleken.
- Optimerad relativ stegstorlek slumpmässig sökning (ORSSRS) av Schrack och Välj ungefär den optimala stegstorleken med en enkel exponentiell minskning. Formeln för beräkning av minskningsfaktorn är dock något komplicerad.
Se även
- Slumpmässig optimering är en nära besläktad familj av optimeringsmetoder som samlas från en normalfördelning istället för en hypersfär.
- Luus – Jaakola är en närbesläktad optimeringsmetod som använder en enhetlig fördelning i provtagningen och en enkel formel för att exponentiellt minska provtagningsområdet.
- Mönstersökning tar steg längs axlarna i sökutrymmet med exponentiellt minskande stegstorlekar.
