Hvad er simuleret annealing?

Simuleret annealing er en computerteknik, der kan finde god mdash;skønt ikke nødvendigvis optimal mdash;løsninger til et problem.Det er så navngivet, fordi det efterligner den metallurgiske proces med udglødning.I metaller er annealing processen med oprensning ved at opvarme metallet og derefter afkøle det langsomt.Computerprogrammet renser løsningsrummet, indtil alt det der er tilbage er løsninger, der er bedst eller meget næsten bedst.

Der er to kritiske faktorer, som brugeren af et simuleret udglødningsprogram skal specificere: starttemperaturen eller procentdelen af værre løsninger, der kan udforskes;og afkølingshastigheden, som er den hastighed, hvormed denne procentdel reduceres.En lav starttemperatur slutter ofte med et resultat langt væk fra det optimale.At starte ved en meget høj temperatur kan resultere i, at søgningen tager langt mere tid end nødvendigt.Tilsvarende vil en afkølingshastighed, der er for høj, generere dårlige resultater, mens en meget lav afkøling vil resultere i et program, der kører i meget lang tid.

Den høje temperaturtilstand for det simulerede annealingsprogram er en indstilling, derTillader det at se på en lang række løsninger, inklusive mange, der er værre end løsninger, det allerede har fundet.Computeren får lov til at se på mange løsninger, der er værre end den aktuelle løsning for at undgå at klæbe på et lokalt minimum, der er væsentligt værre end det bedste.Som et eksempel kan man forestille sig at starte øverst på en bakke eller bjerg med det mål at nå basen.Undervejs kan der være sluge eller chasmer.Hvis computeren ikke kan gå op ad bakke langt nok til at komme ud, vil den sidde fast, selvom den ikke er nogen steder tæt på basen.

Hvor langt op ad bakken programmet kan gå bestemmes af procentdelen af værre løsninger, som programmet får lov til at undersøge.Med tidens gang findes der gradvist bedre løsninger, og risikoen for en dyb kløft mindskes, så procentdelen af værre løsninger, som computeren kan udforske, mindskes.At formindske denne brøkdel kaldes afkøling.Når temperaturen når en forudindstillet fraktion mdash;som ikke behøver at være 0 mdash;Søgningen slutter.

Årsagen til at bruge simuleret udglødning eller anden kunstig intelligens søgeteknikker er at reducere til et håndterbart beløb, den tid, der er nødvendig for at finde en næsten optimal løsning.For mange problemer er en udtømmende søgning mdash;testning af hver mulig løsning mod hinanden mulig opløsning mdash;kunne tage måneder eller år.Det mest kendte alternativ til simuleret annealing er genetiske algoritmer.Andre populære kunstige efterretningssøgningsalgoritmer inkluderer myrekolonimensoptimering, optimering af partikelswarm, nærmeste nabo og Bayesiske klassifikatorer.