Lokale Suche und Optimierung

Kernmechanismus eines lokalen Suchalgorithmus ist die

Ähnlichkeitsvariation der Objektvariablen V einer beliebigen Qualitätsfunktion. Die Variation ∆V n

der Objektvariablen V ist komplementär zu ihrer Variablenvergangenheit V n .

V n+1 = V n + ∆V n

(1)

Die Lokale Suche ist transient. Sie nutzt Eigenschaften einer (fluktuativen) Entwicklung des Systems hinsichtlich seiner

Zustandseigenschaften über die Zeit. In fortschreitenden diskreten Intervallen (n) erhalten wir eine über das Qualitätsgelände der gestellten Optimierungsaufgabe verlaufende Spur der Systemzustände,

beschrieben durch den Vektor V der Objektvariablen in einer Ahnenfolge (V n+1 , V n+2 , V n+3 ,….usw.).

Zu den leistungsfähigsten lokal arbeitenden Optimierungsstrategien gehören heute die Evolutionären Algorithmen: Genetische Algorithmen (GA) und Evolutionsstrategie (ES). Bei der Evolutionsstrategie wird die Ähnlichkeitsvariation ∆V n durch den mit der Variationsschrittweite δ δ n δ δ

dotierten Zufallszahlenvektor Z bestimmt:

V m, n+1 = V m, n + δ δ m, n Z m, n δ δ (2)

Evolutionäre Algorithmen (hier Evolutionsstrategien) simulieren das biologische Wechselspiel von Variation und Selektion in jeder Generation und wenden es auf mathematisch modellierte Optimierungsaufgaben an. Dabei werden in einem einfachsten Szenario m Kopien eines Startsystems erstellt. Zufällige Modifizierungen führen auf eine Schar von m Variationen ∆V m,n des Elter-Systems (Mutation).

Lokale Suche und Optimierung

In jeder Generation n werden alle Variationen des aktuellen Elter (in bestimmten Strategien einschließlich dem Elter, siehe [Rec-94]) mittels einer Zielfunktion einer Bewertung unterzogen, die Qualität aller Systeme wird berechnet oder gemessen (Evaluation). MUTANTEN und ELTER, respektive ihre Qualitäten, bilden somit ein gemeinsames Selektionsensemble. Aus der Schar bewerteter Systeme wird ein neuer, aktueller Elter für die folgende Generation erwählt (Selektion). Mit der Variation dieses Elter-Systems setzt sich die Kampagne fort. Auf diese Weise steigt die Qualität des Ensembles von Generation zu Generation, bzw. fällt nicht hinter die des aktuellen Elter zurück. Aus biologistischer Sicht betrachtet, untersuchen Evolutionsstrategien (jedoch nur) den Phänotyp eines Zielsystems und zielen somit auf das „äußere Evolutionsgeschehen“.

Der Variation kommt bei evolutionären Algorithmen eine besondere Bedeutung zu. In unserem Szenario sollen normalverteilt zufällige Variationen den Objektvariablen- Vektor des Nachkommen von dem des ELTER unterscheiden.

Neben den Merkmalen des als ELTER der nächsten Generation bestellten Nachkommen wird ein Strategieparameter vererbt: die Variations-Schrittweite δ δ. Sie ist in einfachen Evolutionsstrategien ein δ δ Skalar δ δ n (globale Schrittweite) oder den Komponenten des δ δ

Objektvariablen- Vektors V m, n zugeordnet δ δ m, n (individuelle Schrittweite) δ δ

Ein einfachster evolutionärer Algorithmus besteht wenigstens aus den drei formalen Elementen: