Suchraum: Exploration und Exploitation

Der Suchraum eines Problems wird durch dessen Variablensatz $V$ bestimmt. Die darin enthaltenen $n$ Variablen spannen den $n$-dimensionalen Suchraum auf. Wird jedem Punkt des Suchraums durch die Zielfunktion ein Ergebniswert zugeordnet, so kann der Suchraum als hyperdimensionale Ergebnislandschaft mit $n+1$ Dimensionen angesehen werden [27]. Eine Ergebnislandschaft mit mehreren Optima (Minima oder Maxima) wird als multimodal bezeichnet.

Als Exploitation^3.14 wird der Prozess bezeichnet, bei dem Information von früher besuchten Punkten im Suchraum für die Bestimmung der nächsten zu untersuchenden Punkte benutzt wird. Als Beispiel können einfache Hillclimber dienen, welche über Gradienteninformation oder über die Auswertung einiger benachbarter Punkte die Richtung ihres nächsten Schrittes bestimmen. Ein solches Verfahren eignet sich also gut, um ein lokales Optimum zu bestimmen.

Im Gegensatz dazu steht die Exploration. Hier werden Sprünge ins ``kalte Wasser'' unbekannter Regionen gewagt, zu denen keine Information über die Güte zur Verfügung steht. Aufgabenstellungen, deren Lösung viele lokale (Sub-) Optima enthält, können oftmals nur unter Zuhilfenahme von Exploration gelöst werden [27].

Entscheidend für den Erfolg eines Genetischen Algorithmus mit multimodaler Problemstellung wird also die richtige Mischung aus Exploration und Exploitation sein. Dazu dienen die beiden Operatoren Crossover - mit explorativem und exploitativem Charakter - und Mutation, mit rein explorativem Anteil.