Wikipedia

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][2]

Restriktionsverletzungen sind anwendungsbezogen und daher hängt es von der aktuellen Aufgabenstellung ab, ob und welche Art der Reparatur sinnvoll ist.[3][4] 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.[5] Wenn eine phänotypische Reparatur durchführbar ist, dann ist sie gegenüber den anderen Maßnahmen auch meist die effizienteste.[5][6]

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.[7] Dies kann z. B. durch Straffunktionen geschehen, die die Fitness absenken.[8][9][10]

Reparaturbedarf besteht häufig auch bei kombinatorischen Aufgabenstellungen.[11][12] Die Anwendung eines 1- oder n-Punkt-Crossoveroperators 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 in Kombination mit speziell für Permutationen entwickelte Crossoverarten zumindest bei bestimmten Aufgabenstellungen als sinnvoll erwiesen.[13]

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:[14]

  1. 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.
  2. 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.[14]

Einzelnachweise

Bearbeiten
  1. ↑ Karsten Weicker: Evolutionäre Algorithmen. 3. Auflage. Springer Fachmedien, Wiesbaden 2015, ISBN 978-3-658-09957-2, Optimieren mit Randbedingungen, S. 189–200, doi:10.1007/978-3-658-09958-9 (springer.com [abgerufen am 28. Februar 2023]).
  2. ↑ A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). 2. Auflage. Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, Repair Functions, S. 208–209, doi:10.1007/978-3-662-44874-8 (englisch, springer.com [abgerufen am 28. Februar 2023]).
  3. ↑ Zbigniew Michalewicz: Constraint-handling techniques. In: Thomas Bäck, David Fogel, Zbigniew Michalewicz (Hrsg.): Evolutionary Computation 2: Advanced Algorithms and Operators. CRC Press, Bristol 2000, ISBN 978-0-7503-0665-2, S. 38–86, doi:10.1201/9781420034349 (taylorfrancis.com [abgerufen am 2. März 2023]).
  4. ↑ Volker Nissen: Einführung in Evolutionäre Algorithmen. Vieweg+Teubner Verlag, Wiesbaden 1997, ISBN 978-3-528-05499-1, Berücksichtigung von Nebenbedingungen, S. 81–85, doi:10.1007/978-3-322-93861-9 (springer.com [abgerufen am 28. Februar 2023]).
  5. ↑ a b Zbigniew Michalewicz: Introduction to constraint-handling techniques. In: Thomas Bäck, David Fogel, Zbigniew Michalewicz (Hrsg.): Evolutionary Computation 2: Advanced Algorithms and Operators. CRC Press, Bristol 2000, ISBN 978-0-7503-0665-2, S. 38–40, doi:10.1201/9781420034349 (taylorfrancis.com [abgerufen am 2. März 2023]).
  6. ↑ A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). 2. Auflage. Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, Constraint Handling, S. 203–213, doi:10.1007/978-3-662-44874-8 (englisch, springer.com [abgerufen am 28. Februar 2023]).
  7. ↑ Wilfried Jakob: Applying Evolutionary Algorithms Successfully: A Guide Gained from Real-world Applications. KIT Scientific Working Papers, Nr. 170. KIT Scientific Publishing, Karlsruhe 2021, Which Restrictions are There?, S. 6–7, doi:10.5445/IR/1000135763, arxiv:2107.11300 (englisch).
  8. ↑ Karsten Weicker: Evolutionäre Algorithmen. 3. Auflage. Springer Fachmedien, Wiesbaden 2015, ISBN 978-3-658-09957-2, Straffunktionen, S. 197–200, doi:10.1007/978-3-658-09958-9 (springer.com [abgerufen am 28. Februar 2023]).
  9. ↑ Alice E. Smith, David W. Coit: Penalty functions. In: Thomas Bäck, David Fogel, Zbigniew Michalewicz (Hrsg.): Evolutionary Computation 2: Advanced Algorithms and Operators. CRC Press, Bristol 2000, ISBN 978-0-7503-0665-2, S. 41–48, doi:10.1201/9781420034349 (taylorfrancis.com [abgerufen am 2. März 2023]).
  10. ↑ 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, Penalty Functions, S. 206–208, doi:10.1007/978-3-662-44874-8 (englisch).
  11. ↑ Volker Nissen: Einführung in Evolutionäre Algorithmen. Vieweg+Teubner Verlag, Wiesbaden 1997, ISBN 978-3-528-05499-1, Intelligente Decodierung, S. 83–84, doi:10.1007/978-3-322-93861-9 (springer.com [abgerufen am 28. Februar 2023]).
  12. ↑ Zbigniew Michalewicz: Repair algorithms. In: Thomas Bäck, David Fogel, Zbigniew Michalewicz (Hrsg.): Evolutionary Computation 2: Advanced Algorithms and Operators. CRC Press, Bristol 2000, ISBN 978-0-7503-0665-2, S. 56–61, doi:10.1201/9781420034349 (taylorfrancis.com [abgerufen am 2. März 2023]).
  13. ↑ 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).
  14. ↑ a b Wilfried Jakob, Sylvia Strack, Alexander Quinte, Günther Bengel, Karl-Uwe Stucky, Wolfgang Süß: Fast Rescheduling of Multiple Workflows to Constrained Heterogeneous Resources Using Multi-Criteria Memetic Computing. In: Algorithms. Band 6, Nr. 2, Juni 2013, ISSN 1999-4893, 4.2.3 Genotypic and Phenotypic Repair, S. 245–277, doi:10.3390/a6020245 (englisch, mdpi.com [abgerufen am 28. Februar 2023]).
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Genotypische_und_phänotypische_Reparatur&oldid=240884495“