Wie wichtig ist der Zufall in evolutionären Algorithmen?

DrZoidberg

Mit evolutionären Algorithmen kann man z.B. virtuelle Wesen simulieren, die sich im Computer weiterentwickeln. Man könnte ganze Welten simulieren, mit Tieren, Pflanzen, etc.
Eine solche virtuelle Welt hätte natürlich einen hohen Informationsgehalt.
Das Problem ist nun, dass solche Programme in der Regel Pseudozufallszahlen für die Simulation verwenden. Pseudozufallszahlen haben aber praktisch keinen Informationsgehalt. Bzw. sie enthalten nur so viel an Information, wie in dem Algorithmus steckt, der sie erzeugt hat.
Nimmt man z.B. eine unendlich lange Zahlenreihe, die so anfängt: 2, 4, 8, 16, 32, ...
Auch wenn diese Zahlenreihe unendlich lang ist, ist ihr Informationsgehalt doch sehr gering. Nämlich genau so hoch, wie der Informationsgehalt der Gleichung f(x)=2^x
Also höchstens ein paar Byte.
Bei Pseudozufallszahlen sieht es ähnlich aus. Egal wie lang eine solche "zufällige" Zahlenreihe auch sein mag. Der Informationsgehalt ist sehr gering.
Erstellt man also nun eine virtuelle Welt, die Anfangs einen geringen Informationsgehalt hat, und lässt dort eine künstliche Evolution ablaufen unter Verwendung von Pseudozufallszahlen, kann es dann überhaupt möglich sein, dass sich dort komplexe "Lebewesen" entwickeln? Oder setzt der Informationsgehalt des Programms der Evolution Grenzen?

SeppJ

Oder setzt der Informationsgehalt des Programms der Evolution Grenzen?

Nein. Ich kann auch deine Argumentation dazu überhaupt nicht nachvollziehen. Du wirfst da wild Begriffe aus der Informationstheorie durcheinander. Deiner Argumentation zufolge könnte man überhaupt gar nichts ausrechnen.

Was dich eventuell einschränkt ist die Anzahl möglicher Evolutionspfade zu einer gegebenen Anfangskonfiguration bei mehrfachen, unabhängigen Läufen. Diese entspräche der Länge des Seeds. Aber das ist keine echte Einschränkung, da die Zahl der Seeds extrem groß ist und die Anfangskonfigurationen beliebig.

DrZoidberg schrieb:

Bei Pseudozufallszahlen sieht es ähnlich aus. Egal wie lang eine solche "zufällige" Zahlenreihe auch sein mag. Der Informationsgehalt ist sehr gering.

Es gibt zweifellos RNGs, die für diese Art von Anwendung mehr als ausreichend zufällig verteilte Zahlen liefern.

DrZoidberg schrieb:

Mit evolutionären Algorithmen kann man z.B. virtuelle Wesen simulieren, die sich im Computer weiterentwickeln. Man könnte ganze Welten simulieren, mit Tieren, Pflanzen, etc.

Nö. Damit kann man garnichts simulieren.

Evolution selber braucht gar keinen Zufall.
Nimm ein Gen, mutiere es auf alle möglichen Arten und schau. Schau, welche Tiere überleben und lass sie weiter mutieren.

ipsec

Beispiel Mersenne Twister, ein performanter, häufig verwendeter RNG: dessen Periode ist 2¹⁹⁹³⁷-1. D.h., selbst wenn du jede Pikosekune (1/1000 Nanosekunde) eine neue Zahl anforderst, reicht das 10⁵⁹⁷² mal das Alter des Universums, bis sich die Folge wiederholt. Der Seed hat 20000 Bits, d.h. es gibts 2²⁰⁰⁰⁰ mögliche solcher Folgen. Diese Zahl entspricht dem fast 10 Trillionenfachen (ja, Trillionen, eine Trillion sind eine Millarde Millarden) der Periode. D.h. die gesamte Menschheit könnte bis zum Ende aller Tage pausenlos diese Simulation laufen lassen und würde niemals alle Möglichkeiten, nicht mal alle Startwerte, durchprobieren können.

Und es gibt Generatoren, da sind diese Werte noch viel höher...

SeppJ

ipsec schrieb:

...

Das ist egal. Die ganze Argumentation mit der Information ist an sich schon falsch. Du kannst auch mit dem billigsten Zufallsgenerator bei genetischen Algorithmen alles machen.

ipsec

SeppJ schrieb:

ipsec schrieb:

...

Das ist egal. Die ganze Argumentation mit der Information ist an sich schon falsch. Du kannst auch mit dem billigsten Zufallsgenerator bei genetischen Algorithmen alles machen.

Naja nicht ganz. Billiger Zufallsgeneator: http://xkcd.com/221/
=> jede Simulation ist gleich. Etwas langweilig.

Außerdem wollte ich mal ein bisschen auf die Größenordnungen hinweisen. Selbst wenn der Informationsgehalt "nur" in den 20000 Bit bestehen würde, reicht das trotzdem für alle Simulationen, die man je wird machen können.

SeppJ

ipsec schrieb:

SeppJ schrieb:

ipsec schrieb:

...

Das ist egal. Die ganze Argumentation mit der Information ist an sich schon falsch. Du kannst auch mit dem billigsten Zufallsgenerator bei genetischen Algorithmen alles machen.

Naja nicht ganz. Billiger Zufallsgeneator: http://xkcd.com/221/
=> jede Simulation ist gleich. Etwas langweilig.

Trotzdem wäre ich mir gerade nicht so sicher, ob die Simulation selbst damit nicht doch halbwegs funktionieren würde. Es geht ja nicht darum, jedes mal etwas anderes herauszubekommen, sondern ein Optimum zu finden (und dieses sollte idealerweise immer das gleiche sein, denn sonst wäre es ja kein Optimum ). Dazu kann man auch mit dem xkcd-Generator den gesamten Konfigurationsraum systematisch durchgehen. Natürlich ist dies die denkbar schlechteste Strategie, aber an sich sollte dies funktionieren.

volkard

Du verkennst etwas: Die komplette Simulation mit dem genetischen Algo ist ein großer Pseudozufallsgenerator. Der kann gigantiche Periedenlämgen haben, ohne daß Fremdzuzfall zugeführt werden muß.
Mit "gigantisch" meine ich nicht nur 10 hoch (ganz viel), sondern sowas wie "Abschätzung unralistisch" auf http://de.wikipedia.org/wiki/Fleißiger_Biber

otze

Das ist egal. Die nötigen Informationen liefert die Oberfläche der Fehlerfunktion auf denen die Individuen erzeugt werden. Solange dein Verfahren eine lokale Metrik auf dieser Fehleroberfläche schätzen kann (paradebeispiel CMA-ES), ist es egal, wie die Zufallszahlen aussehen. Wir haben zum Beispiel nach mehreren jahren gemerkt, dass unsere mehrdimensionale Gaussverteilung mit dem von uns verwendeten RNG spiralen auf der Oberfläche erzeugt. Guess what? hat tadellos funktioniert.

ipsec

Ich hatte es so verstanden, dass der TE mit seinen evolutionären Algorithmen (nicht genetischen Algorithmen) eine hübsche Evolutionssimulation bauen will. Also er drückt auf Start und sieht schön viele kleine unterschiedliche Viecher sich entwickeln. Wäre natürlich blöd, wenn jede Simulation da den gleichen Ablauf hat. Eventuell habe ich das aber auch missverstanden.
(Frage: gibt es bei der Evolution ein Optimum?)

It0101

ipsec schrieb:

(Frage: gibt es bei der Evolution ein Optimum?)

Das hängt wohl eher von deiner Fitnessfunktion ab. Es kann beliebig viele gleichwertige Minima in der Fehleroberfläche geben

Als Beispiel:
sin(x) = 1

Da hast du unendlich viele Lösungen für x...

DrZoidberg

Gut. Ich hätte wahrscheinlich nicht von evolutionären Algorithmen reden sollen.
Worauf ich eigentlich hinaus wollte ist eine Simulation unseres Universums inklusive der Erde und aller Lebewesen.
Also angenommen man hätte unendlich viel Speicher und Rechenleistung.
Im Moment des Urknalls enthielt das Universum nur sehr wenig Information. Mit der Zeit wuchs aber die Entropie und damit auch der Informationsgehalt.
Wollte man also die Entwicklung des Universums, angefangen beim Urknall, im Computer simulieren, müsste man der Simulation dann nicht ständig Information hinzufügen, um die Entropie weiter und weiter zu erhöhen?
Verwendet man einen Seed von 20000 bits, dann könnte dieses "Universum" zwar 2²⁰⁰⁰⁰ verschiedene Endzustände annehmen, das ist aber doch ziemlich wenig. Das reale Universum hat 10⁸⁰ Atome. Ich bin mir nicht sicher wie hoch die Anzahl der möglichen Zustände ist, aber es dürfte mehr als 10¹⁰80^ sein.

volkard

DrZoidberg schrieb:

Mit der Zeit wuchs aber die Entropie und damit auch der Informationsgehalt.

Eventuell.

a) Das Universum ist deterministisch, vorherbestimmt, zwangsläufig und so. Daher nimmt der Informationsgehalt gar nicht zu.

b) Es ist nicht deterministisch, aber die Entwicklung ist zwangsläufig, zum Beispiel fällt alles wieder zurück in einen erneuten Urknall, dann ist zwischenzeitlich mal mehr Information da, aber die ist irrelevant und kurzlebig.

c) Es ist nicht deterministisch und fehlerverstärkend (meine Vermutung). Dann schlägt sich jedes Bit aus dem seed nieder. Jede mögliche Bitfolge erzeugt ein eigenes unverwechselbares Universum. Wenn es Quantensprünge noch gäbe, konnte man wohl dort reinzufallen. Wieviele Quantensprungentscheidungen seit dem Urknall?

Beim Suchen nach "komplexen" Lebewesen kommt es auf die Spielregeln an, wie die Guten ausgesucht werden und wie sie sie Schlechten verdrängen. Manchmal tentieren die Lösungen in die selbe Richtung. Vielleicht ist das Modell "Symmetrischer Zweibeiner mit Hirn oben" prinzipiell am stärksten und gewinnt in allen Universen. Dann hat der Zufall am Ende viel weniger Effekt. Die Welt wäre zwar stark zufällig im Detail (wenn ich nur mal an die Namen der ganzen Chinesen denke), aber da alle Welten zu "Symmetrischer Zweibeiner mit Hirn oben" konvergieren, ist es recht egal, wie stark der Zufall ist, wenn man nur einen Guten sucht.

SeppJ

DrZoidberg schrieb:

Gut. Ich hätte wahrscheinlich nicht von evolutionären Algorithmen reden sollen.
Worauf ich eigentlich hinaus wollte ist eine Simulation unseres Universums inklusive der Erde und aller Lebewesen.
Also angenommen man hätte unendlich viel Speicher und Rechenleistung.
Im Moment des Urknalls enthielt das Universum nur sehr wenig Information. Mit der Zeit wuchs aber die Entropie und damit auch der Informationsgehalt.
Wollte man also die Entwicklung des Universums, angefangen beim Urknall, im Computer simulieren, müsste man der Simulation dann nicht ständig Information hinzufügen, um die Entropie weiter und weiter zu erhöhen?
Verwendet man einen Seed von 20000 bits, dann könnte dieses "Universum" zwar 2²⁰⁰⁰⁰ verschiedene Endzustände annehmen, das ist aber doch ziemlich wenig. Das reale Universum hat 10⁸⁰ Atome. Ich bin mir nicht sicher wie hoch die Anzahl der möglichen Zustände ist, aber es dürfte mehr als 10¹⁰80^ sein.

Schön, das gibt dir die Anzahl der möglichen Universen die du mit deinem Computer simulieren kannst. Aber wo ziehst du die Verbindung mit der möglichen Komplexität der so entstehenden Universen?

Muss der Computer der das Universum simuliert auch simuliert werden?

otze

DrZoidberg schrieb:

Worauf ich eigentlich hinaus wollte ist eine Simulation unseres Universums inklusive der Erde und aller Lebewesen.

Alle Information steckt in dem Programmcode deiner Simulation. Nichts kann da irgendwie Informationen hinzufügen. Das Einzige, was der PRNG da verändern kann ist, wie gut du die Informationen ausschöpfen kannst. Das wirkt sich aber nur dadurch aus, dass du mit einem PRNG niemals alle möglichen Universen erzeugen kannst. Aber das willst du ja auch nicht. 1 Universum wird dir für den Anfang sicherlich reichen ;).

(vergiss niemals, dass egal welche Sequenz ein noch so schlechter PRNG erzeugt, diese Sequenz auch genau so von einem echten RNG erzeugt werden könnte)

volkard

otze schrieb:

Alle Information steckt in dem Programmcode deiner Simulation. Nichts kann da irgendwie Informationen hinzufügen.

Dessen war ich mir auch völlig sicher; bis Du es ausgesprochen hast. (Liegt nicht an Dir persönlich, ich bezweifle alles, was ich lese.)

Ist das so? Kann man ein Programm schreiben, was so schlau wie ein Mensch ist? Nehmen wir das mal an. Ich bin der Meinung, daß die Menschheit derzeit Wissen schöpft. Ist das der Gegenbeweis, daß Programme niemals schlau werden? Das mag ich nicht glauben.

SeppJ

Wenn Programme keine Information erzeugen könnten, dann wäre die ganze Computerei sinnlos. Aus einfachen Grundregeln kann (und wird in der Regel auch) komplexes Verhalten folgen. Das nennt man Emergenz und ist praktisch die Basis unseres ganzen Weltbildes, welches alles auf einfache Grundregeln zurückführen will und kann. Und da dieses Weltbild so gut funktioniert, ist da wohl auch was dran.

Schönes Beispiel für Informatiker ist Langtons Ameise. Der Programmcode passt auf eine Bildschirmseite, aber das was rauskommt, darüber kann man ein halbes Buch schreiben.