[Artikel] Simulierte Evolution

[Luckie]

Simulierte Evolution

Um was geht es dabei? 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 faszinierend ist, was man damit zum Schluss in der Praxis selber, überraschenderweise oder auch nicht, erleben kann.

Artikel: Simulierte Evolution

[negaH]

Sorry aber da muß ich widersprechen.

Man kann sehr wohl ein Program so konstruieren das man math. beweisen kann es es formal immer korrekt arbeiten wird. ABER! Laut Turing kann man eben kein zweites Program schreiben das nun quasi automatisch dieses erste Program testet und somit zu jeder möglichen Eingabe in dieses Program beweisen kann das es korrekt arbeitet.
Dh. per Definition kan man ein Program schreiben so das man es auch beweisen kann das es korrekt funktionieren muß. Aber man kann kein Program schreiben das ein anderes Program als math. korrekt beweisen kann.
Das ist meiner Meinung nach ein großer Unterschied und darf nicht in einen Topf geschmissen werden.

Delphi-Quellcode:

Genetische Algorithmen verfahren ja auf Gleiche Weise, nur dass sie den Quelltext nicht selber zusammenwürfeln. 
Das find ich schon erstaunlich.

Doch, genetische Algorithmen beruhen ja gerade darauf das sie mit Zufall=Mutationen ein Program "zusammenwürfeln". Das ist ja gerade das Faszinierende an der Evolution, eine rießige Kette von immer kleinen und zufälligen Veränderungen führt durch eine Selektionsfunktion zu einem lebenigen,lebensfähigem System. Grundsätzlich gesprochen ist das für Menschen schwer greifbare der Zusammenhang von Zufall bei der Entstehung und denoch absolut Logischem im finalen System. Wenn man den Menschen unter die Lupe nimmt so stellt man fest das alle Vorgänge in unserem Organismus absolut logisch ineinander greifen, aber wir wissen auch das all das durch zufällige Mutationen erzeugt wurde. Das entscheidende an diesem Prozess ist die Selektionsfunktion, quasi der Überlebenskampf durch Anpassung an unsere Umwelt. Dieser Prozess ist nicht zufällig !

Ein vergleichbares Beispiel wäre:

Wir füllen einen rießige Napf mit vielen M&M's. Den mischen wir kräftig und erzeugen so eine Menge von zufällig verteilten farbigen Kugeln. Das wäre unser Zufall.
Nun nehmen wir aber immer nur rot M&Ms raus, wie selektieren ganz bewusst, und legen diese auf einen Haufen.
Fertig ist ein wohl geordnerter und nach der Eigenschaft Farbe sortiertes System.
Wohin sich also die Evolution entwickelt entscheidet die Selektierungsfunktion und diese ist nicht zufällig.


Gruß Hagen

[Luckie]

@stoxx: Das was du als genetische Algorithmen bezeichnest, ist wohl in meinem Artikel das, wa sichmit sexueller Reproduktion bezeichne.

[3_of_8]

Das ist wirklich unglaublich. Ich würde das ganze fast für einen Aprilscherz halten, aber da nicht April ist, finde ich das wirklich erstaunlich... Der Evolutionsalgorithmus würde mich sehr interessieren.

[Tubos]

Sehr interessant.

Zitat:

das interessante ist die Tatsache, dass [die resultierenden Algorithmen] 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.
[..]
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.

Das glaube ich nicht. Aber ich habe ja auch nicht das Buch gelesen oder das Programm gesehen.

Während dem Mittagessen ist mir gerade eine Variante eines solchen Programmes eingefallen, die wohl etwas anschaulicher wäre.
Man stelle sich ein Programm vor mit einer 2-dimensionale Fläche, auf der verschiedene Lebewesen herumlaufen. Die können sich gegenseitig auffressen, es könnte auch simulierte Vegetation darin geben.
Solche Programme gibt es bereits, zum Beispiel .NET Terrarium. Aber bei all diesen Programmen (die ich gesehen habe), wird der Code von Menschen geschrieben.
Man könnte jetzt einen einfachen Interpreter schreiben mit grundlegenden Anweisungen: Vorwärts gehen, drehen, andere Lebewesen attackieren, if, else, verschiedene Bedingungen, etc... Die Anweisungen müssen dabei so gewählt werden, dass eine ausreichende Entscheidungsvielfalt möglich wird.
Dann erzeugt man, wie in Luckies Artikel beschrieben, eine bestimmte Anzahl von völlig zufälligen Programmen, die sich dann fortpflanzen können.

Vermutlich gibt es sowas schon, vielleicht kann mir jemand einen Hinweis geben?
Interessanter wäre es trotzdem, das Ganze selbst zu programmieren.

[Mirilin]

Zitat:

@stoxx: Das was du als genetische Algorithmen bezeichnest, ist wohl in meinem Artikel das, wa sichmit sexueller Reproduktion bezeichne.

So wie ich mich erinnere ist der unterschied zwischen GA und GP der, dass man mit GAs nur
die "Parameter" einer "Lösung" sucht, bei der GP evoluiert man aber einen Algorithmus/Programm.
GP ist also viel freier als GA.
Crossover spielt bei beiden die/eine wichtige Rolle.

Aber ist auch schon ein Weilchen her, kann mich gut irren^^


mfg Tobias

[negaH]

Zitat:

Man könnte jetzt einen einfachen Interpreter schreiben mit grundlegenden Anweisungen: Vorwärts gehen, drehen, andere Lebewesen attackieren, if, else, verschiedene Bedingungen, etc... Die Anweisungen müssen dabei so gewählt werden, dass eine ausreichende Entscheidungsvielfalt möglich wird.
Dann erzeugt man, wie in Luckies Artikel beschrieben, eine bestimmte Anzahl von völlig zufälligen Programmen, die sich dann fortpflanzen können.

Genauso arbeiten Genetische Algorithmen.

Stell dir mal vor das deine Anweisungen -> Vorwärts, Rückwärts usw. die Gene = DNA eines Wesens darstellen. Diese Gene werden in der Anfangspopulation komplett per Zufall erzeugt.

Nun lässt man in einer Selektierungsfunktion quasi diese Gene eines Individums als interpretierbares Program ablaufen, quasi eine Arbeitsanweisung wie sich das Individuum bewegen soll. Die Selektierungsfunktion bewertet nun an Hand der erreichten örtlichen Position die Qualität dieses Individuums, zb. 0 bis 100%. Sollte 100% erreicht worden sein so endet im Allgmeinen die komplette Evolution, denn wir haben ja eine maximal perfekte Lösung gefunden. Das ist aber real sehr wenig der Fall, man findet als viel öfters Lösungen die optimial aber nicht maximal gut sind.

Gut nachdem diese Selektierungsfunktion ALLE Individuen eienr Population auf diese Art bewertet hat beginnt man mit der Reproduktion, sprich Fortpflanzung. Dafür gibt es mehrer Ansätze, monogam/asexuell -> Zellteilungen und Klonen, oder sexuell dh. die Gene der neuen Population = Kinder setzen sich per Rekombinationen aller beteiligten Eltern zusammen. Dabei kann es zweigeschlechtlich, multigewschlechtlich usw. zugehen.

Wichtig ist nur eines! Die Häufigkeit in wieweit sich ein Individuum reproduzieren darf ist abhängig von deren Fitness. Die Fitness ist das was als Bewertung durch die Selektierungsfunktion ermittelt wurde. Das bedeutet das ein überaus gutes Individuum sich wesentlich stärker reproduzierenn darf als ein weniger gutes, es produziert also viel mehr Nachkommen und wird somit seine Gene viel stärker in der neuen Population verteilen. Ergo: die neue Population von Individuuen -> Kinder, wird ansich schon besser das Ziel ereichen.

Nach diesem Schritt der Fortpflanzung wird noch ein "Störfaktor" eingebaut, die Mutationen. Dabei werden zu einem geringen Prozentsatz von 1-3 Prozent die Gene der neuen Kinder per Zufall verändert. Dies schafft die Grundlage, als zufällige Varianz, das sich Neues und damit bis dahin Unbekanntes entwickeln kann.

Nach diesen Schritten stirbt die Elternpopulation aus und die neue Kinderpopulation tritt an ihre Stelle. Und der ganze Vorgang begint von neuem.

Die genetischen Algos. sind also defakto sehr effiziente Suchalgorithmen die im Besoinderen enorm rießige, ja unendlich große Suchräume effizient absuchen können und im Worstcase meistens ein Optima-> optimales Resultat erzielen aber nur unter seltesten Umständen das absolut beste Maximum der Lösung.

Neben den Neuronalen Netzen waren die genetischen Algortihmen und die Evolutionsstrategien eines meiner liebsten Hobbies

Gruß Hagen

[stoxx]

Zitat von negaH:

Delphi-Quellcode:

Genetische Algorithmen verfahren ja auf Gleiche Weise, nur dass sie den Quelltext nicht selber zusammenwürfeln. 
Das find ich schon erstaunlich.

Doch, genetische Algorithmen beruhen ja gerade darauf das sie mit Zufall=Mutationen ein Program "zusammenwürfeln".

damit meinte ich, dass Genetische Algorithmen nur Parameter verändern, aber sich selbst nicht im Quelltext verändern.
Und damit also "normale" Programme darstellen, wie man sie kennt.

[negaH]

Zitat:

So wie ich mich erinnere ist der unterschied zwischen GA und GP der, dass man mit GAs nur
die "Parameter" einer "Lösung" sucht, bei der GP evoluiert man aber einen Algorithmus/Programm.
GP ist also viel freier als GA.

Das sehe ich anders. Hierarisch betrachtet sind GPs eine Anwendung der GA's. GPs sind also nur eine spezielle Anwendungsform der Grundregeln der GA.

Die Frage ist nämlich was ist ein Program ? Es ist eine Sequenz von sequientiellen Anweisungen. Nun die Gene auf einer DNA sind auch nur ein Sequenz von Anweisungen und dieses Konzept ist in der GA verankert.

Ob man nun in den GAs und dessen Genen Programmanweisungen codiert oder Formeloperatoren zur Erzeugung von math. Formeln oder nur Parameter eines Neuronalen Netzwerkes ist egal.

Aber im allgemeinen sind es die Evolutuionsstrategieen die sich auf reine Parameter einer Optimierung beziehen. Die Evolutionsstrategien wurden in Deutschland entwickelt. Sie zielten zb. auf die konkrete Optimierung von Kränen, Düsen usw. ab und arbeiteten daher mit Floatzahlen als "Gene". Sie konzentrierten sich in keinster Weise um die Frage "wie werden Informationen kodiert".

Die Genetischen Algorithmen wiederum sind eine amerikanische Erfindung. Sie hatten kein reales Ziel als Fokus sondern wurden erstmal nur entwicklelt um zu lernen wie die Natur Informationen in den Genen kodiert und wie sich das auswirkt. Es ging also eher um theoretische Aspekte.

Gruß Hagen

[Mirilin]

Ich seh den unterschied darin, dass man wenn man zum Beispiel das Maximum einer Funktion sucht, dann sucht man mit dem GA die Koordianten, mit der GP aber erstellt man ein Programm dass das Maximum einer Funktion bestimmt. Also das eine erstellt Punkte im Raum, das andere Lösungsmethoden.
Die Lösung des GAs ist dann problemspezifisch, die Lösung des GPs idealerweise nicht.

mfg Tobias

[negaH]

Zitat:

damit meinte ich, dass Genetische Algorithmen nur Parameter verändern, aber sich selbst nicht im Quelltext verändern.
Und damit also "normale" Programme darstellen, wie man sie kennt.

Ja ich weis, und diese Meinung erachte ich eben als falsch.
Was und wie in den Genen welche Informationen kodiert sind ist irrelevant für die Theorie der GAs. Es ist eine reine Definitionsfrage die nur von der jeweiligen Interpreation und Zielsetzung abhängig sind. Es könnten eben auch Programme->Sourcecodes sein.

GAs verändern eben keine Parameter, das ist falsch bzw. viel zu einseitig betrachtet, sie verändern kodierte Informationen, sie arbeiten direkt auf der Kodierung, den Genen, Allelen, Chromosomen, DNA Strängen. Die Werkzeuge für diese Bearbeitungen sind die Selektion=Bewertungsfunktion der Fitness, die Vererbung durch Rekombination der Kodierung, Crossover etc.pp. und die zufällige Varianz über die Mutationen.

Bei den GAs ist es also das Schwierigste die Zielsetzungen die man verfolgt so in eine geeignete Kodierung der Gene usw. zu bekommen das sich daraus auch "lebensfähige" Individuuen bilden können, dh. das dieser Optimierungsalgo. als GA auch wirklich unserem Ziel annähern kann.

Die ES -> Evolutionsstrategien, umgehen eindeutig dieses Problem, weil es für die konkreten Optimierungen eigentlich auch irrelevant ist. Und als Endeffekt ergab sich auch das gerade die ES mit konkreten Erfolgen aufwarten konnte, eben stabilere Krane, bessere Unterwasser-Luft-Düsen mit bis dato ungeahnten Formen usw. Die GAs wiederum brachten zuerst nur Erfolge in der Fragestellung wie die Natur Informationen kodiert, übrigens sehr überraschende Antworten. Zb. die Frage: wieviel Prozent der Gene werden durchsachnittlich durch Mutationen verändert ? DIe Antwort, ca. 2.3 Prozent und das frappieende ? die Natur mutiert nachweislich ca. 2.3 Prozent der Gene. Man fand also unabhängig voneinander heraus, also die Biologen und die Informatiker, das sich dieser Prozentsatz als am besten erwies. (so schlagt mich bitte nicht wenn es nicht 2.3 Prozent sind, könnte mich da leicht irren )

Gruß Hagen