Many-objective Optimization via Voting for Elites

Jackson Dean, Nick Cheney

TL;DR

MOVE is a novel evolutionary algorithm that tackles the "curse of dimensionality" in many-objective optimization by maintaining a map of "elites" that specialize in random subsets of objectives. By allowing solutions to "goal-switch"—jumping between different objective niches—the algorithm discovers intermediate stepping stones that lead to high performance across all objectives simultaneously.

What Problem Does This Paper Address?

In the real world, we often want to optimize for many things at once (e.g., a car that is fast, safe, cheap, and fuel-efficient). Traditional Multi-Objective Optimization (MOO) works well for 2 or 3 objectives using Pareto fronts, but as the number of objectives grows (becoming "Many-objective"), the math breaks down. The population size needed to maintain a Pareto front scales exponentially, making it computationally impossible.

Existing workarounds usually involve "collapsing" objectives into a single weighted sum, but this requires knowing the relative importance of each goal beforehand. The authors aim to find a way to optimize dozens of objectives without needing prior knowledge of their trade-offs or massive population sizes.

Methods

The authors introduce MOVE (Many-objective Optimization via Voting for Elites), which draws inspiration from the MAP-Elites algorithm used in Quality Diversity (QD) research.

  1. The Map: Instead of a single population, MOVE maintains a grid (map) of cells. Each cell is assigned a random subset of the total objectives (e.g., if there are 14 total objectives, a cell might only care about 3 specific ones).
  2. The Voting Mechanism: To determine if a new "child" solution should replace the current "elite" in a cell, the child must win a majority vote. It is compared against the elite on each of the cell’s assigned objectives; if it performs better on more than half, it takes the elite's place.
  3. Goal-Switching (Jumping): This is the key innovation. When a child is born, it isn't just compared to its parent's cell. It is compared against the elites in every cell. If it’s better at a different subset of objectives than its parent was, it "jumps" to that new niche.
  4. Encoding: The researchers used Compositional Pattern Producing Networks (CPPNs) to evolve images, a common benchmark in neuroevolution known for having many deceptive local optima.

Datasets

The paper evaluates MOVE on an image-reconstruction task.

  • Target Images: A sunrise, a dolphin, and a skull.
  • Metrics: The "objectives" are 14 different Image Quality Assessment (IQA) metrics from the PyTorch Image Quality (PIQ) library. These include standard metrics like Mean Squared Error (MSE) and PSNR, as well as complex perceptual metrics like SSIM, LPIPS, and HaarPSI.

Key Insights and Ideas

  • Implicit Curriculum Learning: By optimizing for subsets of objectives, MOVE effectively breaks a massive problem into simpler sub-problems. A solution might get "good" at texture (one subset) before jumping to a cell that cares about both texture and color.
  • The Necessity of Jumps: The authors found that 96% to 98% of successful offspring replaced elites in cells other than their parent's. Without this "goal-switching" ability, performance plummeted.
  • Synergy over Competition: Surprisingly, MOVE performed as well as (or better than) single-objective hillclimbers on 9 out of 14 metrics. This suggests that searching for many objectives at once can actually make the search easier by providing diverse pathways to the solution, rather than harder.
  • Efficiency: While Pareto optimization for 14 objectives would theoretically require a population of over 8,000, MOVE achieved superior results with a population (map size) of just 50 to 100.

Key Results

  • Superiority over Baselines: MOVE significantly outperformed an "all-objective" hillclimber (which tries to optimize the average of all 14 metrics at once).
  • Optimal Specialization: The best performance came when each cell focused on 3 to 5 objectives. Too few objectives (1) didn't provide enough direction; too many (11) made it too hard for children to "win the vote" and replace elites.
  • Lineage Diversity: By tracking the "ancestry" of the final champion solution, the researchers found that its ancestors had occupied nearly 50% of all the different niches in the map during the evolutionary process.

Limitations and Future Work

  • Objective Alignment: The 14 IQA metrics used are somewhat "aligned" (they all generally want the image to look like the target). The authors acknowledge that MOVE might behave differently if objectives were strictly anti-correlated or "adversarial."
  • Hyperparameter Sensitivity: The number of functions per cell and the map size were tuned to specific images. It is unclear how these settings generalize to entirely different domains (like robotics or circuit design).
  • Lack of Recombination: The current version of MOVE only uses mutation. The authors suggest that adding crossover (combining two successful elites) could further improve the search.
  • Static Subsets: Currently, the subsets of objectives for each cell are fixed at the start. Future versions could potentially evolve the objective groupings themselves.

Summary updated

Abstract

Real-world problems are often comprised of many objectives and require solutions that carefully trade-off between them. Current approaches to many-objective optimization often require challenging assumptions, like knowledge of the importance/difficulty of objectives in a weighted-sum single-objective paradigm, or enormous populations to overcome the curse of dimensionality in multiobjective Pareto optimization. Combining elements from Many-Objective Evolutionary Algorithms and Quality Diversity algorithms like MAP-Elites, we propose Many-objective Optimization via Voting for Elites (MOVE). MOVE maintains a map of elites that perform well on different subsets of the objective functions. On a 14-objective image-neuroevolution problem, we demonstrate that MOVE is viable with a population of as few as 50 elites and outperforms a naive single-objective baseline. We find that the algorithm's performance relies on solutions jumping across bins (for a parent to produce a child that is elite for a different subset of objectives). We suggest that this type of goal-switching is an implicit method to automatic identification of stepping stones or curriculum learning. We comment on the similarities and differences between MOVE and MAP-Elites, hoping to provide insight to aid in the understanding of that approach - and suggest future work that may inform this approach's use for many-objective problems in general.
BibTeX
@inproceedings{dean2023many,
  author = {Jackson Dean and Nick Cheney},
  title = {{Many-objective Optimization via Voting for Elites}},
  booktitle = {GECCO Companion},
  year = {2023},
  url = {https://openreview.net/forum?id=7PaQcSfTXw},
}

Loading related content...

Figure