Simuleret udglødning

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

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

Generel beskrivelse af algoritmen[redigér | redigér wikikode]

S. Kirkpatrick et al. sammenligner kombinatoriske optimeringsproblemer med opførslen af mekaniske systemer, hvor antallet af frihedsgrader er for stort til at man kan finde 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[redigér | redigér wikikode]

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[redigér | redigér wikikode]

Matematik Stub
Denne artikel om matematik er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.