Genetische Repräsentation

Als genetische Repräsentation (auch Problemrepräsentation) wird die Art und Weise bezeichnet, wie ein Optimierungsproblem codiert wird, sodass es mit einem evolutionären Algorithmus (EA) gelöst werden kann. EA suchen Lösungen für Optimierungsprobleme mit Methoden der natürlichen Evolution. Der Begriff der genetischen Repräsentation umfasst dabei sowohl die konkreten Datenstrukturen und Datentypen, mit denen das genetische Material der Lösungskandidaten in Form eines Genoms realisiert wird, als auch die Beziehungen zwischen Suchraum und Problemraum. Im einfachsten Fall entspricht der Suchraum dem Problemraum (direkte Repräsentation). Die Wahl der Problemrepräsentation ist gebunden an die Wahl der genetischen Operatoren, beide wirken sich entscheidend auf die Effizienz der Optimierung aus. Die Unterschiede in den genetischen Repräsentationen sind eines der Hauptkriterien für die Klassifizierung der unterschiedlichen EAs. Das Genom eines Lösungskandidaten hat oft die Form eines Bitstrings, einer Liste reeller Zahlen, einer Reihenfolge (bei kombinatorischen Problemen wie Travelling Salesman) oder eines Baumes.

Die Terminologie entspricht oft dem biologischen Vorbild. So werden die Daten, die einen Lösungskandidaten kennzeichnen, als Individuum bezeichnet. Die zugehörige Datenstruktur nennt man ein Chromosom. Jedes Chromosom besteht aus Genen und die möglichen Werte eines bestimmten Gens heißen Allele.

Unterscheidung Such- und Problemraum

In der Natur ist die Information über sämtliche grundlegenden Eigenschaften (Phänotyp) eines Organismus (z. B. Äußere Erscheinung, Stoffwechsel oder basales Verhalten) innerhalb jedes Organismus gespeichert, wie schon Gregor Mendel um 1860 entdeckte. Heute ist bekannt, dass diese Speicherung mit dem genetischen Code realisiert wird. Auf molekularer Ebene sind die definierenden Eigenschaften als DNA codiert. Die gesamte genetische Ausstattung eines Organismus wird als Genotyp bezeichnet. Der Genotyp bestimmt den Phänotyp, allerdings über einen komplizierten Prozess, die Genexpression.

Analog zur Biologie wird bei evolutionären Algorithmen zwischen Problemraum (entspricht Phänotyp) und Suchraum (entspricht Genotyp) unterschieden. Der Problemraum enthält also konkrete Lösungen für das behandelte Problem, während der Suchraum die codierten Lösungen enthält. Die Abbildung (engl. mapping) von Suchraum auf Problemraum wird als Genotype-Phenotype-Mapping bezeichnet. Die genetischen Operatoren werden auf Elemente des Suchraums angewandt, zur Auswertung werden Elemente des Suchraums per Genotype-Phenotype-Mapping auf Elemente des Problemraums abgebildet.

Beziehungen zwischen Such- und Problemraum

Die Bedeutung einer geeigneten Wahl des Suchraums für den Erfolg einer EA-Anwendung wurde schon früh erkannt. An einen geeigneten Suchraum und damit an eine geeignetes Genotype-Phenotype-Mapping können folgende Anforderungen gestellt werden:

Vollständigkeit

Alle möglichen zulässigen Lösungen müssen im Suchraum enthalten sein.

Redundanz

Wenn mehr mögliche Genotypen als Phänotypen existieren, nennt man die genetische Repräsentation des EA redundant. In der Natur spricht man vom degenerierten genetischen Code. Bei einer redundanten Repräsentation sind neutrale Mutationen möglich, dabei handelt es sich um Mutationen, die den Genotyp verändern, die sich dabei aber nicht auf den Phänotyp auswirken. So kann es je nach Anwendung der genetischen Operatoren phänotypisch unveränderte Nachkommen geben, was u. a. zu unnötigen Fitnessbestimmungen führt. Da die Bewertung in realen Anwendungen in der Regel den größten Teil der Rechenzeit ausmacht, kann dies den Optimierungsprozess verlangsamen. Darüber hinaus kann es dazu führen, dass die Population eine höhere genotypische als phänotypische Diversität aufweist, was ebenfalls den evolutionären Fortschritt behindern kann.

In der Biologie besagt die Neutrale Theorie der molekularen Evolution, dass dieser Effekt eine dominierende Rolle in der natürlichen Evolution spielt. Forschungsergebnisse im Bereich der evolutionären Algorithmen legen wiederum nahe, dass neutrale Mutationen die Funktionsfähigkeit von EA insofern verbessern können, als Populationen, die zu einem lokalen Optimum konvergiert sind, durch genetische Drift eine Möglichkeit besitzen, diesem lokalen Optimum zu entkommen. Das Thema wird jedoch kontrovers diskutiert, und es gibt keine eindeutigen Ergebnisse zur Neutralität in EAs. Andererseits existieren bewährte Vorgehensweisen zur Behandlung von vorzeitiger Konvergenz von EAs.

Lokalität

Die Lokalität einer genetischen Repräsentation entspricht dem Maß, zu dem Abstände im Suchraum nach dem Genotype-Phenotype-Mapping im Problemraum erhalten bleiben. Das heißt, eine hohe Lokalität hat eine Repräsentation genau dann, wenn Nachbarn im Suchraum auch Nachbarn im Problemraum sind. Damit erfolgreiche Schemata durch das Genotype-Phenotype-Mapping nach einer geringfügigen Mutation nicht zerstört werden, muss die Lokalität einer Repräsentation hoch sein.

Skalierung

Beim Genotype-Phenotype-Mapping können die Elemente des Genotyps verschieden skaliert (gewichtet) werden. Der einfachste Fall ist die uniforme Skalierung: Alle Elemente des Genotyps sind im Phänotyp gleich gewichtet. Eine häufige Skalierung ist die exponentielle. Werden ganze Zahlen binär codiert, haben die einzelnen Stellen der entstandenen binären Zahl exponentiell verschiedene Gewichtungen bei der Repräsentation des Phänotyps.

Beispiel: Die Zahl 90 wird binär (also zur Basis zwei) als 1011010 geschrieben. Verändert man nun eine der vorderen Stellen in der binären Schreibweise, hat dies deutlich größere Auswirkungen auf die codierte Zahl als etwaige Veränderungen an den hinteren Stellen (der Selektionsdruck wirkt an den vorderen Stellen exponentiell stärker).

Aus diesem Grund tritt bei exponentieller Skalierung der Effekt auf, dass die „hinteren“ Stellen im Genotyp zufällig fixiert werden, bevor die Population nahe genug am Optimum angelangt ist, um diese Feinheiten anzupassen.

Hybridisierung und Reparatur beim Genotyp-Phänotyp-Mapping

Bei der Abbildung des Genotyps auf den zu bewertenden Phänotyp kann aufgabenspezifisches Wissen verwendet werden, um den Phänotyp zu verbessern und/oder sicherzustellen, dass Einschränkungen eingehalten werden. Dies dient auch zur Verbesserung der EA-Leistung in Bezug auf Laufzeit und Lösungsqualität.

Beispiele eines Genotyp-Phänotyp-Mappings

Beispiel einer direkten Repräsentation

Eine naheliegende und häufig verwendete Kodierung für das Travelling-Salesman-Problem und verwandte Aufgaben besteht darin, die zu besuchenden Städte fortlaufend zu nummerieren und als ganze Zahlen im Chromosom zu speichern. Ein Chromosom stellt dann eine Tour als Permutation der Städtenummern dar. Die genetischen Operatoren müssen so angepasst werden, dass sie nur die Reihenfolge der Gene (Städte) ändern und keine Löschungen oder Verdoppelungen verursachen. Somit entspricht die Reihenfolge der Gene der der Städte, und es liegt eine einfache Eins-zu-Eins-Abbildung vor.

Beispiel eines komplexen Genotyp-Phänotyp-Mappings

Bei kombinatorischen Aufgaben ist in der Regel eine umfangreiche Abbildung des Genoms auf den Phänotyp als Element des Problemraums erforderlich. Zum Beispiel enthält das Genom einer Schedulingaufgabe alle erforderlichen Informationen für die einzelnen Schedulingoperationen, insbesondere deren Reihenfolge und eventuell weitere Daten z. B. über die Ressourcenauswahl. Ein Phänotyp besteht je nach Aufgabenstellung aus einer oder mehreren Belegungsmatrizen, die die zeitliche Belegung einer Ressourcenart darstellen. Eine Belegungsmatrix besteht aus ${\displaystyle N}$ Ressourcen und ${\displaystyle T}$ Zeiteinheiten, wobei ${\displaystyle T}$ eine obere Abschätzung der benötigten Zeit darstellt. Der Inhalt eines Matrixelements ist die Kennung (meist ein Index in einer Tabelle) derjenigen Schedulingoperation, die die Ressourcenbelegung veranlasst hat. In der Liste der Schedulingoperationen sind meist weitere Daten hinterlegt, wie beispielsweise die erforderliche Dauer der Belegung. Was unter einer Schedulingoperation genau zu verstehen ist, hängt von der Aufgabenstellung ab. Dazu zwei Beispiele: Bei der Produktionsplanung (Job-Shop-Scheduling) sind es einzelne Arbeitsschritte, bei der Schulstundenplanung sind es Unterrichtsstunden einer Klasse, wobei hier mindestens 2 Ressourcen zu belegen sind: ein geeigneter Raum und eine geeignete Lehrkraft, der dann aber auch alle Unterrichtsstunden des betreffenden Faches zuzuordnen sind (zusätzliche Restriktion). Nach Abarbeitung aller Gene des Chromosoms können aus den Belegungsmatrizen eine Reihe von Kennziffern für die Bewertung des Schedules und damit zur Fitnessermittlung abgelesen werden: Beispielsweise die Fertigstellungszeit eines Auftrags, die gesamte Bearbeitungszeit aller Aufträge, die Auslastung der Ressourcen oder die Freistunden von Schulklassen oder Lehrkräften. Außerdem ermöglicht die Aufstellung der Matrizen die Erkennung und Beseitigung von Belegungskonflikten.

Die Erstellung einer Belegungsmatrix soll anhand des Schedulingbeispiels erläutert werden, das bereits bei der Beschreibung eines Genoms für komplexe Gene Verwendung gefunden hat. Das linke Bild zeigt noch einmal den dort gezeigten Chromosomausschnitt, der auf den im Beispiel definierten Gentypen beruht. Zur leichteren Beschreibung sind die Gene hier unterschiedlich eingefärbt und die braun gekennzeichneten Indizes entsprechen den Indizes der zu verplanenden Ressourcen, die durch die Genparameter aus der Menge der für den Teiljob geeigneten Ressourcen ausgewählt wurden. Der erste Genparameter gibt dabei die dem Teiljob zugeordnete Hardware an und der zweite die zu verwendende Software, sofern diese lizenzrechtlichen Mengenbegrenzungen unterliegt. Mit Hilfe des dritten Parameters kann dem Teiljob bei Bedarf zusätzliches Equipment zugeordnet werden. Jedes Gen beschreibt eine Schedulingoperation, wobei der Gentypcode dem zu verplanenden Teiljob der Workflows entspricht.

Zur Verwaltung der zu verplanenden Ressourcen mögen zwei Belegungsmatrizen dienen, eine für Rechnerhardware und zusätzliches Equipment und eine für die Software. Die Unterscheidung reflektiert den Umstand, dass im ersten Fall eine Ressource nur einmal belegt werden kann und es für die Auswertung wichtig ist, zu vermerken, durch welchen Teiljob. Bei der Software ist hingegen lediglich von Bedeutung, dass das Limit gleichzeitiger Verwendung nicht überschritten wird. Ausschnitte beider Matrizen sind im rechten Bild mit einer teilweisen Belegung durch bereits abgearbeitete Gene (grau) dargestellt. Dabei wird die SW 0 durch die Teiljobs 8 und 35 verwendet, was zu den unterschiedlichen Einträgen führt. Zuerst wird der Teiljob 32 verplant. Ihm hat der Genparameter die Ressource 7 zugeteilt, die er ab Zeiteinheit (ZE) 14 für drei ZE belegt. Danach wird das Gen für den Teiljob 47 abgearbeitet, der wegen der Belegung der Equipmentressource 4 erst ab ZE 18 starten kann. Daher entsteht für die ebenfalls belegte Hardwareressource 7 eine Lücke von einer ZE. Schließlich belegt Teiljob 15 die Hardwareressource 8 und die SW 2. Nach Abarbeitung des Chromosoms enthalten die Belegungsmatrizen den zugehörigen Phänotyp. Es sei angemerkt, dass die jeweilige Bearbeitungsdauer den Stammdaten der Teiljobs entnommen wird. Außerdem wird davon ausgegangen, dass alle HW-Ressourcen gleich schnell sind, also keine Anpassungen der Belegungszeiten erforderlich sind.

Das Beispiel zeigt deutlich, dass die Genotyp-Phänotyp-Abbildung recht aufwändig sein kann und phänotypische Eigenschaften nicht unbedingt direkt aus den Allelwerten des Genoms ablesbar sind. So steht beispielsweise das Gen von Teiljob 15 zwar hinter dem von Teiljob 47, aber der zugehörige Job wird im Beispiel trotzdem früher ausgeführt. Als weiteres Beispiel für komplexe Genotyp-Phänotyp-Abbildungen können die meisten simulationsbasierten Aufgabenstellungen angesehen werden, bei denen das Genom ein mehr oder weniger komplexes Simulationsmodell konfiguriert.

Bei der hier vorgestellten beispielhaften Interpretation dreier Gene eines Chromosoms wurde nicht berücksichtigt, dass die Teiljobs als Workflows organisiert sind und es demzufolge Reihenfolgerestriktionen gibt. Deren Beachtung kann durch eine entsprechende Erweiterung der Bewertung oder besser durch geeignete Reparaturmaßnahmen umgesetzt werden.

Literatur

• Karsten Weicker: Evolutionäre Algorithmen. Springer Vieweg, Wiesbaden 2015, ISBN 978-3-658-09957-2, doi:10.1007/978-3-658-09958-9. 
• Volker Nissen: Einführung in evolutionäre Algorithmen: Optimierung nach dem Vorbild der Evolution. Vieweg, Braunschweig 1997, ISBN 3-528-05499-9, doi:10.1007/978-3-322-93861-9. 
• A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, doi:10.1007/978-3-662-44874-8. 
• Franz Rothlauf: Representations for Genetic and Evolutionary Algorithms. Springer, Berlin Heidelberg 2006, ISBN 3-540-25059-X, doi:10.1007/3-540-32444-5. 

Einzelnachweise

1. A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, S. 40, doi:10.1007/978-3-662-44874-8. 
2. A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, Representation and the Roles of Variation Operators, S. 49–51, doi:10.1007/978-3-662-44874-8. 
3. A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, Popular Evolutionary Algorithm Variants, S. 99–118, doi:10.1007/978-3-662-44874-8. 
4. D.B. Fogel: Phenotypes, genotypes, and operators in evolutionary computation. In: IEEE (Hrsg.): Proceedings of 1995 IEEE International Conference on Evolutionary Computation. Band 1. IEEE, 1995, ISBN 978-0-7803-2759-7, S. 193–198, doi:10.1109/ICEC.1995.489143. 
5. Franz Rothlauf: Representations for Genetic and Evolutionary Algorithms. In: Representations for Genetic and Evolutionary Algorithms. Springer, Berlin, Heidelberg 2006, ISBN 978-3-540-25059-3, S. 9–32, doi:10.1007/3-540-32444-5_2. 
6. A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, Representation, Mutation, and Recombination, S. 49–78, doi:10.1007/978-3-662-44874-8. 
7. A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, Representation (Definition of Individuals), S. 28–30, doi:10.1007/978-3-662-44874-8. 
8. Karsten Weicker: Evolutionäre Algorithmen. Springer Fachmedien, Wiesbaden 2015, ISBN 978-3-658-09957-2, Formale Einführung evolutionärer Algorithmen, S. 34–39, doi:10.1007/978-3-658-09958-9. 
9. Peter A. Whigham, Grant Dick, James Maclaurin: On the mapping of genotype to phenotype in evolutionary algorithms. In: Genetic Programming and Evolvable Machines. Band 18, Nr. 3, September 2017, ISSN 1389-2576, S. 353–361, doi:10.1007/s10710-017-9288-x. 
10. Richard A. Caruana, J. David Schaffer: Representation and Hidden Bias: Gray vs. Binary Coding for Genetic Algorithms. In: Machine Learning Proceedings 1988. Elsevier, 1988, ISBN 978-0-934613-64-4, S. 153–161, doi:10.1016/b978-0-934613-64-4.50021-9 (elsevier.com [abgerufen am 18. Januar 2023]). 
11. Gunar E. Liepins, Michael D. Vose: Representational issues in genetic optimization. In: Journal of Experimental & Theoretical Artificial Intelligence. Band 2, Nr. 2, April 1990, ISSN 0952-813X, S. 101–115, doi:10.1080/09528139008953717 (tandfonline.com [abgerufen am 18. Januar 2023]). 
12. M. Coli, P. Palazzari: Searching for the optimal coding in genetic algorithms. In: Proceedings of 1995 IEEE International Conference on Evolutionary Computation. IEEE, Perth, WA, Australia 1995, ISBN 978-0-7803-2759-7, S. 92, doi:10.1109/ICEC.1995.489291 (ieee.org [abgerufen am 18. Januar 2023]). 
13. Franz Rothlauf: Three Elements of a Theory of Representations. In: Representations for Genetic and Evolutionary Algorithms. Springer, Berlin, Heidelberg 2006, ISBN 978-3-540-25059-3, S. 33–96, doi:10.1007/3-540-32444-5_3. 
14. Edgar Galván-López, Stephen Dignum, Riccardo Poli: The Effects of Constant Neutrality on Performance and Problem Hardness in GP. In: Genetic Programming. LNCS 4971. Springer, Berlin, Heidelberg 2008, ISBN 978-3-540-78670-2, S. 312–324, S. 313, doi:10.1007/978-3-540-78671-9_27. 
15. Edgar Galván-López, Riccardo Poli, Ahmed Kattan, Michael O’Neill, Anthony Brabazon: Neutrality in evolutionary algorithms… What do we know? In: Evolving Systems. Band 2, Nr. 3, September 2011, ISSN 1868-6478, S. 145–163, doi:10.1007/s12530-011-9030-5. 
16. Joshua D. Knowles, Richard A. Watson: On the Utility of Redundant Encodings in Mutation-Based Evolutionary Search. In: J.J Merelo Guervós, P. Adamidis, H.-G. Beyer, H.-P. Schwefel, J.-L. Fernández-Villacañas (Hrsg.): Parallel Problem Solving from Nature — PPSN VII. LNCS 2439. Springer, Berlin, Heidelberg 2002, ISBN 978-3-540-44139-7, S. 88–98, doi:10.1007/3-540-45712-7_9. 
17. A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, Hybridisation During Genotype to Phenotype Mapping, S. 177–178, doi:10.1007/978-3-662-44874-8. 
18. Emma Hart, Peter Ross, Jeremy Nelson: Solving a Real-World Problem Using an Evolving Heuristically Driven Schedule Builder. In: Evolutionary Computation. Band 6, Nr. 1, März 1998, ISSN 1063-6560, S. 61–80, doi:10.1162/evco.1998.6.1.61 (mit.edu [abgerufen am 24. Oktober 2023]). 
19. A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, Permutation Representation, S. 67–74, doi:10.1007/978-3-662-44874-8. 
20. P. Larrañaga, C.M.H. Kuijpers, R.H. Murga, I. Inza, S. Dizdarevic: Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators. In: Artificial Intelligence Review. Band 13, Nr. 2, 1. April 1999, ISSN 1573-7462, S. 129–170, doi:10.1023/A:1006529012972. 
21. 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, 22. April 2013, ISSN 1999-4893, S. 245–277, S. 253, doi:10.3390/a6020245 (mdpi.com [abgerufen am 18. Januar 2023]).