Genom (evolutionärer Algorithmus)

Unter einem Genom versteht man die Menge aller Chromosomen eines Individuums, das einer Lösung einer Aufgabenstellung entspricht, welche mit einem evolutionären Algorithmus (EA) bearbeitet wird. Das Genom eines Individuums entspricht der genetischen Repräsentation einer Aufgabenstellung und ist damit ein Element des Suchraums. In diesem Zusammenhang versteht man unter einem Chromosom eine zusammenhängende Menge von Genen, wobei ein Gen aus einem oder mehreren semantisch zusammenhängenden Parametern besteht, die oft auch Entscheidungsvariable genannt werden. Sie bestimmen eine oder mehrere phänotypische Eigenschaften des Individuums oder haben zumindest einen Einfluss darauf.

Zur Bewertung des Individuums muss die in seinem Genom enthaltene Information, welche auch als Genotyp bezeichnet wird, auf seinen Phänotyp abgebildet werden, welcher ein Element des Problemraums darstellt, siehe auch Hauptartikel: Genetische Repräsentation.

Häufig basiert ein Individuum auf einem einzigen Chromosom, das z. B. aus einer Kette einheitlicher Gene besteht, wobei jedes Gen z. B. ein Bit oder eine ganze oder reelle Zahl darstellt. Es gibt aber durchaus auch evolutionäre Algorithmen, die zur Lösung spezieller Aufgaben Genome verwenden, welche pro Individuum aus mehreren Chromosomen bestehen.

Anforderungen an ein Genom

Der Optimierer hat bei der Gestaltung des Genoms ausgehend von der zu lösenden Aufgabenstellung eine Reihe von Freiheiten. An ein gut geeignetes Genom sind folgende Anforderungen zu stellen:

1. Erreichbarkeit aller zulässigen Punkte im Suchraum
2. Gestaltung des Genoms derart, dass es nur den Suchraum und keine zusätzlichen Bereiche abdeckt und dass es keine oder möglichst wenig Redundanz gibt.
3. Beachtung der starken Kausalität: Kleine Änderungen am Genom sollen nur zu geringen Änderungen des Phänotyps führen. Dies wird auch als Lokalität der Beziehung zwischen Such- und Problemraum bezeichnet.
4. Gestaltung des Genoms derart, dass es unzulässige Bereiche im Suchraum ganz oder möglichst weitgehend ausschließt.

Während die erste Anforderung unabdingbar ist, muss man sich je nach Anwendung und verwendetem EA meist nur mit einer möglichst weitgehenden Erfüllung der verbleibenden Anforderungen zufriedengeben. Es sei aber darauf hingewiesen, dass die evolutionäre Suche durch eine möglichst vollständige Erfüllung unterstützt und unter Umständen erheblich beschleunigt wird. Nissen schreibt zu dem Problem der Gestaltung eines Genoms:

„Nach Ansicht des Autors sollten sich die Lösungsrepräsentation und die Codierung möglichst direkt aus der gegebenen Problemstellung ableiten. Insbesondere sollten strukturelle Eigenheiten (Regelmäßigkeiten) des Lösungsraumes durch die Codierung erhalten bleiben, soweit sie den Suchprozeß erleichtern.“

– Volker Nissen: Evolutionäre Algorithmen - Darstellung, Beispiele, Betriebswirtschaftliche Anwendungsmöglichkeiten, S.33

Es besteht ein enger Zusammenhang zwischen der genetischen Repräsentation einer Aufgabenstellung und den dafür geeigneten genetischen Operatoren, darunter insbesondere Mutationen und Rekombinations- bzw. Crossoveroperatoren. Beides muss aufeinander abgestimmt sein, wobei die verwendeten Operatoren eine leichte Erreichbarkeit aller Punkte im Suchraum ermöglichen sollten.

Nachfolgend wird von Genomen ausgegangen, die jeweils aus einem Chromosom pro Individuum bestehen.

Lineare Genome

Bei linearen Genomen besteht das Chromosom aus einer Genkette, die z. B. durch ein Feld oder eine verlinkte Liste implementiert werden kann. Felder eignen sich für Anwendungen, bei denen die Position der Gene im Chromosom nicht verändert wird. Andernfalls können auch Listen von Vorteil sein.

Genome für klassische genetische Algorithmen

Die genetischen Algorithmen (GA) verwenden in ihrer klassischen Form Bitstrings und bilden die zu optimierenden Entscheidungsvariablen darauf ab. Ein Beispiel für eine boolsche und drei ganzzahlige Entscheidungsvariablen mit den Wertebereichen $0\leq E_{1}\leq 60$, $5\leq E_{2}\leq 30$ und $-12\leq E_{3}\leq 14$ mag dies illustrieren:

Repräsentation von vier Entscheidungsvariablen in einem Bitstring

Entscheidungsvariable:	$E_{1}=22$						$E_{2}=25$					$E_{3}=-4$					$E_{4}=0$
Bits:	0	1	0	1	1	0	1	1	0	0	1	1	1	1	0	0	0
Position:	17	16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1

Man beachte, dass die negative Zahl hier im 2er-Komplement angegeben ist. Bei den klassischen GAs wird die Mutation für jedes Bit mit gleicher Wahrscheinlichkeit durchgeführt, was wegen der unterschiedlichen Wertigkeit der Bits dazu führt, dass kleine Änderungen große Auswirkungen auf den Phänotyp haben können. Die damit verbundene Verletzung der dritten Anforderung an Genome kann durch die Verwendung von Gray-Codes vermieden werden oder aber durch entsprechend angepasste Mutationen.

Für Aufgaben, deren Entscheidungsvariable boolesche Größen sind, ist die Codierung in Form von Bitstrings sicher eine adäquate und den Anforderungen an Genome entsprechende Darstellung. Es gab aber bereits frühzeitig Kritik an der Verwendung binärer Genome für ganzzahlige oder reellwertige Größen.

Genome mit reellwertigen oder ganzzahligen Genen

Für die Bearbeitung von Aufgabenstellungen mit reellwertigen oder gemischt-ganzzahligen Entscheidungsvariablen bieten sich EAs wie die Evolutionstrategie (ES) oder die reellcodierten GAs an. Im Falle gemischt-ganzzahliger Werte wird häufig gerundet, was aber eine gewisse Verletzung des Redundanzgebotes (2. Forderung an ein Genom) darstellt. Wenn die Genauigkeiten der reellen Werte sich sinnvoll eingrenzen lassen, kann dieser Verletzung durch die Verwendung ganzzahlig codierter EAs abgeholfen werden. Dazu werden die gültigen Ziffern reeller Werte durch Multiplikation mit einem geeigneten Faktor auf ganze Zahlen abgebildet. Beispielsweise wird aus 12,380 durch Multiplikation mit 1000 der Integerwert 12380. Dies ist natürlich bei der Genotyp-Phänotyp-Abbildung für Bewertung und Ergebnisdarstellung zu berücksichtigen.

Genome für Permutationen

Bei kombinatorischen Problemen geht es in erster Linie darum, eine optimale Abfolge einer Reihe von Elementen zu finden. Nummeriert man die $n$ Elemente einer kombinatorischen Aufgabe in einer beliebigen Reihenfolge durch, so kann eine Lösung als Permutation der natürlichen Zahlen $1,\ldots ,n$ dargestellt werden. Die einfachste Abbildung auf ein Chromosom ist dann eine Sequenz ganzzahliger Gene, bei denen die Werte $1,\ldots ,n$ jeweils nur einmal vorkommen dürfen und die Reihenfolge der Gene eine Lösung repräsentiert. Folglich dürfen die genetischen Variationsoperatoren Mutation und Rekombination nur die Genreihenfolge verändern und keinesfalls Gene entfernen oder duplizieren. Als Beispiel kann das Problem des Handlungsreisenden dienen, der eine bestimmte Anzahl von Städten auf der kürzest möglichen Tour jeweils genau einmal besuchen möchte. Sollen z. B. zehn Städte besucht werden, würde die Sequenz $4,7,1,8,6,2,5,3,10,9$ dem folgenden Chromosom entsprechen:

4

7

1

8

6

2

5

3

10

9

Neben obiger Codierung, die auch als Pfaddarstellung bekannt ist, gibt es noch mehrere andere Möglichkeiten, eine Permutation darzustellen, z. B. die ordinale Darstellung oder die Matrixdarstellung.

Genome für Koevolution

Wenn ein Genom neben den Entscheidungsvariablen zusätzliche Informationen enthält, die die Evolution und/oder die Abbildung der Entscheidungsvariablen in ihrer Gesamtheit auf den Phänotyp beeinflussen und selbst der Evolution unterliegen, spricht man von Koevolution. Ein typisches Beispiel dafür ist die ES, die eine oder mehrere Mutationsschrittweiten als Strategieparamter in jedes Chromosom mit aufnimmt. Ein anderes Beispiel ist ein zusätzliches Gen zur Steuerung einer Auswahlheuristik für die Ressourcenzuordnung bei Schedulingaufgaben.

Diesem Vorgehen liegt die Annahme zu Grunde, dass gute Lösungen auf einer passenden Auswahl der Strategieparameter oder auf dem Steuerungsgen, das die Genotyp-Phänotyp-Abbildung beeinflusst, beruhen. Der Erfolg der ES gibt dieser Annahme Recht.

Genom für komplexe Gene

Die oben vorgestellten Genome sind gut zur Bearbeitung von Aufgabenstellungen der kontinuierlichen, gemischt-ganzzahligen, rein ganzzahligen oder der kombinatorischen Optimierung geeignet. Bei einer Kombination dieser Optimierungsgebiete wird es hingegen je nach Aufgabenstellung schwierig, diese auf einfache Werteketten abzubilden. Eine Lösung besteht darin, das bisher verwendete Genkonzept zu erweitern und ein Gen als die Beschreibung eines Elements oder einer elementaren Eigenschaft des Phänotyps anzusehen. Dazu wird ein Gentyp definiert, der so viele Parameter des jeweils passenden Datentyps enthält, wie zur Beschreibung des jeweiligen Elements des Phänotyps erforderlich sind. Ein Gen wird damit als die Beschreibung semantisch zusammengehöriger Teileigenschaften des Phänotyps begriffen. Ein Chromosom besteht nun aus Genen als Datenobjekte der Gentypen, wobei je nach Anwendung jeder Gentyp genau einmal als Gen vorkommt oder aber beliebig oft im Chromosom enthalten sein kann. Letzteres führt zu Chromosomen dynamischer Länge, wie sie für manche Aufgaben erforderlich sind. Die Gentypdefinitionen können auch Angaben zu den zulässigen Wertebereichen der Genparameter enthalten, welche bei der Chromosomenerzeugung und durch geeignete Mutationen eingehalten werden, sodass keine Letalmutationen entstehen können. Implementiert wurde dieses Konzept im EA GLEAM (General Learning Evolutionary Algorithm and Method).

Drei beispielhafte Gene passend zu den nebenstehenden Gentypdefinitionen in einem als Liste organisiertem Chromosom.

Beispiel für drei Gentypen mit unterschiedlich vielen Parametern und jeweils eigenen Wertebereichen. Generell erlaubt das Gentypkonzept auch unterschiedliche Datentypen.

Zur Illustration soll ein Beispiel dienen, bei dem es um das Scheduling von Workflows an heterogene Ressourcen geht, wobei ein Arbeitsschritt mehrere unterschiedliche Ressourcen benötigen kann. Ein Workflow gibt vor, welche Arbeitsschritte parallel bearbeitet werden können und welche hintereinander ausgeführt werden müssen. Heterogene Ressourcen bedeuten in diesem Zusammenhang unterschiedliche Bearbeitungszeiten bei unterschiedlichen Kosten. Jede Schedulingoperation benötigt also ein oder mehrere Parameter, die die Ressourcenauswahl bestimmen. Ein dafür geeignetes Genom sieht pro Arbeitsschritt einen Gentyp vor, der einen Parameter für jede benötigte Ressource hat, wobei die Wertebereiche der Parameter von der Anzahl der jeweils verfügbaren alternativen Ressourcen für diesen Arbeitsschritt abhängen. Der Gentyp des Arbeitsschritts 15 mit zwei Ressourcen, für die es jeweils vier bzw. sieben Alternativen gibt, sähe dann wie im linken Bild dargestellt aus. Da die Parameter Indizes in Listen der verfügbaren Ressourcen für den jeweiligen Arbeitsschritt darstellen, beginnt ihr Wertebereich bei 0. Das rechte Bild zeigt exemplarisch drei zu den Gentypen gehörige Gene eines Chromosoms in Listendarstellung. Die Genotyp-Phänotyp-Abbildung dieses Beispiels wird im Artikel Genetische Repräsentation dargestellt.

Weitere Anwendungen, deren Aufgabenstellung durch das beschriebene Gentypenmodell einfach und direkt auf ein Genom abbildbar ist, sind z. B. die im Buch über GLEAM vorgestellte kollisionsfreie Roboterbahnplanung und die Designoptimierung einer Aktorplatte mit vorher nicht bekannter Komponentenanzahl.

Genome für die Genetische Programmierung

Syntaxbaum einer Formel

Die genetische Programmierung (GP) ist ein EA-Typ zur Erzeugung von Computerprogrammen oder Schaltkreisen. Der bei der Übersetzung eines Computerprogramms vom Compiler als interne Repräsentation erzeugte Syntaxbaum kann als eine den Anforderungen an ein Genom genügende Darstellung eines Programms angesehen werden. Nebenstehendes Bild zeigt als Beispiel den Syntaxbaum eines mathematischen Ausdrucks. Mutationsoperatoren können je nach dargestellter Syntaxstruktur Teilbäume umhängen, verändern oder löschen. Die Rekombination erfolgt durch den Austausch dafür geeigneter Teilbäume.

Literatur

• Hartmut Pohlheim: Evolutionäre Algorithmen. Verfahren, Operatoren und Hinweise für die Praxis. Springer, Berlin 1999, ISBN 3-540-66413-0.
• Karsten Weicker: Evolutionäre Algorithmen. Teubner, Stuttgart 2002, ISBN 3-519-00362-7.
• 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. 
• Hans-Paul Schwefel: Evolution and Optimum Seeking. Wiley & Sons, New York 1995, ISBN 0-471-57148-2.
• Keshav P. Dahal, Kay Chen Tan, Peter I. Cowling (Hrsg.): Evolutionary Scheduling. Studies in Computational Intelligence, Bd. 49, Springer, Berlin, Heidelberg, 2007. doi:10.1007/978-3-540-48584-1, ISBN 978-3-642-08017-3
• Amir H. Gandomi, Ali Emrouznejad, Mo M. Jamshidi, Kalyanmoy Deb, Iman Rahimi (Hrsg.): Evolutionary Computation in Scheduling. John Wiley & Sons, 2020. ISBN 978-1-119-57387-6