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 oder Korrektur 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] Michalewicz betont die Bedeutung von Beschränkungen in realen Anwendungen folgendermaßen: "In general, constraints are an integral part of the formulation of any problem".^[3]

Restriktionsverletzungen sind anwendungsbezogen und daher hängt es von der aktuellen Aufgabenstellung ab, ob und welche Art der Reparatur sinnvoll ist.^[4][5] Dabei ist zu beachten, dass Restriktionsverletzungen in der Regel auch durch eine entsprechend erweiterte Bewertung^[6][7] behandelt werden können und es von der Problemstellung abhängt, welche Maßnahmen möglich und welche die am besten geeignete ist.^[3] Wenn eine phänotypische Reparatur durchführbar ist, dann ist sie gegenüber den anderen Maßnahmen auch meist die effizienteste.^[3][8] Eine Übersicht über Reparaturmethoden, die als Techniken zur Behandlung von Restriktionen verwendet werden, findet sich in ^[9][10][11].

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 häufig durch die Bewertung behandelt.^[12] Dies kann z. B. durch Straffunktionen geschehen, die die Fitness absenken.^{[13][6][7][14]}

Reparaturbedarf besteht häufig auch bei kombinatorischen Aufgabenstellungen.^{[15][16][17][18]} Die Anwendung eines 1- oder n-Punkt-Crossoveroperators kann z. B. dazu führen, dass in einem der Kindgenome Gene fehlen, die im anderen doppelt vorhanden sind. In diesem Fall besteht eine geeignete genotypische Reparaturmaßnahme 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.^[17]

Es wurde beobachtet, dass die genotypische Reparatur vor allem bei kombinatorischen Problemen einerseits vorzeitige Konvergenz auf ein Suboptimum fördern, aber auch eine erfolgreiche Suche erheblich beschleunigen kann.^[16][9] Untersuchungen zu verschiedenen Aufgabenstellungen haben gezeigt, dass dies anwendungsabhängig ist.^[16][19] Als wirksame Maßnahme zur Vermeidung vorzeitiger Konvergenz gilt generell die Verwendung strukturierter Populationen anstelle der üblichen panmiktischen.^[20][21][22]

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:^[23]

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. Das gleiche gilt für die alternative Verschiebung von Gen A vor Gen B.

Die genotypische Reparatur hat hier den Nachteil, dass sie einen sinnvollen Umbau der Genreihenfolge im Chromosom verhindern wird, wenn dieser mehrere Zwischenschritte (Mutationen) erfordert, welche zumindest teilweise Restriktionen verletzen.^[23]