In der Frühzeit der Computerei - also in jenen fernen, dunklen Tagen ohne Betriebssysteme, Compiler oder gar 4GL-Verheißungen - da erschien so manchem Informatiker der ersten Stunde das Programmieren eines Rechners in Machinensprache doch als arg mühselige Plackerei. Und so tauchte denn auch schon früh die Idee auf, das Programmieren doch lieber einfach "von selbst" geschehen zu lassen; und zwar ganz nach dem Muster der biologischen Evolution, die quasi aus dem Nichts ein so hochkomplexes Lebewesen wie den Menschen hervorgezaubert hat.

Einer der frühen Verfechter jenes Gedankens, so erinnerte unlängst in einem Vortrag Heinz Mühlenbein von der GMD (Gesellschaft für Mathematik und Datenverarbeitung), war kein Geringerer, als der renommierte Rechner-Pionier John von Neumann. Und der wiederum stützte sich bei seinen Hoffnungen, evolutive Methoden könnten das "Komplexitätsproblem des Programmierens" für uns Menschen lösen, auf einen noch weit berühmteren Wissenschaftler, auf Charles Darwin nämlich, dem wir unter anderem ein auch den Satz verdanken: "Die komplexesten Systeme, die wir in der Natur beobachten, sind das Ergebnis eines evolutionären - also, wörtlich gesprochen: entwickelnden - Prozesses".

Programme als Anfänge evolutionärer Ketten

Mit von Neumanns Komplexitätsproblem wird in der Fachwelt kurz die Tatsache umschrieben, daß ein Programm um so mehr Mühe beim Schreiben macht, je schwieriger das Problem ist, das mit Hilfe dieses Programms gelöst werden soll. Und deshalb interessierte den Informatik-Ahnherrn auch die Frage, ob Automaten beziehungsweise Programme, die der automatischen Konstruktion weiterer Automaten beziehungsweise Programme dienen können, nicht auch einfach den Anfang einer evolutiven Kette bilden könnten, die dann sozusagen zwangsläufig von einfachen zu immer komplizierteren - und eben auch leistungsfähigeren - Typen führt?

Zwar kann man eine solche Kette, die zu immer komplexeren Strukturen führt, in der freien Natur beobachten - doch für die Welt der Technik sah Neumann seinerzeit keinen praktikablen Ansatz, Gleiches schaffen. Denn in der Technik scheint der Bau eines komplexen Systems beziehungsweise Automaten durch einfachere Systeme beziehungsweise Automaten zunächst ja nur dann denkbar, wenn letztere schon den vollständigen Bauplan des komplexeren Gebildes mit sich führen. Während simple Einzeller der Urzeit ja gewiß keinen vollständigen Bauplan des heutigen Homo sapiens in sich geborgen oder mit sich getragen haben dürften.

Der Wissenschaftler konnte in seiner Theorie über zelluläre Automaten die Beschreibung eines Automaten skizzieren, der sich selbst zu reproduzieren vermag - weshalb ihm dann übrigens auch Systeme nicht mehr völlig unmöglich scheinen wollten, die sogar kompliziertere Automaten, als sie es selbst sind, herstellen können. Richtig schätzte Neumann auch ein, daß zur Evolution zwei entscheidende Prinzipien gehören, nämlich erstens die Variation, die unversehens immer neue Varianten einer Art hervorbringt, sowie zweitens die Selektion, die verschiedene Varianten bei der Fortpflanzung unterschiedlich erfolgreich sein läßt. Doch meinte er skeptisch, allein das Wissen um diese elementaren Mechanismen der Entwicklung immer "höherer" Arten reiche wohl noch längst nicht aus, es schon in eine umfassende Theorie der Automaten einzubauen. Denn dazu wären erst noch eingehender, weiterführender Studien nötig gewesen bezüglich der Möglichkeit, solche Prinzipien in die - damals eher beschränkte - technische Realität umzusetzen.

Die recht dürftige Rechner-Technik der späten 50er Jahre setzte dann auch noch den praktischen Experimenten von Selfridge Grenzen, der 1959 die laut Mühlenbein - erste künstliche Evolutions-Architektur" konzipierte, bei der verschiedene evolutionäre Prozesse zusammenwirken sollten. Denn Selfridge führte schon damals neuronale Netze ein, die individuell lernen. sollten. Überdies schuf er auch noch ein Schema der genetischen Evolution innerhalb einer ganzen Population dieser Netze beziehungsweise "Pandämonien".

Bestimmte Probleme der Mustererkennung

Diese genetisch sich entwickelnden Netze sollten laut Originaltext aus dem Jahre 1959 in der Lage sein, sich adaptiv immer weiter zu verbessern, und ,auf diese Weise allmählich dazu fähig werden, bestimmte Probleme der Musterkennung zu bearbeiten. Gedacht wurde dabei insbesondere an solche Probleme, für die man die Lösungsmethoden nicht schon im vornherein spezifizieren kann.

Gern hätte Selfridge wohl schon vor drei Jahrzehnten im praktischen Betrieb erprobt, ob seine Pandämonien tatsächlich - wie erhofft - "den Samen zur steten Selbstverbesserung" in sich tragen, ob man eine ganze Gruppe solcher Pandämonien tatsächlich der Selektion unterwerfen kann und ob dann wohl tatsächlich die weniger geeigneten eliminiert würden, während die besseren immer neue Maschinen nach ihrem eigenen Ebenbild schaffen würden?

Unterschiede künstlicher und natürlicher Evolution

Heute, so räumt Mühlenbein ein, haben wir für praktische Experimente mit Konzepten dieser und ähnlicher Art erheblich mehr Möglichkeiten - und prompt wurden inzwischen auch schon vielfältige Methoden der künstlichen Evolution entwickelt und untersucht. Dabei unterscheiden sich künstliche und natürliche Evolution im Grunde nur in zwei Punkten, wie der GMD-Forscher betont, nämlich in der Feinstruktur der jeweiligen "Organismen' und zweitens vor allem auch darin, daß die natürliche Evolution sich frei entwickelt und keinem - oder wenigstens keinem erkennbaren - Ziel entgegenstrebt. Die künstliche Evolution soll im Gegensatz dazu "Organismen" mit ganz bestimmte und in ihren wesentlichen Um rissen - nicht aber in ihren Details - zuvor schon festgelegte Eigenschaften beziehungsweise Fertigkeiten hervorbringen.

Eine weitere wichtige Gemeinsamkeit zwischen natürlicher und künstlich organisierter Evolution, so Mühlenbein weiter, liegt aber auch darin daß beide immer dann am besten voranzukommen scheinen, wenn die Lebensräume der Organismen im steten Wechsel zeitweise voneinander getrennt und später wieder vereint werden ähnlich geologischen Modellen, die dieses Phänomen j für ganze Kontinente beschreiben.

Denn bei so einem Wechselspiel sind die Arten ja immer dann einem heftigen Wettbewerbs- und damit Selektionsdruck ausgesetzt, wenn groß zusammenhängende Kontinente existieren. Da dieser Druck alle hochspezialisierten Formen rasch aussterben läßt, wird die Zahl unterschiedlicher Arten mit der Zeit bald entsprechend klein. In Phasen getrennter, kleinerer Lebensraum-Inseln sinkt der Selektionsdruck wiederum ab, und mithin ist es möglich, daß sich dann auch seltsame und extreme Mutationen gut behaupten. Zwischenzeitlich kann also eine immense Fülle neuer Arten entstehen und sich am Leben erhalten, ehe es wieder zum Zusammenwachsen der Inseln, zu einem neuen Super-Kontinent und zur erneuten Beschneidung der Vielfalt kommt.

Betrachtet man nun zunächst allein nur Algorithmen der künstlichen Evolution, die in vielfältigen Ausformungen bekannt sind und die alle der optimalen Anpassung einer Ausgangsstruktur - beziehungsweise einer ganzen Population solcher Strukturen - an eine vorgegebene Aufgabe dienen, so wächst die quasi-biologische "Fitneß" dieser Strukturen natürlich in dem Maße, in dem sie sich immer besser zur Lösung der vorgegebenen Aufgabe eignen. Das heißt, solche Algorithmen verfolgen auf die eine oder andere Weise alle das Ziel, Fitneß dadurch zu verbessern, daß von Generation zu Generation bevorzugt die stärksten unter den gerade "lebenden" Strukturen Nachkommen produzieren. Wobei natürlich, um diesen wichtigen Punkt nicht aus den Augen zu verlieren, die jeweiligen Nachkommen auch bei der künstlichen Evolution infolge von Rekombinations-Effekten und Mutationen häufig anders gestaltet sein werden, als ihre direkten Eltern. Denn es wird hier je bewußt das Erfolgsrezept der lebendigen Natur kopiert.

Nimmt man die Problematik solcher Algorithmen der künstlichen Evolution nun näher unter die Lupe, so stößt man sogleich auf eine Fülle einzelner Fragen, die schwer zu beantworten sind. Sollten die jeweiligen Nachkommen nicht einfach all jene Mitglieder der bisherigen Population ersetzen, die die geringste Fitneß aufweisen, sollte beide oder aber nur ein Eltern teil nach dem Maß seiner Fitneß ausgewählt werden?

Abstrakt ausgedruckt laufen die einzelnen Antworten au Fragen der vorstehenden Art in ihrer Summe auf eine Entscheidung darüber hinaus, ob die künstliche Evolution nun eher auf das Prinzip der Exploration oder auf das der Exploitation setzen soll. Durch die Exploration werden vorrangig, immer neue, bisher unbekannte Möglichkeiten erprobt, während die Bindung an das schon Gefundene, Bewährte eher schwach ist. Im Extremfall bedeutet dies einfach nur eine rein zufallsbestimmte Suche im Raum aller denkbaren Möglichkeiten, die ihr Wissen darüber, daß etwa Typ A besser geeignet ist als Typ Z, überhaupt nicht zu nutzen weiß. Während stark Exploitations-betonte Evolutionsalgorithmen das schon Bewährte kaum mehr verlassen und selten völlig Neues entdecken. Sie führen somit höchstens sehr langsam zum optimalen Endprodukt, sofern sie nicht schon vorzeitig in einem lokalen Optimum hängenbleiben - wie etwa der urtümliche und dennoch weiterhin existierende Quastenflosser.

Passive Populationen unter externer Kontrolle

Es zeigt sich nun in der experimentellen Praxis der künstlichen Evolution, aber insbesondere auch in der Natur selber, betont Mühlenbein, daß es keinen schlechthin "besten" Evolutions-Algorithmus und mithin auch kein allgemeingültiges Gleichgewicht zwischen Exploration und Exploitation gibt. Und deshalb werden bei den einzelnen Studien - wie beispielsweise beim kombinatorischen Optimieren einer Struktur - immer wieder andere Varianten gewisser elementarer, grundlegender Evolutions-Strategien benützt.

Dabei ist nun allerdings ganz besonders zu betonen, daß die künstliche Evolution im Gegensatz zur natürlichen nur mit "passiven Populationen" und damit auch immer nur unter "externer Kontrolle" arbeitet. Denn auf jeder Stufe beziehungsweise in jeder Generation berechnet ja immer wieder erst ein objektiver Außenstehender die Fitneß der einzelnen Individuen wie auch der Gesamtpopulation. Ein solcher Außenstehender fehlt zweifellos in der Natur. Mithin stehen wir damit vor der Frage: Können wir denn nicht auch genetische Algorithmen entwerfen, die ohne oder mit nur geringer externer Steuerung arbeiten und die sich der Natur daher stärker annähern, als die bisher skizzierten?

Nachbarschaften überlappen sich

Eine Lösung dieses Problems sieht Mühlenbein ansatzweise in sogenannten parallelen genetischen Algorithmen, die der Erzeugung eigenständiger - und hier nunmehr endlich aktiver und nicht mehr bloß passiver Einheiten beziehungsweise Individuen dienen. Jedes dieser - virtuellen - Individuen sucht nämlich dann in seiner Nachbarschaft aktiv nach einem "Paarungspartner", wobei es besser angepaßte Partner bevorzugt.

Die einzelnen, in sich abgeschlossenen Nachbarschaften überlappen einander bei diesem Algorithmus , wechselseitig und außerdem sorgt er dafür, daß das jeweils beste" Individuum einer gegebenen Nachbarschaft die Chance hat, ebenso viele Nachkommen zu bekommen, wie das global beste Individuum in der ganzen sämtliche Nachbarschaften umfassenden

Population.

Bei diesem parallelen genetischen Algorithmus, so der Bonner Forscher weiter, ist der Selektionsdruck eher sanft; denn jedes Individuum habe hier ja die Chance, mindestens die Hälfte seines genetischen Materials - also praktisch seiner selbst - in einem Nachkommen weiterleben zu lassen. An dieser Stelle sollte kurz rekapituliert werden, daß a schon Darwin erkannt hatte, daß sanfter Selektionsdruck eine viel größere Variantenbreite ermöglicht - und mithin dem Evolutionsprozeß selbst natürlich förderlicher ist als strenger Selektionsdruck nach dem Motto: nur der Allerbeste überlebt genetisch und zwar natürlich in Gestalt seiner Nachkommen.

Weitere Merkmale des asynchronen, parallelen genetischen Algorithmus bestehen darin, daß die einzelnen Individuen sich hier in begrenztem Rahmen im Sinne einer betont exploitistischen Strategie verbessern und mithin einem lokalen Fitneß-Optimum zustreben können, sowie ferner darin, daß eine Art von genetischem Reparaturmechanismus - wie auch die Natur ihn kennt - am Werk ist und versucht, Schäden zu beheben. Dieser Reparatur-Algorithmus nämlich setzt immer dann ein, wenn die genetischen Mechanismen der Vererbung zu einem an sich nicht mehr lebensfähigen Individuum geführt haben, und bauen es in eine Struktur um, die dann, doch wieder leben kann.

Wie all' dies nun praktisch zusammenspielen kann, illustriert Mühlenbein am Beispiel eines kombinatorischen Optimierungs-Problems, für das ein hocheffizienter paralleler genetischer Algorithmus entwickelt: wurde, der bevorzugt auf massiv parallelen Computern, also Rechnern, die mit einer großen Zahl einzelner Rechenelemente ausgestattet sind, laufen soll.

Die Aufgabe, die dieser Algorithmus zu bearbeiten hat, ist das bekannte Problem des Handlungsreisenden: Denn der will - idealisiert gesehen - auf einer Rundreise jede Stadt nur einmal besuchen, am Ende wieder daheim sein und dabei den kürzesten denkbaren Weg genommen haben. Diese Aufgabe gehört zu einer Klasse schwer lösbarer Probleme - und deterministische Algorithmen herkömmlicher Art benötigen bei "n"-Städten hier doch tatsächlich 2(n) Vergleichsrechnungen, ehe sie am Ziel sind. Was schon bei bloß 64 Städten auf eine zwanzigstellige Dezimalzahl hinauslaufen würde.

Reparaturmechanismen machen Ordnung

Bei einem genetischen Vorgehen indes wird einfach eine beliebige, gültige Tour als Chromosom' betrachtet und jedes "Gen" mit der Nummer i auf diesem Chromosom gibt dann an, zu welcher Stadt k der Reisende von der Stadt i aus fährt. Dabei ist natürlich klar, daß in jeder gültigen, also korrekten beziehungsweise "lebensfähigen" Rund-Tour zu jedem i nur ein ganz bestimmtes k gehören und daß kein k zweimal erscheinen kann.

Existieren nun beispielsweise zwei Eltern-Chromosomen, die jeweils eine andere Tour repräsentieren, so können sie zu einem Nachkommen quasi verschmelzen, indem einfach Teile der beiden Touren miteinander kombiniert werden. Dabei entsteht dann vielfach eine zunächst ungültige, nicht lebensfähige Tour - mit ausgelassenen oder doppelt besuchten Städten -, doch die erwähnten Reparaturmechanismen bringen diese Fehler wieder in Ordnung.

Ohne hier weiter Details skizzieren zu können, läßt sich summarisch doch feststellen, daß parallele genetische Algorithmen für das Reisenden-Problem am Beispiel amerikanischer Städte zielstrebig eine Lösung finden. In einem Versuch wurden hier Populationen mit 64 Individuen geschaffen, die durch Evolution dann schrittweise immer mehr Teilstrecken als "brauchbar" in das "gemeinsame Erbgut" übernahmen. Das bedeutete, daß diese Teilstrecken sich bei späteren Evolutionsschritten beziehungsweise Generationen fortan nicht; mehr änderten.

Mit der von Mühlenbein beschriebenen Methode wurden in zwei verschiedenen Versuchen Routen gefunden, die mit 5086 beziehungsweise 27 715 Streckeneinheiten den überhaupt möglichen minimalen Wegen von 5069 beziehungsweise 27 694 Streckeneinheiten sehr nahe kamen; dabei haben die Forscher übrigens einen Rechner mit 64 Prozessoren eingesetzt. Angewandt auf andere Probleme aus dein Bereich der Kombinatorik sollen derartige Systeme sogar, schon "bessere Lösungen, als sie zuvor bekannt waren" entdeckt haben.

Grundlegender Algorithmus sehr robust

Zum Auffinden dieser besseren Lösungen, so der Wissenschaftler aus Bonn, mußten zahlreiche Rechenläufe durchgeführt und dabei Zug um Zug jene Faktoren isoliert werden, die die Evolution am kräftigsten beschleunigen konnten. Es waren dies erstens die Zahl der Individuen pro Population, zweitens das Rekombinations-Schema, das die Übertragung des Erbguts auf die Nachkommen regelt, und drittens das Selektions-Schema.

Die Beobachtung hat inzwischen gelehrt, daß es für die verschiedenen denkbaren Anwendungen eines solchen Systems keine einheitlich "beste" Einstellung der diversen Parameter gibt. Doch konnte auch beobachtet werden, daß der grundlegende Algorithmus ziemlich robust ist und bei einer ganzen Reihe von Problemen aller möglichen Arten gute Ergebnisse erhoffen läßt.

Charles Darwin wird bestätigt

Zur Geschwindigkeit der Evolution ist anzumerken, daß bei schwer lösbaren Problemen wie jenem der Routenplanung das Tempo, mit dem das System sich der optimalen Lösung nähert, von Generation zu Generation immer geringer wird. Je besser also eine schon gefundene Teillösung ist, desto mehr Generationen sind nötig, um von dort aus eine noch bessere Lösung zu finden. Und das oben erwähnte System mit seien 64 Prozessoren hat insgesamt an die 1200 Generationen erschaffen müssen, ehe es die beachtlich kurze Lösung. von 7715 Streckeneinheiten erreichte.

Der parallele genetische Algorithmus, den Mühlenbein beschreibt, kann in der Sprache der Biologen als "Evolution bigeschlechtlicher Organismen, zum Beispiel von Schnecken, mit geschlechtlicher Selektion und in einer flußartigen Umwelt" beschrieben werden. Der Algorithmus arbeitet mit weit weniger externer Steuerung als herkömmliche, nur einfach genetische Algorithmen und schlägt jene vor allem dann deutlich, wenn er auf Parallelrechnern eingesetzt wird. Dabei sei dieser Tempo-Gewinn eindeutig der Tatsache zu verdanken, betont der Forscher, daß die Variation der Population hier nun deutlich höher ist. Das wiederum bestätigt Charles Darwin, der genau erkannt hatte: Je breiter die Variation in einer Population bis hin zu Extremen aller möglichen Ausprägungen ist, desto rascher kann die Evolution Neues - und außerdem optimal an die Umwelt Angepaßtes - hervorbringen.

Wie weiter oben schon skizziert, sind Individuen in einem großen, einheitlichen Lebensraum starkem Wettbewerbs- oder Selektionsdruck ausgesetzt. Er läßt erstens allzu spezialisierte Arten aussterben und erschwert zweitens die Bildung neuer Mutanten beziehungsweise Arten. Dies ist in kleineren, isolierten Inseln beziehungsweise Nachbarschaften nicht der Fall, weshalb die Variationsbreite dort größer sein kann. Doch andererseits besteht in den Populationsinseln wieder die Gefahr, daß entstehende neue Arten allzu spezialisiert sind und damit deren weitere Evolution in Richtung auf die optimale Gestalt blockiert - oder doch wenigstens extrem verlangsamt - wird.

Genau deshalb spielt der Begriff der einzelnen, lokalen Nachbarschaften im vorgestellten System der parallelen genetischen Algorithmen eine zentrale Rolle. Denn dadurch ist es möglich, ein Wechselspiel einzuführen, bei dem partiell mit separaten Nachbarschaften und teilweise mit großen, einheitlichen "Lebensräumen" für sämtliche Individuen operiert wird.

Mühlenbein hat erkannt, daß die Evolution nur dann zügig voranschreiten kann, wenn ein stetes Wechselspiel zwischen einheitlichem Groß-Lebensraum und isolierten Klein-Räumen stattfindet. Andernfalls nämlich käme die Weiterentwicklung irgendwann zum Stillstand. Denn sie lebt - und dies eben nicht allein nur in der Natur sondern nach genau den gleichen Regeln auch im mathematischen Computer-Modell - vom Wechsel zwischen einerseits globaler Zusammenführung der Individuen mit entsprechend scharfem Selektionsdruck und andererseits lokaler Isolation mit der Möglichkeit, in der schützenden Nische neue Ideen, Konzepte und Arten sich entwickeln zu lassen.

Man müsse also klar sehen, betont Mühlenbein, daß alle herkömmlichen gängigen Vorstellungen von Darwins Ideen und vom Gang der Evolution fälschlich Gleichgewichts-Modelle postulieren, bei denen sich im Laufe der Zeit ein bestimmtes, stabiles Verhältnis der Arten zueinander herausbilden sollte. In Wirklichkeit führe das Wechselspiel zwischen starkem und leichtem Selektionsdruck doch zu einem dynamischen Modell ohne bleibendes Gleichgewicht. Zwar haben die parallelen genetischen Algorithmen am Beispiel der Optimisierungsprobleme gezeigt, daß auch sie am Ende ein Gleichgewicht herstellen; doch der Grund hierfür liege allein darin, betont Mühlenbein, daß hier die Definition dessen, was "Fitneß' im gegebenen Fall bedeute, über alle Generationen hinweg konstant gehalten wurde.

Im konkreten Beispiel war und blieb dies die kürzeste Strecke von Stadt zu Stadt. In der dynamisch sich laufend ändernden Natur kann dagegen schon morgen etwas nützlich sein, was gestern noch das Überleben bedroht haben mag - und umgekehrt.

Man darf sich von diesem Quasi-Gleichgewicht im simulierten Experiment also nicht beirren lassen. Auch die Experimente: am Computer haben deutlich gezeigt, wie wichtig die Strukturierung der hier involvierten Population in Nachbarschaften ist, will man einen möglichst raschen, steten Fortschritt hin zum Ziel der Evolution erreichen.

Der auf dem Felde der genetischen Algorithmen heute erreichte Stand erlaubt allmählich deren versuchsweise Anwendung auf kompliziertere Aufgabengebiete, wie beispielsweise bei - virtuellen - sehenden Robotern, die in einer zweidimensionalen Welt mit sich verändernden Hindernissen hantieren. Auch der Einsatz in Bewegungssystemen ist schon heute möglich. Dabei kann die genetische Darstellung der Eigenschaften eines solchen Roboters sich fortan - da sie ja nicht mehr fest verschaltet ist - im Zuge seiner Evolution ändern.

Dies alles führt am Ende kurz wieder zu von Neumanns Frage zurück, ob denn wohl ein einfacher Roboter denkbar sei, aus dem durch Evolution ein anderer hervorgehen könne, der kompliziertere Dinge bewerkstelligen kann als sein Ahnherr?

Mühlenbein meint, diese Frage könne vorerst noch nicht sicher beantwortet werden. Doch weitere Forschung werde sie einer Klärung näherbringen - und ganz sicher auch das Verständnis der biologischen Evolution immer weiter vertiefen. Einer überaus geduldigen Langzeit-Evolution, aus der letztlich auch wir Menschen selbst hervorgegangen sind.