Hva er simulert annealing?

Simulert annealing er en datateknikk som kan finne gode - men ikke nødvendigvis optimale - løsninger på et problem. Den er så navngitt fordi den etterligner den metallurgiske prosessen med annealing. I metall er annealing prosessen med rensing ved å varme opp metallet og deretter avkjøle det sakte. Dataprogrammet "renser" løsningsplassen til alt som gjenstår er løsninger som er best eller veldig nesten best.

Det er to kritiske faktorer som brukeren av et simulert glødeprogram trenger å spesifisere: starttemperaturen, eller prosentandelen dårligere løsninger som kan utforskes; og avkjølingshastigheten, som er hastigheten som den prosentandelen reduseres. En lav starttemperatur vil ofte ende med et resultat som er fjernet fra det optimale. Å starte ved en veldig høy temperatur kan føre til at søket tar mye mer tid enn nødvendig. Tilsvarende vil en for høy kjøling gi dårlige resultater, mens en veldig lav avkjøling vil resultere i et program som kjører i veldig lang tid.

Tilstanden "høy temperatur" for det simulerte glødeprogrammet er en innstilling som lar den se på et bredt spekter av løsninger, inkludert mange som er dårligere enn løsninger den allerede har funnet. Datamaskinen har lov til å se på mange løsninger som er dårligere enn dagens løsning for å unngå å holde seg til et lokalt minimum som er vesentlig dårligere enn de beste. Som et eksempel kan man tenke seg å starte på toppen av en ås eller et fjell med målet å nå basen. Underveis kan det være sluker eller chasmer. Hvis datamaskinen ikke kan gå oppover langt nok til å komme seg ut, vil den sitte fast selv om den ikke er i nærheten av basen.

Hvor langt opp bakken programmet kan gå, bestemmes av prosentandelen dårligere løsninger programmet har lov til å undersøke. Med tiden går det gradvis bedre løsninger og risikoen for en dyp kløft reduseres, slik at prosentandelen dårligere løsninger som datamaskinen kan utforske reduseres. Å redusere denne brøkdelen blir referert til som "kjøling." Når temperaturen når en forhåndsinnstilt brøk - som ikke trenger å være 0 - avsluttes søket.

Årsaken til å bruke simulert annealing eller andre søketeknikker for kunstig intelligens er å redusere tiden som er nødvendig for å finne en nær optimal løsning til en håndterbar mengde. For mange problemer kan et uttømmende søk - testing av hver mulig løsning mot hverandre mulig løsning - ta måneder eller år. Det mest kjente alternativet til simulert annealing er genetiske algoritmer. Andre populære søkealgoritmer for kunstig intelligens inkluderer optimalisering av myrkolonier, optimalisering av partikkelsvermer, nærmeste nabo og Bayesianske klassifisere.