Genetische Alogrithmen
aus BORG Wiki, der freien Wissensdatenbank
Genetische Algorithmen (kurz.: GA) sind Algorithmen, die eine Lösung zu einem eigentlich nicht lösbaren Problem finden, indem sie "Lösungsvorschläge" solange verändern bzw. vertauschen und miteinander kombinieren, bis einer dieser Vorschläge den gestellten Anforderungen entspricht.
Genauer definiert sind diese Verfahren als heuristische(bed.:Aha-Erlebnis) Optimierungsverfahren und gehören zu den Evolutionären Algorithmen. Sie werden vor allem für Probleme eingesetzt, für die keine geschlossene Lösung vorliegt bzw. kein ideales Ergebnis vorliegt(ca. 10% vom Optimum entfernt)
Anwendungsbeispiele
- Finden des globalen Maximums/Minimums einer Funktion
- zur Planung von Bewegungsabläufen in Robotern
- Konstruktion von komplexen Bauteilen oder ganzen Systemen. Bsp.:Brückenbau. GA dienen hier der Optimierung von Lage, Form und Gewicht der einzelnen Brückenbestandteile.
- Erstellen von Fahr-, Stunden- und Raumplänen
- Lösung NP-Problematischer Aufgaben (NP-Problem = Menge aller Probleme die von nicht deterministischen Problemen in polynomialer Zeit gelöst werden können)
Vorgangsweise
- Initialisierung: Erzeugen einer ausreichend großen Menge von Knoten
- Evaluation: Für jeden einzelnen Knoten wird anhand einer Zielfunktion ein Wert bestimmt
- Selektion: Zufällige Auswahl von Knoten aus der vorhandenen Knotenmenge. Dabei werden Knoten mit besseren erreichbarkeit ausgewählt.
- Rekombination: die Daten verschiedener Knoten werden gemischt und aus den neuen eine neue Generation von Knoten erzeugt
- Mutation: Zufällige Veränderung der Datenteile der Knoten der neuen Generation
- Nach einem bestimmten Verfahren wird die Menge der neuen Knoten aus der Menge der alten Knoten und der Menge der mutierten Knoten der Gewinner der Menge der alten Knoten gebildet. Der Algorithmus wird anschließend ab Schritt 2 wiederholt, oder nach einem Abbruchkriterium beendet und der beste verfügbare Lösungskandidat als Knoten definiert.
