Mathematische Einfachheit kann der Geschwindigkeit der Evolution zugrunde liegen.

Informatiker lassen sich von der Evolutionsbiologie inspirieren, um optimale Lösungen für astronomische Dimensionssätze zu finden

Wenn wir die riesigen Räume möglicher Lösungen für das Problem untersuchen, sehen wir uns mit der Tatsache konfrontiert, dass die meisten Wege Sackgassen sein werden. Aber die Evolution hat vielleicht Wege gefunden, um die Erfolgschancen zu erhöhen.

Kreationisten lieben es, darauf zu bestehen, dass die Evolution bis zu 300 Aminosäuren in der richtigen Reihenfolge sammeln muss, um nur ein einziges mittelgroßes menschliches Protein zu erzeugen. Und da an jeder Position eine der 20 möglichen Aminosäuren lokalisiert werden könnte, scheint es mehr als ^20.300 Suchoptionen zu geben, was viele Größenordnungen höher ist als die Anzahl der Atome im beobachtbaren Universum. Selbst wenn wir Redundanz finden, aufgrund derer einige dieser Optionen gleichwertig sind, scheint die Wahrscheinlichkeit, dass die Evolution durch Zufall und zufällige Mutationen auf die richtige Kombination gestoßen ist, selbst in den vergangenen Milliarden Jahren ungeheuer gering.

Der Hauptnachteil solcher Argumente ist, dass die Evolution diese Sequenzen nicht zufällig erlebt hat: Der Prozess der natürlichen Selektion beseitigte das Unnötige. Darüber hinaus ist es wahrscheinlich, dass die Natur andere Problemumgehungen entdeckt hat, um eine große Anzahl von Wahrscheinlichkeiten auf kleine, untersuchbare Teilmengen einzugrenzen, die mit größerer Wahrscheinlichkeit nützliche Lösungen bieten.

Informatiker haben ähnliche Probleme, einschließlich der Suche nach optimalen Lösungen unter den vielen Optionen der astronomischen Größe. Einige von ihnen wenden sich zur Inspiration an die Biologie - trotz der Tatsache, dass Biologen selbst nur versuchen zu verstehen, wie es in der Natur ausgeht.

Genetische Algorithmen, seit mehreren Jahrzehnten beliebte Optimierungsmethoden, verwenden die Prinzipien der natürlichen Selektion, um neue Designs zu erstellen (unter anderem für Roboter, Medikamente und Transportsysteme), neuronale Netze zu trainieren oder Daten zu verschlüsseln und zu entschlüsseln. Diese Technologie beginnt mit der Tatsache, dass zufällige Lösungen für das Problem als einige „Organismen“ angesehen werden, die bestimmte Merkmale aufweisen, oder als Elemente, die in ihrem Code „genetisch“ definiert sind. Diese Lösungen sind nicht besonders gut, aber dann unterliegen sie verschiedenen zufälligen Mutationen (und manchmal anderen Änderungen, die den Prozess des Gen-Shufflings kopieren) und produzieren die zweite Generation von Organismen, die wiederum ihre Eignung zur Lösung des Problems testen. Infolgedessen führt dieser Prozess nach vielen Wiederholungen zur Entstehung eines äußerst gut angepassten Individuums oder einer Entscheidung.

Einige Experten bringen diese Methode auf die nächste Stufe und führen genetische Programmierung durch, um Programme zu erhalten, die Programme schreiben und effektive Lösungen produzieren können (hier können die „Gene“ Codezeilen sein). Dieses Ziel erwies sich als besonders schwierig zu erreichen, da die Forscher bestimmte Arten von Daten und Strukturen sowie viele andere Bedingungen berücksichtigen müssen.

Interessanterweise überschneiden sich diese auf Evolution basierenden Denkmethoden (insbesondere genetische Programmierung) konzeptionell mit einer mathematischen Theorie, die sich immer irgendwo an der Peripherie von Biologie und Informatik befunden hat. In letzter Zeit haben einige Wissenschaftler versucht, damit zu verstehen, wie natürliche und künstliche Evolution effizient arbeiten, etwas Neues schaffen und lernen kann, wie man lernt. Die Hauptsache hier war ein spezielles Konzept von Komplexität, Zufälligkeit und Information, das bis heute keine praktischen Anwendungen hatte.

Affen hinter den Tastaturen

Diese in den 1960er Jahren erfundene Theorie arbeitet mit sogenannten algorithmischen Informationen. Es geht von einer intuitiven Denkweise über Wahrscheinlichkeit und Komplexität aus: Die Idee, dass es für einige Eingabedaten rechnerisch schwieriger sein wird, zu beschreiben, wie etwas erstellt wird, als es zu erstellen. Nehmen Sie die bekannte Analogie mit einem Affen, indem Sie zufällig Tasten drücken. Die Wahrscheinlichkeit, dass sie die ersten 15.000 Ziffern der Zahl π druckt, ist lächerlich gering - und sie nimmt mit zunehmender Ziffernzahl exponentiell ab.

Wenn wir jedoch Tastenanschläge als zufälligen Text für ein Computerprogramm interpretieren, das die Zahl π anzeigt, werden die Erfolgschancen oder die „algorithmische Wahrscheinlichkeit“ radikal verbessert. Mit dem Code zum Anzeigen der ersten 15.000 Ziffern der Zahl π in der Sprache C können Sie beispielsweise insgesamt bis zu 133 Zeichen verkleinern.

Mit anderen Worten, die algorithmische Informationstheorie besagt, dass die Wahrscheinlichkeit, bestimmte Arten von Ausgabedaten zu liefern, viel höher ist, wenn zufällige Prozesse auf der Ebene des Programms ablaufen, das diese Daten beschreibt, als auf der Ebene der Daten selbst, da das Programm kurz sein wird. In diesem Sinne sind komplexe Strukturen - zum Beispiel Fraktale - durch Zufall viel einfacher zu bekommen.

Bei diesem Ansatz trat jedoch bald ein Problem auf: Mathematiker fanden heraus, dass die algorithmische Komplexität (auch bekannt als Kolmogorov-Komplexität , benannt nach Andrei Nikolaevich Kolmogorov , einem der Begründer der Theorie) der gegebenen Ausgabedaten - die Länge des kürzestmöglichen Programms, das sie erzeugen wird - nicht berechnet werden kann . Daher können Informatiker nicht den perfekten Weg finden, um einen String oder ein anderes Objekt zu komprimieren.


Die algorithmische Komplexität des Netzwerks auf der linken Seite ist hoch, da Sie zur Beschreibung alle Kanten auflisten müssen, die die Scheitelpunkte verbinden. In der Mitte ist die Komplexität geringer, da wir bei der Beschreibung dieses Netzwerks schreiben können, dass der Scheitelpunkt A mit allen anderen verbunden ist. Das richtige Netzwerk hat die geringste Schwierigkeit, da seine Beschreibung darin besteht, dass alle Eckpunkte paarweise durch Kanten verbunden sind.

Infolgedessen wurde die algorithmische Informationstheorie hauptsächlich auf dem Gebiet der reinen Mathematik entwickelt, wo sie verwendet wird, um verwandte Theoreme zu untersuchen und die Konzepte von Zufälligkeit und Struktur zu bestimmen. Seine praktische Anwendung schien unzugänglich. "Mathematisch gesehen ist dies ein einfaches und schönes Maß für die Komplexität", sagte der berühmte Mathematiker Gregory Chaitin, einer der Begründer der Theorie, der am Thomas J. Watson IBM Center und an der Federal University von Rio de Janeiro arbeitete. "Aber unter dem Gesichtspunkt der Anwendbarkeit in der realen Welt sah es uneinnehmbar aus."

Aber das brachte ihn nicht zurück. Er hoffte, dass diese Theorie verwendet werden könnte, um die Idee zu formalisieren, dass sich DNA wie ein Programm verhält. 2012 veröffentlichte er ein Buch, in dem er beschrieb, wie Evolution als zufälliger Spaziergang durch den Programmraum dargestellt werden kann. Mutationen, die auf diesem Weg auftreten, unterliegen keiner statistisch zufälligen Wahrscheinlichkeitsverteilung. Sie gehorchen einer Verteilung, die auf der Komplexität von Kolmogorov basiert. Aber er konnte es nicht verifizieren.

Nun hoffen einige Wissenschaftler, diese Theorie in diesem Zusammenhang wiederzubeleben und gleichzeitig mit Biologie und Informatik zu verbinden.

Der Wunsch nach Einfachheit

Hector Zenil , IT-Spezialist am Karolinska-Institut in Schweden, ist einer von denen, die versuchen, diese Theorie wiederzubeleben. Er arbeitet mit anderen Forschern zusammen, um die Kolmogorov-Komplexität als Messgröße für die Analyse der Komplexität biologischer Netzwerke zu verwenden - beispielsweise Genregulationsnetzwerke oder die Interaktion von Proteinen in Zellen. Die Forscher schätzen den algorithmischen Inhalt des Netzwerks grob ein (der genaue Wert ist nicht berechenbar), mutieren dann das Netzwerk und überprüfen, inwieweit es die Kolmogorov-Komplexität beeinflusst. Sie hoffen, dass diese Methode ihnen eine Vorstellung von der relativen Bedeutung der verschiedenen Elemente des Netzwerks und seiner funktionalen Reaktion auf absichtliche Änderungen gibt.


Der berühmte Mathematiker Gregory Chaitin, einer der Begründer der algorithmischen Informationstheorie

In einer kürzlich auf arxiv.org veröffentlichten Arbeit wurde beschrieben, dass, wenn Sie das Netzwerk in Richtung zunehmender Kolmogorov-Komplexität bewegen - Mutationen einführen, die das Netzwerkbeschreibungsprogramm größer werden lassen - dies normalerweise zu einer Erhöhung der Anzahl der Funktionen führt, die es ausführen kann Netzwerk, während es empfindlicher für Störungen macht. Als sie das Netzwerk dazu zwangen, einfacher zu werden, wurden die Funktionen geringer und die Stabilität erhöht.

Es bleibt jedoch unklar, ob Kolmogorovs Komplexität eine größere Rolle spielen kann als ein einfaches Werkzeug - zum Beispiel, wie Chaytin glaubt, als Hauptantriebskraft für Veränderungen. Trotz aller Probleme scheinen algorithmische Informationen eine attraktive Theorie für die Biologie zu sein. Zur Beschreibung der Evolutionsdynamik wurde traditionell Mathematik im Bereich der Populationsgenetik verwendet - statistische Modelle, die die Häufigkeit von Genen in der Population beschreiben. Die Populationsgenetik hat jedoch ihre eigenen Grenzen: Sie beschreibt nicht den Ursprung des Lebens und andere grundlegende biologische Übergangsprozesse oder das Auftreten völlig neuer Gene. "In dieser schönen mathematischen Theorie ging die Idee der biologischen Kreativität irgendwie verloren", sagte Chaitin. Aber wenn wir die algorithmischen Informationen berücksichtigen, sagte er: "Dann passt Kreativität natürlich in das Gesamtbild."

Ebenso wie die Idee, dass sich der Evolutionsprozess im Laufe der Zeit verbessert und die Effizienz erhöht. "Ich bin überzeugt, dass Evolution Lernen ist", sagte Daniel Polanyi , IT-Spezialist und Professor für künstliche Intelligenz an der Universität von Hertfordshire in England. "Ich bin nicht überrascht, wenn dies durch eine asymptotische Abnahme der algorithmischen Komplexität ausgedrückt werden kann."

Zenil und das Team beschlossen, die biologischen und rechnerischen Konsequenzen des Einflusses der Plattform der algorithmischen Komplexität experimentell zu testen. Mit der gleichen Technik zur Schätzung der Komplexität, mit der sie Netzwerke analysierten und störten, führten sie die „Evolution“ künstlicher genetischer Netzwerke in Richtung spezifischer Ziele durch - Matrizen von Nullen und Einsen, die Geninteraktionen bezeichnen - und wählten Mutationen aus, mit denen Matrizen erzeugt wurden weniger algorithmische Komplexität. Mit anderen Worten, sie entschieden sich für größere Strukturen.


Hector Zenil, Informatikspezialist, Caroline Institute

Kürzlich veröffentlichten sie Ergebnisse in der Zeitschrift Royal Society Open Science, aus der hervorgeht, dass ihre Auswahl von Mutationen im Vergleich zu statistisch zufälligen Mutationen zu einer signifikanten Beschleunigung der Entwicklung von Netzwerken hin zu Lösungen führte. Andere Merkmale zeigten sich auch, zum Beispiel konstante und regelmäßige Strukturen - Abschnitte von Matrizen, die bereits einen gewissen Grad an Einfachheit erreicht hatten, den neue Generationen kaum verbessern konnten. "Einzelne Regionen waren mehr oder weniger anfällig für Mutationen, einfach weil sie bereits ein gewisses Maß an Einfachheit erreicht hatten", sagte Zenil. "Es war den Genen sehr ähnlich." Dieses genetische Gedächtnis hat dazu beigetragen, dass große Strukturen schneller entstehen - Forscher glauben, dass daraus algorithmisch wahrscheinliche Mutationen zu Ausbrüchen von Diversität und Aussterben führen können.

"Dies bedeutet", sagte Zenil, "dass es ziemlich fruchtbar sein wird, Rechenprozesse bei der Untersuchung der Evolution zu berücksichtigen." Er hofft, dieses Verständnis von Zufälligkeit und Komplexität nutzen zu können, um Austauschwege zu identifizieren, die anfälliger für Mutationen sind, oder um zu verstehen, warum bestimmte Geninteraktionen mit Krankheiten wie Krebs assoziiert sein können.

Programmentwicklung

Zenil hofft zu verstehen, ob die biologische Evolution nach denselben Rechenregeln funktioniert, aber die meisten Experten haben Zweifel. Es ist nicht klar, welcher natürliche Mechanismus für eine grobe Abschätzung der algorithmischen Komplexität oder für die gezielte Entwicklung von Mutationen verantwortlich sein könnte. Darüber hinaus wäre es falsch zu glauben, dass das Leben vollständig in vier Buchstaben kodiert ist, sagte Giuseppe Longo , Mathematiker am französischen Nationalen Zentrum für wissenschaftliche Forschung. "DNA ist extrem wichtig, macht aber außerhalb der Zelle, des Organismus und des Ökosystems keinen Sinn." Andere Interaktionen funktionieren, und die Verwendung algorithmischer Informationen kann diese Komplexität nicht abdecken.

Dennoch erregte dieses Konzept ein gewisses Interesse - insbesondere, weil solche Ansichten über Evolution und Rechenprozesse etwas gemeinsam haben, zumindest ein gemeinsames Thema, mit dem Ziel der genetischen Programmierung -, ein Programm zu erhalten, das sich weiterentwickeln kann.

Es gab bereits ziemlich interessante Anspielungen auf den möglichen Zusammenhang zwischen den Ideen von Chaitin und Zenil im Zusammenhang mit der Komplexität von Kolmogorov und den Methoden der genetischen Programmierung. Beispielsweise berichtete ein Forscherteam im Jahr 2001, dass die Komplexität der Ausgabe eines genetischen Programms durch die Kolmogorov-Komplexität des ursprünglichen Programms begrenzt ist.

Zum größten Teil spielte die Komplexität von Kolmogorov jedoch keine Rolle bei den Versuchen der Informatiker, diese Ideen zu verstehen. Sie versuchten andere Wege, um Genetik und Mutationen zu verändern. Einige Gruppen änderten die Geschwindigkeit von Mutationen, andere zwangen das System, zu Mutationen zu tendieren, die große Codeteile ersetzten. "Die Leute haben Dutzende und möglicherweise Hunderte verschiedener Versionen von Mutationen und Genotypen entwickelt", sagte Lee Spector , IT-Spezialist am Hampshire College in Massachusetts. Spector leitete kürzlich ein Team, das die Vorteile des Hinzufügens und Entfernens von Mutationen im gesamten Körpergenom gegenüber dem direkten Ersatz eines Gens durch ein anderes demonstrierte . Diese neue Art von genetischem Operator erhöhte exponentiell die Anzahl der Pfade durch den Raum der genetischen Suche und führte letztendlich zu besseren Lösungen.


Lee Spector, Computerspezialist am Hampshire College, Massachusetts

Viele Forscher gingen jedoch in die entgegengesetzte Richtung, um nach ausgeklügelten Wegen zu suchen, um den Prozess zu beschleunigen, das Suchfeld einzuschränken, es jedoch nicht so stark einzuschränken, dass die Suche optimale Ergebnisse verfehlen würde. Eine Idee war es, Einfachheit zum Ziel zu machen: In den 1960er Jahren bemerkte Eugene Wigner „die unzumutbare Wirksamkeit der Mathematik in den Naturwissenschaften“, und Informatiker stellten fest, dass oft einfachere und elegantere Modelle effizienter und häufiger anwendbar sind. "Die Frage ist", sagte Spector, "sagt uns diese Tatsache etwas Tiefes über die Struktur des Universums oder nicht?" Und wird es uns nützlich sein? “

Er warnt auch davor, dass der Versuch, sich entwickelnde Programme zur Einfachheit zu bringen, destruktiv sein kann: Belohnungsprogramme für Kürze können den scheinbaren Müll reduzieren, aber für zukünftige Generationen nützlich sein, was zu geopferten optimalen Lösungen führt. "Und wir stecken fest", sagte er.

Einfachheit bleibt jedoch ein verführerisches Ziel, das sich darüber hinaus als nützlich erwiesen hat. In einem im letzten Jahr veröffentlichten Artikel stellten Spector und Kollegen fest, dass, wenn Sie die Größe der Programme - manchmal nur um 25% der ursprünglichen Länge - nach Anwendung genetischer Programmiertechniken reduzieren, die Programme mit neuen Daten besser abschneiden und für ein breiteres Spektrum allgemeiner Anwendungen verwendet werden können Probleme.

Insbesondere aus diesem Grund überwacht er die Arbeit auf dem Gebiet der algorithmischen Informationstheorie, obwohl er sagt, dass ihre Auswirkungen auf diesen Forschungsbereich noch abzuwarten sind.

Aus dem Leben lernen

Vielleicht hat das Zenil-Team den ersten Schritt bei der Suche nach diesem Einfluss unternommen. Für eine realistische Anwendung ihrer Arbeit müssen sie ihre Methode jedoch zunächst auf andere Arten von Suchproblemen testen.

Und doch "zeigten sie überzeugend die Notwendigkeit strukturbasierter Einschränkungen", sagte Larisa Albantakis , Neurowissenschaftlerin an der Universität von Wisconsin, die auch daran arbeitete, genetische Algorithmen durch Begrenzung des Suchraums zu beschleunigen. "Die Natur ist strukturiert, und wenn Sie dies als Ausgangspunkt nehmen, wäre es dumm zu versuchen, alle möglichen homogenen Mutationen zu testen." Und sie fügte hinzu: "Alles, was für uns Sinn macht, ist irgendwie strukturiert."

Und obwohl Spector skeptisch ist, dass Zenils Arbeit auf etwas angewendet werden kann, das außerhalb des Bereichs der spezifischen Aufgabe liegt, die er untersucht hat, "ist die Informationstheorie, die ihren Konzepten zugrunde liegt, faszinierend und möglicherweise sehr wichtig", sagte er. "Es scheint mir teilweise interessant, weil es irgendwie fremd aussieht." Vielleicht gibt es Ideen, die Genossen aus unserer Gemeinde nicht kennen. “ In der Tat beziehen sich algorithmische Informationen auf eine Vielzahl von Ideen, die einige Experten für genetische Programmierung möglicherweise nicht in ihre Arbeit einbeziehen, beispielsweise die unbegrenzte Natur der Evolution.

"Ich habe ein starkes Gespür für etwas Wichtiges in diesem Bereich", sagte Spector. Er fügte jedoch hinzu, dass "bisher eine große Distanz zwischen ihrer Arbeit und praktischen Anwendungen besteht".

"Die Idee, sich das Leben als sich entwickelndes Programm vorzustellen, ist sehr fruchtbar", sagte Chaitin, obwohl sein Wert noch zu früh ist, um ihn zu bestimmen. Ob wir über künstliches oder biologisches Leben sprechen, "wir müssen sehen, wie weit wir gehen können."