Direkt zum Inhalt

Informatik: Algorithmen üben Evolution

Mit Ideen aus der Evolutionsbiologie suchen Informatiker unter astronomisch vielen möglichen Lösungen die optimale. Dahinter steht eine mathematische Theorie, laut der es einfacher ist, ein Ergebnis durch ein Programm zu erzeugen, als dieses Ergebnis direkt zu erzielen.
AlgorithmenLaden...

Kreationisten bemühen gerne folgendes Argument: Um ein einziges mittelgroßes menschliches Protein zu erschaffen, musste die Evolution mehr als 300 Aminosäuren in der richtigen Reihenfolge zusammenfügen. Das könne kein Zufall gewesen sein. Denn da jedes Glied eines Moleküls aus einer von 20 möglichen Aminosäuren besteht, gibt es mehr als 20300 Möglichkeiten, so ein Protein aufzubauen. Neben einer solchen Zahl wirkt selbst die Anzahl der Atome im beobachtbaren Universum vernachlässigbar klein. Selbst wenn man Redundanzen, die einige Sequenzen aus biochemischer Sicht gleichwertig machen, nicht mitrechnet, wäre es tatsächlich höchst unwahrscheinlich, dass die Evolution die richtige Kombinationen rein durch zufällige Mutationen finden kann, selbst nach Jahrmilliarden.

Doch das Argument der Kreationisten hat einen entscheidenden Haken: Die Evolution testet genetische Sequenzen nicht allein nach dem Zufallsprinzip. Sie arbeitet mit natürlicher Auslese und hat darüber hinaus vermutlich Wege gefunden, den unermesslichen Raum genetischer Möglichkeiten auf kleinere, erforschbare Teilgebiete einzugrenzen.

Wie die Evolution suchen auch Informatiker oft die eine optimale Lösung unter astronomisch vielen möglichen. Dabei lassen sie sich manchmal sogar von der Biologie inspirieren. Genetische Algorithmen sind eine seit Jahrzehnten beliebte Optimierungsmethode, die die Prinzipien der natürlichen Selektion nachahmt. Mit ihr suchen Forscher nach neuen Designs für Roboter, Medikamente und Transportsysteme oder nach neuen Wegen, neuronale Netze zu trainieren oder Daten zu ver- und entschlüsseln.

Genetische Algorithmen starten mit dem Zufall

Genetische Algorithmen starten immer mit einer Hand voll zufällig gewählter Lösungen. Die sind in der Regel noch nicht gut. Allerdings werden die Lösungen in genetischen Algorithmen als Organismen aufgefasst, deren Merkmale in einer Art genetischem Code beschrieben sind. Dieser Code wird dann, wie in der Evolution, einer Kombination von Manipulationen unterzogen. Das können zufällige Mutationen sein oder Eingriffe, die die genetischen Mischprozesse in der Natur nachahmen. So entsteht eine weitere Generation von Organismen, die wiederum auf ihre Fitness getestet werden, also die Fähigkeit, die Aufgabe zu lösen. Wiederholt man diese Schritte, kann das zu hochgradig angepassten Individuen führen: zu guten Lösungen für das vorliegende Problem.

Manche Experten gehen sogar einen Schritt weiter: Sie nutzen die genetische Programmierung, um Software zu entwickeln, die sich selbst umschreibt, um bessere Lösungen zu finden. Die »Gene«, also der Code der Software, agieren dabei selbst als Programmieranweisungen. Diese Herangehensweise hat sich allerdings als ziemlich schwierig erwiesen, vor allem weil die genetische Programmierung besondere Datentypen und -strukturen erfordert.

Interessanterweise überschneiden sich die beiden evolutionsbasierten Denkweisen (genetische Algorithmen und Programmierung) konzeptionell mit einer mathematischen Theorie, die an der Grenze zwischen Biologie und Informatik angesiedelt ist. Mit Hilfe dieser Theorie versuchen ein paar Forscher herauszufinden, was die Evolution, ob natürlich oder künstlich, so effizient macht. Wie schafft sie es immer wieder, innovative Lösungen zu finden, und wie lernt sie? Der Schlüssel zur Beantwortung solcher Fragen liegt womöglich in einem spezifischen Begriff von Komplexität, Zufälligkeit und Information, der bisher kaum praktische Anwendung gefunden hat.

Affen, die auf Tastaturen einhämmern

Die besagte Theorie wurde bereits in den 1960er Jahren entwickelt. Sie beschreibt das Konzept der algorithmischen Information und beruht auf einem recht intuitiven Verständnis von Wahrscheinlichkeit und Komplexität: dass es für einige Outputs effizienter ist, sie in einem Algorithmus zu beschreiben, der die Outputs erzeugen kann, statt sie tatsächlich zu generieren.

Als Beispiel kann die abgegriffene Analogie des Affen herhalten, der Tasten auf einem Keyboard zufällig drückt. Die Wahrscheinlichkeit, dass der Affe dabei genau die ersten 15 000 Ziffern der Zahl Pi eingibt, ist absurd gering, und sie sinkt exponentiell mit der Anzahl der gewünschten Ziffern. Interpretiert man die Tastenanschläge stattdessen als Computerprogramm zur Erzeugung von Pi, verbessern sich die Erfolgschancen erheblich. Der einfache Grund: Ein Programm zum Erzeugen der ersten 15 000 Ziffern von Pi in der Programmiersprache C benötigt normalerweise nicht mehr als 133 Zeichen Code. Anders gesagt: Die algorithmische Wahrscheinlichkeit, dass der Affe mit seinen Zufallseingaben die Zahl Pi erzeugt, wächst.

Die Theorie der algorithmischen Information besagt also im Wesentlichen, dass die Wahrscheinlichkeit, einen bestimmten Output durch Zufall zu erzeugen, viel größer ist, wenn der Zufall auf der Ebene von Programmen operiert statt auf der Ebene der Outputs. Das ist auch der Grund dafür, dass selbst komplexe Strukturen wie Fraktale leicht durch reinen Zufall erzeugt werden können.

Optimales Programm ist nicht vorausberechenbar

Mathematiker haben allerdings schon recht früh herausgefunden, dass der Ansatz seine Schwierigkeiten hat: Sie konnten beweisen, dass die algorithmische Komplexität – die Länge des kürzestmöglichen Programms, das einen gewünschten Output erzeugt – nicht berechenbar ist. Deshalb können Informatiker nicht berechnen, wie man eine Zeichenkette (oder einen beliebigen anderen Output) auf optimale Weise in ein Programm verpackt. (Die algorithmische Komplexität ist übrigens auch als Kolmogorow-Komplexität bekannt, nach Andrei Kolmogorow, einem der Begründer der Theorie.)

Auf Grund dieser Einschränkung fristete die algorithmische Informationstheorie lange ein Nischendasein in der Welt der reinen Mathematik. Dort wurde sie zur Erforschung verwandter Theoreme und zur Definition der Konzepte von Zufall und Struktur genutzt. Praktische Anwendungen schienen unwahrscheinlich.

»Aus mathematischer Sicht ist algorithmische Information ein einfaches und schönes Maß der Komplexität«, sagt Gregory Chaitin. Der bekannte Mathematiker ist einer der Begründer der Theorie und arbeitete früher am IBM Thomas J. Watson Center und an der Federal University of Rio de Janeiro. »Aber die Theorie schien unzugänglich für reale Anwendungen.«

Das hielt Chaitin nicht davon ab, es trotzdem zu probieren. Mit Hilfe der algorithmischen Information hoffte er die Idee von DNA als Software zu formalisieren. Im Jahr 2012 veröffentlichte er ein Buch, in dem er darlegte, wie man die Evolution als so genannten »random walk«, einen Zufallspfad durch einen Software-Raum, auffassen kann. Dort zeigt Chaitin, dass die Mutationen entlang eines Pfades keiner statistisch zufälligen Wahrscheinlichkeitsverteilung folgen, sondern einer Verteilung, die auf der Kolmogorow-Komplexität basiert. Seine Theorie testen konnte Chaitin bisher allerdings nicht.

Eine Tendenz zur Einfachheit

Hector Zenil, Informatiker am Karolinska-Institut in Schweden, ist einer derjenigen, die genau das versuchen. Er und seine Kollegen nutzen die Kolmogorow-Komplexität als Metrik, die die Komplexität biologischer Netzwerke beschreibt, wie jene, die die Genregulation oder die Proteininteraktionen in Zellen steuern. Die Forscher beginnen damit, indem sie den algorithmischen Informationsgehalt eines Netzwerks grob schätzen (der Ist-Wert ist schließlich nicht genau berechenbar). Dann mutieren sie das Netzwerk und testen, welchen Einfluss die Mutation auf die Kolmogorow-Komplexität hat. Auf diese Weise hoffen sie die relative Bedeutung der Elemente des Netzwerks zu ergründen und nachzuweisen, wie es funktional auf Veränderungen reagiert.

Kürzlich veröffentlichten Zenil und seine Kollegen eine Studie auf der Preprint-Seite arxiv.org. Darin beschreiben sie, wie die Mutationen in einem Netzwerk dazu führten, dass das Programm, welches das Netzwerk beschreibt, länger wurde. Sie konnten zeigen, dass diese Verschiebung des Netzwerks in Richtung höherer Kolmogorow-Komplexität dazu führt, dass die Anzahl der Funktionen, die das Netzwerk ausführen kann, ebenfalls zunimmt. Allerdings reagierte das Netzwerk dann auch empfindlicher auf Störungen. Verschoben die Forscher das Netzwerk dagegen in Richtung Einfachheit, konnte es weniger, dafür aber stabilere Funktionen ausführen.

»Biologische Kreativität ist ein Begriff, der in dieser mathematisch schönen Theorie nicht vorkommt«(Gregory Chaitin)

Ob die Kolmogorow-Komplexität zum Werkzeug der Biologen wird – zur treibenden Kraft des Wandels, wie Chaitin es ausdrückt –, bleibt jedoch abzuwarten. Immerhin übt das Konzept der algorithmischen Information trotz seiner Grenzen schon jetzt einen gewissen Reiz auf die Biologie aus. Traditionell ist der mathematische Rahmen der Evolutionsbiologie die so genannte Populationsgenetik, ein statistisches Modell der Häufigkeit, mit der Gene in einer Population vorkommen. Doch dieses Modell hat seine Grenzen: So kann die Populationsgenetik weder den Ursprung des Lebens erklären noch, wie andere radikale Übergänge zu Stande kommen. Auch warum neue Gene entstehen, kann das Modell nicht vollständig erklären. »Biologische Kreativität ist ein Begriff, der in dieser mathematisch schönen Theorie nicht vorkommt«, erklärt Chaitin. Berücksichtigten wir dagegen die algorithmischen Informationen, »passt die Kreativität auf ganz natürliche Weise hinein«.

Das gilt offenbar auch für die Auffassung, der evolutionäre Prozess verbessere sich mit der Zeit selbst und werde damit effizienter. »Ich bin fest davon überzeugt, dass die Evolution von selbst lernt«, sagt etwa Daniel Polani, Informatiker und Professor für künstliche Intelligenz an der University of Hertfordshire in England. Er wäre nicht überrascht, wenn die Fähigkeit der Evolution zu lernen »durch asymptotisch abnehmende algorithmische Komplexität formalisiert werden könnte«.

Künstliche genetische Netzwerke auf evolutionäre Weise

Zenil und sein Team haben sich nun darangemacht, die biologischen und rechnerischen Auswirkungen der algorithmischen Komplexität experimentell zu testen. Mit der gleichen Methode, die sie zur Schätzung und Annäherung an die Komplexität von Netzwerken entwickelt haben, erzeugen sie jetzt »auf evolutionäre Weise« künstliche genetische Netzwerke. Konkret bedeutet das: Sie programmieren Netzwerke evolutionär wachsender Matrizen aus Einsen und Nullen, die Wechselwirkungen zwischen Genen darstellen. Und sie treiben die Mutationen in diesen Netzwerken in Richtung geringerer algorithmischer Komplexität.

Vor Kurzem berichteten Zenil und seine Kollegen in »Royal Society Open Science«, dass die mutationsbedingte Tendenz zu geringerer algorithmischer Komplexität mehr Struktur hervorbringt als Zufallsmutationen. Außerdem entwickelten die Netzwerke sich deutlich schneller zu optimalen Lösungen hin. Und die Wissenschaftler beobachteten weitere Eigenschaften, darunter stabile regelmäßige Strukturen, Abschnitte der Matrizen, die einen so hohen Grad an Einfachheit erreicht hatten, dass nachfolgende Generationen sie kaum noch verbessern konnten. »Einige Regionen waren anfälliger für Mutation, andere weniger, vermutlich weil sie ein bestimmtes Level an Einfachheit entwickelt hatten«, berichtet Zenil. »Das erinnerte uns sofort an Gene.« Diese Regionen mit genetischem Gedächtnis wiederum erzeugten mehr Struktur als andere Regionen. Algorithmisch wahrscheinliche Mutationen können also zu einer Explosion oder Implosion der Vielfalt führen.

»Das bedeutet auch: Es ist nützlich, in der Evolution von Rechenprozessen zu sprechen«, sagt Zenil. Er hofft nun mit dieser Herangehensweise evolutionäre Pfade zu entdecken, die anfälliger für Mutationen sind als andere, und so zum Beispiel herauszufinden, warum bestimmte genetische Interaktionen mit Erkrankungen wie Krebs assoziiert sind.

»DNA ist extrem wichtig. Aber außerhalb einer Zelle, eines Organismus oder eines Ökosystems macht sie keinen Sinn«(Giuseppe Longo)

Zenil will zudem untersuchen, ob die biologische Evolution den gleichen Rechenregeln folgt wie die künstliche Evolution in seinen Gennetzwerken. Die meisten Experten haben da ihre Zweifel. Vor allem weil noch unklar ist, welcher Mechanismus in der Natur für die Verringerung der algorithmischen Komplexität verantwortlich ist. Außerdem sei es falsch zu glauben, das Leben sei durch die vier Buchstaben des DNA-Codes vollständig beschrieben, meint Giuseppe Longo, Mathematiker am Centre national de la recherche scientifique in Frankreich. »DNA ist extrem wichtig. Aber außerhalb einer Zelle, eines Organismus oder eines Ökosystems macht sie keinen Sinn.« Andere Interaktionen spielten eine vergleichbare Rolle. Zenils Anwendung der algorithmischen Informationen könne die damit einhergehende Komplexität jedoch nicht einfangen.

Dennoch hat das Konzept schon ein gewisses Interesse geweckt – zumal diese neue Art, über die Evolution nachzudenken (als Rechenprozess), mit der genetischen Programmierung zumindest ein wenig zu tun zu haben scheint. Tatsächlich gibt es einige faszinierende Hinweise auf einen Zusammenhang zwischen Chaitins und Zenils Ideen zur Kolmogorow-Komplexität und genetischen Programmiermethoden. So berichtete ein Forscherteam bereits im Jahr 2001, dass die Kolmogorow-Komplexität die Komplexität des Outputs eines genetischen Programms begrenzen kann.

In der Regel aber hat die Kolmogorow-Komplexität bisher kaum eine Rolle in der Informatik gespielt. Stattdessen haben Informatiker andere Möglichkeiten genutzt, um die Genetik zu modellieren: Sie haben an den Mutationsraten gedreht oder Mutationen begünstigt, die größere Codeblöcke ersetzen. »Es gibt Dutzende, vielleicht hunderte Wege, Mutationen und Vertauschungen zu modellieren«, sagt Lee Spector, Informatiker am Hampshire College in Massachusetts. Ein Team, das Spector leitete, zeigte kürzlich, dass es Vorteile hat, Mutationen über das gesamte Genom eines Organismus zu verteilen, statt immer direkt ein Gen durch ein anderes zu ersetzen. Mit dieser neuen Art genetischer Operation vergrößerte sich die Zahl möglicher Wege durch den genomischen Suchraum exponentiell, was bessere Lösungen zur Folge hatte.

»Über das Leben als eine sich entwickelnde Software nachzudenken, ist eine Idee mit Potenzial«(Gregory Chaitin)

Viele Forscher haben bisher auch in entgegengesetzter Richtung nach Wegen gesucht, den Prozess der Evolution zu beschleunigen. Manche haben versucht, den Suchraum gerade so weit einzuschränken, dass die optimalen Ergebnisse nicht verfehlt werden. Andere haben sich die Einfachheit selbst als Ziel gesteckt. Ähnlich wie Eugene Wigner, der im Jahr 1960 die »unangemessene Wirksamkeit der Mathematik in den Naturwissenschaften« beschrieb, haben Informatiker festgestellt, dass sich einfachere und elegantere Modelle oft als allgemeingültiger und effektiver erweisen.

»Die Frage ist immer: Sagt uns ein Modell etwas Tiefes über das Universum oder nicht?«, stellt Spector fast. Es könne destruktiv sein, selbstentwickelnde Programme in Richtung Einfachheit zu verzerren. Denn kürzere Programmlängen reduzieren zwar vermeintlichen genetischen Müll. Der jedoch könnte für spätere Generationen hilfreich sein. Die optimalen Lösungen gingen dabei also vermutlich verloren.

Dennoch bleibt Einfachheit ein verlockendes Ziel. Nicht zu Unrecht, schließlich hat sie sich als nützlich erwiesen. So fanden Spector und seine Kollegen 2017 heraus, dass ihre Programme bei neuen Input-Daten besser abschnitten und für eine größere Bandbreite allgemeiner Probleme verwendet werden könnten, wenn sie die Größe der Programme nach den evolutionären Programmierschritten reduzierten – manchmal auf bis zu 25 Prozent der ursprünglichen Größe. Das war einer der Gründe, warum Spector überhaupt auf die Entwicklungen der algorithmischen Informationstheorie aufmerksam geworden war. Wie genau die Theorie das Feld beeinflussen wird, sieht er allerdings noch nicht.

Vom Leben lernen

Womöglich ist Zenils Team den ersten Schritt gegangen. Doch bevor ihre Arbeit realistische Anwendungen erlaubt, müssen die Forscher ihre Methode an andersartigen Suchproblemen testen. Sie hätten »mit der strukturellen Eingrenzung eine gute Idee gehabt«, erzählt die theoretische Neurowissenschaftlerin Larissa Albantakis von der University of Wisconsin, Madison. Auch Albantakis arbeitet daran, genetische Algorithmen durch eine Begrenzung des Suchraums zu beschleunigen. Die Natur sei in vielerlei Hinsicht strukturiert, argumentiert sie. »Nimmt man das als Ausgangspunkt, dann ist es schon albern, alle möglichen gleichartigen Mutationen auszuprobieren.«

Spector dagegen bleibt skeptisch, ob Zenils jüngste Arbeit auf andere Probleme anwendbar sein wird. Die Informationstheorie hinter dem Ansatz findet er dennoch faszinierend. »Ich finde die Arbeiten auch deshalb so spannend, weil sie von einem anderen Planeten zu stammen scheinen. Vielleicht geben sie ja Erkenntnisse her, die den Leuten in unserer Gemeinde einfach nicht bewusst sind.«

Schließlich greift die algorithmische Information auf eine Reihe von Konzepten zurück, die Experten für genetische Programmierung womöglich noch nicht in ihre Arbeit einbeziehen, etwa der Begriff der Offenheit der Evolution. »Ich habe das starke Gefühl, da schlummert Wichtiges«, sagt Spector. Praktische Anwendungen lägen nach seinem Dafürhalten allerdings noch in weiter Ferne.

Chaitin sieht ebenfalls viel Potenzial in der Idee, über das Leben als sich entwickelnde Software nachzudenken, auch noch unklar ist, welchen Wert das Ganze hat. Ob biologisches oder künstliches Leben, »man muss halt schauen, wie weit man damit kommt.«

Logo Quanta MagazineLaden...

Von »Spektrum der Wissenschaft« übersetzte und redigierte Fassung des Artikels »Mathematical Simplicity May Drive Evolution's Speed« aus »Quanta Magazine«, einem inhaltlich unabhängigen Magazin der Simons Foundation, die sich die Verbreitung von Forschungsergebnissen aus Mathematik und den Naturwissenschaften zum Ziel gesetzt hat.

07/2019

Dieser Artikel ist enthalten in Spektrum - Die Woche, 07/2019

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Partnervideos