Genotypische und phänotypische Reparatur
Genotypische und phänotypische Reparatur sind Begriffe aus der Algorithmentheorie, einem Teilgebiet der Informatik, genauer aus der Theorie der evolutionären Algorithmen. Unter genotypischer Reparatur versteht man die Beseitigung von unzulässigen Einträgen im Chromosom, welche Restriktionen verletzen. Bei der phänotypischen Reparatur erfolgen die Korrekturen nur bei der Genotyp-Phänotyp-Abbildung und das Genom bleibt unverändert.[1]
Restriktionsverletzungen sind anwendungsbezogen und daher hängt es von der aktuellen Aufgabenstellung ab, ob und welche Art der Reparatur sinnvoll ist. Dabei ist zu beachten, dass Restriktionsverletzungen in der Regel auch durch eine entsprechend erweiterte Bewertung behandelt werden können und es von der Problemstellung abhängt, welche Maßnahmen möglich und welche die am besten geeignete ist. Wenn eine phänotypische Reparatur durchführbar ist, dann ist sie gegenüber den anderen Maßnahmen auch meist die effizienteste.
Eine Verletzung von Wertebereichsgrenzen der Gene sollte durch die Formulierung des Genoms möglichst weitgehend ausgeschlossen werden. Soweit dies nicht möglich ist oder wenn es um Beschränkungen innerhalb des durch das Genom definierten Suchraums geht, werden deren Verletzungen in der Regel durch die Bewertung behandelt.[2] Dies kann z. B. durch Straffunktionen geschehen, die die Fitness absenken.[1]
Reparaturbedarf besteht häufig auch bei kombinatorischen Aufgabenstellungen. Die Anwendung eines 1- oder n-Punktcrossoveroperators kann z. B. dazu führen, dass in einem Kindgenom Gene fehlen, die im anderen doppelt vorhanden sind. In diesem Fall besteht ein geeignete Reparaturmaßname darin, die überzähligen Gene positionstreu in das jeweils andere Genom zu verschieben. Die Verwendung der genannten Operatoren bei kombinatorischen Aufgaben hat sich auch im Zusammenhang mit speziell für Permutationen entwickelte Crossoverarten zumindest bei bestimmten Aufgabenstellungen als sinnvoll erwiesen.[3]
Bei vielen Schedulingaufgaben spielen Reihenfolgerestriktionen eine Rolle, etwa wenn es um die Planung von Workflows geht. Wenn beispielsweise festgelegt ist, dass Arbeitsschritt A vor Schritt B kommen muss und das Gen von Schritt B vor dem Gen von A im Chromosom steht, so liegt eine unzulässige Genreihenfolge vor. Denn die Schedulingoperation von Schritt B benötigt für eine korrekte Einplanung das geplante Ende von Schritt A und dieser ist aber zum aktuellen Zeitpunkt der Abarbeitung des Chromosoms noch gar nicht verplant. Das Problem lässt sich auf zwei Arten lösen:
- Die Schedulingoperation von Schritt B wird solange zurückgestellt, bis das Gen von Schritt A abgearbeitet ist. Das Genom bleibt dabei unverändert und die Reparatur beeinflusst lediglich das Genotyp-Phänotyp-Mapping. Da nur der Phänotyp verändert wird, spricht man von phänotypischer Reparatur.
- Wenn hingegen das Gen von Schritt B hinter das Gen von Schritt A verschoben wird, handelt es sich um eine genotypische Reparatur.
Die genotypische Reparatur hat den Nachteil, dass sie einen sinnvollen Umbau der Genreihenfolge im Chromosom verhindern wird, wenn dieser mehrere Zwischenschritte (Mutationen) erfordert, welche zumindest teilweise Restriktionen verletzen.
Einzelnachweise
- ↑ a b Agoston E. Eiben, Jim E. Smith: Introduction to Evolutionary Computing. 2. Auflage. Natural Computing Series. Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, doi:10.1007/978-3-662-44874-8 (englisch).
- ↑ Wilfried Jakob: Applying Evolutionary Algorithms Successfully: A Guide Gained from Real-world Applications. KIT Scientific Working Papers, Nr. 170. KIT Scientific Publishing, Karlsruhe 2021, doi:10.5445/IR/1000135763, arxiv:2107.11300 (englisch).
- ↑ Wilfried Jakob, Alexander Quinte, Karl-Uwe Stucky, Wolfgang Süß: Fast Multi-objective Scheduling of Jobs to Constrained Resources Using a Hybrid Evolutionary Algorithm. In: Günter Rudolph (Hrsg.): Conf. Proc. of Parallel Problem Solving from Nature (PPSN X). LNCS, Nr. 5199. Springer, Berlin, Heidelberg 2008, ISBN 978-3-540-87699-1, doi:10.1007/978-3-540-87700-4 (englisch).
