Toward civilized evolution: developping inhibitions

Michèle Sébag, Marc Schoenauer, Caroline RaviséHAL 1997

TL;DR

This paper introduces "flee-mutation," a novel evolutionary algorithm operator that learns from past failures to guide future evolution. By maintaining a "virtual loser" representing unfit individuals, flee-mutation encourages offspring to actively move away from these past mistakes, leading to improved performance on complex optimization problems.

What Problem Does This Paper Address?

Evolutionary Computation (EC) methods, like Genetic Algorithms (GAs), typically rely on a population of individuals to implicitly remember past successes. However, this paper argues for an explicit collective memory that learns from failures to prevent repeating them. Existing approaches often focus on remembering and reusing successful strategies or parameters. This work aims to address the gap of actively learning from and avoiding past errors, which can be crucial for efficient exploration of complex search spaces and preventing premature convergence.

Methods

The core contribution is the flee-mutation operator. This operator is designed to evolve individuals by actively moving them away from a "virtual loser" (VL). The VL is a representation of past unfit offspring, updated using a relaxation mechanism from a fraction of the worst individuals in the population.

Key aspects of flee-mutation:

  • Virtual Loser (VL): A vector representing the average characteristics of past unsuccessful individuals.
  • Flee-Mutation Operator: Instead of standard mutation or recombination, this operator modifies an individual (X) to be "further away" from the VL than its parents. This is achieved by flipping bits in X based on how much they differ from the corresponding bits in VL.
  • Flee Step Size (M): This parameter controls how many bits are flipped. The paper explores two strategies:
  • Population Level: A fixed step size (M) or a step size that decreases over generations (hyperbolic schedule).
  • Individual Level: A fixed number of bits to flip for all individuals, or a number determined by a Poisson distribution for each individual.
  • Inhibitions: The mechanism of learning from past errors is referred to as "inhibitions." The strength and scope of these inhibitions are controlled by parameters like the relaxation factor (α) and tournament size for bit selection.

The paper contrasts flee-mutation with standard mutation and self-adaptive mutation, highlighting that flee-mutation's bit modifications are correlated by the EC-memory (VL), unlike independent modifications in self-adaptive mutation.

Datasets

The paper evaluates its approach on six functions from {0,1}^900, which are binary and Gray encodings of three numerical functions (F1, F2, F3) defined over 100 numerical variables. These functions are designed to be challenging optimization problems. The paper notes that these problems are taken from a previous work by Baluja (1995).

Key Insights and Ideas

  • Learning from Failure is Powerful: The most significant insight is that explicitly learning from and avoiding past evolutionary errors (represented by the "virtual loser") can be more effective than solely focusing on past successes.
  • "Civilized Evolution": This approach embodies a "civilized evolution" where knowledge (in this case, knowledge of what not to do) is acquired and used to guide the evolutionary process, potentially speeding it up.
  • Flee-Mutation as a Hybrid: Flee-mutation blends aspects of mutation (bit flipping) and recombination (bias from population data), but with a novel directionality guided by past failures.
  • Constant Flee Step Size is Desirable: Surprisingly, the experiments suggest that a constant flee-mutation step size (M) across the population, rather than varying it per individual (e.g., via Poisson distribution), leads to better results. This implies that a consistent level of exploration/exploitation is beneficial.
  • Decreasing Step Size Over Time: Similar to other EC approaches, a decreasing flee step size over generations (hyperbolic schedule) generally improves performance, allowing for broader exploration early on and finer tuning later.

Key Results

  • Improved Performance: Flee-mutation, particularly with a decreasing step size over generations and a constant step size within the population, significantly outperforms standard GAs and ESs on the tested problems. It also shows improvements over PBIL (a population-based learning algorithm).
  • Onemax-like Function Exception: The approach performs exceptionally well on the Onemax-like F3 Gray function, achieving near-optimal results.
  • Flee-Mutation vs. Free-Mutation: Flee-mutation (with inhibitions) consistently outperforms "free-mutation" (which uses void inhibitions, effectively acting like standard mutation with a VL set to 0.5), demonstrating the utility of learning from errors.
  • Parameter Sensitivity: The paper notes that the flee step size (M) is a critical parameter that requires careful tuning, though the other parameters (related to inhibitions) were found to be relatively robust.

Limitations and Future Work

  • Parameter Tuning: The authors acknowledge that determining the optimal value for the flee step size (M or M°) remains an open question.
  • Artificial Test Functions: The authors suggest that the observed gains might be an artifact of the artificial test functions used and that performance on more complex, less regular binary functions needs further investigation.
  • Limited Inhibition Strength: The strength and scope of inhibitions were intentionally kept low in the experiments. Future work will explore increasing these to see their impact.
  • Continuous Search Spaces: Extending flee-mutation to continuous search spaces is a key future direction.
  • Dual Memory Systems: The authors propose investigating a scheme that combines memory of errors (inhibitions) with memory of successes (motivations), potentially leading to even better performance.
  • Fitness Distance Correlation: The paper suggests using insights from Fitness Distance Correlation to aid in setting the flee step size.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{sebag1997toward,
  author = {Michèle Sébag and Marc Schoenauer and Caroline Ravisé},
  title = {{Toward civilized evolution: developping inhibitions}},
  booktitle = {HAL},
  year = {1997},
}
Figure