Vad är simulerad annealing?

Simulerad glödgning är en datorteknik som kan hitta bra - men inte nödvändigtvis optimala - lösningar på ett problem. Den heter så eftersom den efterliknar den metallurgiska processen för glödgning. I metaller är glödgning processen för rening genom att värma metallen och sedan kyla den långsamt. Datorprogrammet "renar" lösningsutrymmet tills allt som återstår är lösningar som är bäst eller nästan bäst.

Det finns två kritiska faktorer som användaren av ett simulerat glödgningsprogram behöver specificera: starttemperaturen eller procentandelen sämre lösningar som kan utforskas; och kylningshastigheten, som är den hastighet med vilken procentandelen reduceras. En låg starttemperatur slutar ofta med ett resultat långt bort från optimalt. Att börja vid en mycket hög temperatur kan resultera i att sökningen tar mycket mer tid än nödvändigt. På samma sätt ger en för hög kylningshastighet dåliga resultat, medan en mycket låg kylningshastighet resulterar i ett program som körs under mycket lång tid.

Tillståndet "hög temperatur" för det simulerade glödgningsprogrammet är en inställning som gör det möjligt att titta på ett brett utbud av lösningar, inklusive många som är sämre än lösningar som det redan har hittat. Datorn får titta på många lösningar som är sämre än den nuvarande lösningen för att undvika att hålla fast vid ett lokalt minimum som är väsentligt sämre än det bästa. Som exempel kan man tänka sig att börja på toppen av en kulle eller ett berg med målet att nå basen. Längs vägen kan det finnas galies eller chasms. Om datorn inte kan gå uppåt tillräckligt långt för att komma ut, kommer den att fastna trots att den inte finns någonstans nära basen.

Hur långt uppför programmet kan gå bestäms av procenttalet av sämre lösningar som programmet får undersöka. Med tiden går successivt bättre lösningar och risken för ett djupt klömsminskning, så att andelen sämre lösningar som datorn kan utforska minskar. Att minska denna fraktion kallas "kylning". När temperaturen når en förinställd fraktion - som inte behöver vara 0 - slutar sökningen.

Anledningen till att använda simulerad glödgning eller andra tekniker för artificiell intelligens är att minska tiden som krävs för att hitta en nästan optimal lösning till en hanterbar mängd. För många problem kan en uttömmande sökning - testning av varje möjlig lösning mot varandra möjlig lösning - ta månader eller år. Det mest kända alternativet till simulerad glödgning är genetiska algoritmer. Andra populära sökalgoritmer för artificiell intelligens inkluderar optimering av myrkolonier, optimering av partikelvärmen, närmaste granne och Bayesiska klassificerare.

ANDRA SPRÅK

Hjälpte den här artikeln dig? Tack för feedbacken Tack för feedbacken

Hur kan vi hjälpa? Hur kan vi hjälpa?