# Many-objective Optimization via Voting for Elites

Jackson Dean  0009-0007-3276-1890<EMAIL_ADDRESS>University of
VermontBurlingtonVermontUSA05401 and  Nick Cheney  0000-0002-7140-2213
<EMAIL_ADDRESS>University of VermontBurlingtonVermontUSA05401

(2023)

###### 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.

Neuroevolution, Indirect Encoding, CPPN, Many-Objective Optimization, MAP-
Elites, Stepping Stones

††copyright: acmcopyright††journalyear: 2023††doi:
10.1145/3583133.3590693††conference: the Genetic and Evolutionary Computation
Conference 2023; July 15–19, 2023; Lisbon, Portugal††price: 15.00††isbn:
79-8-4007-0120-7/23/07

##  1\. Introduction

Complex real-world optimization problems often require solutions that
carefully balance non-linear and non-intuitive trade-offs between many
competing objectives. As a result, evolutionary algorithms excel at finding
solutions to multi-objective problems, with approaches such as Pareto
optimization able to simultaneously explore a wide range of trade-offs between
objectives and optimize each goal synergistically, in spite of, or agnostic to
other competing objectives (Deb, 2011).

However evolving solutions to many-objective problems becomes increasingly
challenging as the number of objectives grows (Coello et al., 2007). The
population size required to maintain Pareto fronts scales exponentially and
quickly becomes computationally infeasible (Deb et al., 2005; Ishibuchi et
al., 2008). Alternative approaches that collapse the many objectives down into
a single weighted-sum objective or optimize them on a schedule may not
properly weight/order each objective in the aggregate fitness
function/schedule, as doing so would require knowledge of the dynamics and
trade-offs between the objectives a priori (Gomez and Miikkulainen, 1997).
Existing approaches to optimize many-objectives (see (Chand and Wagner, 2015)
for a review) often assume that this privileged knowledge is available and
assign different weights to the objectives.

Pareto dominance is the traditional way to compare solutions on multiple
objectives without weighting (Deb, 2011). Existing algorithms, such as NSGA-II
(Deb et al., 2002) and SPEA2 (Zitzler et al., 2001), are effective at
approximating a theoretical Pareto front (the set of non-dominated solutions)
when there are few objectives. However, extrapolating from the population
sizes determined in (Pan et al., 2017), we estimate that we would need a
population of over 8000 to optimize our 14 objectives via Pareto optimization.
A previous attempt to improve on Pareto dominance for use with many objectives
is PPD-MOEA which uses partial Pareto dominance on subsets of objectives (Sato
et al., 2010). Unlike our approach, PPD-MOEA uses two subsets, the ordering of
objectives is fixed and predetermined, and is only tested up to 10 objectives.

Determining the attributes of goals that lead to intermediate _stepping
stones_ towards a complex solution is a significant challenge for evolutionary
algorithms (Lehman and Stanley, 2011a; Woolley and Stanley, 2011). Open-ended
novelty-seeking and Quality Diversity algorithms similarly seek to explore a
diversity of novel solutions in hopes of discovering promising stepping
stones, and may combine this with a pressure to become highly fit within a
wide variety of behavioral/phenotype niches (Pugh et al., 2016; Lehman and
Stanley, 2011b; Pugh et al., 2015; Cully and Demiris, 2017; Lehman et al.,
2008; Secretan et al., 2008; Stanley et al., 2017; Soros and Stanley, 2014;
Stanley et al., 2016).

MAP-Elites (Mouret and Clune, 2015) is popular _quality diversity_ algorithm
with a map of discrete cells which each represent a phenotypic behavioral
characteristic. Each cell maintains a member of the population, the top
performing (elite) individual on a global objective function that matches the
subset of behavior characteristics assigned to that cell. This approach
generates significant Quality Diversity, while implicitly overcoming the
problem of determining stepping stones or learning curriculum order, as
offspring for any given subset of the phenotypic space compete to become the
elite in every other cell within the map – constantly goal-switching to find
potential stepping stones that may enable them to perform well on other
phenotypic subsets (Gaier et al., 2019; Nguyen et al., 2015). Multi-Objective
MAP-Elites (Pierrot et al., 2022) fills each cell in the behavior map with a
Pareto front rather than a single individual. Unlike in our work, each cell
corresponds with a unique behavior descriptor and optimizes all objectives
simultaneously.

##  2\. Approach

Inspired by these approaches, we introduce a new variation of the MAP-Elites
algorithm for optimizing many-objective search problems. Our approach, Many-
objective Optimization via Voting for Elites (MOVE), defines each cell within
a map as a subset of the many objectives that make up the overall search
problem, and maintains a map of elites that are the best solutions found for
each objective-combination in the map (Fig. A3). While this approach inherits
the structure, goal-switching, and diverse stepping-stones of the above
approaches, its goal of finding the single optimal solution for the many-
objective problem means that it is not exactly a quality diversity algorithm.
Quality diversity algorithms seek to maximize the sum of fitness across all
cells (phenotypic niches) in the map, while MOVE is more similar to approaches
which construct building blocks that all ultimately lead to a single aggregate
solution (Forrest and Mitchell, 1993) as it explores many different subsets of
the possible trade-offs and relationships between objectives in parallel.

In MOVE, the population of genomes is stored in a map of cells. Each cell is
assigned a fixed number of fitness functions selected randomly from all
possible combinations. Every cell contains up to one elite, the most fit
solution found thus far on the objectives in that cell. During selection and
reproduction, each elite produces one child, a mutated copy of itself. For
every cell on the map, each child is compared to the current elite by summing
the number of fitness functions (of the cell’s assigned functions) on which
the child scores higher than the elite. If the child earns more than half of
these ‘votes’, it replaces the elite. Further intuition for MOVE is provided
in Appendix A and a full implementation is available at github.com/uvm-
neurobotics-lab/MOVE.

While this generic algorithm is agnostic to the particular type of solution
being evolved, here we use a 14-dimensional optimization problem known to be
fraught with local optima (Woolley and Stanley, 2011): target image generation
via Compositional Pattern Producing Networks (Stanley, 2007). In the
experiments below we set out to evolve synthetic images which maximize 14
different Image Quality Assessment metrics from the PyTorch Image Quality
(PIQ) library (Kastryulin et al., 2022) (Appendix A.3).

This approach allows evolution to exploit goal-switching, since a solution
that performs well on one fitness function may produce offspring that perform
well on different fitness functions. Unlike traditional scheduling approaches,
no information about the ideal order of tasks is required as the algorithm
designer does not have to choose when solutions jump between cells.

Results reported here employ the target image in Fig. 1. Results from
additional target images are reported in Appendix C. Each condition includes
20 trials of 1000 generations. Unless otherwise noted, each trial used a map
(i.e. population size) of 100 cells. We evaluate significance via a Wilcoxon
rank-sum test with $\alpha=0.05$.

To analyze how MOVE compares with a naive multi-objective approach, we
conducted two baseline experiments: Single-objective hillclimbers each
optimize only one of the 14 objectives. Each of the 14 hillclimbers produce 7
children per generation, approximating the computational costs of MOVE. The
all-objective hillclimber control consist of a single hillclimber with 100
children per generation, resulting in the same total compute as MOVE. The
fitness of a given image is the mean normalized fitness of all 14 objectives,
as is the case in a traditional multi-term fitness function.

##  3\. Results

Figure 1. Target image (left) and examples of evolved images under different
experimental conditions. See Appendix A for baselines results and additional
target images.

Images

Functions |  Total unique | Cells | Jumps | Total | Jump | Champion
---|---|---|---|---|---|---
per cell | solutions | in ancestry | in ancestry | replacements | proportion | fitness
1 | 12.75 | 6.73 | 24.57 | 261 | 47.43% | 1.10
3 | 40.95 | 38.59 | 69.33 | 36,199 | 96.36% | 1.22
5 | 30.90 | 48.67 | 100.85 | 41,283 | 97.40% | 1.19
7 | 22.30 | 40.08 | 84.18 | 28,891 | 97.78% | 1.21
9 | 16.10 | 38.85 | 94.2 | 28,092 | 98.30% | 1.20
11 | 11.75 | 32.27 | 101.36 | 22,665 | 98.55% | 1.15

Table 1. Statistics on the movement, diversity, and performance of solutions
as a function of objectives per cell. The highest value (and those not
significantly different from it) in each column are bold.

Statistics about the movement, performance, and diversity of solutions.

Figure 2. The most fit image across all objectives (left) and the most fit
image on each individual objective function (remaining 14). All single-
objective values are normalized relative to the single-objective hillclimber,
while the all-objective result is normalized relative to the all-objective
hillclimber.

Max fitness by objective function.

###  3.1. Functions per cell

While the general concept and flow of the MOVE algorithm is straightforward to
describe, its ideal implementation and the impact of such decisions on
performance relative to existing baselines are largely uncertain. Firstly, it
is not immediately clear how many objectives should be in each subset. Having
more functions per cell would lead each subset to more closely approximate the
full many-objective problem, while having fewer functions per cell would
enable greater diversity across cells and potentially simpler subproblems to
solve with fewer competing trade-offs in each. Here we explore subsets of 1,
3, 5, 7, 9, and 11 random objective functions per cell. Only odd numbers of
functions were included to avoid ties.

With any number of functions per cell, MOVE results in a significantly higher
final overall fitness than the all-objective hillclimber (all $p<0.01$; Table
1). The top performer according to overall fitness average across all 14
functions is the setting with 3 functions per cell, but it was not
significantly better than 5, 7, or 9.

As the number of objective functions per cell grow, the number of objectives
that any two cells have in common is expected to increase. Thus one might
expect it to become easier for an offspring to goal-switch with more functions
per cell and perform well on a different cell than its parent. In all cases,
parents were far more likely to produce offspring that replaced other cells in
the map than themselves (Table 1). If replacements happened randomly to each
of the 100 cells, 99% would be to a new (non-parent) cell. With 11 functions
per cell, we see 98.55% of replacements jumping cells. Even with just 3
functions per cell, we already see 96.26% of cells replacing a parent other
than their own, suggesting both the importance of goal switching above
replacing parents – and perhaps the potential of this algorithm to find many
unique stepping stones and learning trajectories towards an ultimate solution.

Looking at the diversity within search, the total number of unique solutions
across the 100 cells at the end of training was highly correlated with the
number of functions per cell – with 3 func./cell resulting in the greatest
unique solutions ($p<0.001$) and diversity of this final population dropping
as func./cell increase.

All trials in Table. 1 employ 100 cells, but we also ran experiments with 25,
50 cells. With 5 functions per cell, MOVE worked just as well with 50 cells
but worse with 25 (Appendix A.4), suggesting the potential even further
computational savings than provided here.

###  3.2. Goal-switching

The results from the number of functions per cell experiments suggest that an
important feature of MOVE is the ability of offspring to replace cells other
than their parent cell. We hypothesized that this allows MOVE to find stepping
stones and escape local optima along the path of any one cell in isolation. To
investigate further, we conduct an ablation study that tests the importance of
switching between cells in the map. We explore three experimental conditions
in which children were eligible to replace a different set of elites.

No jumping: children can only replace their parents. This is functionally
similar to 100 parallel hillclimbers. One jump: children can replace any cell,
including their parent, but only one. If a child is eligible to replace
multiple elites, the one that lost the vote by the largest margin is chosen.
Unlimited jumping: children can replace any cell and replace multiple cells
each generation.

With 5 functions/cell, allowing unlimited jumping (all-objective fitness:
1.19) or a one jump (1.18) significantly increased performance compared with
no jumping (1.09). Allowing multiple jumps per offspring was the same (for 1,
7, and 9 functions per cell) or better (for 3, 5, and 11 functions per cell).
These data support the hypothesis that MOVE benefits from the ability to goal-
switch.

Furthermore, when an elite produced a surviving offspring, the replaced cell
shared significantly more functions with the parent cell than would be
expected from two random cells (Appendix B.2), suggesting that shared
objectives do enable increased goal-switching. Additionally, with 5 functions
per cell, the path taken by the ancestors of a final solution included almost
half of all the cells in the map on average, suggesting that a wide variety of
cells serve as stepping stones en route to a final solution (Table 1, Appendix
B).

###  3.3. By function

Table 1 demonstrated that MOVE can achieve a higher mean performance across
all objectives at once than an all-objective hillclimber attempting to
optimize an aggregate function of all objectives. But how does this translate
to performance on the individual objectives? In Fig. 2, we compare the
performance of MOVE (5 fn/cell; with unlimited jumping) to the all-objective
hillclimber, and also to each single-objective hillclimber on how well each
algorithm performs on each single objective. MOVE significantly outperforms
the aggregate hillclimber training on 13 of the 14 objectives.

Surprisingly, MOVE also performs as well as, or better, than the single-
objective hillclimber which does not have to compromise on any trade-offs
between objectives on 9 of the 14 objective functions. This suggests that not
only is MOVE able to overcome the trade-offs between objectives, it is able to
find synergistic relationships between the different objectives and identify
stepping stones to make the 14-dimensional many-objective optimization problem
even easier than solving 14 independent single-objective searches.

##  4\. Discussion

This paper offers a proof-of-concept for a novel way to optimize many-
objectives, and tests the approach on an image neuroevolution problem. Our
method maintains solution diversity by separating a many-dimensional fitness
landscape into parallel, but not fully independent, searches on smaller-
dimensional spaces. Rather than maintaining a single many-dimensional Pareto
front, MOVE stores a population of elites which each perform well on a
different subset of the objective functions. This allows MOVE to successfully
find stepping stones while maintaining a much smaller population than would be
necessary in traditional Pareto optimization.

This study finds important relationships between hyperparameters of this model
and its overall performance. The number of objectives per cell influenced
overall aggregate fitness found, the propensity of offspring to replace their
parents within the same cell vs goal-switching to become the elite in a new
cell, and the diversity of solutions found (Table 1).

Much like MAP-Elites (Mouret and Clune, 2015) and Innovation Engines (Nguyen
et al., 2015), one of the driving forces behind the success of MOVE is the
ability of solutions to jump between cells and generate their own trajectories
of stepping stones over time (as seen in Appendix A3). We find that final
solutions have used as many as 48% of the cells in the map as stepping stones
throughout their evolutionary trajectory – switching goals as many as 100
times over the course of evolution (Table 1), and that removing the ability of
MOVE to goal-switch across cells significantly hinders performance (Table 1).
These migrations between cells evolving in parallel for different goals is
also reminiscent of migration in island models (Skolicki and De Jong, 2005).
The ease and order of jumps between cells may also inform weightings or
orderings for other many-objective optimization approaches.

Future extensions of MOVE may incorporate concepts from multi-objective
evolutionary algorithms, such as weighted objectives or other ways to condense
multiple objectives into a single criterion to determine the ranking of an
elite and a competing offspring in a cell. Though, in our limited
investigations, voting over objectives appeared to outperform normalized-
weighted-sum fitness functions. Random objective weightings of many or all
objectives (as opposed to the current binary inclusion of a random subset of
functions) assigned to each cell in the map could be employed as a softened
version of the voting mechanism.

The results presented in this paper are likely highly dependent on the
specific target images, encoding, and task chosen (see Appendix C for
experiments with other target images and D for discussion of potential
extensions). Future work should consider anti-correlated objectives, since
MOVE may behave differently in problems where objectives are less aligned with
one another than is the case with different Image Quality Assessment metrics
here.

Despite its simplicity, MOVE is an effective method for many-objective
optimization in this particular setting. We are curious about the potential
for this approach to generalize to the challenging problems of many-objective
optimization across various domains.

###### Acknowledgements.

This material is based upon work supported by NSF Grant No. 2218063.
Computations were performed on the Vermont Advanced Computing Core supported
in part by NSF award No. 1827314. Thanks to Rachel Gehman for helpful
brainstorming.

## References

  * (1)
  * Chand and Wagner (2015) Shelvin Chand and Markus Wagner. 2015.  Evolutionary many-objective optimization: A quick-start guide.  _Surveys in Operations Research and Management Science_ 20, 2 (2015), 35–42.
  * Coello et al. (2007) Carlos A Coello Coello, Gary B Lamont, David A Van Veldhuizen, et al. 2007\.  _Evolutionary algorithms for solving multi-objective problems_. Vol. 5.  Springer.
  * Cully and Demiris (2017) Antoine Cully and Yiannis Demiris. 2017.  Quality and diversity optimization: A unifying modular framework.  _IEEE Transactions on Evolutionary Computation_ 22, 2 (2017), 245–259.
  * Deb (2011) Kalyanmoy Deb. 2011\.  _Multi-objective optimisation using evolutionary algorithms: an introduction_.  Springer.
  * Deb et al. (2002) Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. 2002.  A fast and elitist multiobjective genetic algorithm: NSGA-II.  _IEEE transactions on evolutionary computation_ 6, 2 (2002), 182–197.
  * Deb et al. (2005) Kalyanmoy Deb, Dhish Kumar Saxena, et al. 2005\.  On finding pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems.  _Kangal report_ 2005011 (2005), 1–19.
  * Forrest and Mitchell (1993) Stephanie Forrest and Melanie Mitchell. 1993.  Relative building-block fitness and the building-block hypothesis.  In _Foundations of genetic algorithms_. Vol. 2. Elsevier, 109–126.
  * Gaier et al. (2019) Adam Gaier, Alexander Asteroth, and Jean-Baptiste Mouret. 2019\.  Are quality diversity algorithms better at generating stepping stones than objective-based search?. In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_. 115–116.
  * Gomez and Miikkulainen (1997) Faustino Gomez and Risto Miikkulainen. 1997.  Incremental evolution of complex general behavior.  _Adaptive Behavior_ 5, 3-4 (1997), 317–342.
  * Ishibuchi et al. (2008) Hisao Ishibuchi, Noritaka Tsukamoto, Yasuhiro Hitotsuyanagi, and Yusuke Nojima. 2008.  Effectiveness of scalability improvement attempts on the performance of NSGA-II for many-objective problems. In _Proceedings of the 10th annual conference on Genetic and evolutionary computation_. 649–656.
  * Kastryulin et al. (2022) Sergey Kastryulin, Jamil Zakirov, Denis Prokopenko, and Dmitry V. Dylov. 2022.  PyTorch Image Quality: Metrics for Image Quality Assessment.  https://doi.org/10.48550/ARXIV.2208.14818
  * Lehman and Stanley (2011a) Joel Lehman and Ken Stanley. 2011a.  Abandoning objectives: Evolution through the search for novelty alone.  _Evolutionary computation_ 19, 2 (2011), 189–223.
  * Lehman and Stanley (2011b) Joel Lehman and Kenneth O Stanley. 2011b.  Evolving a diversity of virtual creatures through novelty search and local competition. In _Proceedings of the 13th annual conference on Genetic and evolutionary computation_. 211–218.
  * Lehman et al. (2008) Joel Lehman, Kenneth O Stanley, et al. 2008\.  Exploiting open-endedness to solve problems through the search for novelty.. In _ALIFE_. 329–336.
  * Mouret and Clune (2015) Jean-Baptiste Mouret and Jeff Clune. 2015.  Illuminating search spaces by mapping elites.  _arXiv preprint arXiv:1504.04909_ (2015).
  * Nguyen et al. (2015) Anh Nguyen, Jason Yosinski, and Jeff Clune. 2015\.  Innovation engines: Automated creativity and improved stochastic optimization via deep learning. In _Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation_. 959–966.
  * Pan et al. (2017) Linqiang Pan, Cheng He, Ye Tian, Yansen Su, and Xingyi Zhang. 2017.  A region division based diversity maintaining approach for many-objective optimization.  _Integrated Computer-Aided Engineering_ 24, 3 (2017), 279–296.
  * Pierrot et al. (2022) Thomas Pierrot, Guillaume Richard, Karim Beguir, and Antoine Cully. 2022.  Multi-objective quality diversity optimization. In _Proceedings of the Genetic and Evolutionary Computation Conference_. 139–147.
  * Pugh et al. (2016) Justin K Pugh, Lisa Soros, and Kenneth O Stanley. 2016\.  Quality diversity: A new frontier for evolutionary computation.  _Frontiers in Robotics and AI_ (2016), 40.
  * Pugh et al. (2015) Justin K Pugh, Lisa B Soros, Paul A Szerlip, and Kenneth O Stanley. 2015.  Confronting the challenge of quality diversity. In _Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation_. 967–974.
  * Sato et al. (2010) Hiroyuki Sato, Hernán E Aguirre, and Kiyoshi Tanaka. 2010.  Pareto partial dominance MOEA and hybrid archiving strategy included CDAS in many-objective optimization. In _IEEE Congress on Evolutionary Computation_. IEEE, 1–8.
  * Secretan et al. (2008) Jimmy Secretan, Nicholas Beato, David B D Ambrosio, Adelein Rodriguez, Adam Campbell, and Kenneth O Stanley. 2008.  Picbreeder: evolving pictures collaboratively online. In _Proceedings of the SIGCHI conference on human factors in computing systems_. 1759–1768.
  * Skolicki and De Jong (2005) Zbigniew Skolicki and Kenneth De Jong. 2005.  The influence of migration sizes and intervals on island models. In _Proceedings of the 7th annual conference on Genetic and evolutionary computation_. 1295–1302.
  * Soros and Stanley (2014) L Soros and Kenneth Stanley. 2014.  Identifying necessary conditions for open-ended evolution through the artificial life world of chromaria. In _ALIFE 14: The Fourteenth International Conference on the Synthesis and Simulation of Living Systems_. MIT Press, 793–800.
  * Stanley (2007) Kenneth O Stanley. 2007\.  Compositional pattern producing networks: A novel abstraction of development.  _Genetic programming and evolvable machines_ 8, 2 (2007), 131–162.
  * Stanley et al. (2016) Kenneth O Stanley, Nick Cheney, and Lisa B Soros. 2016\.  How the strictness of the minimal criterion impacts open-ended evolution. In _Artificial Life Conference Proceedings_. MIT Press, 208–215.
  * Stanley et al. (2017) Kenneth O Stanley, Joel Lehman, and Lisa Soros. 2017\.  Open-endedness: The last grand challenge you’ve never heard of.  _While open-endedness could be a force for discovering intelligence, it could also be a component of AI itself_ (2017).
  * Woolley and Stanley (2011) Brian G Woolley and Kenneth O Stanley. 2011.  On the deleterious effects of a priori objectives on evolution and representation. In _Proceedings of the 13th annual conference on Genetic and evolutionary computation_. 957–964.
  * Zitzler et al. (2001) Eckart Zitzler, Marco Laumanns, and Lothar Thiele. 2001\.  SPEA2: Improving the strength Pareto evolutionary algorithm.  _TIK-report_ 103 (2001).

## Appendix:

Figure A3. The evolutionary lineage of a solution to a 14-objective problem
found by the MOVE algorithm. Each bin in the map optimizes for a different
subset of the overall objectives, and contains the single best solution found
thus far (the elite) on that subset of objectives. The arrows indicate the
jumps (63 in total) between 40 unique cells in the lineage leading up to the
champion of this run (colored warm to cool over evolutionary time). We find
that this map of elites is both efficient (able to use a far smaller
population size than Pareto optimization) and effective (outperforming a
single-objective hillclimber that optimizes for the sum of all 14 fitness
functions together) and in 9/14 cases even matching or outperforming a
hillclimber optimizing for only that individual fitness function). The goal
switching observed here is found to be a critical part of the optimization
process, as performance drops significantly when elites are restricted to
replacing existing solutions only within their own cell.

##  Appendix A Detailed Approach

###  A.1. Algorithm

1:objectives $\leftarrow$ a set of many fitness functions to optimize

2:$n\leftarrow\mbox{number of objective functions per cell}$

3:$m\leftarrow\mbox{number of cells in map}$

4:for $i$ in $1,\ldots,m$ do

5: objective_subsetsi$\leftarrow$ rand_choice(objectives, $size=n$)

6:end for

7:elites $\leftarrow$ initial population of size m

8:for generation in total generations do

9: children $\leftarrow[]$

10: for parent in elites do

11: children.append(mutate(parent))

12: end for

13: for child in children do

14: for $i$ in $1,\ldots,m$ do

15: votes $\leftarrow 0$

16: for metric in objective_subsetsi do

17: $F\leftarrow$ fitness(elitesi, metric)

18: $F^{\prime}\leftarrow$ fitness(child, metric)

19: if $F^{\prime}>\mbox{F}$ then votes $\leftarrow$ votes + 1

20: end for

21: if $votes>\frac{n}{2}$ then elitesi $\leftarrow$ child

22: end for

23: end for

24:end for

Algorithm 1 Many-objective Optimization via Voting for Elites (MOVE)

Intuition for the MOVE algorithm is provided in Algorithm 24, however these
operations can be done much more efficiently in practice (see github.com/uvm-
neurobotics-lab/MOVE for an open-source implementation).

###  A.2. Encoding

Similar to (Nguyen et al., 2015), we represent the individuals within our map
as Compositional Pattern Producing Networks (CPPNs) (Stanley, 2007). The CPPNs
in these studies contained the activation functions: $sine$, $cosine$,
$gaussian$, $identity$, and $sigmoid$. The inputs were $x$, $y$, and a $bias$
of $+1.0$. The outputs were $R,G,B$ color values (Stanley, 2007). No
recombination/crossover was used.

###  A.3. Objective functions

The 14 target functions used were: Mean Squared Error (MSE), Peak Signal-to-
Noise Ratio (PSNR), Feature Similarity Index (FSIM), Structural Similarity
Index (SSIM), Multiscale Structural Similarity Index (MS-SSIM), Visual
Information Fidelity (VIF), Visual Saliency-Induced index (VSI), Haar wavelet-
based Perceptual Similarity Index (HaarPSI), Style loss, Gradient Magnitude
Similarity Deviation (GMSD), Mean Deviation Similarity Index (MDSI), DCT
Subband Similarity (DSS) Deep Image Structure and Texture Similarity (DISTS),
and Learned Perceptual Image Patch Similarity (LPIPS). See (Kastryulin et al.,
2022) for a full description and references for all metrics. Metrics that
measure image dissimilarity were inverted so that higher values were
associated with more similar images.

Many of the Image Quality Assessment metrics have been shown to strongly
correlate with human perception. Some metrics focus on low-level structure
like gradients and textures while others reward for high-level similarities.
Newer approaches leverage deep neural network feature extractors trained for
other tasks and compare images based on differences in extracted features.

Fitness values were normalized within each target and function by the mean
highest fitness found by the all-objective hillclimber for that function and
target. Normalizing the range of each fitness function enables more intuitive
visualization and analysis of individual-objective and mean-overall fitness
values (e.g. Figure 2) though the algorithm does not rely on these normalized
values to assess the overall quality across multiple objectives, as majority
voting across individual objectives in a cell is employed during fitness
evaluation/selection. An alternative version of this algorithm that explored
the alternative method of determining fitness by the mean-normalized-fitness
of objectives within a cell was also tested, and resulted in similar
performance – so the simpler and scale-agnostic voting mechanism is used
throughout.

Figure A4 shows the top image found across 20 runs of each single-objective
hillclimber for 4 different target images.

###  A.4. Number of cells

Results in this work are reported from trials with 100 cells in the MOVE map.
However we also ran experiments with as few as 25 cells. With 5 functions per
cell, the 25, 50, and 100 cell conditions all resulted in higher final overall
fitness than the all-objective hillclimber ($p<0.001$). Runs with 25 cells
($1.15\pm 0.03$) performed significantly worse ($p\leq 0.04$) than 50
($1.19\pm 0.03$) and 100 ($1.19\pm 0.03$). Interestingly, 50 cells did not
perform significantly worse than 100 cells ($p=0.83$), suggesting that MOVE
can perform effectively with surprisingly small population sizes.

##  Appendix B Detailed results

Figure A4. The top image found by any single-objective hillclimber for each
objective. No single objective hillclimber creates a faithful reconstruction
of the original due to the presence of deceiving local optima. However, by
looking at the diversity of phenotypes within rows, it is apparent that each
objective finds different local optima. Image of sunrise by Bogdan [CC BY-SA
3.0], via Wikimedia Commons). The dolphin and skull images were produced by
Picbreeder (Secretan et al., 2008) and used in (Gaier et al., 2019).

###  B.1. Functions per cell

| Mean | Mean | Mean | Mean | Mean | Mean final
---|---|---|---|---|---|---
|  total unique | cells | jumps | total | jump | champion
| solutions | in ancestry | in ancestry | replacements | proportion | fitness
| (95% CI) | (95% CI) | (95% CI) | (95% CI) | (95% CI) | (95% CI)
Functions per cell |  |  |  |  |  |
1 | 12.75 ($\pm 0.39$) | 6.73 ($\pm 1.15$) | 24.57 ($\pm 5.48$) | 261 ($\pm 29$) | 47.43% ($\pm 1.72\%$) | 1.10 ($\pm 0.04$)
3 |  40.95 ($\pm 5.52$) | 38.59 ($\pm 6.92$) | 69.33 ($\pm 17.7$) | 36,199 ($\pm 4,851$) | 96.36% ($\pm 0.21\%$) |  1.22 ($\pm 0.03$)
5 | 30.90 ($\pm 4.01$) |  48.67 ($\pm 7.01$) |  100.85 ($\pm 26.09$) |  41,283 ($\pm 5,949$) | 97.40% ($\pm 0.14\%$) |  1.19 ($\pm 0.03$)
7 | 22.30 ($\pm 4.03$) | 40.08 ($\pm 10.14$) |  84.18 ($\pm 26.54$) | 28,891 ($\pm 7,523$) | 97.78% ($\pm 0.13\%$) |  1.21 ($\pm 0.03$)
9 | 16.10 ($\pm 3.85$) | 38.85 ($\pm 7.58$) |  94.2 ($\pm 23.82$) | 28,092 ($\pm 6,766$) | 98.30% ($\pm 0.09\%$) |  1.20 ($\pm 0.03$)
11 | 11.75 ($\pm 4.17$) | 32.27 ($\pm 7.74$) |  101.36 ($\pm 10.15$) | 22,665 ($\pm 6,621$) |  98.55% ($\pm 0.04\%$) | 1.15 ($\pm 0.45$)
Allowed jumps with |  |  |  |  |  |
5 functions per cell |  |  |  |  |  |
Unlimited | 30.90 ($\pm 4.01$) |  48.67 ($\pm 2.23$) |  115.44 ($\pm 11.95$) |  25,939 ($\pm 1,782$) |  97.40% ($\pm 0.14\%$) |  1.19 ($\pm 0.03$)
One |  100 ($\pm 0$) | 44.51 ($\pm 1.90$) | 43.58 ($\pm 3.40$) | 12,012 ($\pm 474$) | 96.31% ($\pm 0.00\%$) |  1.18 ($\pm 0.03$)
None |  100 ($\pm 0$) | 1 ($\pm 0$) | 0 ($\pm 0$) | 4,441 ($\pm 226$) | 0.0% ($\pm 0\%$) | 1.09 ($\pm 0.03$)
Hillclimber |  |  |  |  |  |
Single-objectives | - | - | - | - | - | 0.68 ($\pm 0.01$)
All-objective | - | - | - | - | - |  1.0 ($\pm 0.09$)

Table A2. Statistics on the movement, diversity, and performance of solutions.
The highest value in each column is bold, multiple values in a column are bold
when other rows are not significantly different from the highest. The greatest
diversity of unique solutions at the end of search occurs for subsets of 3
objective functions/cell, while the greatest number of jumps across cells,
unique cells in a run champion’s lineage, and total successful offspring
replacing existing elites are found in conditions with 5 functions/cell.

Statistics about the movement and diversity of solutions.

With 5 functions per cell, when we restrict children to only replacing their
parent within the same cell, performance drops significantly from 1.19 to 1.09
($p<0.001$). Similarly, allowing multiple jumps per offspring was the same
(for 1, 7, 9 functions per cell) or better (for 3, 5, and 11 functions per
cell; $p\leq 0.02$) than only allowing one.

The no-jumping condition still performed better than the single-objective
baseline for 3, 5, 7, 9 and 11 functions per cell
($p\leq$9.41\text{\times}{10}^{-3}$$) but worse than the baseline for 1
function per cell ($p=$3.74\text{\times}{10}^{-06}$$), demonstrating the
importance of including unique combinations of objectives within cells.

###  B.2. Goal-switching

Are there any patterns observable suggesting when goal-switching occurs?
Intuitively we might expect cells with overlapping objective to enable more
jumping between them. With 5 functions per cell, the average number of shared
functions between any two cells in our trials was $1.87/5$ ($\pm.03$).

When an elite produced a surviving offspring, the replaced cell shared
significantly more functions with the parent cell than the overall average
(jumping to one: $1.90/5$ $\pm 0.03$, $p<0.01$; jumping to any: $1.92/5$ $\pm
0.03$, $p<0.001$). As expected, when no jumping was allowed, the average was
$5.0/5$ ($\pm 0$, $p<0.001$) since the children can only replace their parent.
Findings for other number of functions per cell were similar, suggesting that
shared objectives do enable increased goal-switching.

When considering the complete evolutionary history, 5 functions per cell
resulted in more unique cells in the genealogy of the final solutions than any
other number of functions per cell (Table A2, $p<0.01$). While 1 function per
cell resulted in significantly less unique cells in final solution ancestries
($6.73/100\pm 1.15$) than all other conditions ($p<0.001$). With 5 functions
per cell, the path taken by the ancestors of a final solution included almost
half of all the cells in the map on average, suggesting that a wide variety of
cells serve as stepping stones en route to a final solution. Since so many
different cells (each with a random subset of objective functions) are present
in the evolutionary history of a solution, it is understandable how MOVE can
produce solutions that perform well on the mean of all 14 fitness functions,
even when not ever being exposed to more than a handful at any given time.

In addition to more exploration of the map, with 5 functions per cell, there
was significantly more total replacements (i.e. successful offspring) over the
1000 generations ($p\leq$0.01$$; Table A2), followed by 3 functions per cell
which had more than the others ($p\leq$8.03\text{\times}{10}^{-3}$$). With
only 1 function per cell, there were significantly less replacements than all
other conditions ($p\leq$6.3\text{\times}{10}^{-08}$$). As the number of
functions per cell increases, the number of votes that a child needs (i.e. the
number of objectives it must simultaneously satisfy) to replace an elite
increases, perhaps helping to explain why there are fewer replacements with 11
functions per cell.

Ablating the ability for offspring to jump to a cell other than its parents’
(goal-switch) predictably resulted in fewer replacements and more unique
solutions. Similarly, limiting the offspring to only be able to jump to one
cell resulted in more unique solutions and fewer jumps than trials with
unlimited jumps (Table A2).

###  B.3. By function

MOVE champions outperformed the single-objective hillclimber on 9/14 objective
functions. Even when we gave the hillclimber far more compute by increasing
the number of offspring per generation per hillclimber to 100 each (1400/gen
overall across all hillclimbers), MOVE still performed better on 4 objectives
($p\leq 0.03$), the same on 7, and worse on just 3 ($p\leq 1.13e-3$).

##  Appendix C Other target images

Figure A5. Most fit individuals by objective function, averaged across trials
with four different target images, 20 trials per image. Values are transformed
so that $1.0$ corresponds with the mean fitness for the corresponding
hillclimber. MOVE finds a single champion solution (the highest all-objective
mean fitness) from each run that perform the same or better than the solutions
found by the all-objective-hillclimber on mean aggregate fitness. Unlike with
the sunrise image on its own, these all-objective MOVE champions only
significantly outperform the all-objective-hillclimber solutions on 10 of the
14 individual objectives. Averaged across all images, MOVE all-objective
champions also perform as well as, or better, than just 5 of the 14 single-
objective hillclimber solutions on the single objective functions for which
they were trained. The top performing MOVE solutions on each individual
objective (which are trained on the map of all objectives, but may not
necessarily be the all-objective champion from that run) score higher or the
same as the corresponding single-objective hillclimber on 7 of the 14
objectives (all $p<.001$). The single-objective hillclimber still always
significantly outperforms the all-objective hillclimber on single objectives
by focusing on one objective.

Max fitness by objective function.

The results reported in this work were from trials with the sunrise target
image. Hyperparameters were highly tuned to that specific simple image. Trials
with more complicated images show that MOVE champions still outperform the
all-objective hillclimber, but no longer are very likely to outperform the
single-objective hillclimbers (Fig. A5). These more complicated images are
presumably more difficult to find stepping stones for, and a version of MOVE
that is tuned for the sunrise image does not generalize its ability to escape
local optima. More research is required to understand how MOVE can be
generalized to other target images and other tasks.

##  Appendix D Limitations and Future work

The specific objective functions in this work was mostly chosen for
convenience of implementation in (Kastryulin et al., 2022). Preliminary
exploratory data analysis suggested that many, but not all, pairwise
combinations of objectives were well aligned and complementary – such that, on
average, increasing one would also increase the other. This matches the
intuition of the different fitness functions being alternative ways to assess
the similarity of two images (the evolved solution to the target images).
Though there are notable differences in how the different Image Quality
Assessment metrics make this assessment, and the general intuition that color-
based, texture-based, deep-learning-content/encoding-based, etc. metrics being
different; the visual inspection of the single-objective hillclimber evolved
solutions for each (e.g. Figure A4); and the lower performance of the all-
objective hillclimber all similarly suggest that these are not perfectly
complementary objectives. It is not clear how much the alignment between
objectives influences the MOVE algorithm, which is a major limitation for the
generalizability of this work. Future work should consider more carefully
crafted fitness metrics which may be more or less compatible with one another,
as well as a variety of complex real-world many-objective optimization
problems. Additionally, recombination is an important tool for evolutionary
many-objective optimization algorithms and was not implemented for this paper.
Future work should consider different encodings, mutation operators and
recombination.