Way of the Fittest: Optimization by Behavioral Evolution

Jörg Willi Stork

Research output: PhD ThesisPhD-Thesis - Research and graduation internal

43 Downloads (Pure)

Abstract

Evolutionary computation (EC) methods belong to the state-of-the-art for solving optimization problems with complex characteristics, such as no available analytical descriptions or no differentiability. One outstanding EC paradigm in artificial intelligence applications is neuroevolution, a method to construct artificial neural networks (ANN) and optimize their weights, parameters, and topologies. Neuroevolutionary optimization can be challenging due to complex and costly environments in which they are applied, multi-modal fitness landscapes, and the number of degrees of freedom necessary to generate ANNs that can perform in these environments. Surrogate model-based optimization (SMBO) can improve search efficiency by approximating complex fitness landscapes and predicting high-performing candidate solutions. Surrogate models often rely on distance metrics that determine the correlation of a candidate solution's fitness to that of similar individuals. However, the employment of distances for complex-structured candidates, such as ANNs, is difficult due to their non-linear relationships between their encoding (genotype) and realization (phenotype). A possible solution is to compare candidates based on their observable behavior, i.e., an individual's decisions, actions, and movements in an environment. Task-dependent behavior has a strong connection to fitness, which renders optimization in this space of behaviors promising. The central concept of this thesis is to research, analyze and develop methods that exploit the strong connection between an individual's behavior, environment, and fitness. The included publications are, in their entirety, a fundamental step towards establishing behavioral optimization. Initially, an extensive introduction to EC and SMBO in the greater context of global optimization is given to allow an in-depth understanding of their concepts, particularities, and various available implementations. A new taxonomy is presented, and it is determined that global optimization algorithms have close connections in their search strategies and share similar components, which allows combining them into new hybrid algorithm designs. In large parts of this thesis, data-drive Kriging models were employed for the task of SMBO as a flexible and accurate predictor model within the SMBO paradigm. For this purpose, Kriging was extended to allow the use of custom kernels and non-continuous distances, i.e., combinatorial, genotypic, or behavioral measures. Empirical studies confirmed the impact of distance measures: task-dependent distances, which significantly correlate to the underlying problem definition, provide the most accurate performance predictions. On this basis, different genotypic and phenotypic distance metrics were introduced and tested in empirical studies featuring tree-based genetic programming models, fixed-topology ANNs, as well as graph-based, topology-changing ANNs in neuroevolution. In all studies, a phenotypic distance, comparing the individuals' outputs instead of their encodings, provided the most accurate predictions and illustrated superior performance embedded in SMBO processes compared to model-free EC methods. Finally, the developed methods were extended to time-dependent reinforcement learning with a new task-dependent and precise notion of an individual's behavior. An in-depth analysis of ways to compare, control, and steer these behaviors was performed to design efficient behavioral optimization algorithms. Such an algorithm was exemplified in final studies, where behavioral optimization was included in a diverse set of neuroevolutionary optimization and ANN training algorithms. With these methods, the sampling efficiency of neuroevolutionary algorithms improved significantly. In conclusion, this thesis illustrates the benefits of adding behavior-based search methods to EC and SMBO. The methods for searching the behavior space outlined in this work provide examples of how to overcome problems of genotypic variation in optimization, such as the complex, non-linear transitions between the genotypes and their evaluated fitness and the concomitantly challenging optimization. Behavioral optimization allows controlled adaption of individuals, robustly steering them in the direction of high-performing individuals and ultimately improving the sampling efficiency in optimizing complex tasks.
Original languageEnglish
QualificationPhD
Awarding Institution
  • Vrije Universiteit Amsterdam
Supervisors/Advisors
  • Eiben, AE, Supervisor
  • Bartz-Beielstein, T., Co-supervisor, External person
Award date18 Jan 2022
Publication statusPublished - 18 Jan 2022

Keywords

  • Global Optimization
  • Evolutionary Computation
  • Surrogate-Based Optimization
  • Artificial Intelligence
  • Behavioral Optimization
  • Reinforcement Learning
  • Neuroevolution
  • Kriging
  • Phenotypic Distance
  • Behavior Distances

Fingerprint

Dive into the research topics of 'Way of the Fittest: Optimization by Behavioral Evolution'. Together they form a unique fingerprint.

Cite this