Navigation

Die Herkunft des Lebens aus Sicht der Informatik

Evolutionäre Verfahren für Nicht-Informatiker

Immer wieder gibt es Menschen, die voller Überzeugung und mit mehr oder weniger intuitiven, aber nichtsdestotrotz schlussendlich unsinnigen Argumenten daran glauben, dass Gott das Leben, die Pflanzen, Tiere und Menschen, genau sogeschaffen hat, wie sie sind. In meinem letzten Post habe ich in diesem Kontext den Vortrag „Herkunft des Lebens aus Sicht der Informatik“ von Dr. Werner Gitt besprochen, dessen Inhalte hier jedoch nicht von Belang sein werden.

Stattdessen möchte ich heute einen konstruktiven Beitrag zur Debatte um die „Sicht der Informatik“ auf die „Herkunft des Lebens“ machen: Ich möchte in diesem Text die Evolution mit Hilfe von Konzepten aus der Informatik plausibilisieren. Dabei soll dieser Text so einfach und verständlich geschrieben sein, dass auch Nicht-Informatiker verstehen, was hier passiert.

Plausibilisierung

Eines vorweg: Was nun folgt, werden nicht die „harten Fakten“, die unumstößlichen Argumente sein, die so mancher Anhänger des Kreationismus nicht nur fordert, sondern auch glaubt, für sich gefunden zu haben. Die hier vorgestellten Ideen aus der Informatik können Evolution höchstens plausibilisieren, nicht beweisen. Mehr kann die Informatik meiner Meinung nach als in erster Linie Formal-, nicht Naturwissenschaft auch gar nicht leisten.

Nichtsdestotrotz soll hier nicht verschwiegen werden, dass die Biologie über die Jahre eine doch substanzielle Beweislast zugunsten der Evolution angehäuft hat, wie sie zum Beispiel bei Live Science nur grob umrissen wird.

Besonders spannend ist an dieser Stelle eine Untersuchung von Lena A. E. Tibell und Ute Harms,1 die sich in erster Linie mit den Problemen der Vermittlung von Wissen über Evolution beschäftigen und dabei explizit Zufall und große Zeitskalen als Schwelle des Verständnisses nennen. Zufälligerweise ist gerade die Informatik genau hier in der Lage, Abhilfe zu schaffen: Computer können Zufall generieren und in Simulationen Zeit auf einen Bruchteil zusammenschrumpfen. Wollen wir doch mal sehen, ob wir damit so etwas wie Evolution hinbekommen können.

Problemstellungen in der Informatik

Zunächst möchte ich jedoch etwas allgemeiner einsteigen, nämlich mit den Problemen, die man mit Informatik zu lösen versucht. Es stellt sich nämlich heraus, dass es zwei Arten von Aufgaben gibt, die sich fundamental unterscheiden. Zum einen gibt es Aufgabenstellungen, die sich ganz einfach mathematisch lösen lassen: 2x = 4. Umstellen, fertig. Für diese Aufgaben gibt es effiziente Algorithmen, die die Lösung schnell berechnen können. „Wie komme ich am schnellsten von A nach B?“ (also Routenberechnung) ist auch eine dieser Aufgaben.

Die zweite Art von Aufgaben lässt sich nicht so einfach lösen. Hierzu zählt die Tourenplanung, gut bekannt unter dem Namen Traveling-Salesman-Problem: Ein Handelsreisender möchte gerne eine Vielzahl von Städte besuchen, verteilt in ganz Europa. Die Frage ist nun, in welcher Reihenfolge er die Städte aufsucht, um insgesamt die kürzeste Strecke zurückzulegen. Hier wurden lange Zeit verschiedene Verfahren erprobt, die zumindest gute Lösungen finden können, aber um in jedem Fall ganz sicher die beste Route zu finden, muss immer noch jede mögliche Reihenfolge von Städten durchprobiert werden. Das bedeutet insbesondere, dass mit jeder Stadt, die hinzukommt, der Rechenaufwand exponentiell wächst,2 was dazu führt, dass schon bei kleinen Städtezahlen die Zeit zur Berechnung unsinnig lang wird.

Leider gibt es von dieser Sorte Aufgaben eine ganze Reihe; und es sind gerade die wirklich spannenden Anwendungsfälle, die sich als in der Praxis unlösbar erweisen – zumindest, wenn man die exakte Antwort finden will. Wo sollten wir Bahnhöfe hinbauen, sodass die Menschen bestmöglich angebunden sind? Wie ist die beste Ordnung von Paketen im Lastwagen, damit wir ihn so gut wie möglich auslasten? Wie sollten wir den Arbeitsplan einteilen, damit Maschinen nicht so lange unbenutzt herumstehen?

Diese Aufgaben haben zwei Gemeinsamkeiten: Es gibt erstens eine ganze Reihe möglicher Lösungen, die allesamt eine Qualität, ein Gütekriterium, haben, das sich mehr oder weniger leicht berechnen lässt. Allerdings gibt es zweitens eine ganze Reihe von Parametern und Nebenbedingungen, die erfüllt werden müssen.

Lösungssuche

Eine Idee, wie man solche Aufgaben lösen kann, haben wir schon gehört: Ausprobieren, bis man die beste (oder zumindest eine hinreichend gute) Lösung gefunden hat. Aber in der Realität gibt es ja immer irgendeinen Zusammenhang zwischen Parametern (Reihenfolge der Städte, Positionen der Bahnhöfe, …) und der Qualität der Lösung. Vielleicht können wir uns ein geschicktes Suchverfahren ausdenken, mit dem wir graduell immer bessere Lösungen finden, bis wir irgendwann hoffentlich am Optimum sind.

Ich möchte an dieser Stelle ein möglichst anschauliches Beispiel einführen: Sie sind auf einer mystischen, noch unerforschten Insel. Sie haben modernste Ausrüstung dabei: Mit Hilfe von GPS können sie ihre Position (Längen- und Breitengrad) exakt bestimmen, mit dem Höhenmesser können sie genau sehen, wie hoch über dem Meeresspiegel sie sich gerade befinden. Es gibt nur ein großes Problem: Überall herrscht dichter Nebel. Es gibt keine Karte der Insel und Sie sehen quasi nur das Stück Boden, auf dem Sie gerade stehen. Ihre Aufgabe: Finden Sie den höchsten Berg der Insel.

Zunächst wollen wir dieses Beispiel einmal formalisieren. Das Optimierungskriterium ist die Höhe über dem Meeresspiegel – diese wollen wir maximieren, denn am höchsten Punkt der Insel ist natürlich der höchste Berg. Unser Suchraum ist die Insel, genauer gesagt ihre Ausdehnung auf dem Globus, als Parameter kann man x- und y-Position auf der Insel verwenden. Die Grenze des Suchraums ist das Meer ringsherum, aber vielleicht gibt es auch Seen innerhalb der Insel – Bereiche, in die man nicht gehen kann, sogenannte Lücken im Suchraum.

Wie könnten wir jetzt vorgehen? Eine einfache Idee wäre das folgende lokale Suchverfahren: Wir starten an einer zufälligen Stelle der Insel. Dann schauen wir auf den Boden: In welche Richtung geht es bergauf? Je nach Steigung gehen wir dann eine bestimmte Strecke in diese Richtung. Wenn es irgendwann nicht mehr bergauf geht, sind wir an der höchsten Stelle; die Aufgabe ist gelöst.

Herzlichen Glückwunsch, das ist tatsächlich ein valides Suchverfahren, das zum Beispiel beim Training von künstlichen neuronalen Netzen im Bereich der künstlichen Intelligenz eingesetzt wird! Es gibt nur ein Problem: Wenn die Insel nur einen Berg hat, ist das alles schön und gut, sobald es aber mehr als einen Gipfel gibt, können wir nicht sicher sagen, ob wir voller Stolz auf dem Gipfel eines 8000ers stehen, oder nur auf dem kleinen Hügel direkt daneben und uns der dichte Nebel der Insel die Sicht verdeckt. Wir könnten unser Suchverfahren jetzt ein paar mal anwenden und immer an unterschiedlichen Punkten starten, und damit könnten wir wahrscheinlich ein paar der kleineren Hügel ausschließen, aber wirklich sicher wären wir uns nie.

Denn, wie oben schon angedeutet, es handelt sich nur um ein lokales Suchverfahren, von denen es noch eine ganze Reihe weitere gibt. Was wir eigentlich bräuchten, wäre ein globales Suchverfahren – nur wie kann man sich so etwas vorstellen?

Zum Gipfel – per Evolution!

Globale Suchverfahren leihen ihre Ideen erstaunlich oft aus der echten Welt. Es gibt Verfahren, die das Verhalten von Materie beim Abkühlen nachstellen und Verfahren, die das Vorgehen von Ameisenkolonien bei der Futtersuche oder gar das Jagdverhalten von Wölfen oder Delphinen nachbilden.3 Am wahrscheinlich bekanntesten sind die sogenannten evolutionären Verfahren – eine Klasse von Algorithmen, die, wie der Name vermuten lässt, Ideen aus der Evolution einsetzt, um komplexe Probleme zu lösen.

Wie können wir jetzt also mittels Evolution den höchsten Gipfel auf unserer mystischen Insel finden? Naja, wir übertragen einfach Stück für Stück Prinzipien der Evolution auf das Problem der Gipfelsuche.

Schritt 1: Survival of the fittest. Hierbei geht es nicht, wie oft fälschlicherweise angenommen, um das Überleben des (physisch) Stärksten, sondern vielmehr um den (Fortpflanzungs-)Vorteil des Bestangepassten. Und am besten angepasst ist im Sinne unseres Szenarios natürlich derjenige, der an einer möglichst hohen Stelle ist.

Diese „hohe Stelle“ ergibt sich dann durch Schritt 2: Die Gene. Für unsere Individuen ist einzig die Position relevant. Es gibt also ein Gen, das den Längengrad darstellt, auf dem sich das Individuum befindet, und eins für den Breitengrad. Für unser einfaches Problem reicht das als DNA völlig aus.

Für Schritt 3 brauchen wir Population: Wir verteilen jetzt etwa 20 bis 100 Individuen zufällig auf der Insel.4

Und jetzt können sie sich in Schritt 4 immer wieder miteinander fortpflanzen! Zufällig wählt sich jeder auf der Insel einen Partner aus. Je höher man wohnt, desto wahrscheinlicher ist es, dass man als Partner ausgewählt wird – wer oben wohnt, ist im Sinne des Problems ja besser angepasst und somit begehrenswerter. Bei der Fortpflanzung passieren zweierlei Dinge: Zum einen findet eine Vermischung der Genausprägungen der beiden Eltern statt, das sogenannte Crossover: Die Kinder unserer beiden Inselbewohner werden sich irgendwo zwischen ihren Eltern ansiedeln. Dabei ist es nicht wahrscheinlicher für Kinder, eher in der Mitte zwischen beiden zu wohnen, sondern das ist einfach absoluter Zufall. Außerdem kann über Mutation der Wert mancher Gene einfach so zufällig ein bisschen verändert werden. Anschließend ersetzt die Generation der Kinder die der Eltern.5

Das wiederholt man jetzt viele, viele Male. Die Evolution hat bei dem wesentlich komplexeren Problem der Entwicklung ganzer Lebewesen Millionen von Jahren gebraucht. Im Computer kann man unser einfaches Problem innerhalb von Sekunden simulieren. Denn das Faszinierende ist: Dieses Verfahren funktioniert. Man findet so den Gipfel. Man weiß immernoch nicht sicher, dass man wirklich exakt den allerhöchsten Punkt gefunden hat, aber irgendwann werden sich alle Bewohner der Insel in Gipfelnähe befinden. Wenn die Gesamtbevölkerung im Schnitt irgendwann für ein paar Generationen einfach nicht mehr viel besser wird (also höher wohnt), kann man aufhören.

Noch komplexer Evolvieren

Diese Vorgehensweise funktioniert nicht nur bei so einem einfachen Problem mit nur zwei Genen und einem Optimierungskriterium, sondern auch bei wesentlich komplexeren Themengebieten wie der Steuerung von Industrierobotern mit einer Vielzahl von Motoren und Drehachsen oder der Erstellung von Produktionsplänen in industriellen Fertigungsprozessen mit einer Vielzahl von Aufträgen und voneinander abhängigen Arbeitsschritten.6 Insbesondere sind die so erzeugten Lösungen bei manchen Anwendungsfällen grundverschieden von dem und wesentlich besser als das, was ein intelligenter menschlicher Schöpfer designen würde (S. 1776).

Außerdem, und das ist besonders faszinierend: Je mehr Aspekte der natürlichen Evolution man digital „nachbaut“, desto besser werden die Ergebnisse! In der Natur kann sich nicht jedes Individuum mit jedem anderen fortpflanzen, man bleibt bei der Partnerwahl (eher) in seiner Nachbarschaft. Man bildet das digital nach, und die Ergebnisse des Algorithmus werden besser.7 In der Natur gibt es Abschnitte im Genom, die irgendwie zusammengehören und bevorzugt gemeinsam vererbt werden. Man bildet das digital nach, und die Ergebnisse des Algorithmus werden besser. In der Natur stellt man fest, dass ab einem gewissen Evolutionsstand auch so etwas wie kulturelle Evolution stattfindet: Individuen können sich selbst zielgerichtet verbessern (lokale Suche) und dieses Wissen an ihre Nachkommen weitergeben. Man bildet das digital nach, und die Ergebnisse des Algorithmus werden besser.

Und auch in die Welt der KI und der künstlichen neuronalen Netze erhalten evolutionäre Verfahren inzwischen langsam Einzug, wie zum Beispiel an Forschungen von Uber sichtbar wird, die in Experimenten das simple lokale Suchverfahren wie oben beschrieben durch rechenaufwändigere, aber potentiell bessere evolutionäre Verfahren wie genetische Algorithmen oder eine Evolutionsstrategie ersetzen.

Evolutionsgegner

Wenn man mit Gegnern der Evolution redet, hört man oft Argumente wie „Schau dir doch mal das Auge an. Das ist so furchtbar kompliziert und bringt erstmal nur bedingt einen Vorteil, wenn es nicht genau so funktioniert. Also kann das mit der Evolution doch alles gar nicht stimmen!“ Und das ist auf den ersten Blick auch gar keine so unintuitive Einsicht, denn (und das muss man festhalten): Der Mensch und Leben ganz allgemein ist auf eine atemberaubende Art und Weise einzigartig und unfassbar komplex.

Was man als Mensch nur sehr gut falsch einschätzt, sind Zufälle,8 und was man gerne unterschätzt, ist die lange, lange Zeit, die unsere Erde schon um die Sonne kreist und was in dieser Zeit alles Gelegenheit hatte, zu geschehen.

Ich weiß, dass dieser Text nicht der vollumfängliche Beweis für die Evolution oder auch nur ansatzweise eine Antwort auf die Frage ist, wie das Leben entstanden ist oder wo wir herkommen. Nichtsdestotrotz hoffe ich, zumindest ein bisschen mehr Verständnis für die involvierten Dimensionen gegeben zu haben und dass Ihnen, werte Leserinnen und Leser, die Evolution zumindest ein bisschen plausibler erscheint.


  1. Lena A. E. Tibell, Ute Harms. „Biological Principles and Threshold Concepts for Understanding Natural Selection“. In: Science & Education, Nov. 2017. Link (besucht am 17.05.2018). ↩︎

  2. Er wird also nicht nur zum Beispiel mit jeder Stadt um einen festen Wert größer oder vervielfacht sich um einen festen Wert, sondern er wächst noch viel schneller. ↩︎

  3. R. Oftadeh, M. J. Mahjoob, M. Shariatpanahi. „A novel meta-heuristic optimization algorithm inspired by group hunting of animals: Hunting search“. In: Computers & Mathematics with Applications, Okt. 2010. Link (besucht am 27.05.2018). ↩︎

  4. Es gibt bessere und schlechtere Populationsgrößen. Die genaue Zahl hängt immer von der Art des Problems ab, das wir lösen wollen. ↩︎

  5. Es gibt die Variante elitärer Akzeptanz, bei der Kinder ihre Eltern nur ersetzen, wenn sie besser sind. Diese Varianten finden schneller einen Gipfel, verschießen sich aber u. U. zu schnell auf einen der kleineren Berge. ↩︎

  6. Christian Blume, Jacob Wilfried. GLEAM - General Learning Evolutionary Algorithm and Method: ein Evolutionärer Algorithmus und seine Anwendungen. KIT Scientific Publishing, 2009. Link (besucht am 27.05.2018). ↩︎

  7. Man sieht sogar, wie sich in unterschiedlichen Nachbarschaften ganz verschiedene Nischenlösungen für das Problem entwickeln, und wie sich die „Ideen“ unterschiedlicher Nachbarschaften gegenseitig befruchten. ↩︎

  8. Lotto, Blitzschlag, Terror und Autounfall seien an dieser Stelle vier willkürliche Beispiele ↩︎


Titelbild: Daniel Friedman (CC BY-NC 2.0)
Ebenfalls erschienen im Neologismus 18-05

Mehr lesen