Tiere, Pflanzen oder Bakterien sind lebende Lösungen der kompliziertesten Optimierungsprobleme: mit möglichst wenig Aufwand die Bedürfnisse des eigenen Stoffwechsels zu befriedigen, Stabilität oder Schutz gegen Feinde zu erreichen und vieles mehr. Solche optimalen Lösungen haben sich im Laufe der Evolution herausgebildet, indem durch Kreuzung und Mutation neue Kombinationen von Erbanlagen entstanden und der Auslese ausgesetzt wurden. Was für lebende Organismen eine erfolgreiche Strategie ist, stellt sich auch für das Optimieren mit einem Computer als nützlich heraus. Die sogenannten genetischen Algorithmen, deren Wirkungsweise weitgehend der natürlichen Evolution abgeschaut ist, sind bei der Lösung mancher Probleme überraschend erfolgreich. John H. Holland hat sie in dieser Zeitschrift (September 1992, Seite 44) eingehend beschrieben. Wer tieferen Einblick in ihre Wirkungsweise gewinnen will, tut gut daran, mit einem einfachen Problem anzufangen, dessen Lösung er schon kennt. Von dort zu komplizierteren Problemen vorzudringen ist dann nicht allzu schwer. Ich habe das Problem gewählt, denjenigen Punkt x im Intervall zwischen 0 und p zu finden, in dem die Funktion f(x)=x+|sin(32x)| ihren maximalen Wert annimmt. (Winkel werden im Bogenmaß gemessen, so daß p dem Winkel 180 Grad entspricht.) Diese Funktion hat 32 Oszillationen, die zu der Geraden f(x)=x addiert werden (Bild 1). Da f(x) immer positiv ist, kann dieser Wert direkt als Maß für die Tauglichkeit dienen. Man sieht zwar auf den ersten Blick, wo das gesuchte Maximum liegt; gleichwohl ist die Aufgabe für einen klassischen Optimierungsalgorithmus nicht ohne Tücken. Ein solcher sucht nämlich typischerweise in der Umgebung eines x-Wertes, der als vorläufige Näherung an das Optimum anzusehen wäre, nach Werten, die noch größer sind. Dabei findet er zwar lokale Maxima, Stellen, an denen es rechts wie links nur abwärts geht, wird jedoch nie über die scharfkantige Grenze zwischen zwei Buckeln der Funktion hinwegkommen und daher möglicherweise weit links in einem schlechten Nebenmaximum steckenbleiben. Andererseits erfordert wahlloses Herumprobieren bei realitätsnahen Problemen einen maßlosen Aufwand. Die Kunst besteht darin, einerseits Erreichtes nicht aufzugeben, andererseits sich die Chance einer unerwarteten Entdeckung nicht entgehen zu lassen (vergleiche "Toleranzschwelle und Sintflut: neue Ideen zur Optimierung" von Gunter Dueck, Tobias Scheuer und Hans-Martin Wallmeier, Spektrum der Wissenschaft, März 1993, Seite 42). Man rühmt die genetischen Algorithmen wegen einer besonders eleganten Balance zwischen diesen Zielen. Anstelle der Individuen einer echten Population verwendet ein genetischer Algorithmus eine Anzahl von Bit-Ketten, die er nach evolutionsähnlichen Regeln gegeneinander antreten läßt. Jede Bit-Kette steht für eine potentielle Lösung des gestellten Problems. Indem jeweils nur die tauglichsten (im Sinne der Problemstellung optimalen) Individuen zur Fortpflanzung zugelassen werden, entwickelt sich die Population auf die Dauer in Richtung besserer Lösungen. Ich habe für meinen Algorithmus die Programmiersprache C gewählt; aber man kann auch irgendeine andere Sprache nehmen. Ich empfehle Ihnen, einen genetischen Algorithmus in zwei Schritten zu entwickeln. Schreiben Sie zuerst ein Programmstück, das eine zufallsbestimmte Anfangspopulation erzeugt. Weitere Teile des Programms sollen die Tauglichkeit aller Individuen bestimmen, sie nach diesem Kriterium in eine Reihenfolge bringen und die mittlere Tauglichkeit einer Population berechnen können. Eine Anzeige dieser Größen auf dem Bildschirm wäre hilfreich. Im zweiten Schritt fügen Sie dann Unterprogramme für den eigentlichen genetischen Algorithmus hinzu. Diese sollen also Elternpaare aus der gegenwärtigen Population auswählen und Nachkommen dieser Eltern durch Crossing-over und Mutation erzeugen. Die Individuen unserer Population sind die x-Werte (denn wir suchen den optimalen unter ihnen). Wie kann man diese in einer Form darstellen, die der genetische Algorithmus zu verarbeiten vermag, zum Beispiel – wie in Hollands Artikel beschrieben – durch Bit-Ketten? Für meine ersten Experimente habe ich Ketten der Länge L=16 gewählt. (Wenn man L vergrößert, nimmt die Genauigkeit der Lösung zu.) Jede dieser Ket- ten kann als Binärzahl zwischen 0 und interpretiert werden. Da ich aber Zahlen zwischen 0 und darstellen will, multipliziere ich die jeweilige Binärzahl mit . Somit steht die Bit-Kette 0000000000000000 für x=0, 0000000000000001 für , ebenso 0000000000000010 für und so weiter bis 1111111111111111, was für den maximalen Wert steht. (Der Wert selbst ist ausgeschlossen, denn es ist keine Kette mehr übrig, die ihn repräsentieren könnte.) Prüfen wir einmal Ihr intuitives Verständnis: Können Sie sich denken, welchen Wert die Folge 1000000000000000 bezeichnet? Kurz gesagt, die Bit-Ketten repräsentieren Werte für x, die in gleichmäßigem Abstand voneinander das Intervall zwischen 0 und überziehen. Der Algorithmus durchsucht nun den Raum dieser Bit-Ketten und damit eigentlich eine feinverteilte Menge möglicher Werte für x. Wenn man diese Abbildung von Bit-Ketten in den Definitionsbereich von f erst einmal festgelegt hat, ist es interessant zu verfolgen, wie Schemata abgebildet werden. Ein Schema – in Hollands Terminologie: ein Teilgebiet – ist eine Menge von Bit-Ketten, für die nur die Werte an bestimmten Stellen vorgeschrieben sind. Beispielsweise besteht das Schema 0*************** aus allen Ketten, die mit 0 beginnen. (Sterne stehen für nicht festgelegte Bitwerte.) Dieses Schema wird in die linke Intervallhälfte abgebildet, also auf die Zahlen zwischen 0 und . Das Schema 1*************** entspricht der anderen Hälfte zwischen und . Der Mittelwert der Funktion f(x) über 0*************** ist kleiner als der über 1***************. In einer Zufallspopulation von Ketten sollte also die mittlere Tauglichkeit der Individuen aus der ersten Region kleiner sein als der entsprechende Wert für die zweite. Einige meiner Unterprogramme können die Individuen aus jedem vom Benutzer vorgegebenen Schema verfolgen (also beispielweise alle Ketten, die mit 1 beginnen, oder alle, die mit 001 enden, und so weiter). In jeder Generation zählt das Programm die Anzahl der Individuen in der Population, die zu der angegebenen Region gehören, und berechnet deren mittlere Tauglichkeit. So erhält man eine explizite Schätzung für die mittlere Tauglichkeit des Gebiets. Um Ihre Intuition noch einmal zu testen, versuchen Sie doch einmal, einige andere Schemata in den Definitionsbereich von f abzubilden, und untersuchen Sie die Individuen, die in diese Gebiete geraten. Können Sie Schemata angeben, die jede Oszillation von f in acht nebeneinanderliegende Gebiete teilen? Wie groß ist die mittlere Tauglichkeit jeder Region? Wenn die erste Version Ihres Programms zufriedenstellend funktioniert, sollten Sie die Unterprogramme für den Kern des genetischen Algorithmus hinzufügen. Ein Unterprogramm geht alle Individuen einer Population durch und ordnet jedem einen f(x)-Wert als Tauglichkeit zu. Abweichend von Hollands Artikel werden zur Fortpflanzung nicht einfach die tauglichsten Individuen zugelassen, sondern es findet eine Art Brunstkampf statt: Ein entsprechendes Unterprogramm wählt wiederholt per Zufall zwei Individuen aus und reiht eines der beiden – stellen wir uns den Gewinner des Zweikampfs vor – in die neue Population ein; das ist, abhängig vom Zufall, mit einer Wahrscheinlichkeit von 75 Prozent das tauglichere der beiden. Insgesamt werden die tauglicheren Individuen mehr Nachkommen in der neuen Generation haben als die weniger tauglichen. Vielleicht finden Sie es sinnvoll, das tauglichste aller Individuen in jedem Fall (unabhängig vom Ausgang eines Zweikampfs) in die nächste Generation zu kopieren. Beachten Sie, daß der Selektionsdruck vergrößert wird, wenn Sie den Wert 75 Prozent für die oben genannte Wahrscheinlichkeit erhöhen (es wird für weniger taugliche Ketten schwieriger, in die nächste Generation kopiert zu werden), während ein kleinerer Wert den Selektionsdruck vermindert. Bei einem Wert von 50 Prozent gibt es überhaupt keinen Selektionsdruck. Ein weiteres Unterprogramm sollte per Zufall mit einigen Paaren (typischerweise mit 75 Prozent aller Paare) aus der durch Zweikampf ermittelten Population die Crossing-over-Operation durchführen. Ich habe die Variante mit einem einzigen Kreuzungspunkt verwendet, die Holland in seinem Artikel beschreibt. Meine Version mutiert auch einige wenige zufällig gewählte Bits in den einzelnen Ketten, das heißt, ändert eine 1 in eine 0 ab oder umgekehrt. Eine typische Mutationsrate ist 0,005 pro Bit: Im Durchschnitt wird jedes zweihundertste Bit umgedreht.

Anwendung

Sobald die Implementation vollständig ist, können Sie anfangen zu experimentieren. Starten Sie das System zunächst mit einer Zufallspopulation von 200 Ketten und lassen Sie es über 50 Generationen laufen. Beobachten Sie, wie die mittlere und die maximale Tauglichkeit von Generation zu Generation anwachsen. Vergleichen Sie die Ergebnisse für verschiedene Populationsgrößen, Crossing-over- und Mutationsraten. Ich fand es am zweckmäßigsten, Mittelwerte aus mehreren Läufen zu nehmen, die jeweils mit anderen Zufallspopulationen begannen.

Besonders interessant ist es, die Verteilung der Individuen auf die acht genannten Gebiete zu verfolgen. Diese sind durch die Schemata *****000********, *****001******** und so weiter bis *****111******** definiert. Sie zerlegen das gesamte Intervall so, daß jedes der 32 Oszillationsintervalle von f(x) aus einem Stück des ersten Schemas, einem Stück des zweiten und so weiter besteht – in dieser Reihenfolge. Insbesondere besetzen *****011******** und *****100******** die Mitte jedes Buckels (Bild 2); unter den Ketten aus diesen Teilgebieten sind die Punkte größter Tauglichkeit zu finden. (Das Problem ist mit Bedacht so gebaut, daß die genannten Schemata nützliche kompakte Bausteine sind.)

Eine zufällig bestimmte Anfangspopulation müßte etwa gleich viele Individuen in jedem der acht Schemata enthalten. Während der genetische Algorithmus abläuft, sollten Sie im Mittel zunehmend mehr Individuen in den beiden zentralen Schemata finden als in den anderen sechs – obwohl viele Elemente in ihnen für kleine x-Werte mit geringer Tauglichkeit stehen. Das liegt daran, daß diese Schemata eine höhere mittlere Tauglichkeit haben als die anderen.

Durch Beobachtung der acht Schemata versuchte ich herauszufinden, wie stark der Algorithmus seine Suche auf Individuen großer Tauglichkeit konzentriert. Ich ließ für jede Generation die Anzahl der Individuen und ihre mittlere Tauglichkeit je Schema sowie die mittlere Tauglichkeit der Gesamtpopulation aufzeichnen. Nach den theoretischen Sätzen, die Holland in seinem Artikel erwähnt, müßte die Individuenzahl in Gebieten mit überdurchschnittlicher (empirischer) mittlerer Tauglichkeit zunehmen, in den anderen dagegen abnehmen.

Für eine Population von 400, eine Crossing-over-Rate von 0,75 und eine Mutationsrate von 0,001 bestätigte das Programm diese Voraussage in ungefähr zwei Dritteln der Fälle. Je größer die Crossing-over- und die Mutationsrate und je kleiner die Populationsgröße waren, desto schlechter wurde die Vorhersage erfüllt. Das ist plausibel und in Übereinstimmung mit der Theorie, denn größere Mutations- und Crossing-over-Raten zerstören gute Bausteine (Schemata) häufiger, und für kleinere Populationen machen sich statistische Schwankungen deutlicher bemerkbar.

Nachdem Ihr genetischer Algorithmus über viele Generationen gelaufen ist, werden Sie wahrscheinlich feststellen, daß ein Großteil der Population aus sehr ähnlichen oder gar identischen Ketten besteht. Dieses Phänomen heißt Konvergenz und tritt auf, weil der Algorithmus die Population in immer engere Zielgebiete lenkt. Oft konvergiert sie gegen ein nicht-optimales Individuum: Der Algorithmus bleibt in einem lokalen Optimum stecken. Konvergenz kann sehr hinderlich sein, denn sie macht das Crossing-over nahezu wirkungslos – aus zwei gleichen Ketten gehen wieder dieselben hervor, es geschieht nichts Neues mehr.

Konvergenz gegen die falsche Lösung zu verhindern ist ein sehr aktuelles Forschungsziel. Eine mögliche Abhilfe besteht darin, den Selektionsprozeß so zu modifizieren, daß die Population stets eine gewisse Vielfalt bewahrt. Man kann zum Beispiel einem Individuum einen Selektionsvorteil dafür zuschreiben, daß es in einem dünn besetzten Gebiet liegt, so wie in der natürlichen Evolution eine Art davon profitiert, daß sie in ihrer speziellen Nische wenig Konkurrenz hat.


Gefangenendilemma

Sie können den genetischen Algorithmus selbstredend auch auf andere Probleme als die Maximierung von Funktionen anwenden. Ich habe mit mäßigem Aufwand das hier beschriebene Programm für eine Variante des Gefangenendilemmas umgeschrieben. Bei diesem Spiel hat jeder von zwei Gefangenen die Wahl zwischen Kooperation (das heißt, er schweigt über das gemeinsam begangene Verbrechen) oder Verrat (das heißt, er stellt sich als Kronzeuge zur Verfügung). Leider weiß der eine nicht, was der andere tun wird. Wenn er kooperiert und sein Komplize ihn verrät, wird dieser freigesprochen, und der Schweiger kommt für 10 Jahre ins Gefängnis. Wenn beide schweigen, kommen sie mit drei Jahren davon. Wenn aber beide aussagen, werden sie zu je 7 Jahren verurteilt.

Mein modifizierter genetischer Algorithmus probierte zahlreiche Strategien viele Male gegen denselben Gegenspieler aus. Die Bit-Kette eines jeden Individuums steht für zwei Zahlen (p,q), wobei p die Wahrscheinlichkeit für Kooperation angibt unter der Voraussetzung, daß der Gegner im letzten Spiel kooperiert hat, und q die Wahrscheinlichkeit für Kooperation im anderen Fall. Beispielsweise ist (1,0) die Tit-for-Tat-Strategie, und (0,1, 0,1) ist nahezu die Strategie des konsequenten Verrats.

Der genetische Algorithmus zeigt in diesem Spiel ein besonders interessantes Verhalten, wenn die Bit-Kette jedes Individuums eine sogenannte Erkennungsmarke enthält: einige Bits, die der Gegner lesen kann (die aber an und für sich nichts über die Strategie des Individuums aussagen). Einige andere Bit-Positionen beschreiben dann vielleicht, wie die eigene Strategie von der Erkennungsmarke des Gegners abhängig ist, beispielsweise, ob ein Individuum vorzugsweise mit solchen kooperiert, die eine der eigenen ähnliche Erkennungsmarke tragen, oder – wenn es in einer Variante des Spiels die Wahl hat – sich nur mit seinesgleichen zum Spiel bereitfindet. Unter diesen Bedingungen kann sich eine Population entwickeln, in der Tit-for-Tat-Spieler zuverlässig an ihren Erkennungsmarken erkennbar sind und manche Individuen davon profitieren, indem sie vorzugsweise mit solchen Gegnern spielen.

Aus recht einfachen Genstrukturen kann sich eine komplizierte Populationsdynamik entwickeln. Beispielsweise sind Mimikry und andere Formen des Betrugs denkbar: Ein Betrüger würde eine Erkennungsmarke tragen, die bisher nur kooperativen Individuen anhaftete. Mit etwas Phantasie können Sie weitere einfache Genstrukturen erfinden und Ihrem Computer komplexe Evolutionsprozesse entlocken.

Wer ein solches Programm nicht selbst erstellen, aber dennoch mit einem einfachen genetischen Algorithmus experimentieren möchte, kann vom Verlag eine Diskette mit einem Programm namens Genalgor beziehen. Bernhard Foltz hat die in diesem Artikel beschriebenen Grundzüge des Algorithmus in ein Programm umgesetzt, das dem Benutzer zahlreiche komfortable Möglichkeiten zur Beobachtung des evolutionären Geschehens und zum Eingreifen bietet (siehe Anzeige auf Seite 26).

Literaturhinweise

- A Comparative Analysis of Selection Schemes Used in Genetic Algorithms. Von David E. Goldberg und Kalyanmoy Deb in: Foundations of Genetic Algorithms. Herausgegeben von Gregory J. E. Rawlins. Morgan Kaufmann, 1991.

– Handbook of Genetic Algorithms. Herausgegeben von Lawrence Davis. Van Nostrand Reinhold, 1991.

– Tit for Tat in Heterogeneous Populations. Von Martin A. Nowak und Karl Sigmund in: Nature, Band 355, Heft 6357, Seiten 250 bis 253, 16. Januar 1992.


Aus: Spektrum der Wissenschaft 1 / 1994, Seite 12
© Spektrum der Wissenschaft Verlagsgesellschaft mbH