Genetische Algorithmen: Seit Anbeginn der Zeit haben Lebewesen ihre Fähigkeit bewiesen, sich an ihre sich ständig verändernden Lebensumstände anzupassen und sich von Generation zu Generation zu verbessern.
Diese Fähigkeit, zu immer optimaleren Lösungen zu konvergieren, inspiriert gerade die Mathematik. Und insbesondere der genetische Algorithmus, der die Prozesse der natürlichen Auslese zerschneidet, um komplexe Probleme zu lösen.
Die Schritte der genetischen Algorithmen verstehen
Der genetische Algorithmus, der in den 1960er Jahren auf Initiative des Forschers John Holland entstand, wendet die verschiedenen Stufen der natürlichen Evolution auf die Lösung komplexer Probleme an.
Die Erstellung der Anfangsbevölkerung
Der erste Schritt des genetischen Algorithmus besteht darin, eine Anfangspopulation zu schaffen, die sich weiterentwickelt. Diese Population besteht aus potenziellen Lösungen für ein bestimmtes Problem. Sie werden als Individuen oder Chromosomen bezeichnet und können zufällig erzeugt werden. Dadurch kann mehr Vielfalt geschaffen werden.
In diesem Stadium geht es nicht darum, DIE richtige Lösung zu finden. Vielmehr geht es darum, eine ausreichende Anzahl von Lösungen zu finden, die das Problem lösen können. Übrigens: Je vielfältiger die Ausgangspopulation ist, desto besser können die bestmöglichen Lösungen entworfen werden.
Wenn du z. B. den Weg von A nach B suchst, geht es nicht darum, den kürzesten Weg zu finden, sondern alle Wege, die zum Ziel führen. Es spielt keine Rolle, ob du dafür 10 Minuten oder 3 Stunden brauchst, ob du zu Fuß oder mit dem Auto unterwegs bist, ob du an einer Bäckerei oder einer Autowerkstatt vorbeikommst.
Gut zu wissen: Die Bevölkerungsgröße muss nicht übermäßig groß sein. Sie muss nur groß genug sein. Im Durchschnitt führen bereits 100 oder 150 Personen zu einem zufriedenstellenden Ergebnis, wenn alle Schritte des genetischen Algorithmus durchlaufen wurden.
Die Bewertung von Einzelpersonen
Nach der Erstellung der Population ist es an der Zeit, jede Person nach ihrer Fähigkeit, das Problem zu lösen, zu bewerten. Der Datenwissenschaftler kann die Personen nach eigenem Ermessen bewerten. Es ist jedoch besser, ihnen eine Note zu geben, um diejenigen zu identifizieren, die aus der Masse herausstechen. Sie sind es, die zur Verbesserung unserer Bevölkerung beitragen.
Beachte, dass diese Phase des genetischen Algorithmus kompliziert sein kann, da es manchmal schwierig ist, zwei Individuen miteinander zu vergleichen. Dies gilt insbesondere für multikriterielle Probleme, bei denen die optimale Lösung von mehreren Parametern abhängt, ohne dass einer besser als der andere ist.
Die Auswahl
Nachdem die Individuen bewertet wurden, müssen die besten ausgewählt werden. In der Natur entspricht dies dem Prozess der natürlichen Auslese (oder dem Gesetz des Stärkeren), bei dem die Arten, die am besten an ihre Umwelt angepasst sind, überleben, während die anderen aussterben.
In der Mathematik kann man verschiedene Methoden anwenden, um die Besten auszuwählen. Hier sind die häufigsten:
- Roulette: Wie bei der Lotterie geht es darum, das Rad zu drehen, um die Individuen auszuwählen. Aber Vorsicht, denn jedes Individuum wird je nach seiner Qualität einem Sektor auf einem Rad zugeordnet. Je mehr „Wert“ die Person hat, desto wichtiger ist ihr Sektor. Wenn du also am Rad drehst, steigt die Wahrscheinlichkeit, dass du auf Individuen mit höherer Qualität triffst.
- Turnierauswahl: Hierbei handelt es sich um ein zufälliges Treffen zwischen verschiedenen Individuen der Population. Der Gewinner ist derjenige mit der höchsten Qualität. Natürlich ist es möglich, mehrere Sieger auszuwählen.
- Elitismus: Hierbei werden einfach die besten Individuen aufgrund ihrer Qualität ausgewählt. Diese Methode ist zwar schneller zu implementieren, kann aber nicht die gesamte mögliche Vielfalt berücksichtigen.
Die Kreuzungen
Wenn natürliche Arten in der Lage waren, sich im Laufe der Zeit zu verbessern, so ist dies auf die Anreicherung der Populationen im Laufe der Zeit zurückzuführen. Der genetische Algorithmus greift das gleiche Prinzip auf. Um die Population weiterzuentwickeln, kombinieren die Datenwissenschaftler Paare ausgewählter Individuen und schaffen so neue Individuen: das sind die Nachkommen. Für diese Kreuzung wählt der Data Scientist bestimmte Merkmale jedes Elternindividuums aus.
Es ist möglich, Zufallskreuzungen durchzuführen und sogar ein und dasselbe Individuum zu verwenden, um mehrere Nachkommen zu erzeugen. Die nicht verwendeten Merkmale ermöglichen es, weitere Nachkommen zu erzeugen.
Die Mutationen
Anstelle von Kreuzungen sieht der genetische Algorithmus auch Mutationen vor. Zufällige Mutationen sind auch sehr effektiv, um eine maximale Vielfalt zu erreichen und innovative Kombinationen zu ermöglichen.
Gut zu wissen: Es handelt sich um leichte Veränderungen. Das heißt, dass nur ein Merkmal verändert wird, um das ursprüngliche Individuum nicht völlig zu verfälschen. Aber auch manchmal können diese kleinen Veränderungen zu einer völlig anderen Bewertung führen.
Die neuen Generationen
Um die besten Lösungen für das Problem zu finden, entstehen neue Generationen mit Nachkommen, veränderten und unveränderten Individuen. Jeder muss sich an der Verbesserung der Population beteiligen.
Deshalb wiederholt der Datenwissenschaftler den Prozess des genetischen Algorithmus über mehrere Generationen, um die Lösung des Problems immer weiter zu verbessern. Nach und nach wird die Population immer weiter reduziert, bis die optimale Lösung gefunden ist.
Gut zu wissen: Es ist wichtig, einige ursprüngliche (unveränderte) Individuen zu behalten, denn es gibt keine Garantie dafür, dass die neuen Populationen zwangsläufig besser sind.
Den genetischen Algorithmus in der Datenwissenschaft einsetzen
Der genetische Algorithmus wird oft für Optimierungsprobleme verwendet, bei denen es viele mögliche Lösungen gibt. Allerdings erfordert er oft viele Berechnungen, um ein zufriedenstellendes Ergebnis zu erzielen. Aus diesem Grund wenden sich viele Datenwissenschaftler anderen Optimierungsalgorithmen zu, die eine kürzere Rechenzeit haben.
Wie auch immer, es ist wichtig, die verschiedenen Modelle des maschinellen Lernens zu kennen, um aussagekräftige Analysen durchführen zu können. Deshalb ist es so wichtig, sich mit DataScientest weiterzubilden.
