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 multi-objective 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.
Introduction
In many real-world engineering and design scenarios, success is defined by the simultaneous optimization of numerous, often conflicting, objectives. For instance, designing a vehicle requires balancing speed, safety, cost, and fuel efficiency. Traditional Multi-Objective Optimization (MOO) typically relies on Pareto fronts to navigate these trade-offs. However, as the number of objectives increases—transitioning into "many-objective" optimization—these methods encounter the "curse of dimensionality." The population size required to maintain a representative Pareto front scales exponentially, rendering traditional MOO computationally prohibitive for dozens of objectives.
Common workarounds, such as collapsing objectives into a single weighted sum, require a priori knowledge of the relative importance of each goal, which is often unavailable. To address these challenges, we introduce Many-objective Optimization via Voting for Elites (MOVE), an evolutionary framework that leverages the principles of Quality Diversity (QD) to optimize many objectives without requiring massive populations or pre-defined weights.
The MOVE Framework
MOVE draws inspiration from the MAP-Elites algorithm, which is traditionally used to find a diverse set of high-performing solutions across a feature space. MOVE adapts this structure for many-objective optimization through three core mechanisms:
1. The Map of Niches
Instead of maintaining a single global population, MOVE utilizes a map of cells. Each cell is assigned a random subset of the total objectives. For example, in a problem with 14 objectives, a specific cell might be dedicated to optimizing only three specific metrics. This allows the algorithm to maintain "specialists" across various combinations of goals.
2. The Voting Mechanism
To determine if a new candidate solution (a "child") should replace an existing "elite" in a cell, MOVE employs a majority vote. The child is compared against the current elite on each of the objectives assigned to that cell. If the child outperforms the elite on more than half of those objectives, it takes the elite's place in the map.
3. Goal-Switching (Jumping)
A critical innovation in MOVE is the ability for solutions to "jump" between niches. When a child is generated, it is not merely compared to its parent’s cell; it is evaluated against the elites in every cell in the map. If the child proves superior for a different subset of objectives than its parent, it migrates to that new niche. This mechanism allows the search to discover intermediate stepping stones, where progress in one area of the objective space facilitates breakthroughs in another.
Experimental Design
We evaluated MOVE on an image-reconstruction task using Compositional Pattern Producing Networks (CPPNs), a common neuroevolution benchmark known for its deceptive local optima. The task involved evolving images to match three distinct targets: a sunrise, a dolphin, and a skull.
To simulate a many-objective environment, we utilized 14 different Image Quality Assessment (IQA) metrics from the PyTorch Image Quality (PIQ) library. These included standard mathematical metrics like Mean Squared Error (MSE) and Peak Signal-to-Noise Ratio (PSNR), alongside complex perceptual metrics such as Structural Similarity Index (SSIM), Learned Perceptual Image Patch Similarity (LPIPS), and Haar Perceptual Similarity (HaarPSI).
Key Insights and Results
Overcoming the Curse of Dimensionality
While theoretical Pareto optimization for 14 objectives would require a population exceeding 8,000 individuals, MOVE achieved superior results with a population (map size) of just 50 to 100 elites. This represents a significant increase in computational efficiency for many-objective problems.
The Power of Goal-Switching
Our analysis revealed that "jumping" is essential to MOVE’s success. Between 96% and 98% of successful offspring replaced elites in cells other than those of their parents. By tracking the lineage of the final champion solutions, we found that their ancestors had occupied nearly 50% of all available niches during the evolutionary process. This suggests that MOVE performs a form of implicit curriculum learning, where solutions evolve through a sequence of simpler sub-problems before reaching high performance across the full objective set.
Optimal Specialization
We found that the degree of specialization per cell significantly impacts performance. The best results occurred when each cell focused on 3 to 5 objectives. Focusing on a single objective per cell provided insufficient direction, while focusing on too many (e.g., 11) made it too difficult for new candidates to win the majority vote and replace existing elites.
Synergy in Search
MOVE outperformed a naive single-objective hillclimber (which optimized the average of all 14 metrics) on 9 out of 14 metrics. This suggests that searching for many objectives simultaneously can actually make the search easier by providing diverse pathways to the global optimum, rather than complicating the landscape.
Conclusion and Future Work
MOVE demonstrates that many-objective optimization can be effectively managed by maintaining a diverse population of niche specialists. By allowing solutions to switch goals and jump between objective subsets, the algorithm identifies the necessary stepping stones to solve complex, high-dimensional problems.
Future research will explore the performance of MOVE in domains where objectives are strictly anti-correlated or adversarial, such as robotics or circuit design. Additionally, we aim to investigate the impact of adding recombination (crossover) and dynamic objective grouping to further enhance the search capabilities of the MOVE framework.
Summary updated