Simulierte Evolution


Einleitung

Vor etwas längerer Zeit habe ich mal ein Buch gelesen, welches mit vor kurzem wieder in die Hände gefallen ist: Daniel Hillis "Computerlogik" (Amazon-Link) [1] In diesem Buch beschreibt er sehr einfach und verständlich die Funktionsprinzipien moderner Computer. Ein sehr interessantes Buch. Doch am meisten fasziniert hat mich eines der letzten Kapitel: "Simulierte Evolution". Um was geht es in diesem Kapitel? Kurz gesagt geht es darum, dass sich Computerprogramme selber schreiben und verbessern. Sich also entwickeln, sich verbessern und sich der gestellten Aufgabe immer besser "anpassen" bzw. sie immer besser lösen können. Und das fand ich sehr faszinierend. Und am faszinierensten fand ich, was der Autor damit selber erlebt hat. Doch dazu später.

Was ist Evolution?

Zitieren wir doch dazu einfach mal die Wikipeadia:

Evolution (v. lat.: evolvere = abwickeln, entwickeln; PPP evolutum) ist ein Prozess, bei dem durch Reproduktion oder Replikation von einem System Kopien hergestellt werden, die sich voneinander und von ihrem Ursprungssystem durch Variation unterscheiden und bei dem nur ein Teil dieser Kopien auf Grund von Selektion für einen weiteren Kopiervorgang zugelassen werden.

Recht nüchtern, aber denn noch nicht allzu unverständlich, wie ich finde. Es geht also darum, dass sich ein System kopiert und es beim Kopiervorgang zu Veränderungen bei den Kopien kommt. Von den Kopien wiederum vervielfältigen sich nur die Kopien, die am besten angepasst sind.

Wie geht das mit Computerprogrammen?

Dass es in der Natur geht, sollte hinlänglich bewiesen sein. Letztendlich sind Sie ja, der gerade in diesem Moment diesen Text liest, der lebende Beweis. Aber die interessante Frage hier ist jedoch: Geht das auch mit Computerprogrammen? Können sich Computerprogramme selbständig kopieren und dabei eine Evolution erfahren? Die Antwort ist ja, es geht und es wurde auch schon gemacht.

Um zu verstehen, wie so etwas funktionieren kann, nehmen wir mal eine einfache Aufgabe, das sortieren von Zahlen. Im ersten Schritt erzeugt man eine erste Population von Zufallsprogrammen. Zu diesen Zweck kann man mit einem Pseudozufallszahlen-Generator zufällige Befehlsfolgen erzeugen. Um das ganze etwas zu beschleunigen kann man zum Beispiel nur die Befehle benutzen, die zum Sortieren wichtig sind, wie Anweisungen zum Vertauschen und Vergleichen. Jeder dieser zufälligen Befehlsfolgen stellt ein Programm dar. Die Zufallspopulation enthält dann am Ende vielleicht zehntausende solcher Programme.

Als nächstes prüft man diese Programme, um die erfolgreichsten Programme ausfindig zu machen. Dazu lässt man jedes Programm ablaufen und guckt, ob es eine Zahlenfolge richtig sortiert. Natürlich wird keins der so erzeugten Programme die Aufgabe lösen – aber einige haben vielleicht etwas Glück und kommen der richtigen Sortierung näher als andere. Beispielsweise könnten einige Programme niedrige Zahlen zufällig an das Ende der der Reihe stellen. Nach den Test aller Programme können wir den Programmen einen Eignungswert zuweisen.

Dann werden neue Populationen erzeugt, die von den Programmen mit den besten Noten abstammen. Dazu werden schlechte Programme beseitigt, und nur die am besten geeigneten überleben. Die neue Population entsteht, in dem die überlebenden Programme kopiert werden und jeweils kleine, zufällige Abweichungen eingefügt werden.. Dies entspricht dem Vorgang der ungeschlechtlichen Fortpflanzung mit Mutation. Man könnte auch Programme "kreuzen". Also Befehlsfolgen von zwei Elternprogrammen nehmen und daraus ein Kindprogramm erzeugen, welches dann aus den Befehlsfolgen von zwei Programmen besteht, die überlebt haben. Dies entspräche der sexuellen Fortpflanzung.

Mit der neuen Programmgeneration verfährt man wie mit der alten, man trifft also eine Selektion und läßt nur die Programme sich vermehren, die geeignet sind. Allerdings benötigt man dafür sehr schnelle und leistungsstarke Rechner. Mit Parallelrechnern lässt sich ließe sich alle paar Sekunden eine neue Generation erzeugen. Und mit jeder Generation nimmt die durchschnittliche Eignung der Population zu, das heißt die Programme sortieren immer besser. Nach ein paar tausend Generationen erfüllen sie dann die Aufgabe fehlerfrei.

Das Ergebnis

Der Autor des Buches hat genau das obige Beispiel nachvollzogen. Er nur noch als zusätzliches Eignungskriterium die Schnelligkeit hinzugenommen mit der eine Zahlenfolge richtig sortiert wird. Als Ergebnis erhielt er Programme, die die Aufgabe tatsächlich schneller erledigen konnten, wie bekannte Sortieralgorithmen. Das überraschende aber ist nicht die Tatsache, dass Programme entstanden sind, die eine Aufgabe besser lösen als von Menschen programmierte. Nein, das interessante ist die Tatsache, dass sie unverständlich sind. Es konnte in diesem Fall einfach nicht nachvollzogen werden wie sie letztendlich funktionieren. Als Erklärung gab es nur die Befehlsfolge selber. Und genau dies hat mich eben Regel recht fasziniert.

Was bedeutet das? Nun es könnte bedeuten, dass wir die Funktionsweise unseres Gehirns nie richtig verstehen werden, wenn die Evolution, simuliert oder nicht, offensichtlich in der Lage ist, etwas hervorzubringen, was sich einfach nicht begreifen lässt. Es kann auch bedeuten, dass in Zukunft nicht derjenige ein guter Programmierer ist, der weiß, wie man ein Problem löst und mit seinem Werkzeug umgehen kann, sondern derjenige Programmierer, der geschickt die Ausgangs- und Zielparameter definieren kann, so dass man mit möglichst wenig Populationen zum Ziel kommt und die gestellte Aufgabe, wie gefordert, richtig löst.


2010-12-29T23:44:55 +0100, mail+homepage[at]michael-puff.de