Im letzten Artikel gab es eine Einführung in die evolutionären Algorithmen, was man mit ihnen machen kann und wie sie generell funktionieren. Wir erinnern uns: Evolutionäre Algorithmen ermöglichen das Lösen selbst komplexer Optimierungsprobleme, indem immer neue Lösungskandidaten erstellt und modifiziert werden, wobei sich die neuen Kandidaten durch einen vorgegebenen Selektionsdruck langsam dem gewünschten Ziel – der Lösung – annähern. In diesem Artikel wollen wir nun etwas tiefer in die Materie einsteigen und schauen, was bei so einem Algorithmus im Detail geschieht.
Rekapitulation
Rekapitulieren wir zuerst noch einmal die Arbeitsweise eines evolutionären Algorithmus. Ausgehend von einer Anfangsgeneration
g0 werden sukzessive neue Generationen erstellt, indem aus der aktuellen Generation jeweils einige Individuen (die Lösungskandidaten) selektiert, also ausgewählt werden; Vertreter dieser Auswahl werden rekombiniert, also miteinander gekreuzt und das entstehende neue Individuum noch einmal mutiert, also verändert. Durch Wiederholung der Rekombination und Mutation entsteht eine neue Generation, welche die Ausgangsbasis für die nächste Iteration im Algorithmus darstellt. Das ganze wird so lange wiederholt, bis eine hinreichend gute Lösung gefunden wurde. Der Pseudocode hierfür sieht so aus:
(2) t ∈ T
(3) g ∈ Tn, g ← g0
(4) do:
(5) g’, g” ∈ Tn
(6) g’ ← select individuals from g
(7) g” ← recombine individuals in g’
(8) mutate individuals in g”
(9) t ← select best individual in g”
(10) g ← g”
(11) while t not good enough
(12) return t
Schauen wir uns doch die Schritte einmal in der Reihenfolge der Ausführung im Detail an. Anzumerken ist vorher, dass es für jeden Schritt die verschiedensten Strategien gibt, deren Anwendbarkeit meist eng mit der in den jeweils anderen Schritten gewählten Strategie zusammenhängt; bei manchen Strategien kann es sogar passieren, dass Selektion und Rekombination zu einem Schritt verschmelzen. Ich werde im Folgenden das allgemeine Vorgehen bei den einzelnen Schritten beschreiben und einige der möglichen Strategien vorstellen.
Das ganze möchte ich parallel an einem kleinen Beispiel demonstrieren. Bevor ich hier aber mit einem mathematischen Problem anfange und damit zusätzliche Verwirrung stifte, nehme ich lieber ein praktisches (und nicht ganz ernst gemeintes) Problem aus der realen Welt (welches zudem zumindest jedem Katzenbesitzer bekannt sein dürfte). Betrachten wir das folgende Bild (via icanhascheezburger.com):
Das Optimierungsproblem hier dürfte klar sein: wir sind eine Katze und möchten und so positionieren, dass wir den maximalen Platz auf dem Bett einnehmen, also genau in der Mitte liegen. Tun wir zudem so, als wüssten wir nicht genau, wo die Mitte ist und würden sie durch einen evolutionären Algorithmus bestimmen wollen. Das Optimierungsproblem ist also, eine Position genau in der Mitte zu finden; die Lösungskandidaten sind die verschiedenen möglichen Positionen auf dem Bett.
Selektion
Die Selektion ist der Schritt, in welchem aus der aktuellen Generation Individuen für die Rekombination ausgewählt werden. Grundsätzlich lassen sich hier zwei Vorgehensweisen unterscheiden, deren Wahl die genaue Funktionsweise der Rekombination beeinflusst. Zum einen kann zuerst die zu rekombinierende Menge an Individuen komplett ausgewählt werden; die Rekombination erfolgt dann in der Regel, indem jeweils zwei Individuen aus der selektierten Menge zufällig ausgewählt und miteinander gekreuzt werden. Zum anderen können Selektion und Rekombination auch gleichzeitig erfolgen, indem wiederholt zuerst zwei Individuen ausgewählt und diese direkt miteinander rekombiniert werden – die Zeilen (6) und (7) im Pseudocode würden also zu einer verschmelzen und es würde keine Zwischenmenge g’ entstehen.
In jedem Fall wird aber ein Kriterium gebraucht, nach welchem die Individuen ausgewählt werden sollen. Das einfachste wäre natürlich eine zufällige Selektion; dies würde aber vollkommen den Selektionsdruck (dieser entsteht nämlich durch die Strenge der Selektion) nehmen und damit zu einer ungerichteten Evolution führen – dem Ziel würde man damit nicht näher kommen. Ein anderes Selektionsverfahren ist also notwendig!
Im Allgemeinen kann man sagen, dass eher Individuen ausgewählt werden sollen, welche “besser”, also näher an der gewünschten Lösung dran sind. Um ein Individuum nach seiner Güte zu beurteilen, wird dazu die sogenannte Fitnessfunktion (meist mit f bezeichnet) benutzt. Der Wortbestandteil “Funktion” entspricht hier ganz der mathematischen Bedeutung: die Fitnessfunktion ist eine mathematische Funktion, welche ein Individuum als Argument verlangt, dieses intern bewertet und seine Güte als einen Zahlenwert zurückgibt. Dieser Zahlenwert kann je nach Problem in einem begrenzten oder einem offenen Intervall liegen; ob die kleineren Werte “besser” sind oder die größeren, hängt auch vom Problem ab. Unabhängig davon aber können mit Hilfe der Fitnessfunktion sämtliche Individuen in der Generation bewertet und ihrer Güte nach sortiert werden – und das wird in der Regel auch zuerst gemacht.
Für die Selektion gibt es nun die verschiedensten Möglichkeiten. So können zum Beispiel streng die besten X Individuen für die weitere Rekombination ausgewählt werden, es können unter den besten X zufällig Individuen ausgewählt werden (auch mehrfach und damit auch mehr als X – ein Individuum kann sich ja wie ein Lebewesen auch mehrfach paaren) und es ist auch denkbar, unter allen Individuen beliebig zu wählen, wobei die Wahlwahrscheinlichkeit X eines Individuums umso höher ist, je höher seine Güte ist. Weitere Auswahlverfahren sind natürlich möglich; in jedem Fall wird man aber eine Menge von Individuen für die Rekombination erhalten, deren durchschnittliche Güte besser als der Durchschnitt ist – der Evolution wird damit eine Richtung gegeben. Je strenger übrigens der Parameter X gewählt wird, desto stärker ist der Selektionsdruck; im extremsten Fall wird nur noch das beste Individuum zur Rekombination ausgewählt (warum das keine gute Idee ist, sehen wir aber ein andermal). Schreiben wir die Selektion einmal im Pseudocode auf (f ist unsere Fitnessfunktion):
(2) for all t ∈ g:
(3) t.fitness ← f(t)
(4) g’ ∈ Tn, g’ ← {}
(5) while not enough elements in g’:
(6) t ∈ T
(7) t ← select element from g according to strategy
(7) g’ ← g’ ∪ {t}
(8) return g’
Angewendet auf unser Katzenproblem haben wir als Fitnessfunktion natürlich diejenige Funktion, welche die Entfernung von einer Position zur Bettmitte bestimmt; niedrigere Zahlen sind also besser, die 0 wäre das Optimum. Wir nehmen an, dass die Funktion das auf magische Art und Weise bestimmt, da wir ja – wie abgesprochen – nicht wissen, wo die Mitte ist (bei der Lösung realer Probleme weiß man in der Regel auch nicht, wie die beste Lösung aussieht, kann aber die Güte der Individuen trotzdem meist auf die ein oder andere Art berechnen oder wenigstens schätzen). Hier ein kleines Beispielbild mit einigen möglichen (zufällig generierten) Lösungskandidaten, ihrer Güte (geschätzte Entfernung zur Mitte) und (schwarz markiert) denjenigen Individuen, die für die Rekombination nach einer nicht näher benannten Strategie ausgewählt wurden (der schwarze Punkt in der Mitte ist, nun, die Mitte):
Rekombination
Wurde durch Selektion eine Menge von geeigneten Individuen ausgewählt, können wir nun daran gehen, diese miteinander zu (re-)kombinieren, sie miteinander zu kreuzen. Dazu wählt man jeweils zwei Individuen zufällig aus der selektierten Menge aus (oder selektiert, wie bereits erwähnt, erst an dieser Stelle 2 Individuen aus der Gesamtmenge) und vermischt ihre Eigenschaften miteinander, ganz so, wie es bei der natürlichen Fortpflanzung geschieht (das ist jetzt natürlich etwas vereinfachend dargestellt, aber als Analogie geeignet). Jedes Individuum hat in der Regel eine feste Menge an Eigenschaften, genau wie ein Lebewesen (zum Beispiel Haar- oder Fellfarbe, Körpergröße, Blütenblattfarbe und ähnliches) und genau wie in der realen Welt erbt ein erzeugtes Individuum eine Mischung der Eigenschaften seiner Eltern (an etwaig mitlesende Biologen: dominante und rezessive Vererbung spielen bei evolutionären Algorithmen keine Rolle, da jedes Individuum eher einer Keimzelle entspricht und damit haploid ist). Die Vermischung kann auch auf unterschiedliche Arten erfolgen, etwa, indem jede der möglichen Eigenschaften zufällig von einem der beiden Rekombinationspartner gewählt wird oder indem die erste Hälfte der Eigenschaften vom ersten und die zweite Hälfte vom zweiten Partner übernommen wird. Weitere Strategien sind denkbar und ich werde im nächsten Artikel noch eine Möglichkeit vorstellen, wie jede denkbare Rekombinationsstrategie unabhängig von den Eigenschaften ausgeführt werden kann. Hier soll es erst einmal genügen, wenn wir sagen, dass die Eigenschaften je zweier Individuen zu einem neuen Individuum kombiniert werden, welches dann eine Mischung aus Eigenschaften seiner beiden Eltern besitzt. Im Pseudocode sieht das so aus:
(2) g’ ∈ Tn, g’ ← {}
(3) while not enough elements in g’:
(4) t, t1, t2 ∈ T
(5) (t1, t2) ← select randomly from g
(6) t ← recombine t1 and t2 randomly
(7) g’ ← g’ ∪ {t}
(8) return g’
Insgesamt müssen natürlich genügend neue Individuen entstehen, damit die nächste Generation genauso mächtig ist wie die vorherige. Ist sie kleiner, würden irgendwann keine Individuen mehr übrig sein; ist sie größer, würde die Populationsgröße immer weiter zunehmen mit dem Ergebnis, dass irgendwann der Speicher des Computers voll wäre. Übrigens müssen nicht immer genau zwei Individuen miteinander rekombiniert werden; es können natürlich auch mehr sein – zwei hat sich aber als relativ günstige Zahl erwiesen.
Wenden wir nun den Rekombinationsalgorithmus auf unsere selektierten Positionen des Katzenproblems an. Eine Position hat dabei in der Regel lediglich zwei Eigenschaften, nämlich die vertikale und die horizontale Position auf dem Bett. Die Rekombination zweier Eltern soll also immer so geschehen, dass vom ersten Elter die vertikale und vom zweiten Elter die horizontale Position genommen und zu einem neuen Individuum vermischt werden. Wir erhalten damit aus den alten Individuen (grau, diese werden nach diesem Schritt verworfen) die neuen (schwarz), wobei einige der Rekombinationen zweier Eltern mit ihrem Ergebnis durch Pfeile gekennzeichnet sind. Eine Güte wurde für die neuen Kinder jetzt noch nicht eingetragen, da sie noch nicht berechnet wurde (wir sehen aber schon, dass einige der neu generierten Individuen besser sind als ihre Eltern); wie man sieht, stehen die im vorherigen Schritt nicht selektierten Individuen gar nicht mehr zur Diskussion:
Mutation
Damit bleibt noch ein letzter Schritt zu klären: die Mutation. Sie sorgt dafür, dass in den vorhandenen Pool an Eigenschaften (den Genpool) etwas Bewegung kommt und neue Eigenschaften entstehen. Ohne die Mutation würde sich der evolutionäre Algorithmus nämlich im Kreis drehen, da immer nur Individuen mit den gleichen Eigenschaften entstehen würden.
Die Mutation an sich ist relativ simpel: jedes der bei der Rekombination entstandenen Individuen wird hergenommen und eine, einige oder alle seiner Eigenschaften zufällig verändert. Die Stärke der Mutation ist dabei oft ein einstellbarer Parameter, da je nach Problem stärkere oder schwächere Mutationen von Vorteil sein können. Auch hier existiert wie bei der Rekombination ein Verfahren, welches unabhängig von den tatsächlichen Eigenschaften der Individuen (also für alle denkbaren Individuen aller möglichen Probleme) eine Mutation durchführen kann und welches ich im nächsten Artikel vorstellen werde. Der Pseudocode für die Mutation sieht denkbar einfach aus:
(2) for all t ∈ g:
(3) t ← mutate t randomly
(4) return g
Bei unserem Katzenproblem sind die mutierbaren Eigenschaften natürlich wieder die vertikale und die horizontale Position auf dem Bett. Jedes der bei der Rekombination entstandenen Individuen wird nun mutiert, also ein klein wenig auf dem Bett in eine zufällige Richtung verschoben (da wir ja, wie abgesprochen, gar nicht wissen, wo die Mitte ist, können wir auch nicht einfach pauschal “zur Mitte hin” schieben). Bildlich ausgedrückt sieht das so aus (zugegeben, es wirkt etwas chaotisch, aber die Intention sollte erkennbar sein); grau sind die “alten” (rekombinierten) Individuen, der Pfeil zeigt die Schieberichtung an und die schwarzen Kreise markieren die Individuen, welche die nächste Generation bilden werden.
Abschluss
Der Algorithmus würde nun von vorne beginnen und aus den neu erstellten Individuen wiederum eine geeignete Auswahl treffen, diese rekombinieren und mutieren – so lange, bis ein genügend gutes Individuum gefunden wurde. “Genügend gut” liegt hier natürlich immer im Auge des Problemlösers. Ist die Güte der besten Lösung bekannt (im Katzenbeispiel etwa die Entfernung zur Mitte), kann so lange gerechnet werden, bis ein Individuum mit genau dieser Güte oder einer um nicht mehr als X% abweichenden Güte gefunden wurde. Ist die beste Güte dagegen nicht bekannt (was bei vielen Optimierungsproblemen der Fall ist), kann eine bestimmte Anzahl von zu berechnenden Generationen vorgegeben werden, in der Hoffnung, dass nach dieser Zeit bereits ein relativ guter Lösungskandidat gefunden wurde. Alternativ kann das Abbruchkriterium auch sein, dass sich über eine bestimmte Anzahl von Generationen hinweg der durchschnittliche Gütewert einer Generation nicht mehr wesentlich ändert; das kann nämlich auch passieren, dann ist man in einem sogenannten lokalen Optimum gelandet (was das ist, besprechen wir auch ein andermal).
Evolutionäre Algorithmen haben die Eigenschaft, dass für ansonsten schwierig zu berechnende Probleme auf relativ einfache Art und Weise eine gute Lösung gesucht werden kann. Ihr größter Vorteil ist hierbei vor allem die Geschwindigkeit der Berechnung; die traditionelle Suche nach einer guten Lösung eines schwierigen Problems verschlingt meist so viel Zeit, dass sie nicht praktikabel ist. Ein evolutionärer Algorithmus bietet hier einen Ausweg, der zwar nicht zwangsläufig die beste Lösung findet, aber zumindest eine hinreichend gute, und das in annehmbarer Zeit. Betrachten wir zum Beispiel das Katzenproblem; innerhalb einer einzigen Generation wurden aus diesen zufällig generierten Lösungskandidaten
durch Selektion, Rekombination und Mutation diese Kandidaten erzeugt:
Die Kandidaten sind dabei eindeutig mehr Richtung Mitte gewandert. Noch einige Generationen mehr und es kann bereits eine sehr gute Lösung für das Positionierungsproblem verfügbar sein!
Natürlich haben auch die evolutionären Algorithmen Probleme. Insbesondere die Behandlung von lokalen Optima ist hier wichtig (was man genau darunter versteht und wie man sie vermeidet, besprechen wir demnächst). Zudem ist das aktuell beschriebene Vorgehen zwar anwendbar, jedoch sehr problemspezifisch; durch die gezielte Auswahl und Mutation von Eigenschaften ist ein einmal programmierter Algorithmus nur für genau das Problem zu benutzen, für welches er programmiert wurde. Wie man das eleganter lösen kann, möchte ich im nächsten Artikel aufzeigen.
Kommentare (10)