Simulated Annealing grob

Beginner Algorithmen und Datenstrukturen Deutsch

Also available: English

Created by Best · 16.08.2026 at 09:13 UTC

Simulated Annealing ist eine Metaheuristik: akzeptiert manchmal schlechtere Nachbarn, gesteuert durch eine sinkende Temperatur. Ziel: lokale Minima verlassen.

Kein Exact-Algorithmus; Parameter (Temperaturplan) zählen.

$$P=\exp(-\Delta/T)\quad(\Delta\gt 0)$$

Wo gebraucht

Heuristik für harte Optimierung (Layout, Scheduling), wenn Exact Search zu teuer ist. Industriell verwandt mit anderen Metaheuristiken.

Vertiefung

Simulated Annealing ist eine stochastische Suchheuristik. Aus einer aktuellen Lösung wird eine Nachbarlösung erzeugt. Verbesserungen werden angenommen, Verschlechterungen können mit einer von Temperatur und Qualitätsverlust abhängigen Wahrscheinlichkeit ebenfalls akzeptiert werden.

Zu Beginn erlaubt eine hohe Temperatur breite Exploration. Ein Abkühlungsplan reduziert später die Wahrscheinlichkeit ungünstiger Schritte und stabilisiert die Suche. Ergebnisqualität hängt von Nachbarschaft, Startlösung, Temperaturskala und verfügbarer Laufzeit ab; eine endliche Ausführung garantiert im Allgemeinen kein Optimum.

Schwierigkeitsstufen

Nachbarschaft und Bewertungsfunktion eines Problems definieren.
Annahmewahrscheinlichkeiten qualitativ mit Temperatur vergleichen.
Abkühlung und Wiederholungszahl experimentell abstimmen.

Fallstricke

Zu schnelles Abkühlen macht das Verfahren früh nahezu deterministisch. Zu langsames Abkühlen verbraucht viel Zeit ohne Stabilisierung. Auch eine ungeeignete Nachbarschaft kann wichtige Bereiche praktisch unerreichbar machen.

University approvals: 0

Tasks

Question 1

Warum akzeptiert Simulated Annealing schlechtere Zustände?

Weil Sortieren stabil sein muss

Um lokale Optima zu verlassen

Weil equals fehlt

Weil Stacks voll sind

Question 2

Welche Wirkung hat eine höhere Temperatur auf einen verschlechternden Nachbarschritt?

Seine Annahme wird im Allgemeinen wahrscheinlicher.

Seine Annahme wird mathematisch unmöglich.

Er wird unabhängig von der Bewertung immer abgelehnt.

Die Nachbarschaft enthält danach keine Lösungen mehr.

Question 3

Implementiere die Akzeptanzwahrscheinlichkeit. Verbesserungen mit deltaEnergy < 0 werden immer akzeptiert, sonst gilt exp(-deltaEnergy / temperature).

Hint

Die Exponentialfunktion heisst Math.exp(double). Bei Division mit double bleibt das Ergebnis eine Gleitkommazahl.

class Annealing {
  static double acceptProb(double deltaEnergy, double temperature) {
    // TODO
    return 0.0;
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Algorithmen und Datenstrukturen
Difficulty: Beginner
Completed: 0 users

Creator

Best

BestBuddy