Productive fitness in diversity-aware evolutionary algorithms

Thomas Gabor, Thomy Phan, Claudia Linnhoff-PopienNat. Comput 2021 · DOI · OpenReview

Introduction

In the field of Evolutionary Algorithms (EAs), a long-standing paradox exists: algorithms that prioritize diversity—often at the expense of immediate progress toward a goal—frequently find superior solutions compared to those that focus solely on the objective function. While the benefits of balancing exploration and exploitation are well-recognized, a formal theoretical explanation for why diversity-aware search outperforms direct optimization has remained elusive. This paper introduces Productive Fitness (PF), a novel metric designed to quantify the long-term evolutionary value of individuals.

The Problem: The Deceptive Nature of Objective Functions

Standard EAs guide search using an objective function, a score representing current performance. However, early in a search, the objective function can be a "liar," rewarding individuals that reach local optima while penalizing those on a slower, more productive path toward the global optimum. The fundamental question addressed here is: if the objective function is not the ideal signal to optimize, what is?

Methodology: Productive Fitness

The authors propose a framework centered on two concepts:

  1. Productive Fitness (PF): The value of an individual $x$ is defined by the average objective score of its descendants $n$ generations later.
  2. Final Productive Fitness (FPF): The value an individual contributes to the final generation of an evolutionary run.

While FPF is uncomputable during a run (as it requires knowledge of the future), it serves as a powerful a posteriori diagnostic tool. By analyzing successful runs, the authors evaluate how closely various fitness functions—standard and diversity-augmented—approximate this "ideal" but hidden signal.

Experimental Setup

The theory was tested across three benchmark problems designed to challenge standard optimization:

  • Pathfinding: A 2D robot navigation task involving a large central obstacle that acts as a local optimum trap.
  • Route Planning: A discrete optimization problem with non-Euclidean distances.
  • Schwefel Function: A high-dimensional benchmark with numerous deceptive local optima.
The Pathfinding benchmark: a robot must navigate around a central obstacle to reach the target, a task where greedy optimization often fails.

Key Insights and Results

The research demonstrates that diversity-aware algorithms succeed because they more accurately approximate the Final Productive Fitness. By rewarding individuals for being different, these algorithms implicitly preserve lineages with high long-term potential that would otherwise be pruned by a "greedy" objective function.

Performance and Stability

In the Pathfinding and Schwefel tasks, diversity-aware EAs significantly outperformed standard approaches. Specifically, the "Manhattan-diverse" approach maintained a stable relationship with the FPF, whereas standard EAs often saw their most productive lineages die out early.

Comparison of best fitness over time across different EA configurations. Diversity-aware methods (notably the blue trend) achieve significantly higher final performance.

Lineage Continuity

Analysis of evolutionary lineages revealed that diversity-aware methods maintain a "continuous lineage" from the initial population to the final solution. In contrast, standard methods frequently experience "lineage breaks," where the eventual winner emerges from a lineage that was previously considered low-performing by the raw objective function.

Conclusion and Future Work

Productive Fitness provides a formal lens through which to understand the success of diversity in evolution. It suggests that diversity is not just a heuristic for exploration, but a necessary component for approximating the true long-term value of a solution.

Future research will focus on developing surrogate models to predict productive fitness in real-time and exploring dynamic tuning mechanisms that adjust diversity weights based on the stability of the PF signal. This perspective may also offer insights into other search-based domains, such as Monte-Carlo Tree Search and Simulated Annealing.

Summary updated

Abstract

In evolutionary algorithms, the notion of diversity has been adopted from biology and is used to describe the distribution of a population of solution candidates. While it has been known that maintaining a reasonable amount of diversity often benefits the overall result of the evolutionary optimization process by adjusting the exploration/exploitation trade-off, little has been known about what diversity is optimal. We introduce the notion of productive fitness based on the effect that a specific solution candidate has some generations down the evolutionary path. We derive the notion of final productive fitness, which is the ideal target fitness for any evolutionary process. Although it is inefficient to compute, we show empirically that it allows for an a posteriori analysis of how well a given evolutionary optimization process hit the ideal exploration/exploitation trade-off, providing insight into why diversity-aware evolutionary optimization often performs better.
BibTeX
@article{gabor2021productive,
  author = {Thomas Gabor and Thomy Phan and Claudia Linnhoff-Popien},
  title = {{Productive fitness in diversity-aware evolutionary algorithms}},
  journal = {Nat. Comput.},
  year = {2021},
  doi = {10.1007/s11047-021-09853-3},
}
Figure