Abstract
In any search via artificial evolution, the likelihood of stagnation at local optima is determined by the particular choices of representation and search operators. Because the performance impact of these design choices is difficult to predict, it is an attractive option to let the representation and/or operators themselves evolve. However, effective evolution at this meta-level can be difficult to achieve for a number of reasons, including: (1) The complexity of the search space is increased; and (2) selection acts at the level of the fitness function and only indirectly at the meta-level, favoring variations only to the extent to which they are stochastically associated with fitness improvements. This paper investigates the conditions under which the evolution of representation and operators is most effective, specifically focusing on the interplay between self-adapting mutation rates and dynamic fitness functions.
Introduction
The success of evolutionary computation is often contingent on the careful tuning of "meta-parameters," most notably the mutation rate. A high mutation rate risks turning the search into a disorganized random walk, while a rate that is too low causes the population to stagnate at the first local optimum it encounters.
To solve this, researchers often turn to self-adaptation, where the mutation rate is treated as an evolvable trait alongside the solution itself. However, this introduces a meta-level selection problem: because selection acts on fitness rather than the mutation rate directly, the algorithm may inadvertently favor "conservative" individuals with near-zero mutation rates, trapping the population in sub-optimal regions.
The Conservative Trap in Meta-Evolution
The primary obstacle in self-adaptive evolution is what the authors identify as a specific failure mode: the "conservative trap." When a population reaches a broad local optimum, individuals with low mutation rates are statistically more likely to produce offspring that remain on that peak. In contrast, individuals experimenting with higher mutation rates are more likely to produce offspring that "fall off" the peak into lower-fitness regions.
This creates a feedback loop where selection pressure drives mutation rates toward zero. Once the mutation rate vanishes, the population loses the diversity required to explore the landscape further, effectively "nestling" into a sub-optimal hole with no mechanism for escape.
Methodology: Per-Weight Adaptation and Dynamic Fitness
To address these challenges, the research utilizes an Artificial Neural Network (ANN) framework where the objective is to minimize the sum-of-squared error (SSE) for a target function. Two primary mechanisms are introduced:
1. Per-Weight Self-Adaptation
Instead of a global mutation rate, a unique, variable mutation rate is associated with each individual weight in the network. This allows the evolutionary process to focus "search energy" on specific, high-impact weights while maintaining stability in parts of the network that have already been optimized.
2. Dynamic Fitness Functions
To counter the tendency of mutation rates to drop to zero, a dynamic fitness scheme is implemented. Rather than using a static SSE, an individual’s fitness ($f_i$) is calculated relative to the population's performance on specific training examples:
$$f_i = \sum_j \frac{1 - e_{ij}^2}{n - \sum_k e_{kj}^2}$$
In this equation, $e_{ij}$ represents the error of individual $i$ on example $j$, and the denominator represents the aggregate performance of the entire population on that example. This formulation ensures that individuals who solve "hard" examples—those that the rest of the population is failing—receive a higher fitness reward. By making fitness a moving target, the authors create a competitive environment where the "value" of a local optimum decreases as more individuals cluster there.
Results: The Power of Hybrid Strategies
The study found that while per-weight self-adaptation was beneficial, particularly when only a small subset of weights required tuning, it was not sufficient on its own to prevent stagnation. The most significant breakthrough came from a hybrid strategy that balances exploration and exploitation.
The optimal approach involved two distinct phases:
- Exploration Phase: The search begins with the dynamic fitness function. This maintains high mutation rates by constantly shifting the selective pressure toward unsolved parts of the function, preventing the population from stagnating.
- Exploitation Phase: Once the average error drops below a specific threshold, the algorithm switches to a static fitness function (standard SSE). This allows for the precise fine-tuning of weights necessary to reach a global minimum.
This hybrid method successfully "popped" populations out of premature local optima that would have otherwise trapped a standard self-adaptive algorithm.
Limitations and Future Directions
Despite the success of the hybrid approach, several challenges remain. The strategy currently relies on a pre-set threshold to trigger the switch from dynamic to static fitness; automating this transition remains a challenge. Additionally, the dynamic fitness calculation introduces computational overhead, as it requires tracking the performance of the entire population across all training examples. Finally, while effective on simple target functions, the scalability of this approach to high-dimensional, complex deep learning architectures remains to be tested.
Conclusion
Self-adaptation is a powerful tool for evolutionary search, but it requires a dynamic environment to be effective. By making fitness a "moving target," researchers can prevent the premature collapse of mutation rates and ensure that the evolutionary process maintains the diversity needed to navigate complex fitness landscapes.
Summary updated