Mönstersökning (optimering) - Pattern search (optimization)
Mönstersökning (även känd som direkt sökning, derivatfri sökning eller black-box-sökning) är en familj av numeriska optimeringsmetoder som inte kräver en gradient . Som ett resultat kan den användas på funktioner som inte är kontinuerliga eller differentierbara . En sådan mönster sökmetod är "konvergens" (se nedan), som bygger på teorin om positiva baser. Optimering försöker hitta den bästa matchningen (lösningen som har lägst felvärde) i ett flerdimensionellt analysutrymme med möjligheter.
Historia
Namnet "mönster sökning" myntades av Hooke och Jeeves. En tidig och enkel variant tillskrivs Fermi och Metropolis när de arbetade vid Los Alamos National Laboratory . Det beskrivs av Davidon enligt följande:
De varierade en teoretisk parameter åt gången med steg av samma storlek, och när ingen sådan ökning eller minskning av någon parameter förbättrade anpassningen till experimentdata ytterligare halverade de stegstorleken och upprepade processen tills stegen ansågs tillräckligt små.
Konvergens
Konvergens är en mönster sökmetod föreslagen av Yu, som bevisade att den konvergerar med hjälp av teorin om positiva baser. Senare använde Torczon , Lagarias och medförfattare tekniker med positiv bas för att bevisa konvergensen av en annan mönster-sökmetod på specifika funktionsklasser. Utanför sådana klasser är mönstersökning en heuristik som kan ge användbara ungefärliga lösningar för vissa problem, men kan misslyckas på andra. Utanför sådana klasser är mönstersökning inte en iterativ metod som konvergerar till en lösning. faktiskt, mönster-sökmetoder kan konvergera till icke-stationära punkter på vissa relativt tama problem.
Se även
- Golden-sektionen ökning liknar konceptuellt PS i sin förträngning av sökområdet, endast för enkeldimensionella sökning utrymmen.
- Nelder – Mead-metod aka. simplex-metoden liknar begreppsmässigt PS i sin förminskning av sökområdet för flerdimensionella sökutrymmen men gör det genom att upprätthålla n + 1 poäng för n -dimensionella sökutrymmen, medan PS-metoder beräknar 2 n + 1 poäng (den centrala punkten och 2 punkter i varje dimension).
- Luus – Jaakola samplar från en enhetlig fördelning som omger den aktuella positionen och använder en enkel formel för att exponentiellt minska provtagningsområdet.
- Slumpmässig sökning är en relaterad familj av optimeringsmetoder som samlas från en hypersfär som omger den aktuella positionen.
- Slumpmässig optimering är en relaterad familj av optimeringsmetoder som samplar från en normalfördelning som omger den aktuella positionen.
