Simulert gløding - Simulated annealing

Simulert annealing kan brukes til å løse kombinatoriske problemer. Her brukes det på den reisende selgerproblemet for å minimere lengden på en rute som kobler alle 125 punkter.

Reisende selgerproblem i 3D for 120 poeng løst med simulert gløding.

Simulert annealing ( SA ) er en probabilistisk teknikk for å tilnærme det globale optimalet for en gitt funksjon . Nærmere bestemt er det en metaheuristisk å tilnærme global optimalisering i et stort søkeområde for et optimaliseringsproblem . Det brukes ofte når søkeområdet er diskret (for eksempel problemet med omreisende selger, problemet med boolsk tilfredsstillelse , forutsigelse av proteinstruktur og planlegging av jobber ). For problemer der det er viktigere å finne et tilnærmet globalt optimalt enn å finne et presist lokalt optimalt på en bestemt tid, kan simulert gløding være å foretrekke fremfor eksakte algoritmer som nedstigning av gradient eller gren og avgrensning .

Navnet på algoritmen kommer fra gløding i metallurgi , en teknikk som involverer oppvarming og kontrollert avkjøling av et materiale for å endre dets fysiske egenskaper. Begge er attributter til materialet som er avhengig av deres termodynamiske frie energi. Oppvarming og avkjøling av materialet påvirker både temperaturen og den termodynamiske frie energien eller Gibbs -energien. Simulert annealing kan brukes til svært harde beregningsoptimaliseringsproblemer der eksakte algoritmer mislykkes; selv om den vanligvis oppnår en omtrentlig løsning på det globale minimumet, kan det være nok for mange praktiske problemer.

Problemene løst av SA er for tiden formulert av en objektiv funksjon av mange variabler, underlagt flere begrensninger. I praksis kan begrensningen straffes som en del av den objektive funksjonen.

Lignende teknikker har blitt uavhengig introdusert ved flere anledninger, inkludert Pincus (1970), Khachaturyan et al (1979, 1981), Kirkpatrick, Gelatt og Vecchi (1983) og Cerny (1985). I 1983 ble denne tilnærmingen brukt av Kirkpatrick, Gelatt Jr., Vecchi, for en løsning på det reisende selgerproblemet. De foreslo også det nåværende navnet, simulert annealing.

Denne forestillingen om langsom avkjøling implementert i den simulerte glødingsalgoritmen tolkes som en langsom nedgang i sannsynligheten for å godta dårligere løsninger etter hvert som løsningsrommet blir utforsket. Å godta verre løsninger gir mulighet for et mer omfattende søk etter den globale optimale løsningen. Generelt fungerer simulerte glødingsalgoritmer som følger. Temperaturen synker gradvis fra en initial positiv verdi til null. Ved hvert trinnstrinn velger algoritmen tilfeldig en løsning nær den nåværende, måler kvaliteten og beveger seg til den i henhold til de temperaturavhengige sannsynlighetene for å velge bedre eller dårligere løsninger, som henholdsvis under søket forblir på 1 (eller positive ) og reduseres mot null.

Simuleringen kan utføres enten ved en løsning av kinetiske ligninger for tetthetsfunksjoner eller ved å bruke den stokastiske prøvetakingsmetoden. Metoden er en tilpasning av Metropolis - Hastings -algoritmen , en Monte Carlo -metode for å generere prøvetilstander av et termodynamisk system, utgitt av N. Metropolis et al. i 1953.

Oversikt

Den tilstand av enkelte fysiske systemer , og funksjonen E ( r ) som skal minimaliseres, er analog med den indre energi til systemet i den tilstanden. Målet er å bringe systemet, fra en vilkårlig starttilstand , til en tilstand med minst mulig energi.

Simulert annealing som søker etter et maksimum. Målet her er å komme til det høyeste punktet. I dette eksemplet er det ikke nok å bruke en enkel bakkebestigningsalgoritme , da det er mange lokale maksima . Ved å avkjøle temperaturen sakte blir det globale maksimum funnet.

Den grunnleggende iterasjonen

Ved hvert trinn betrakter simulert herding heuristiske noen nabo tilstand s * av den nåværende tilstand s , og sannsynlighets bestemmer seg mellom bevegelige systemet til tilstand s * eller bor i-tilstand s . Disse sannsynlighetene fører til slutt til at systemet flytter til tilstander med lavere energi. Vanligvis gjentas dette trinnet til systemet når en tilstand som er god nok for applikasjonen, eller til et gitt beregningsbudsjett er oppbrukt.

Naboene til en stat

Optimalisering av en løsning innebærer evaluering av naboene til en tilstand av problemet, som er nye stater som produseres ved konservativt å endre en gitt tilstand. For eksempel, i den reisende selgerproblemet er hver stat vanligvis definert som en permutasjon av byene som skal besøkes, og naboene til enhver stat er settet med permutasjoner produsert ved å bytte to av disse byene. Den veldefinerte måten statene endres på for å produsere nabostater kalles et "trekk", og forskjellige trekk gir forskjellige sett med nabostater. Disse trekkene resulterer vanligvis i minimale endringer av den siste tilstanden, i et forsøk på å gradvis forbedre løsningen gjennom iterativt å forbedre delene (for eksempel byforbindelser i det reisende selgerproblemet).

Enkel heuristikk som bakkeklatring , som beveger seg ved å finne bedre nabo etter bedre nabo og stoppe når de har kommet til en løsning som ikke har noen naboer som er bedre løsninger, kan ikke garantere å føre til noen av de eksisterende bedre løsningene - resultatet kan lett bli rettferdig et lokalt optimum , mens den faktisk beste løsningen ville være et globalt optimalt som kan være annerledes. Metaheuristikk bruker naboene til en løsning som en måte å utforske løsningsrommet på, og selv om de foretrekker bedre naboer, godtar de også dårligere naboer for å unngå å bli sittende fast i lokale optima; de kan finne det globale optimale hvis de kjøres for lenge nok tid.

Aksept sannsynligheter

Sannsynligheten for å gjøre overgangen fra den nåværende tilstanden til en kandidat-ny tilstand er spesifisert av en aksept-sannsynlighetsfunksjon , som avhenger av energiene og de to statene, og av en global tidsvarierende parameter som kalles temperaturen . Stater med mindre energi er bedre enn de med større energi. Sannsynlighetsfunksjonen må være positiv selv om den er større enn . Denne funksjonen forhindrer at metoden blir sittende fast på et lokalt minimum som er verre enn det globale. ${\ displaystyle s}$${\ displaystyle s _ {\ mathrm {new}}}$ ${\ displaystyle P (e, e _ {\ mathrm {new}}, T)}$${\ displaystyle e = E (s)}$${\ displaystyle e _ {\ mathrm {new}} = E (s _ {\ mathrm {new}})}$${\ displaystyle T}$${\ displaystyle P}$${\ displaystyle e _ {\ mathrm {new}}}$${\ displaystyle e}$

Når det har en tendens til null, må sannsynligheten ha en nullstilling hvis og til en positiv verdi ellers. For tilstrekkelig små verdier av , vil systemet da i økende grad favorisere trekk som går "nedoverbakke" (dvs. for å senke energiverdiene), og unngå de som går "oppoverbakke". Med prosedyren reduseres til den grådige algoritmen , som bare gjør nedoverbakkeovergangene. ${\ displaystyle T}$${\ displaystyle P (e, e _ {\ mathrm {new}}, T)}$${\ displaystyle e _ {\ mathrm {new}}> e}$${\ displaystyle T}$${\ displaystyle T = 0}$

I den opprinnelige beskrivelsen av simulert gløding var sannsynligheten lik 1 når prosedyren alltid gikk nedoverbakke når den fant en måte å gjøre det, uavhengig av temperaturen. Mange beskrivelser og implementeringer av simulert gløding tar fremdeles denne tilstanden som en del av metodens definisjon. Denne tilstanden er imidlertid ikke avgjørende for at metoden skal fungere. ${\ displaystyle P (e, e _ {\ mathrm {new}}, T)}$${\ displaystyle e _ {\ mathrm {new}} <e}$

Den funksjonen er vanligvis valgt slik at sannsynligheten for å akseptere en overgang minker når forskjellen øker, det vil si små oppoverbakke trekk er mer sannsynlig enn store. Dette kravet er imidlertid ikke strengt nødvendig, forutsatt at kravene ovenfor er oppfylt. ${\ displaystyle P}$${\ displaystyle e _ {\ mathrm {new}} -e}$

Gitt disse egenskapene, spiller temperaturen en avgjørende rolle for å kontrollere utviklingen av systemets tilstand med hensyn til dens følsomhet for variasjonene i systemenergier. For å være presis, for en stor , er utviklingen av sensitiv for grovere energivariasjoner, mens den er følsom for finere energivariasjoner når den er liten. ${\ displaystyle T}$${\ displaystyle s}$${\ displaystyle T}$${\ displaystyle s}$${\ displaystyle T}$

Glødingsplanen

Fort

Langsom

Eksempel som illustrerer effekten av kjøleplanen på ytelsen til simulert gløding. Problemet er å omorganisere pikslene i et bilde for å minimere en viss potensiell energifunksjon , noe som får lignende farger til å tiltrekke seg på kort avstand og frastøte på en litt større avstand. Elementærbevegelsene bytter to tilstøtende piksler. Disse bildene ble oppnådd med en hurtigkjølingsplan (venstre) og en langsom avkjølingsplan (til høyre), og ga resultater som ligner henholdsvis amorfe og krystallinske faste stoffer .

Algoritmens navn og inspirasjon krever at en interessant funksjon knyttet til temperaturvariasjonen er innebygd i algoritmens operasjonelle egenskaper. Dette krever en gradvis reduksjon av temperaturen etterhvert som simuleringen fortsetter. Algoritmen starter først med satt til en høy verdi (eller uendelig), og deretter reduseres den ved hvert trinn etter en annealingsplan - som kan spesifiseres av brukeren, men må ende med mot slutten av det tildelte tidsbudsjettet. På denne måten forventes det at systemet først vandrer mot et bredt område av søkeområdet som inneholder gode løsninger, og ignorerer små funksjoner i energifunksjonen; driver deretter mot lavenergiregioner som blir smalere og smalere; og til slutt bevege oss nedoverbakke i henhold til den bratteste nedstigningsheuristen . ${\ displaystyle T}$${\ displaystyle T = 0}$

For et gitt begrenset problem nærmer sannsynligheten for at den simulerte glødingsalgoritmen avsluttes med en global optimal løsning 1 når glødingsplanen utvides. Dette teoretiske resultatet er imidlertid ikke spesielt nyttig, siden tiden som kreves for å sikre en betydelig sannsynlighet for suksess vanligvis vil overstige tiden som kreves for et fullstendig søk i løsningsområdet .

Pseudokode

Den følgende pseudokoden presenterer den simulerte glødingsheuristikken som beskrevet ovenfor. Den starter fra en tilstand s ₀ og fortsetter til maksimalt k _maks trinn er tatt. I prosessen blir samtalen nabo ( e ) skal generere et tilfeldig valgt nabo av en gitt tilstand s ; samtalen tilfeldig (0, 1) skal velge og returnere en verdi i området [0, 1] , jevnt og tilfeldig . Glødingsplanen er definert av anropstemperaturen ( r ) , som skal gi temperaturen som skal brukes, gitt brøkdelen r av tidsbudsjettet som har blitt brukt så langt.

Velge parametere

For å anvende den simulerte glødemetoden på et bestemt problem, må man spesifisere følgende parametere: tilstandsrommet, energien (mål) -funksjonen E(), kandidatgeneratorprosedyren neighbour(), aksept -sannsynlighetsfunksjonen P()og glødingsplanen temperature()OG initialtemperatur <init temp>. Disse valgene kan ha en betydelig innvirkning på metodens effektivitet. Dessverre er det ingen valg av disse parameterne som vil være bra for alle problemer, og det er ingen generell måte å finne de beste valgene for et gitt problem. De følgende avsnittene gir noen generelle retningslinjer.

Tilstrekkelig nær nabo

Simulert annealing kan modelleres som en tilfeldig spasertur på et søkekart, hvis hjørner alle er mulige tilstander, og hvis kanter kandidatbevegelsene er. Et vesentlig krav for neighbour()funksjonen er at den må gi en tilstrekkelig kort bane på denne grafen fra starttilstanden til en hvilken som helst tilstand som kan være det globale optimalt - diameteren på søkediagrammet må være liten. I eksempelet med reisende selger ovenfor, for eksempel har søkeområdet for n = 20 byer n! = 2.432.902.008.176.640.000 (2,4 kvintillion) tilstander; men antallet naboer til hvert toppunkt er kanter (kommer fra n velger 2), og diameteren på grafen er . ${\ displaystyle \ sum _ {k = 1}^{n-1} k = {\ frac {n (n-1)} {2}} = 190}$${\ displaystyle n-1}$

Overgangssannsynligheter

For å undersøke oppførselen til simulert gløding på et bestemt problem, kan det være nyttig å vurdere overgangssannsynlighetene som følger av de forskjellige designvalgene som er gjort ved implementeringen av algoritmen. For hver kant av søkediagrammet er overgangssannsynligheten definert som sannsynligheten for at den simulerte glødingsalgoritmen vil gå til tilstand når den nåværende tilstanden er . Denne sannsynligheten avhenger av gjeldende temperatur som spesifisert av , i hvilken rekkefølge kandidaten beveger seg generert av funksjonen, og på aksept -sannsynlighetsfunksjonen . (Vær oppmerksom på at overgangssannsynligheten ikke bare er fordi kandidatene blir testet i serie.) ${\ displaystyle (s, s ')}$${\ displaystyle s '}$${\ displaystyle s}$temperature()neighbour()P()${\ displaystyle P (e, e ', T)}$

Aksept sannsynligheter

Spesifikasjonen av neighbour(), P()og temperature()er delvis overflødig. I praksis er det vanlig å bruke den samme akseptfunksjonen P()for mange problemer, og justere de to andre funksjonene i henhold til det spesifikke problemet.

I formuleringen av metoden av Kirkpatrick et al., Ble aksept -sannsynlighetsfunksjonen definert som 1 if , og ellers. Denne formelen ble overfladisk begrunnet i analogi med overgangene til et fysisk system; det tilsvarer Metropolis - Hastings -algoritmen , i tilfellet der T = 1 og forslagets fordeling av Metropolis - Hastings er symmetrisk. Imidlertid brukes denne aksept -sannsynligheten ofte for simulert gløding, selv om funksjonen, som er analog med forslagsfordelingen i Metropolis - Hastings, ikke er symmetrisk eller ikke sannsynlig. Som et resultat samsvarer ikke overgangssannsynlighetene for den simulerte glødingsalgoritmen med overgangene til det analoge fysiske systemet, og den langsiktige fordelingen av tilstander ved en konstant temperatur trenger ikke å ha noen likhet med den termodynamiske likevektsfordelingen over tilstandene til det fysiske system, ved enhver temperatur. Likevel antar de fleste beskrivelser av simulert annealing den opprinnelige akseptfunksjonen, som sannsynligvis er hardkodet i mange implementeringer av SA. ${\ displaystyle P (e, e ', T)}$${\ displaystyle e '<e}$${\ displaystyle \ exp (-(e'-e)/T)}$neighbour()${\ displaystyle T}$

I 1990 foreslo Moscato og Fontanari, og uavhengig av hverandre Dueck og Scheuer, at en deterministisk oppdatering (dvs. en som ikke er basert på den sannsynlige akseptregelen) kan fremskynde optimaliseringsprosessen uten å påvirke den endelige kvaliteten. Moscato og Fontanari konkluderer med å observere det analoge med "spesifikk varme" -kurven for "terskeloppdatering" -glødningen som stammer fra studien at "stokastisiteten til Metropolis -oppdateringen i den simulerte glødingsalgoritmen ikke spiller noen stor rolle i søket etter nær -optimal minima ". I stedet foreslo de at "utjevning av kostnadsfunksjonslandskapet ved høy temperatur og den gradvise definisjonen av minima under kjøleprosessen er de grunnleggende ingrediensene for å lykkes med simulert gløding." Metoden ble deretter populær under betegnelsen "terskelaksept" på grunn av Dueck og Scheuers betegnelse. I 2001 viste Franz, Hoffmann og Salamon at den deterministiske oppdateringsstrategien faktisk er den optimale innenfor den store klassen av algoritmer som simulerer en tilfeldig spasertur på kostnads-/energilandskapet.

Effektiv kandidatgenerering

Når du velger kandidatgeneratoren neighbour(), må du vurdere at etter noen få iterasjoner av den simulerte glødingsalgoritmen forventes den nåværende tilstanden å ha mye lavere energi enn en tilfeldig tilstand. Derfor, som hovedregel, bør en skjev generatoren mot kandidatbevegelser der energien til destinasjonstilstanden sannsynligvis vil være lik energien til den nåværende tilstanden. Denne heuristikken (som er hovedprinsippet for algoritmen Metropolis - Hastings ) har en tendens til å utelukke "veldig gode" kandidatbevegelser så vel som "veldig dårlige"; Imidlertid er førstnevnte vanligvis mye mindre vanlig enn sistnevnte, så heuristikken er generelt ganske effektiv. ${\ displaystyle s '}$

I det reisende selgerproblemet ovenfor, for eksempel, forventes det å bytte to påfølgende byer i en lavenergitur å ha en beskjeden effekt på energien (lengden); mens bytte av to vilkårlige byer er langt mer sannsynlig å øke lengden enn å redusere den. Dermed forventes den påfølgende byttende nabogeneratoren å utføre bedre enn den vilkårlige byttingen, selv om sistnevnte kan gi en noe kortere vei til det optimale (med bytter, i stedet for ). ${\ displaystyle n-1}$${\ displaystyle n (n-1)/2}$

En mer presis uttalelse av heuristen er at man bør prøve første kandidatstater som er store. For "standard" akseptfunksjon ovenfor, betyr det at den er i størrelsesorden eller mindre. Således kan man i reiselivseksemplet ovenfor bruke en funksjon som bytter to tilfeldige byer, der sannsynligheten for å velge et bypar forsvinner etter hvert som avstanden øker utover . ${\ displaystyle s '}$${\ displaystyle P (E (s), E (s), T)}$${\ displaystyle P}$${\ displaystyle E (s)-E (s)}$${\ displaystyle T}$neighbour()${\ displaystyle T}$

Barriere unngåelse

Når du velger kandidatgeneratoren, neighbour()må du også prøve å redusere antall "dype" lokale minima - stater (eller sett med tilkoblede stater) som har mye lavere energi enn alle nabolandene. Slike "lukkede oppsamlingsbeholdere " i energifunksjonen kan fange den simulerte glødingsalgoritmen med stor sannsynlighet (omtrent proporsjonal med antall tilstander i bassenget) og i svært lang tid (omtrent eksponentielt om energiforskjellen mellom de omkringliggende tilstandene og bunnen av bassenget).

Som regel er det umulig å designe en kandidatgenerator som vil tilfredsstille dette målet og også prioritere kandidater med lignende energi. På den annen side kan man ofte forbedre effektiviteten til simulert gløding ved relativt enkle endringer i generatoren. I problemet med den reisende selgeren er det for eksempel ikke vanskelig å vise to turer , med nesten like lange lengder, slik at (1) er optimale, (2) hver sekvens av bybyttebytter som konverterer til går gjennom turer som er mye lengre enn begge, og (3) kan transformeres til ved å snu (reversere rekkefølgen på) et sett med påfølgende byer. I dette eksemplet, og ligge i forskjellige "dype bassenger" hvis generatoren bare utfører tilfeldige parbytter; men de vil være i samme bassenget hvis generatoren utfører tilfeldige segment-flips. ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$

Avkjølingsplan

Den fysiske analogien som brukes til å rettferdiggjøre simulert gløding, antar at kjølehastigheten er lav nok til at sannsynlighetsfordelingen for den nåværende tilstanden til enhver tid er nær termodynamisk likevekt . Dessverre avhenger avspenningstiden - tiden man må vente på at likevekten skal gjenopprettes etter en endring i temperaturen - sterkt av energifunksjonens "topografi" og av den nåværende temperaturen. I den simulerte glødingsalgoritmen avhenger avslapningstiden også av kandidatgeneratoren, på en veldig komplisert måte. Vær oppmerksom på at alle disse parameterne vanligvis er gitt som black box -funksjoner til den simulerte glødingsalgoritmen. Derfor kan den ideelle kjølehastigheten ikke bestemmes på forhånd, og bør justeres empirisk for hvert problem. Adaptive simulerte glødingsalgoritmer løser dette problemet ved å koble nedkjølingsplanen til søkefremgangen. Andre adaptive tilnærminger som Thermodynamic Simulated Annealing, justerer automatisk temperaturen i hvert trinn basert på energiforskjellen mellom de to statene, i henhold til lovene i termodynamikk.

Starter på nytt

Noen ganger er det bedre å gå tilbake til en løsning som var betydelig bedre enn å alltid flytte fra den nåværende tilstanden. Denne prosessen kalles omstart av simulert annealing. For å gjøre dette setter vi sog etil sbestog ebestog kanskje starter glødingsplanen på nytt. Beslutningen om å starte på nytt kan være basert på flere kriterier. Bemerkelsesverdig blant disse inkluderer omstart basert på et fast antall trinn, basert på om den nåværende energien er for høy i forhold til den beste energien som er oppnådd så langt, omstart tilfeldig osv.

Relaterte metoder

• Interaktive Metropolis-Hasting-algoritmer (aka Sequential Monte Carlo ) kombinerte simulerte glødetrinn med aksept-avvisning av de best utstyrte personene utstyrt med en samhandlende resirkuleringsmekanisme.
• Quantum annealing bruker "kvantefluktuasjoner" i stedet for termiske svingninger for å komme gjennom høye, men tynne barrierer i målfunksjonen.
• Stokastiske tunnelforsøk for å overvinne de økende vanskeligheter som simulerte glødeløp har å rømme fra lokale minima når temperaturen synker, ved å 'tunnelle' gjennom barrierer.
• Tabu -søk flytter normalt til nabolandene med lavere energi, men vil ta oppoverbakker når det befinner seg fast i et lokalt minimum; og unngår sykluser ved å holde en "tabubeliste" over løsninger som allerede er sett.
• To-fase evolusjon er en familie av algoritmer og prosesser (som simulert annealing tilhører) som formidler mellom lokalt og globalt søk ved å utnytte faseendringer i søkeområdet.
• Reaktiv søkoptimalisering fokuserer på å kombinere maskinlæring med optimalisering, ved å legge til en intern tilbakemeldingssløyfe for å selvjustere de gratis parametrene til en algoritme til egenskapene til problemet, forekomsten og den lokale situasjonen rundt den nåværende løsningen.
• Genetiske algoritmer opprettholder en mengde løsninger fremfor bare én. Nye kandidatløsninger genereres ikke bare ved "mutasjon" (som i SA), men også ved "rekombinasjon" av to løsninger fra bassenget. Sannsynlighetskriterier, lik de som brukes i SA, brukes til å velge kandidatene for mutasjon eller kombinasjon, og for å kaste overflødige løsninger fra bassenget.
• Memetiske algoritmer søker etter løsninger ved å bruke et sett med agenter som både samarbeider og konkurrerer i prosessen; noen ganger innebærer agentenes strategier simulerte glødingsprosedyrer for å skaffe løsninger av høy kvalitet før de rekombineres. Annealing har også blitt foreslått som en mekanisme for å øke mangfoldet i søket.
• Uteksaminert optimalisering "glatter" målfunksjonen degressivt mens du optimaliserer.
• Optimalisering av maurekoloni (ACO) bruker mange maur (eller agenter) for å krysse løsningsrommet og finne lokalt produktive områder.
• Den tverrentropi metode (CE) genererer kandidater oppløsninger via en parameterisert sannsynlighetsfordeling. Parametrene oppdateres via kryssentropiminimering, for å generere bedre prøver i neste iterasjon.
• Harmonisøk etterligner musikere i improvisasjonsprosessen der hver musiker spiller et notat for å finne den beste harmonien sammen.
• Stokastisk optimalisering er et paraply -sett med metoder som inkluderer simulert gløding og mange andre tilnærminger.
• Partikkelsvermoptimalisering er en algoritme modellert etter svermintelligens som finner en løsning på et optimaliseringsproblem i et søkeområde, eller modell og forutsi sosial atferd i nærvær av mål.
• Runner-root-algoritmen (RRA) er en meta-heuristisk optimaliseringsalgoritme for å løse unimodale og multimodale problemer inspirert av løperne og røttene til planter i naturen.
• Intelligent vanndråpsalgoritme (IWD) som etterligner oppførselen til naturlige vanndråper for å løse optimaliseringsproblemer
• Parallell temperering er en simulering av modellkopier ved forskjellige temperaturer (eller Hamiltonians ) for å overvinne potensielle barrierer.
• Multiobjective Simulated Annealing ble designet for ( multi-objektiv optimalisering ) problemer og kan trolig løse noen av dem med mer objektive funksjoner enn andre strategier.

Se også

Referanser

Videre lesning

• A. Das og BK Chakrabarti (red.), Quantum Annealing and Related Optimization Methods , Lecture Note in Physics, Vol. 679, Springer, Heidelberg (2005)
• Weinberger, E. (1990). "Korrelert og ukorrelert treningslandskap og hvordan man kan se forskjellen". Biologisk kybernetikk . 63 (5): 325–336. doi : 10.1007/BF00202749 . S2CID  851736 .
• Trykk, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Del 10.12. Simulerte glødemetoder" . Numeriske oppskrifter: The Art of Scientific Computing (3. utg.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Strobl, MAR; Barker, D. (2016). "På simulerte glødende faseoverganger i fylogenirekonstruksjon" . Molekylær fylogenetikk og evolusjon . 101 : 46–55. doi : 10.1016/j.ympev.2016.05.001 . PMC  4912009 . PMID  27150349 .
• V.Vassilev, A.Prahova: "The Use of Simulated Annealing in the Control of Flexible Manufacturing Systems", International Journal INFORMATION THEORIES & APPLICATIONS, VOLUME 6/1999

Eksterne linker

• Simulert annealing En Javascript -app som lar deg eksperimentere med simulert annealing. Kildekode inkludert.
• "General Simulated Annealing Algorithm" Et MATLAB-program med åpen kildekode for generelle simulerte glødingsøvelser.
• Selvstyrt leksjon om simulert annealing Et Wikiversity-prosjekt.
• Google i superposisjon om å bruke, ikke bruke kvantecomputere Ars Technica diskuterer muligheten for at D-Wave-datamaskinen som brukes av Google faktisk kan være en effektiv simulert annealing-co-prosessor.
• [1] En simulert annealing-basert multiobjektiv optimaliseringsalgoritme: AMOSA.