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
Kommentare (10)