Evolution zur Problemlösung in der Informatik

Jetzt stellt sich natürlich die Frage, wie die Mechanismen von Mutation, Rekombination und Selektion genutzt werden können, um Probleme in der Informatik zu lösen. Zuerst einmal: ein Problem kann jede Fragestellung sein, die sich mit Hilfe computergestützter Methoden beantworten lässt. Bekannte Problemstellungen sind etwa die Suche nach einer möglichst kurzen Route durch verschiedene Orte (bekannt als Rundreiseproblem), die optimale Auswahl von Objekten aus einer Menge nach bestimmten Kriterien (das Rucksackproblem) oder die platzsparendste Anordnung von Objekten auf einem Trägermaterial (was zum Beispiel besonders wichtig bei der Entwicklung von Prozessoren ist). Insbesondere die sogenannten Optimierungsprobleme sind von Interesse; damit sind Probleme gemeint, die nicht nur eine eindeutige Lösung besitzen, sondern deren verschiedene Lösungen nach ihrer Güte eingeteilt werden können. So gibt es etwa bei der Suche nach einer Rundreise vielleicht eine optimale Route, aber die anderen möglichen Routen sind ebenfalls Lösungen des Problems – nur eben nicht so gute.

Der Trick ist nun, eine möglichst gute Lösung eines Problems zu suchen, indem verschiedene Lösungskandidaten zufällig generiert und diese dann in einer künstlichen Umgebung unter der Einwirkung der Mechanismen von Evolution und Genetik zu modifizieren, um sich so einer optimalen Lösung anzunähern. Und genau das ist es, was die evolutionären Algorithmen machen. Im Groben sieht das Vorgehen dabei wie im Folgenden beschrieben aus:

Zu Beginn wird (manuell oder automatisch) eine Menge von zufälligen Lösungskandidaten – jeder Lösungskandidat ist ein einzelnes Individuum – erstellt, welche die Ausgangsbasis der Suche bilden. Diese Individuen haben nun die Möglichkeit, sich unter einem gewissen Selektionsdruck so lange “fortzupflanzen”, bis ein hinreichend guter Lösungskandidat entstanden ist (oft genug reicht das nämlich schon zur Lösung eines Optimierungsproblems). Für gewöhnlich wird dabei noch ein Alterungskonzept zugrunde gelegt, durch welches alte Individuen “sterben” und durch ihre Nachkommen ersetzt werden; die Individuen werden dabei meist in aufeinanderfolgende Generationen (oder – biologisch ungenau – in Populationen) eingeteilt.

Die Vermehrung der Individuen geschieht, indem etwa die Eigenschaften zweier nach bestimmten Kriterien ausgesuchter (selektierter) Individuen miteinander (re-)kombiniert und der so entstehende Nachfahre noch einmal zufällig mutiert wird. Dies wird für verschiedene Individuen einer Generation mehrmals ausgeführt, wodurch die Nachfolgegeneration entsteht, welche ihre Vorgänger für den nächsten Iterationsschritt im Algorithmus ersetzt. Der Prozess wird insgesamt so lange wiederholt, bis oben genanntes Abbruchkriterium – ein hinreichend guter Lösungskandidat – erreicht wurde. Wenn wir das ganze in Pseudocode notieren, erhalten wir folgenden Algorithmus (g0 ist die Ausgangsgeneration,
T ist der Typ eines Lösungskandidaten):

(1)  Evolutionary Algorithm: g0 TnT:
(2)    t ∈ T
(3)    g ∈ Tn, g ← g0
(4)    do:
(5)       g’, g” ∈ Tn
(6)       g’ ← select individuals from g
(7)       g” ← recombine individuals in g’
(8)       mutate individuals in g”
(9)       t ← select best individual in g”
(10)   while t not good enough
(11)   return t

Durch diesen Algorithmus kann auf ziemlich elegante Weise eine gute Lösung für
ein ansonsten
recht schwierig zu lösendes Problem gefunden werden. Jetzt muss natürlich aber auch noch geklärt werden, wie denn nun die Mutation, Rekombination und Selektion der Individuen genau stattfindet, was das ganze mit den anfänglich erwähnten Begriffen von Genotyp und Phänotyp zu tun hat und – so ehrlich wollen wir sein – wo die Probleme des Verfahrens liegen. Aber das hebe ich mir für das nächste mal auf.

1 / 2

Kommentare (24)

  1. #1 Sascha
    Dezember 5, 2011

    Jaja, das haben wir gerne. Erst den Mund wässrig machen und dann auf später vertrösten.

    Interessant dürfte in diesem Zusammenhang dann auch die Betrachtung von geeigneten Programmiersprachen sein.

  2. #2 Marcus Frenkel
    Dezember 5, 2011

    @Sascha
    Naja…einen Artikel der doppelten Länge lesen vermutlich weniger. Der Folgeartikel wird aber nicht lang auf sich warten lassen, versprochen. 😉

    Wozu ich allerdings nichts sagen werde, sind geeignete Programmiersprachen. Nach meinen bisherigen Erfahrungen ist jede Sprache geeignet, um evolutionäre Algorithmen umzusetzen – abhängig vom Einsatzgebiet, aber das hat man bei Sprachen ja immer (z.B. HPC u.ä.). Sollte es natürlich eine DSL extra für evolutionäre Algorithmen geben, erwähne ich die gerne, aber mir ist keine bekannt.

  3. #3 OKI
    Dezember 6, 2011

    “…Jetzt muss natürlich aber auch noch geklärt werden, wie denn nun die Mutation, Rekombination und Selektion der Individuen genau stattfindet…”

    Jetzt kommen wir zum “Gott-Kern”! Lasst mich dazu etwas ausholen bitte.

    Schon sehr früh habe ich mich mit (damals noch) Philosophie, heute mit Kosmologie plus angrenzende Wissenschaften (Psychologie, Bio-Chemie…) beschäftigt.

    In meiner Jugend irritierte mich, dass sehr viele große Wissenschaftler trotzdem an Gott (was auch immer das für sie darstellt) glaubt. Ich bin absolut atheistisch aufgewachsen und habe das verteidigt auf “Teufel, komm raus!”.

    Je mehr ich weiß oder zu wissen glaube (schon wieder Glaube), desto mehr hinterfrage ich Sinn und Mechanik (positiver Sinn des Seins an sich).

    Ich glaube inzwischen kaum noch an den Menschen, er ist eine Kolonie anderer lebender Organismen, die sich ihn zu Nutze machen. Klingt hart, trifft aber “meinen” Kern.

    Je mehr ich die Entdeckungen zum gewollten (wer will wie sowas?) Austausch, von DNA-Stücken begreife, desto kleiner wird mein Bild von Intelligenz. Diese Intelligenz, die den Menschen dazu bringt, auf andere Wesen herabzuschauen.

    Bestimmt ist Intelligenz nur eine Steigerung von Information. Insofern stimme ich mit bestimmten Thesen zum informativen Weltall überein. Information geht nicht verloren! Vielleicht für uns (z.B: black hole) aber nie im Gesamtkonsens.

    Anschaulich?, ich kann schon 100erte Mio Jahre tot sein, meine Information ist immer noch im Kontext der Raumzeit vorhanden und abrufbar.

    Ich denke, unsere ja/nein-Informatik ist ein falscher Weg. Wie S. Lem die Technologie für einen falschen Weg der Menschheit hielt.

    Informatik, ist für mich quanten-physikalisch, ein “Willst du mit mir gehen: ja/Nein/vielleicht)”. Wir haben uns nur von der Urmathematik auf einen falschen Pfad bringen lassen.

    Die Physik hat sich geändert, nur die Mathematik und Informatik noch nicht.

  4. #4 Marcus Frenkel
    Dezember 6, 2011

    @OKI
    Könnten Sie bitte in Bezug auf Ihren Kommentar den Zusammenhang zum Artikel-Inhalt darstellen? Der erschließt sich mir nämlich noch nicht.

  5. #5 oki
    Dezember 6, 2011

    Sorry, ich war etwas ausschweifend, der Knackpunkt auch bei Darvin und der Biochemie bleibt die Umwandlung von unbelebter in handelnder Materie, es ist das gleiche Dilemma wie KI, nur vom anderen Ende her. In der Mitte ist eine Singularität und keiner weiß, wie es aufgelöst werden kann! Ansonsten würde der Papst bei mir Asyl suchen….

  6. #6 oki
    Dezember 6, 2011

    @marcus:

    Darvinismus als programm, leben simulieren, das ist eine (zur Zeit, mit unserem Wissen) nicht lösbare Aufgabe. Mathematiker und Informatiker greifen sich nur Aspekte aus und stellen diese dar….

    Tut mir leid, ich hab die Welt nicht erfunden.

  7. #7 Marcus Frenkel
    Dezember 6, 2011

    Niemandem geht es bei evolutionären Algorithmen darum, leben zu simulieren. Die Algorithmen dienen allein zur Lösung von Problemen, wobei er sich lediglich aus der Biologie bekannter Mechanismen bedient wird – sie haben nicht den Anspruch, Leben in irgendeiner Form zu simulieren oder die Evolution nachzubilden o.ä.

    Abgesehen davon weiß ich nicht wirklich, was nun genau die Aussage Ihrer Kommentare ist. Sind Sie gegen/für die Benutzung von evolutionären Algorithmen? Denken Sie, dass sie falsch benutzt werden? Sprechen Sie hier von der Informatik oder von der Evolutionstheorie an sich? Es fehlt eine klare Aussage – Allgemeinplätze sind nicht hilfreich und zu schwammig.

  8. #8 CM
    Dezember 6, 2011

    OKIs Kommentare sind zwar extrem schwurbelig (ich jedenfalls verstehe gar nichts), aber Marcus, ich darf Dich trösten: Es gibt genügend Biologen, die entweder Evolution nicht verstehen oder / und sich gegen genetische Algorithmen sperren oder / und in esoterisches Geschwafel abgleiten wenn sie drüber sprechen. (Habe ich so tatsächlich mal gehabt; Zitat eines W3 der jüngeren Generation: “Das geht aber nicht, dass Sie (sic!) hier einfach von genetischen Algorithmen sprechen. Genetik ist schließlich ein belegter Begriff.”

    Wie dem auch sei: Schöner Beitrag, hoffentlich komme ich heute Abend dazu ihn ganz zu lesen.

  9. #9 Name erforderlich
    Dezember 6, 2011

    Ein schönes praktisches Beispiel, leider ohne das dazugehörige Programm: http://www.mandelbrotgenetics.com/

  10. #10 BreitSide
    Dezember 6, 2011

    xxx:-)

  11. #11 Christoph
    Dezember 7, 2011

    Ich hätte geflattrt, hab’ aber keinen Butten gefunden 😉

  12. #12 Dr. Webbaer
    Dezember 7, 2011

    Die Vermehrung der Individuen geschieht, indem etwa die Eigenschaften zweier nach bestimmten Kriterien ausgesuchter (selektierter) Individuen miteinander (re-)kombiniert und der so entstehende Nachfahre noch einmal zufällig mutiert wird.

    Wie ‘ausgesucht wird’? Das ist ja der Knackpunkt. Sie können, kreationistische Ideen einmal ausgenommen, nur über entsprechend befähigte Algorithmen iterativ aussuchen lassen. [1] Sie sind hier auf dem Holzweg.

    MFG
    Dr. Webbaer

    [1] Weil die IT der Realität, also der Sachlichkeit dient, müssten Sie natürlich auch das “Aussuchen” “designen”, Dr. W hat keine Probleme mit diesbezüglichen Überlegungen – sofern diese dem Vortragenden geläufig sind. – Was hier nicht ganz klar ist, letztlich wäre man übrigens beim Nachbau der Welt, dieser Welt, und bei dementsprechender Selektion, SciFi-Literatur steht bereit, wird aber zur Sache nicht direkt helfen.

    PS: Jaja, GL anyway!

  13. #13 Dr. Webbaer
    Dezember 7, 2011

    @Frenkel
    OKI hat ein dulles Vorhaben dull ausgebaut.

    HTH
    Wb

  14. #14 H.M.Voynich
    Dezember 7, 2011

    @Webbär:
    Zitat Marcus Frenkel: “Insbesondere die sogenannten Optimierungsprobleme sind von Interesse; damit sind Probleme gemeint, die nicht nur eine eindeutige Lösung besitzen, sondern deren verschiedene Lösungen nach ihrer Güte eingeteilt werden können.”

    Man erzeugt einen Satz Algorithmen, sortiert sie nach ihrer Güte, verwirft die schlechten und macht mit den guten weiter. Wo genau liegt Ihr Problem?

  15. #15 Donnamara
    Dezember 8, 2011

    @Frenkel

    “Sind Sie gegen/für die Benutzung von evolutionären Algorithmen? Denken Sie, dass sie falsch benutzt werden?”

    Der Fehler ist die Bezeichnung “evolutionäre A.”! Es gibt bei der behaupteten Evolution nur den Zufall als Algorithmus! Es gibt keine auswertende Instanz, keine Intelligenz, welche beurteilt und den nächsten Schritt logisch anlegt, keine Instanz, welche ein Ziel vorgibt und das Erreichte damit vergleicht!

    Das ist der Betrug!

    Deine Algorithmen sind also auf gar keinen Fall “evolutionär”!

  16. #16 Donnamara
    Dezember 8, 2011

    @Frenkel

    Deine Algorithmen entsprechen dem kreationistischem Prinzip “Versuch und Irrtum”, welches nicht ganz so intelligente Schöpfer gezwungen sind anzuwenden. Einem intelligenten Schöpfer gelingt dies sogar ohne Versuch und ohne Irrtum sogar in einem höchst komplexen Produkt auf einen Schlag !

    Hahahaha.

  17. #17 Dr. Webbaer
    Dezember 8, 2011

    @Voynich

    Man erzeugt einen Satz Algorithmen, sortiert sie nach ihrer Güte, verwirft die schlechten und macht mit den guten weiter. Wo genau liegt Ihr Problem?

    Wir haben dann bestenfalls einen kompetitiven Ansatz in einem festen Rahmen, der wiederum bestenfalls einem Survival of the Fittest entspricht, aber die im Artikel bemühte Evolution ist keineswegs mit einem SotF korrekt beschrieben; sie ist nicht [Ergänzung für Donnamara: erkennbar ;] zielgerichtet.

    HTH
    Dr. Webbaer

  18. #18 engywuck
    Dezember 8, 2011

    klar werden evolutionäre Algorithmen gerne auch dazu benutzt, auf ein bekanntes (gewolltes) Optimum hin zu optimieren. Das ist dann nicht unbedingt weit vom Eingreifen eines Schöpfers entfernt.

    Andererseits stellt man teilweise aber auch “nur” eine sehr allgemeine Frage, also z.B. “es soll eine Methode gefunden werden, um aus den vorhandenen Bausteinen (möglichst effizient) zwei verschiedene angelegte Signale unterscheiden zu können” (hier n einem Hardware-nahen Beispiel. Da ist nicht viel “designter” als real: es gibt eine “Umwelt”, die Unterscheidungsfähigkeit (real: z.B. giftig von ungiftig) “belohnt”, zudem sind als Nebenbedingung gute Effizienz erwünscht (real: wenn ein Individuum wenig verbraucht bleibt für Verwandte und Nachkommen mehr, Population wächst (oder sackt in Krisenzeiten nicht so rapide ab))

    Und teilweise sind die Ergebnisse doch recht “kreativ” (im Sinne von: man erhält nicht unbedingt das, was ein Mensch nach Kochrezept erwartet hätte). Ein Beispiel aus der computergenerierten Biologie: verschiedene “Tiere” wurden aus “Knochen” und “Muskeln” aufgebaut, “Futter” im Wasser verteilt und als Fitness-Funktion das möglichst zielgerichtete Schwimmen darauf genutzt. Ergebnis des ersten Durchlaufs: die “Qualle”, die am effizientesten war bewegte sich nicht wie real beobachtet durch Zusammenziehen des Körpers fort sondern durch um den Körper laufende Wellenbewegungen. Hoppla. Meines Wissens haben die beteiligten Forscher das nachgerechnet und haben bemerkt, dass diese Variante gar nicht so viel ineffizienter als die Zusammenzieh-Methode ist…

    Meine Vermutung: um evolutionäre Algorithmen ohne Randbedingungen (außer: Energiequelle vorhanden) eine biologische Evolution simulieren lassen zu können bräuchte man einen Aufwand, der nicht weit von “man nehme einen Gesteinskörper mit etwa 6000km Radius und Atmosphäre in etwa 150 Millionen km Entfernung von einem G2V-Stern und warte 4 Milliarden Jahre” entfernt ist. Dafür funktionieren sie für die begrenzten Probleme, die wir ihnen “vorsetzen”, aber erstaunlich gut.

  19. #19 Dr. Webbaer
    Dezember 8, 2011

    Es handelt sich eigentlich um kreationistische Algorithmen, was nicht unwitzig ist.

    Übrigens geht man auch in Teilen der Wirtschafts- und Politikwissenschaften davon aus, dass das beste, was ein Gesetzesgeber tun kann, das Setzen von Rahmenbedingungen ist, so dass die Schwarmintelligenz möglichst ungehindert, aber im Rahmen, Mittel und Wege finden kann. – ‘Das Leben findet immer einen Weg.’, so oder so ähnlich ein Zitat aus ‘Jurassic Park’

    Mit Ihrer Aufwandsschätzung könnten Sie hinkommen, das Schaffen eigener Welten mit ihren Regelmengen und dem Betrieb ist extra-aufwendig, stellte dann aber tatsächlich evolutionäre Algorithmen bereit – sofern die Regelmengen sinnvoll gewählt sind und der Betrieb problemlos verläuft…

  20. #20 Compuholic
    Dezember 11, 2011

    @Donnamara

    Es gibt bei der behaupteten Evolution nur den Zufall als Algorithmus! Es gibt keine auswertende Instanz, keine Intelligenz, welche beurteilt und den nächsten Schritt logisch anlegt, keine Instanz, welche ein Ziel vorgibt und das Erreichte damit vergleicht!

    Das ist nicht richtig. Der Zufall spielt lediglich bei der Erzeugung der Lösungen eine Rolle. Die Auswertung ist es nicht. Im Falle der evolutionären Algorithmen wird die Auswertung von einer Funktion übernommen, die die Güte einer Lösung berechnet. In der Biologie übernimmt die Natur die “Auswertung” und die ist nicht zufällig (bzw. ist der Zufall hier nur auf das Rauschen beschränkt).

    Davon abgesehen ist es in dieser Disziplin immer wieder der Gegenstand von Diskussionen ob jetzt die Selektion oder die Rekombination die dominierende Kraft hinter den Algorithmen sind. Für beide Seiten gibt es gute Argumente.

    Besonders interessant finde ich persönlich “Genetic Programming” wo die Lösung, die vom Algorithmus entwickelt wird. Das finde ich sehr interessant vor dem Hintergrund von maschinellem Lernen und künstlicher Intelligenz.

  21. #21 Compuholic
    Dezember 11, 2011

    Ups, da hab ich wohl was wichtiges gelöscht:

    Besonders interessant finde ich persönlich “Genetic Programming” wo die Lösung, die vom Algorithmus entwickelt wird.

    Soll heißen:

    Besonders interessant finde ich persönlich “Genetic Programming” wo die Lösung, die vom Algorithmus entwickelt wird selbst ein Programm ist.

  22. #22 Donnamara
    Dezember 11, 2011

    @Compuholic

    Hast du schon einmal diese Monster “Natur” gesehen, welches etwas “will” und Auswerungsalgorithmen fabriziert? Ich kenne dieses Monster bisher nicht. Höchstens aus der Religion, welche einen direkten Draht zu diesem Monster zu haben behauptet.

    “Das ist nicht richtig. Der Zufall spielt lediglich bei der Erzeugung der Lösungen eine Rolle. ”

    Das “lediglich” ist total daneben, da es bereits eine Wahrscheinlichkeit von 10^(-1000 000 000) behinhaltet! Wahrscheinlich sogar noch 100 Nullen mehr, mindestens. Die zufällige Erzeugung der Lösung ist eben das eigentliche Problem und nicht die zufällige Beurteilung der Lösung, wie du selbst sagst!

    Nach der Evolutionslogik bedarf es nämlich gar keiner Beurteilung mehr, ob die zufällige Kreation lebensfähig ist. Jedes Kind kommt auch ohne Beurteilung der dummen Mutter, welche nicht einmal eine Ahnung hat, wie “sie” das Kind fabriziert hat, zur Welt. Es gilt nur ein gefühlloses Gesetz: Überlebensfähig oder nicht. Entschieden wird hier von niemandem etwas. Auch nicht von der “Natur”.

  23. #23 Kretzer
    Dezember 22, 2011

    @Donnamara: Eine Natur, die etwas will, ist hierfür nicht notwendig. Es genügt, dass in zufälliger Variation entstandene Nachkommen dann mit höherer Wahrscheinlichkeit überleben, wenn sie an ihre Umgebung besser angepasst sind. Diese Überlebenswahrscheinlichkeit ist somit nicht(!) zufällig höher.

    Was du mit den 10^irgendwas-Wahrscheinlichkeiten sagen willst, ist unklar: Es behauptet doch keiner, dass in einem Evolutionsschritt irgendein Ziel erreicht wird, dessen Erreichen dir dann so unwahrscheinlich erscheint.

    Dein letzter Absatz ist dann komplett wirr: Das Überleben der Nachkommenschaft ist(!) doch die “Beurteilung”! Keine bewusste Instanz beurteilt hier irgendwas, die ist dafür nicht nötig.

    “Climbing mount improbable”: So wurde das von Richard Dawkins genannt; ich kann nur sein wunderbares Buch “The Greatest Show on Earth” wärmstens empfehlen, da sollten eigentlich keine Fragen offen bleiben.

  24. #24 monadingsda
    Dezember 23, 2011

    @Kretzer

    “@Donnamara: Eine Natur, die etwas will, ist hierfür nicht notwendig. Es genügt, dass in zufälliger Variation entstandene Nachkommen dann mit höherer Wahrscheinlichkeit überleben, wenn sie an ihre Umgebung besser angepasst sind.”

    Du bist vielleicht lustig. Dir ist anscheinend gar nicht bewußt, was das “es genügt” bedeutet! Dies bedeutet nämlich realiter eine totale Unmöglichkeit, welche eben gar nicht zufällig auftreten kann!

    Das “Überleben” dieses Textes kann nur dann erfolgen, wenn er generiert wurde und das ist eben zufällig vollkommen unmöglich.

    “Was du mit den 10^irgendwas-Wahrscheinlichkeiten sagen willst, ist unklar: Es behauptet doch keiner, dass in einem Evolutionsschritt irgendein Ziel erreicht wird, dessen Erreichen dir dann so unwahrscheinlich erscheint.”

    Der genetische Code ist nicht fehlertolerant! Es genügt bereits eine Abweichung vom “Soll” von weniger als 1 ppm, um das Leben zum Erlösschen zu bringen. Das bedeutet, der Weg von der einen Lebensform zu einer anderen muß praktisch in einem einzigen Sprung geschafft werden.

    Aus der bekannten tödlichen Dosis (5 Sv) gegenüber radioaktiver Bestrahlung kann abgeleitet werden, daß eine Fehlerrate von 1 ppm in der DNA praktisch zum Tod innerhalb von kurzer Zeit führt. Dies entspricht beim Menschen dann 3000 Basenpaarfehlern im Genom statistisch verteilt.

    Der Mensch soll rund 30000 Gene haben und die durchschnittliche Länge eines Gens entspricht dann 100000 Basenpaaren. Diese 3000 Basenpaarfehler auf 30000 Gene verteilt bedeutet dann, daß durchschnittlich bereits weniger als ein einziges falsches Basenpaar von 100000 in einem Gen tödlich ist!

    Um zu einer “besseren” Art zu gelangen, welche bestimmt nicht mit mit der Änderung nur eines einzigen Basenpaares in einem Gen zu erreichen ist, sondern eher mit der richtigen Änderung von vielleicht 1000 Basenpaaren, muß daher die gesamte Änderung auf einen Schlag erfolgen.

    Und das ist einfach unmöglich.