Die Informatik der Evolution: eine Einführung in genetische Algorithmen

Foto von Hal Gatewood auf Unsplash

Als Informatiker mit Interesse an Evolution und biologischen Prozessen, dem Thema genetischer Algorithmen und allgemeiner gesagt, ist evolutionäre Berechnung für mich das, was ein Süßwarenladen für einen 5-Jährigen bedeutet: Himmel. Die bloße Möglichkeit, zwei meiner Interessen auf solch nahtlose Weise zusammenzuführen, war äußerst aufregend, und es wäre falsch, dieses Wissen und diese Aufregung für mich zu behalten.

Um einige meiner bisherigen Erkenntnisse zu testen und meine Erkenntnisse mit dem Rest der Welt zu teilen, habe ich beschlossen, eine Reihe von Artikeln zu diesem Thema zusammenzustellen.

In diesem Beitrag werde ich eine kurze Einführung in genetische Algorithmen geben und erklären, wie sie dieselben natürlichen Prozesse imitieren, die seit Milliarden von Jahren auf der Erde stattfinden.

Leben auf der Erde

In den letzten 3,5 Milliarden Jahren haben Mutter Natur, Vaterzeit, Evolution und natürliche Selektion zusammengearbeitet, um alle speziellen Lebensformen hervorzubringen, die wir heute auf der Erde sehen: wie die fleischfressende Venusfliegenfalle; der im Ozean lebende Atlantikfliegende Fisch; echolocation-using Fledermäuse; langhalsige Giraffen; superschnelle Geparden, tanzende Honigbienen; Und natürlich, mit freundlichen Grüßen, der smarte Homo Sapiens.

Die Venusfliegenfalle ist eine fleischfressende Pflanze, die sich hauptsächlich von Insekten und Spinnentieren ernährt.Einige Fledermäuse nutzen die Echolokalisierung, um zu navigieren und Beute zu jagen, und entgegen der landläufigen Meinung sind Fledermäuse tatsächlich nicht blind. Eine Fledermausart namens The Flying Foxes hat tatsächlich ein besseres Sehvermögen als der Mensch.Fliegende Fische können nicht so fliegen wie Vögel, jedoch können diese Fische kraftvolle, selbstfahrende Sprünge aus dem Wasser machen, bei denen sie mit ihren langen, flügelartigen Flossen beträchtliche Entfernungen über die Wasseroberfläche gleiten können.

Unnötig zu erwähnen, dass das Leben auf der Erde eines der erfolgreichsten Experimente ist, die jemals in unserem Universum durchgeführt wurden. Anhand der beeindruckenden Ergebnisse dieses Experiments ist klar, dass die Evolution eindeutig auf etwas abzielt.

Vor kurzem haben wir Menschen - nur eines der vielen Endprodukte dieses Prozesses - erkannt, dass wir diesen genialen Ansatz zur fortschrittlichen Problemlösung auch nutzen können, und seit den 1950er Jahren haben es Informatiker, Genetiker, Mathematiker und Biologen versucht ahmen diese biologischen Prozesse durch die Implementierung von Computersimulationen nach. Mit dem Ziel, auf effiziente Weise optimale Lösungen für schwierige, nicht triviale Probleme zu finden.

Der blinde Uhrmacher

Eines der ersten Bücher, auf die ich gestoßen bin und die mein Interesse auf dem Gebiet der Evolutionsbiologie geweckt haben, war The Blind Watchmaker von Richard Dawkins. In diesem Buch erklärt Richard Dawkins, wie komplexe Mechanismen wie die Echolokalisierung (ein Prozess, mit dem Fledermäuse navigieren, jagen und suchen, auch als Biosonar bezeichnet), komplexe Strukturen wie Spinnennetze (mit denen Spinnen ihre Beute anziehen und fangen) und Komplexe Instrumente wie das menschliche Auge (diese beiden kugelförmigen Objekte, mit denen Sie diesen Artikel gerade lesen) sind einfach das Ergebnis von Tausenden, wenn nicht Millionen von Jahren Evolution und Anpassung.

Die fortschreitende Entwicklung des menschlichen Auges. Was als einfache lichtempfindliche Zellen begann, entwickelte sich zu einem komplexen Instrument, das wir oft als selbstverständlich betrachten. Die ersten Tiere mit etwas, das einem Auge ähnelt, lebten vor ungefähr 550 Millionen Jahren. Und nach Berechnungen eines Wissenschaftlers würde es nur 364.000 Jahre dauern, bis sich ein kameraähnliches Auge aus einem lichtempfindlichen Fleck entwickelt.

Auch wenn diese Wunder der Natur den Eindruck erwecken, dass sie von Anfang an (dh von einem bewussten „Macher“) zu einem bestimmten Zweck erbaut wurden, sind sie eigentlich nur das Ergebnis von Iterationen über Iterationen von Versuch und Irrtum, die mit Ewigkeit gebündelt sind -ändernden Selektionsdruck (dh eine Änderung des Klimas, des Lebensraums oder des Verhaltens und der Fähigkeiten von Raubtieren oder Beutetieren). Während sie also wie das Ergebnis eines präzisen, vorausschauenden Engineerings aussehen und sich verhalten, sind sie tatsächlich das Ergebnis eines völlig blinden Prozesses, ein Prozess, der nicht im Voraus weiß, wie die perfekte „Lösung“ aussehen würde.

Was sind genetische Algorithmen und warum brauchen wir sie?

Genetische Algorithmen sind eine Technik, mit der qualitativ hochwertige Lösungen für Optimierungs- und Suchprobleme generiert werden, die auf grundlegenden biologischen Prozessen basieren. Diese Algorithmen werden in Situationen verwendet, in denen das mögliche Lösungsspektrum sehr groß ist und die grundlegenderen Lösungsansätze wie erschöpfende Suche / Brute Force zu viel Zeit und Mühe kosten würden.

Das Problem des Handlungsreisenden stellt die folgende Frage: „Bei einer gegebenen Liste von Städten und den Entfernungen zwischen jedem Städtepaar ist die kürzestmögliche Route, die jede Stadt besucht und in die Ausgangsstadt zurückkehrt, die kürzeste Route.“ Dies ist ein NP-schwieriges Problem in kombinatorische Optimierung.

Wir können genetische Algorithmen verwenden, um qualitativ hochwertige Lösungen für dieses Problem zu wesentlich geringeren Kosten bereitzustellen als die primitiveren Problemlösungstechniken wie die erschöpfende Suche, bei der Sie alle möglichen Lösungen durchgehen müssen.

Wie funktionieren genetische Algorithmen?

Ein Algorithmus durchläuft eine Reihe von Schritten, bis er einen vordefinierten Endpunkt erreicht. Jede Iteration des genetischen Algorithmus führt zu einer neuen Generation möglicher Lösungen, die theoretisch eine Verbesserung gegenüber der vorherigen Generation darstellen sollten.

Die Schritte sind wie folgt:

1. Erstellen Sie eine Grundgesamtheit von N möglichen Lösungen (die Ursuppe)

Der erste Schritt des Algorithmus besteht darin, eine anfängliche Gruppe von Lösungen zu erstellen, die als Basislösungen in Generation 0 dienen. Jede Lösung in dieser anfänglichen Population enthält einen Satz von Chromosomen, die aus einer Sammlung von Genen bestehen, in denen jedes Gen vorhanden ist ist einer der möglichen Variablen des Problems zugeordnet. Es ist wichtig, dass die Lösungen in der Anfangspopulation mit zufällig zugewiesenen Genen erstellt werden, um einen hohen Grad an genetischer Variation zu erzielen.

2. Ordnen Sie die Lösungen der Bevölkerung nach Fitness (Überleben der Stärkeren, Teil 1).

In diesem Schritt muss der Algorithmus in der Lage sein, zu bestimmen, was eine Lösung besser passt als eine andere. Dies wird durch die Fitnessfunktion bestimmt. Das Ziel der Fitnessfunktion ist es, die genetische Lebensfähigkeit der Lösungen in der Bevölkerung zu bewerten, wobei diejenigen mit den lebensfähigsten, günstigsten und überlegenen genetischen Merkmalen ganz oben auf der Liste stehen.

In dem Problem des Handlungsreisenden könnte die Fitnessfunktion eine Berechnung der von der Lösung zurückgelegten Gesamtstrecke sein. Wo eine kürzere Distanz einer höheren Fitness gleichkommt.

3. Finde die schwächeren Lösungen (Überleben der Stärkeren, Teil 2)

In diesem Schritt entfernt der Algorithmus die weniger passenden Lösungen aus der Grundgesamtheit. Das Stärkste bedeutet nicht unbedingt das Stärkste, das Schnellste oder das Stärkste, wie der Mensch normalerweise annimmt. Das Überleben des Stärkeren bedeutet einfach, dass ein Organismus umso länger lebt, je besser er in seiner Umwelt überlebt, um seine Gene zu reproduzieren und auf die nächste Generation auszubreiten.

Die Schritte 3 und 4 werden zusammen als Auswahl bezeichnet.

4. Züchte die stärkeren Lösungen (Überleben der Stärkeren, Teil 3)

Die verbleibenden Lösungen werden dann miteinander gepaart, um die Nachkommen zu paaren und zu vermehren. Während dieses Prozesses trägt jeder Elternteil in seiner grundlegendsten Form einen Prozentsatz seiner Gene (in der Natur ist es eine 50/50-Aufteilung) zu jedem seiner Nachkommen bei, wobei P1 (G)% + P2 (G)% = 100 %. Der Prozess der Bestimmung, welche Gene der Eltern von den Nachkommen geerbt werden, wird als Crossover bezeichnet.

5. Mutieren Sie die Gene der Nachkommen (Mutation)

Die Nachkommen enthalten einen Prozentsatz der Gene der Mutter und einen Prozentsatz der Gene der Väter. Gelegentlich kommt es zu einer Mutation eines oder mehrerer dieser Gene. Eine Mutation ist im Wesentlichen eine genetische Abnormalität, ein Kopierfehler, der dazu führt, dass sich eines oder mehrere der Gene der Nachkommen von den Genen unterscheiden, die sie von ihren Eltern geerbt haben. In genetischen Algorithmen erhöht in einigen Fällen eine Mutation die Fitness der Nachkommen, in anderen Fällen verringert sie sie.

Es ist wichtig zu beachten, dass nicht bei jedem Nachwuchs eine Mutation vorhanden sein muss. Die erforderliche Mutationsfrequenz kann auch ein Parameter des Algorithmus sein.

In genetischen Algorithmen werden Selektion, Crossover und Mutation als genetische Operatoren bezeichnet.

6. Kündigung

Die Schritte 2 bis 5 werden bis zu einem vordefinierten Endpunkt wiederholt. Dieser Endpunkt kann einer der folgenden sein:

  1. Maximale Zeit- / Ressourcenzuweisung erreicht.
  2. Eine feste Anzahl von Generationen ist vergangen.
  3. Die Fitness der vorherrschenden Lösung kann von zukünftigen Generationen nicht übertroffen werden.

Lösungskonvergenz

1. Globales Optimum

Im Idealfall hat die am besten geeignete Lösung den höchstmöglichen Fitnesswert, d. H. Sie ist die optimale Lösung, sodass der Algorithmus nicht fortgesetzt und keine weiteren Generationen erstellt werden müssen.

2. Lokales Optimum

Wenn die Parameter des Algorithmus nicht angemessen sind, tendiert die Population in einigen Fällen möglicherweise zu einer vorzeitigen Konvergenz bei einer weniger optimalen Lösung, bei der es sich nicht um das von uns angestrebte globale Optimum, sondern um ein lokales handelt. Hier kann es sinnlos sein, den Algorithmus fortzusetzen und weitere Generationen zu erzeugen.

Globales Optimum vs. lokales Optimum

Was würde passieren, wenn es keine Mutationen gäbe?

Mutationen können auf den ersten Blick als unnötiger, irrelevanter Teil des Prozesses erscheinen. Ohne diesen grundlegenden Aspekt der Zufälligkeit würde sich die Evolution durch natürliche Selektion vollständig auf die genetische Vielfalt beschränken, die von der ursprünglichen Population vorgegeben wird, und danach würden keine neuen Merkmale in die Population eingeführt. Dies würde die Fähigkeiten der Natur zur Problemlösung erheblich beeinträchtigen, und das Leben auf der Erde wäre nicht in der Lage, sich zumindest nicht physisch an seine Umgebung anzupassen.

Wenn dies in unserem genetischen Algorithmus der Fall wäre, könnten die zukünftigen Generationen der Bevölkerung irgendwann in unserer Simulation keinen Teil des Lösungsraums erkunden, den ihre Vorgänger nicht erkundet haben. Eine Simulation ohne Mutationen würde die genetische Variation innerhalb der Population stark einschränken und in den meisten Fällen - abhängig von der ursprünglichen Population - verhindern, dass wir jemals ein globales Optimum erreichen.

Ohne Mutationen hätten wir keine Mutanten und ohne Mutanten hätten wir kein X-Men-Franchise.

Was würde passieren, wenn die Bevölkerungszahl nicht groß genug wäre?

Ich war kürzlich im Jukani Wildlife Sanctuary in Plettenberg, wo ich das Privileg hatte, einen weißen Tiger zu treffen. Er war ein wahrhaft majestätisches Tier. Er war groß, er sah wild aus und er war auch zu 80% blind und wurde mit den Jahren immer schlimmer.

Warum war er blind? Weil er ein Produkt von Generationen der Inzucht ist. Diese weißen Tiger werden nur produziert, wenn zwei Tiger, die ein rezessives Gen tragen, das die Fellfarbe kontrolliert, zusammen gezüchtet werden. Um den Fortbestand dieser Tiger in Gefangenschaft zu gewährleisten, haben die Menschen diese Tiger in einer sehr begrenzten Population gezüchtet, um sie entweder in Zirkussen vorzuführen, in Zoos vorzuführen oder als Haustiere zu halten.

Eine der negativen Auswirkungen der Inzucht ist jedoch, dass Sie die genetische Variation innerhalb der Art stark einschränken, was die Wahrscheinlichkeit, dass schädliche rezessive Merkmale auf die Nachkommen übertragen werden, zunehmend erhöht.

Der weiße Tiger, den ich im April 2019 im Jukani Wildlife Sanctuary getroffen habe. Er sieht majestätisch aus, leidet aber.

Selbst in freier Wildbahn kann Inzucht immer noch ein massives Problem sein. In den letzten Jahrzehnten wurde die Nashornpopulation im südlichen Afrika durch Wilderei erheblich beeinträchtigt. Wenn die Populationsgröße niedrig genug ist, wäre es äußerst schwierig, die genetische Vielfalt dieser bedrohten Nashornspezies zu erhalten. Selbst wenn Wilderei sie nicht vollständig zum Aussterben bringt, könnte Inzucht

Foto von redcharlie auf Unsplash.

Natürlich sind Menschen keine Unbekannten für Inzucht. Ein berühmtes Ergebnis kontinuierlicher Inzucht innerhalb unserer eigenen Spezies ist Karl II. Von Spanien.

„Der habsburgische König Carlos II. Von Spanien war traurigerweise mit einem enormen unförmigen Kopf degeneriert. Sein habsburgischer Kiefer ragte so weit heraus, dass sich seine beiden Zahnreihen nicht treffen konnten; er konnte nicht kauen. Seine Zunge war so groß, dass er kaum sprechen konnte. Sein Intellekt war in ähnlicher Weise behindert. “

Der habsburgische König Karl II. Von Spanien. Sein Vater war der Onkel seiner Mutter und machte Charles zu ihrem Sohn, dem Urneffen und dem Ersten Cousin.

"Inzucht" in unserem genetischen Algorithmus bedeutet im Wesentlichen die Züchtung von Lösungen mit einem sehr ähnlichen genetischen Aufbau, die in diesem Fall glücklicherweise keine Nachkommen mit einer Veranlagung für physische Anomalien zur Folge hätten. Wenn die Population jedoch sehr klein ist und alle Lösungen ein sehr ähnliches Erbgut aufweisen, wird die Fitness der zukünftigen Generationen der Bevölkerung stark eingeschränkt. Das bedeutet, dass die Konvergenz zu einer global optimalen Lösung viel länger dauern kann, wenn wir überhaupt dort ankommen.

Inzucht ist nicht immer eine schlechte Sache, es hängt nur davon ab, in welcher Phase der Simulation Sie sich befinden. In sehr fortgeschrittenen Phasen der Simulation ist es offensichtlich sehr schwer, Inzucht zu vermeiden, da sich die Population einem globalen / lokalen Optimum nähert In einigen Fällen werden sich viele der vorherrschenden Lösungen sehr ähnlich sein und daher viele der gleichen genetischen Merkmale aufweisen.

Einpacken

Okay, das sollte die Grundlagen abdecken. Wenn Sie Fragen, Wünsche oder genetische Mutationen haben, hinterlassen Sie bitte unten einen Kommentar.

Im nächsten Beitrag werden wir uns mit Code befassen, während wir uns ansehen, wie sich jeder der oben beschriebenen genetischen Operatoren in der Welt der Programmierung verhält. Ich habe die Ruby-Programmiersprache für die Softwaresimulation verwendet, an der ich gearbeitet habe, und darin zeige ich, wie ein genetischer Algorithmus in nur wenigen Generationen ein vordefiniertes Wort oder eine vordefinierte Phrase aus einer anfänglichen Sammlung von vollständigem und vollständigem Kauderwelsch erzeugen kann. Der gesamte Code wird auf Github gehostet.