Hva er simulert annealing?

Simulert annealing er en datateknikk som kan finne bra - selv om det ikke nødvendigvis er optimalt - løsninger på et problem. Det er så navngitt fordi det etterligner den metallurgiske annealingprosessen. I metaller er annealing prosessen med å rense 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 nesten best.

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

"Høytemperatur" -tilstanden for det simulerte annealing -programmet er en innstilling som lar den se på et bredt spekter av løsninger, inkludert mange som er verre enn løsninger den allerede har funnet. Datamaskinen har lov til å se på mange løsninger som er verre enn den nåværende løsningen for å unngå å feste seg på et lokalt minimum som er vesentlig verre enn det beste. Som et eksempel kan man forestille seg å starte på toppen av en høyde eller fjell med målet å nå basen. Underveis kan det være slipper 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 av dårligere løsninger programmet får lov til å undersøke. Med tidenes tid blir det funnet gradvis bedre løsninger og risikoen for en dypChasm reduseres, så prosentandelen av dårligere løsninger som datamaskinen kan utforske blir redusert. Å redusere denne brøkdelen blir referert til som "kjøling." Når temperaturen når en forhåndsinnstilt brøkdel-som ikke trenger å være 0-avsluttes søket.

Årsaken til å bruke simulert annealing eller annen kunstig intelligens søketeknikker er å redusere til en håndterbar mengde tiden som trengs for å finne en nesten optimal løsning. For mange problemer kan et uttømmende søk - testingen 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 kunstige intelligenssøkalgoritmer inkluderer optimalisering av maurkolonien, optimalisering av partikler, nærmeste nabo og bayesiske klassifiserere.