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 an Genen, wobei ein Gen aus einem oder mehreren semantisch zusammenhängenden Parametern besteht, die eine oder mehrere phänotypische Eigenschaften des Individuums bestimmen oder zumindest Einfluss darauf haben. 

Zur Bewertung des Individuums muss die in seinem Genom enthaltene Information, welche auch als Genotyp bezeichnet wird, auf seinem 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:
 Erreichbarkeit aller zulässigen Punkte im Suchraum
 Gestaltung des Genoms derart, dass es nur den Suchraum und keine zusätzlichen Bereiche abdeckt, es also keine Redundanz gibt. 
 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. 
 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:

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 ,  und  mag dies illustrieren:

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 ganzzahligcodierter 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.

Für kombinatorische Probleme bietet sich die Verwendung ganzzahliger Genome an. Es empfiehlt sich, dann auch daran angepasste EAs zu verwenden, die insbesondere über geeignete Mutations- und Crossoveroperatoren verfügen.

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).
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 Roboterbahnplanung und die Designoptimierung einer Aktorplatte mit vorher nicht bekannter Komponentenanzahl.

Genome für die Genetische Programmierung 

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.

Einzelnachweise