Grundlagen & Single-State-Heuristiken

Dieser Abschnitt behandelt die fundamentalen Konzepte der heuristischen Suche, grenzt sie von der klassischen gradientenbasierten Optimierung ab, führt das zentrale Dilemma zwischen Exploration und Exploitation ein und erläutert die Funktionsweise grundlegender evolutionärer Strategien.

Gradientenbasierte Optimierung: Anwendbarkeit und Umgehung

Die gradientenbasierte Optimierung, repräsentiert durch Verfahren wie das Gradientenaufstiegsverfahren, ist eine leistungsstarke Methode zur Optimierung. Ihre Anwendbarkeit ist jedoch an die Bedingung geknüpft, dass die zu optimierende Funktion bekannt und differenzierbar sein muss. Der iterative Prozess berechnet den Gradienten (Richtung des steilsten Anstiegs) und macht kleine Schritte in diese Richtung, bis ein lokales Maximum erreicht ist. Die Anwendbarkeit endet abrupt, wenn diese Voraussetzung nicht erfüllt ist, was bei vielen realen „Black-Box-Optimierungsproblemen“ der Fall ist.

Problemklassen ohne Anwendbarkeit

• Unbekannte Zielfunktion: Die Zielfunktion ist nicht als explizite mathematische Formel gegeben (z.B. Laufzeit eines Programms). Das System verhält sich wie eine „Black Box“.

• Nicht-differenzierbare oder diskrete Suchräume: Optimierungsprobleme mit diskreten oder nicht-kontinuierlichen Suchräumen (z.B. Traveling Salesman Problem) erlauben keine Gradientendefinition.

• Skalierungsprobleme in hochdimensionalen Räumen: Selbst wenn eine Funktion bekannt ist, kann die Gradientenberechnung in extrem hochdimensionalen Suchräumen rechentechnisch zu aufwendig oder instabil werden.

Umgehung des Problems durch Heuristiken

Da gradientenbasierte Methoden für diese Problemklassen versagen, sind alternative Strategien, sogenannte Heuristiken, erforderlich. Diese „Faustregeln“ oder intelligenten Suchstrategien navigieren den Suchraum auch ohne Kenntnis des Gradienten. Meta-Heuristiken sind übergeordnete Frameworks, die eine allgemeine Vorgehensweise zur Problemlösung bieten, indem sie Kandidatenlösungen evaluieren und basierend darauf neue Bereiche des Suchraums erkunden.

Exploration vs. Exploitation

Im Kern jeder intelligenten Suchstrategie liegt ein fundamentaler Zielkonflikt zwischen Exploration (Erkundung) und Exploitation (Ausbeutung). Ein erfolgreicher Algorithmus muss diese dynamisch ausbalancieren, um eine hohe Lösungsqualität zu erzielen.

• Exploration (Erkundung):

  • Konzept: Untersuchung neuer, unerforschter Bereiche des Suchraums, oft durch große, zufällige „Sprünge“.

  • Vorteile: Überwindet lokale Optima, erhöht die Wahrscheinlichkeit, das globale Optimum zu finden.

  • Nachteile: Ineffizient, sehr langsame oder keine Konvergenz zu einer guten Lösung.

• Exploitation (Ausbeutung):

  • Konzept: Intensive Untersuchung der unmittelbaren Nachbarschaft bekannter, guter Lösungen durch kleine, gezielte Änderungen.

  • Vorteile: Effizient bei der Verbesserung bestehender Lösungen, schnelle Konvergenz in vielversprechenden Regionen.

  • Nachteile: Gefahr der vorzeitigen Konvergenz (premature convergence), wobei der Algorithmus in einem lokalen Optimum „gefangen“ ist und das potenziell bessere globale Optimum nicht findet.

Die Herausforderung im Design von Meta-Heuristiken besteht darin, diesen Konflikt zu managen.

Algorithmen wie Simulated Annealing beginnen mit hoher Exploration und gehen allmählich zu mehr Exploitation über. In evolutionären Algorithmen steuern Parameter wie die Varianz σ² der Gausschen Konvolution dieses Gleichgewicht.

Evolutionäre Algorithmen (EA): Strategien (1+1), (1+λ) und (1,λ)

Evolutionäre Algorithmen (EA) sind eine Klasse von Meta-Heuristiken, die von der biologischen Evolution inspiriert sind. Die hier betrachteten Strategien sind einfache, auf einem einzelnen Elternteil basierende Varianten, die oft als Erweiterungen des Hill-Climbing-Verfahrens verstanden werden können. Sie nutzen typischerweise die Gausssche Konvolution zur Erzeugung neuer Kandidatenlösungen. Die Notation (μ+λ) bzw. (μ,λ) beschreibt, wie viele Eltern (μ) wie viele Nachkommen (λ) erzeugen und wie die nächste Generation ausgewählt wird. Das „+“ impliziert Elitismus (Eltern überleben und konkurrieren mit den Nachkommen), während das „,“ bedeutet, dass die Eltern verworfen werden.

• (1+1)-Strategie:

  • Konzept: Die einfachste Form und entspricht einem grundlegenden Hill-Climbing-Algorithmus. Ein einzelner Elter (μ = 1) erzeugt einen einzelnen Nachkommen (λ = 1) durch kleine Modifikation (Tweak), z.B. mittels Gaussscher Konvolution.

  • Selektion: Der Nachkomme ersetzt den Elter nur dann, wenn seine Fitness besser ist. Dies ist ein rein elitärer und gieriger Ansatz, der stark auf Exploitation ausgerichtet ist.

• (1+λ)-Strategie:

  • Konzept: Entspricht einem Steepest-Ascent Hill Climbing. Ein einzelner Elter (μ = 1) erzeugt parallel λ Nachkommen, die leicht modifizierte Versionen des Elters sind.

  • Selektion: Der beste der λ Nachkommen wird ausgewählt und ersetzt den ursprünglichen Elter nur, wenn er fitter ist. Diese Strategie ist noch stärker auf Exploitation ausgerichtet als die (1+1)-Strategie.

• (1,λ)-Strategie:

  • Konzept: Ähnlich wie bei (1+1) erzeugt ein einzelner Elter (μ = 1) parallel λ Nachkommen.

  • Selektion: Der beste der λ Nachkommen wird ausgewählt und ersetzt den Elter immer, unabhängig von dessen Fitness. Diese Strategie ist nicht elitär, fördert die Exploration und ermöglicht das Entkommen aus lokalen Optima.

StrategieElternüberleben (Elitismus)Primäre Tendenz(1+1)JaGierige Exploitation(1+λ)JaAggressive Exploitation(1,λ)NeinExploration

Gaussian Convolution (Bonus): Erklärung, Bestandteile und Algorithmus

Die Gausssche Konvolution ist eine spezifische Methode zur Realisierung von Modifikations- oder Mutationsoperatoren in evolutionären Algorithmen, insbesondere wenn Kandidatenlösungen als Vektoren von reellen Zahlen repräsentiert werden.

• Konzept und Anwendungszweck: Die Grundidee besteht darin, die Zahlenwerte in einem Lösungsvektor durch das Hinzufügen von Rauschen (noise) aus einer Normalverteilung (Gausssche Verteilung) mit dem Mittelwert 0 zu verändern. Dies ermöglicht eine flexible Balance:

  • Kleine Änderungen (hohe Wahrscheinlichkeit): Fördern die Exploitation und die Feinabstimmung der Lösung.

  • Große Änderungen (geringe Wahrscheinlichkeit): Fördern die Exploration und ermöglichen Sprünge in neue Bereiche des Suchraums.

• Bestandteile: Zur Durchführung der Gaussschen Konvolution werden folgende Komponenten benötigt:

  • x: Der Vektor der zu modifizierenden Kandidatenlösung.

  • p: Die Wahrscheinlichkeit, mit der ein einzelnes Element X_i des Vektors modifiziert wird.

  • σ²: Die Varianz der Normalverteilung N(0, σ²). Dies ist der entscheidende Parameter zur Steuerung des Verhältnisses von Exploration und Exploitation. Eine große Varianz führt zu stärkerem Rauschen und somit zu mehr Exploration.

  • min, max: Die zulässigen Minimal- und Maximalwerte für die Elemente im Vektor.

  • n: Eine Zufallszahl, die aus der Normalverteilung N(0, σ²) gezogen wird.

• Algorithmus (Modifikationsprozedur):

  1. Initialisierung: Nimm den Eingabevektor x.

  2. Iteration über Vektorelemente: Für jedes Element X_i im Vektor (von i = 1 bis I):

     1. Erzeuge eine gleichverteilte Zufallszahl zwischen 0.0 und 1.0.

     2. Prüfung der Modifikationswahrscheinlichkeit: Wenn diese Zufallszahl kleiner oder gleich p ist:

        • Wiederhole: Ziehe eine Zufallszahl n aus der Normalverteilung N(0, σ²).

        • Bis: Der neue Wert X_i + n innerhalb der zulässigen Grenzen liegt (min ≤ X_i + n ≤ max).

        • Update: Weise den neuen Wert zu: X_i ← X_i + n.

  3. Rückgabe: Gib den modifizierten Vektor x zurück.