Mönstersökning (optimering)

För annan användning, se Mönstersökning .

Exempel på konvergens av en direktsökningsmetod på Broyden-funktionen. Vid varje iteration rör sig mönstret antingen till den punkt som bäst minimerar dess objektiva funktion, eller krymper i storlek om ingen punkt är bättre än den aktuella punkten, tills den önskade noggrannheten har uppnåtts, eller så når algoritmen ett förutbestämt antal iterationer.

Mönstersökning (även känd som direktsökning, derivatfri sökning eller svart-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önstersökningsmetod är "konvergens" (se nedan), som bygger på teorin om positiva baser. Optimering försöker hitta den bästa matchningen (den lösning som har det lägsta felvärdet) i ett flerdimensionellt analysutrymme av möjligheter.

Historia

Namnet "mönstersökning" myntades av Hooke och Jeeves. En tidig och enkel variant tillskrivs Fermi och Metropolis när de arbetade på Los Alamos National Laboratory . Det beskrivs av Davidon, enligt följande:

De varierade en teoretisk parameter åt gången i steg av samma storlek, och när ingen sådan ökning eller minskning av någon parameter ytterligare förbättrade anpassningen till experimentdata, halverade de stegstorleken och upprepade processen tills stegen ansågs vara tillräckligt små.

Konvergens

Konvergens är en mönstersökningsmetod som föreslagits av Yu, som bevisade att den konvergerar med hjälp av teorin om positiva baser. Senare Torczon , Lagarias och medförfattare positiva tekniker för att bevisa konvergensen av en annan mönstersökningsmetod på specifika klasser av funktioner. 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önstersökningsmetoder kan konvergera till icke-stationära punkter på några relativt tama problem.

Se även

• Gyllene sektionssökning liknar begreppsmässigt PS i sin inskränkning av sökintervallet, endast för endimensionella sökutrymmen.
• Nelder–Mead metod aka. simplexmetoden liknar begreppsmässigt PS i sin avsmalning av sökintervallet för flerdimensionella sökutrymmen men gör det genom att bibehålla n + 1 punkter för n -dimensionella sökutrymmen, medan PS-metoder beräknar 2 n + 1 punkter (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 samplingsintervallet.
• Slumpmässig sökning är en relaterad familj av optimeringsmetoder som samplar 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.