#Evolutionäre Algorithmen – Die Evolution als Vorbild zur Problemlösung – Teil 4 – Von Bits und Bytes

So, hier nun endlich – mit einiger Verspätung (ich weiß gar nicht, wie Florian neben der Arbeit noch so produktiv im Blog sein kann) – der vorerst letzte Teil der Reihe zu den evolutionären Algorithmen. Wir erinnern uns: in Teil 1 wurde vorgestellt, was sich überhaupt unter evolutionären Algorithmen vorgestellt werden kann. In Teil 2 wurde dann ihre allgemeine Funktionsweise besprochen und in Teil 3 habe ich vorgestellt, wie mit Hilfe aus der Genetik bekannten Mitteln die Arbeitsweise der Algorithmen verbessert und verallgemeinert werden kann. Zum Abschluss soll es heute nun noch darum gehen, welche Probleme bei der Nutzung von evolutionären Algorithmen auftreten können und wie sie sich – zumindest teilweise – vermeiden lassen.

Das generelle Problem evolutionärer Algorithmen (im weiteren auch einfach als EA bezeichnet) ist, dass sie nicht wirklich zielgerichtet arbeiten; nicht zielgerichtet heißt, dass der “Wert” der optimalen Lösung meist nicht bekannt ist und daher auch nicht gezielt danach gesucht werden kann. Es kann lediglich gesagt werden, welche von 2 möglichen Lösungen für ein Problem die bessere ist. Die eigentliche Problemlösung besteht also aus der Suche nach einer möglichst optimalen Lösung (daher der Name Optimierungsproblem) und nicht aus der Suche nach der optimalen Lösung (weil sie eben meist nicht bekannt ist).

Das ganze lässt sich auch grafisch sehr gut veranschaulichen. Ein Optimierungsproblem besitzt eine (endliche oder unendliche, das spielt keine Rolle) Menge an Lösungen (Individuen), wobei jede Lösung einen bestimmten Fitness-Wert hat. Zudem besitzt der Phänotyp – das Erscheinungsbild – der Lösungen eine bestimmt Anzahl von Parametern (im Katzenbeispiel waren es etwa 2: die x- und die y-Koordinate auf dem Bett). Bei nicht allzu vielen Parametern (im Grunde nur bei 1 oder 2) kann man zur Verdeutlichung der Problematik ein Diagramm anlegen, welches für jede Parameterwahl die Fitness anzeigt

Nehmen wir zum Einstieg das Katzenbeispiel; in diesem Fall besitzt der Phänotyp 2 Parameter (die x- und die y-Koordinate), stellt also ein zweidimensionales Problem dar. Zur Darstellung im Diagramm bietet sich hier zum Beispiel die Nutzung von Graustufen an; weiße Bereiche stellen “gute”, im Katzenbeispiel also zentrumsnahe Positionen dar, schwarze Bereiche eher “schlechte Positionen, also solche, die weiter Weg vom Zentrum sind. Für das Katzenbeispiel ergibt sich hier ein relativ homogenes Bild mit einem weißen Zentrum und gleichmäßig dunkler werdenden Bereichen:

 

Eine Anmerkung noch, bevor es weitergeht: wenn wir nicht nur auf 3 Dimensionen beschränkt wären, ließen sich auch Probleme mit mehr Parametern darstellen; so beschränken wir im Folgenden aber auf Grund physikalischer Gesetzmäßigkeiten auf 1 und 2 Dimensionen – alles gesagt ist aber natürlich ebenso auf komplexere Probleme anwendbar!

Jetzt ist das Katzenbeispiel relativ simpel, da der Kurvenverlauf für die Fitnesswerte relativ eindeutig ist: von jedem Punkt des Koordinatensystems aus werden die Werte zur Mitte hin besser und erreichen genau in der Mitte ihr Optimum. Reale, durch evolutionäre Algorithmen lösbare und gelöste Probleme haben diesen Luxus nicht. Ein (beliebiges) anderes Problem mit 2 Parametern könnte etwa das folgende Fitnessdiagramm aufweisen (welches natürlich so meist überhaupt nicht bekannt ist – wir tun nur einmal so, als würden wir es kennen):

 

Im Bild erkennen wir, dass neben dem “besten” Optimum links oben noch ein “weniger gutes” Optimum rechts unten existiert (für die Sprachpedanten unter den Lesern: ich weiß, dass es kein “bestes” oder “weniger gutes” Optimum geben kann – die Begriffe sind hier eher umgangssprachlich gemeint; man möge mir verzeihen). Das Optimum oben links wollen wir im Folgenden als globales Optimum bezeichnen, da es global (also im ganzen Diagramm) das beste ist; das Optimum rechts unten ist dementsprechend ein lokales Optimum, da es lokal (unmittelbar in seiner Umgebung) den besten Wert darstellt (das globale Optimum ist somit auch gleichzeitig ein lokales). Gängige Probleme der Realität haben nicht nur 2 lokale Optima, sondern viel viel mehr, und leider weiß man in der Regel nicht, wo denn diese lokalen Optima liegen.