Simulerad glödgningsalgoritm

Simulerad annealing- algoritm är en allmän algoritmisk metod för att lösa ett globalt optimeringsproblem, särskilt diskret och kombinatorisk optimering . Ett exempel på Monte Carlo metoder .

Allmän beskrivning

Algoritmen är baserad på simulering av den fysiska process som sker under kristalliseringen av ett ämne , inklusive glödgning av metaller . Det antas att materiens atomer redan nästan är uppradade i ett kristallgitter , men övergångar av enskilda atomer från en cell till en annan är fortfarande acceptabla. Atomernas aktivitet är ju större desto högre temperatur , som gradvis sänks, vilket leder till att sannolikheten för övergångar till tillstånd med högre energi minskar. Ett stabilt kristallgitter motsvarar atomernas lägsta energi, så atomen går antingen in i ett tillstånd med en lägre energinivå eller förblir på plats. (Denna algoritm kallas även N. Metropolis- algoritmen , efter dess författare).

Simulering av en liknande process används för att lösa ett globalt optimeringsproblem, som består i att hitta en sådan punkt eller uppsättning punkter där minimum av någon objektiv funktion ("systemenergi") uppnås, där ( är "tillståndet för system", är uppsättningen av alla tillstånd). $F(x)$ ${x}\in X$ ${x}$ $X$

Algoritmen för att hitta minimum genom glödgningssimuleringsmetoden antar en fri inställning:

${x_{0}}\in X$ — Systemets initiala tillstånd.
en operatör som slumpmässigt genererar ett nytt tillstånd för systemet efter det i-te steget, med hänsyn till det aktuella tillståndet (denna operatör ska å ena sidan ge en ganska fri slumpmässig promenad i rymden och å andra sidan arbeta målmedvetet i viss utsträckning, säkerställa sökhastighet); $A({x},i):X\times \mathbb {N} \to X$ ${x}$ $X$
$T_{i}>0$ — minskande till noll positiv sekvens, vilket ställer in analogen för sjunkande temperatur i kristallen. Nedkylningshastigheten (minskande lag) kan också ställas in (och varieras) godtyckligt, vilket ger algoritmen avsevärd flexibilitet.

Algoritmen genererar en process av slumpmässig vandring över tillståndsutrymmet . Lösningen söks genom successiv beräkning av punkter i rymden ; varje punkt, med början från , "påstår sig" approximera lösningen bättre än de tidigare. Vid varje steg beräknar algoritmen (som beskrivs nedan) en ny punkt och sänker värdet på den (initialt positiva) kvantitet som förstås som "temperatur". $X$ ${x_{0)),\;{x_{1)),\;{x_{2)),\;\ldots ,\;$ $X$ ${x_{1))$

Sekvensen av dessa punkter (tillstånd) erhålls enligt följande. Operatören appliceras på punkten , vilket resulterar i en kandidatpoäng för vilken motsvarande förändring i "energi" beräknas . Om energin minskar ( ), övergår systemet till ett nytt tillstånd: . Om energin ökar ( ), kan övergången till ett nytt tillstånd endast ske med en viss sannolikhet, beroende på storleken på energiökningen och den aktuella temperaturen, i enlighet med Gibbs distributionslag : ${x_{i))$ $A$ ${x_{i}^{*}}=A(x_{i},i)$ $\Delta F_{i}=F({x_{i}^{*)))-F({x_{i)))$ $\Delta F_{i}\leq 0$ ${x_{i+1}}={x_{i}^{*}}$ $\Delta F_{i}>0$

P({x_{i}^{*}}\to {x_{i+1}}\mid {x_{i}})=\exp(-\Delta F_{i}/{T_{i }})

Om övergången inte inträffade förblir systemets tillstånd detsamma: . Algoritmen stannar när den når en punkt som visar sig vara vid noll temperatur. ${x_{i+1}}={x_{i}}$

Simuleringsglödgningsalgoritmen liknar gradientnedstigning , men på grund av slumpmässigheten i valet av mellanpunkt och förmågan att ta sig ur lokala minima, bör det vara mindre sannolikt att fastna i lokala, men inte globala minima än gradientnedstigning. Den simulerade glödgningsalgoritmen garanterar inte att man kan hitta funktionens minimum, men med den korrekta inställningen att generera en slumpmässig punkt i rymden uppstår som regel en förbättring av den initiala approximationen. $X$

Applikation

Utbildning av neurala nätverk
Att lösa kombinatoriska problem, till exempel problemet med att placera damer
Att lösa problemet med resande säljare [1]

Se även

Kvantglödgningsmetod

Anteckningar

↑ Problemet med Hamiltons cykel . Hämtad 19 februari 2014. Arkiverad från originalet 25 februari 2014. (obestämd)

Litteratur

Callan Robert. Grundläggande begrepp för neurala nätverk. - M. : Williams Publishing House, 2003. - 288 sid. — ISBN 5-8459-0219-X . - S. 146-148.
Kirsanov M. N. Grafer i lönn . — M. : Fizmatlit, 2007. — 168 sid. - ISBN 978-5-9221-0745-7 . - S. 151-154.
Jones M. T. Programmering av artificiell intelligens i applikationer. - M. : DMK Press, 2004. - 312 sid. — ISBN 5-94074-275-0 . - S. 25-42.

Länkar

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powell metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering