Simuleret udglødning

Simuleret udglødning (SA) er en generisk metaheuristik for det globale optimeringsproblem i anvendt matematik.

Generel beskrivelse af algoritmen

S. Kirkpatrick et al. sammenligner kombinatoriske optimeringsproblemer med opførslen af mekaniske systemer, hvor antallet af frihedsgrader er for stort til at man kan ﬁnde begyndelsesbetingelserne for systemet. Der foreslås en analogi, hvor udglødende faste stoffer giver et framework for optimering af komplekse systemer. Kirkpatrick forklarer, hvordan analogien kan anvendes til at udnytte to grundlæggende strategier for heuristikker: divide-and-conquer og iterativ forbedring. Algoritmen Simulated Annealing introduceres. I Simulated Annealing adskiller temperaturen klasser af ændringer i objektfunktionen, sådan at store ændringer sker ved høje temperaturer, mens mindre ændringer først bliver udført ved lave temperaturer. Dette svarer til en adaptiv form for divide-and-conquer-strategi. Samtidig forbedrer Simulated Annealing iterativt en lovlig løsning, hvilket svarer til strategien iterativ forbedring. Temperaturen forhindrer algoritmen i at sidde fast i et lokalt optimum ved at tillade ændringer der resulterer i en (midlertidig) dårligere løsning.

Pseudo-kode

s ← s0; e ← E(s)                             // Initial state, energy.
sb ← s; eb ← e                               // Initial "best" solution
k ← 0                                        // Energy evaluation count.
while k < kmax and e > emax                  // While time remains & not good enough:
  sn ← neighbour(s)                          //   Pick some neighbour.
  en ← E(sn)                                 //   Compute its energy.
  if en < eb then                            //   Is this a new best?
    sb ← sn; eb ← en                         //     Yes, save it.
  if P(e, en, temp(k/kmax)) > random() then  //   Should we move to it?
    s ← sn; e ← en                           //     Yes, change state.
  k ← k + 1                                  //   One more evaluation done
return sb                                    // Return the best solution found.

Relaterede artikler

Spire

Denne artikel om matematik er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den.