Exploring the population dynamics of evolutionary algorithms using gene heritage

Abstract

The idea of evolutionary algorithms (EAs) is derived from the principle of natural selection in biology. A population of solutions to an optimization problem gets recombined and mutated to create a new generation of offspring. The best survive to the next generation. The idea of this evolutionary loop is simple. However, the resulting search dynamics become very complex, as we usually evolve hundreds or thousands of solutions over many generations. Even though we understand each component in this process, the sheer amount of data quickly becomes incomprehensible for humans. Furthermore, these algorithms are often only tested and evaluated in terms of their performance. While this is an important aspect of the algorithm, we disregard its behavior in the search space. Essentially, only half of the search process is evaluated. This means that we know that one algorithm performed better than another, but we do not truly know why. This question is typically subject to speculation or educated guesses from the user. Subsequently, designing and tailoring EAs for new problems relies mostly on intuition. We believe a better and proven base of knowledge about the search dynamics can only be beneficial for the development and application of EAs. For this reason, we want to explore their population dynamics in this thesis. The idea of evaluating the population dynamics of EAs is not new. However, there is a lack of overview of existing approaches, as, to the best of our knowledge, neither review works nor a shared vocabulary around this topic exists. Here, we provide a first starting point by collecting and classifying existing approaches based on the data they collect. We find that in recent years, works visualizing and evaluating the paths of a population through the search space have gained traction. Furthermore, genealogical evaluations, which are also inspired by the field of biology, are often used to evaluate parent-child relationships of the evolutionary process. However, we do only find a small number of works that focus on precisely tracking how each part of a solution was assembled. Here lies the focus of this dissertation. This thesis proposes a new approach for research into the population dynamics of EAs on a gene-based level. For this, we develop the traceable evolutionary algorithm (T-EA), which allows us to track the heritage of each gene from the initial population throughout the evolutionary process. Furthermore, we propose metrics to evaluate the newly collected data. Most importantly, we can evaluate the influence of a past individual with the amount of genetic material present in the current population. Besides creating new tools to evaluate the population dynamics in EAs, we also want to create first knowledge on how these algorithms assemble their solution. For this, we conduct first exploratory tests to gain a better idea of how the T-EA can be used and get a first interesting insight into the population dynamics of EAs. Our goal is to identify influential individuals in the evolutionary process. For this, we design a system to create individuals of desired genome and fitness properties. Empirically testing both performance and tracing gene heritage in EAs, we can identify which properties, and therefore which individuals, are influential in the search process. We do these tests both for single-objective evolutionary algorithms (SOEAs) and multi-objective evolutionary algorithms (MOEAs). We find that optimizing more than one objective, while only changing the survival process of the evolutionary loop, creates large differences in the convergence behavior.

Die Idee von evolutionären Algorithmen (EAs) leitet sich aus dem Prinzip der natürlichen Selektion ab. Eine Population von Lösungen für ein Optimierungsproblem wird über mehrere Generationen neu kombiniert und mutiert, um neue Lösungen als Nachkommen zu schaffen. Diese neuen Lösungen werden mit einer Fitnessfunktion bewertet. Die Besten werden für die nächste Generation ausgewählt und der Rest wird aussortiert. Die Idee dieser simulierten Evolution ist einfach. Wir können jeden einzelnen Schritt nachvollziehen und wissen genau, wie die neuen Lösungen erstellt werden. Der daraus resultierende Suchprozess wird jedoch schnell komplex und von Menschen nicht mehr nachvollziehbar, da im Laufe aller Generationen zu viele neue Lösungen entstehen. Außerdem werden EAs oft nur anhand der Qualität oder Performance der Lösungen verglichen, die sie gefunden haben. Ihr Verhalten im Suchraum wird oft nicht evaluiert. Damit wird ein wesentlicher Teil des Suchprozesses ignoriert. Dadurch können wir zwar sagen, dass ein Algorithmus bessere Lösungen für ein Problem findet als ein anderer, aber nicht warum. Diese Frage nach dem Warum wird oft nicht oder lediglich durch Vermutungen und Spekulationen beantwortet. Das bedeutet, dass neue Algorithmen oft nur durch Intuition der Anwender an neue Optimierungsprobleme angepasst werden. Ein besseres Verständnis des Suchverhaltens von EAs ist sowohl für ihre Entwicklung als auch für ihre Anwendung wichtig. Das Ziel dieser Dissertation ist daher, dieses Suchverhalten zu untersuchen. Dabei ist dieses Forschungsgebiet schon Jahrzehnte alt. Es gibt allerdings bisher keine Reviews, und kein gemeinsames Vokabular zu diesem Thema. Diese Arbeit schafft daher einen ersten Überblick über existierende Ansätze, und sammelt bisherige Erkenntnisse. Wir finden unter anderem Arbeiten, welche den Suchprozess von Algorithmen im Suchraum visualisieren und vergleichbar machen. Oder Ansätze, die ähnlich wie Ahnenforschung in der Biologie Eltern-Kind-Beziehungen erfassen, und Stammbäume erstellen. Allerdings gibt es nur wenige Arbeiten auf der kleinsten Einheit dieses simulierten Evolutionsprozesses, dem Gen. Hier liegt der Schwerpunkt dieser Arbeit. In dieser Dissertation haben wir einen neuen Algorithmus zum Tracken der Suchdynamik auf der Genebene entwickelt, den tracebaren evolutionären Algorithmus (T-EA). Mit diesem Werkzeug kann die Herkunft jedes Gens von der initialen Population durch den Evolutionsprozess verfolgt werden. Darüber hinaus schlagen wir Metriken zur Auswertung dieser Daten vor. Wir können den Einfluss einer initialen Lösung anhand der Menge des genetischen Materials in der aktuellen Generation bewerten. Mit dem T-EA möchten wir auch erste Untersuchungen der Suchdynamik von EAs erstellen. Dafür führen wir erste explorative Tests durch, um eine bessere Vorstellung davon zu bekommen, wie der T-EA eingesetzt werden kann, und um erste Einblicke in die Populationsdynamik zu gewinnen. Unser Ziel ist es, einflussreiche Individuen im Evolutionsprozess zu identifizieren. Dazu entwerfen wir ein System, um Lösungen mit den gewünschten Genom- und Fitnesseigenschaften zu erstellen. In empirischen Tests messen wir die Performance und tracken die Suchdynamik mithilfe des T-EA, um zu evaluieren, welche Eigenschaften, und damit welche Lösungen, wichtig für den Evolutionsprozess sind. Wir führen diese Tests sowohl für EAs mit einem einzelnen Suchkriterium, als auch für multikriterielle EAs durch. Hier werden die Unterschiede im Suchverhalten für Probleme mit mehr als einem Suchkriterium deutlich.