Multi-Objective Covariance Matrix Adaptation MAP-Annealing Conference: Genetic and Evolutionary Computation Conference; July 14–18, 2025; Malaga, Spain Genetic and Evolutionary Computation Conference (GECCO ’25), July 14–18, 2025, Malaga, Spain DOI: 10.1145/3712256.3726463 ISBN: 979-8-4007-1465-8/20
Shihan Zhao, Stefanos Nikolaidis · 2025
Read Multi-Objective Covariance Matrix Adaptation MAP-Annealing Conference: Genetic and Evolutionary Computation Conference; July 14–18, 2025; Malaga, Spain Genetic and Evolutionary Computation Conference (GECCO ’25), July 14–18, 2025, Malaga, Spain DOI: 10.1145/3712256.3726463 ISBN: 979-8-4007-1465-8/20 by Shihan Zhao, Stefanos Nikolaidis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-20712.txt.
Introduction
Zhao and Nikolaidis put forth a new search tool in twenty twenty-five that finds sets of scores that are both mixed in acts and high in quality on many aims at once. Past tools of this kind used fixed steps like swaps and cross-es, which search in a blunt way. Their tool uses a curve-fit search that adapts its steps as it goes.
It scores each set in the bank by the vol-ume its top scores span. On three test fields and on co-op game map builds it beat past tools by clear gaps. Such banks can serve games that need maps of mixed hard-ness and feel.
Catalog record
| CREATOR | Shihan Zhao, Stefanos Nikolaidis |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-20712
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multi-Objective Covariance Matrix Adaptation MAP-Annealing Conference: Genetic and Evolutionary Computation Conference; July 14–18, 2025; Malaga, Spain Genetic and Evolutionary Computation Conference (GECCO ’25), July 14–18, 2025, Malaga, Spain DOI: 10.1145/3712256.3726463 ISBN: 979-8-4007-1465-8/2025/07 CCS: Applied computing Multi-criterion optimization and decision-making CCS: Computing methodologies Search methodologies CCS: Theory of computation Evolutionary algorithms Shihan Zhao, Stefanos Nikolaidis Abstract . Quality-Diversity (QD) optimization is an emerging field that focuses on finding a set of behaviorally diverse and high-quality solutions. While the quality is typically defined w.r.t. a single objective function, recent work on Multi-Objective Quality-Diversity (MOQD) extends QD optimization to simultaneously optimize multiple objective functions. This opens up multi-objective applications for QD, such as generating a diverse set of game maps that maximize difficulty, realism, or other properties. Existing MOQD algorithms use non-adaptive methods such as mutation and crossover to search for non-dominated solutions and construct an archive of Pareto Sets (PS). However, recent work in QD has demonstrated enhanced performance through the use of covariance-based evolution strategies for adaptive solution search. We propose bringing this insight into the MOQD problem, and introduce MO-CMA-MAE, a new MOQD algorithm that leverages Covariance Matrix Adaptation-Evolution Strategies (CMA-ES) to optimize the hypervolume associated with every PS within the archive. We test MO-CMA-MAE on three MOQD domains, and for generating maps of a co-operative video game, showing significant improvements in performance. † † cc-license: by 1. Introduction Quality-Diversity (QD) is a growing field of optimization focused on finding a diverse archive of solutions that achieve high objective values. QD algorithms addressing this problem have been successfully applied across various scenarios, such as searching for control policies that exhibit distinct behaviors ( Cully et al. 2015 ; Grillotti and Cully 2022 ) , generating niche testing scenarios ( Fontaine and Nikolaidis 2022 ; Bhatt et al. 2022 ) , and providing illustrative examples to probe and learn human preferences ( Ding et al. 2023 ; Gallotta et al. 2023 ) . While the qualities of solutions are usually evaluated through a single objective function in the QD paradigm, recent work on Multi-Objective Quality-Diversity (MOQD) ( Pierrot et al. 2022 ; Janmohamed et al. 2023 ) has extended QD to optimize multiple objectives. Instead of finding an archive of individual solutions, MOQD seeks to find a diverse archive of local Pareto Sets (PS). Each PS in the archive consists of solutions representing the optimal trade-offs among the objectives, while different local PSs capture solutions that exhibit different behaviors. The need to find behaviorally diverse PSs arises when a problem simultaneously features multiple objectives to be optimized , and behavior-characterizing measure functions to be explored . For example, when generating game level maps for a co-op maze game such as Overcooked ( Carroll et al. 2019 ) , we may want the generated maps to make it more difficult for players to achieve high scores, but in the meantime also cheaper to construct in the sense that more space is left empty. In addition to maximizing these two objectives, we may also want the maps to promote diversity in the playstyles they elicit from the cooperating players, ranging from specialized to even task divisions. We highlight the difference between optimization and exploration . When optimizing the objectives, we purposefully search for more difficult and more empty maps. However, when exploring the space spanned by measure functions, we want to cover all induced playstyles, with no consistent preference on either even or uneven task divisions. In this particular application, we may use an MOQD algorithm to generate a behaviorally diverse archive of PSs, with each PS containing maps that balance difficulty and emptiness. This is illustrated in Figure 1 . Figure 1. Game maps found by MO-CMA-MAE that induce diverse task divisions while achieving good trade-off between the difficulty and emptiness objectives. In this case, the two task divisions we consider are the difference between numbers of ingredients held by the two cooperating players, and difference between numbers of plates held. In the two upper-left maps, the blue player starts between the plate (represented by three white circles) and the delivery counter (represented by a gray tile), and thus is induced to specialize in delivering cooked meals on plates to the counter. The two upper-right maps induce the opposite, where the green player specializes in delivery. To address the MOQD problem, prior work ( Pierrot et al. 2022 ; Janmohamed et al. 2023 ) has proposed the Multi-Objective MAP-Elites (MOME) algorithm. Similar to the QD algorithm MAP-Elites ( Mouret and Clune 2015 ) , MOME constructs a behaviorally-indexed archive by tessellating the measure space into discrete cells. Each solution is assigned into a cell according to its measure function outputs, and locally competes with other solutions assigned to this same cell. Unlike MAP-Elites, MOME does not maintain and update a single highest-objective elite within each cell, but an incumbent PS consisted of non-dominated solutions optimizing various trade-offs among all objectives. MOME shows promising results at finding a behaviorally diverse set of PSs on Rastrigin ( Hansen et al. 2021 ) and Brax ( Freeman et al. 2021 ) domains. However, MOME searchs for non-dominated solutions using mutation and crossover operations, which do not self-adapt according to the search progress. This limitation has been partly addressed in MOME-PGX ( Vassiliades and Mouret 2018 ) , which employs policy gradient to accelerate optimization of solution objectives. Nonetheless, MOME-PGX does not explicitly use policy gradient to assist measure space exploration, and additionally assumes the problem to be a Markov Decision Process (MDP). To overcome these limitations, we propose a new MOQD algorithm, Multi-Objective Covariance Matrix Adaptation MAP-Annealing (MO-CMA-MAE). MO-CMA-MAE utilizes the black-box optimizer Covariance Matrix Adaptation Evolution Strategy (CMA-ES) ( Hansen 2016 ) to search for solutions that either explore the measure space by exhibiting an under-represented behavior, or optimizes a discovered behavior by achieving non-dominance within its corresponding PS. We highlight two key insights as contributions of this work: (1) We recognize the hypervolume improvement of a solution over its archive cell as a metric that simultaneously motivates measure space exploration and multi-objective optimization, and optimize this metric with CMA-ES. (2) To further incentivize CMA-ES to explore the measure space, we boost hypervolume improvements within under-explored archive cells by implementing a threshold acceptance mechanism inspired by the QD algorithm Covariance Matrix Adaptation MAP-Annealing (CMA-MAE) ( Fontaine and Nikolaidis 2023 ; Zhao et al. 2024 ) . We benchmark MO-CMA-MAE on 4 test domains against MOME, NSGA-II ( Deb et al. 2002 ) , SMS-EMOA ( Beume et al. 2007 ) , and a modified COMO-CMA-ES ( Touré et al. 2019 ) . MO-CMA-MAE outperforms all baselines in 2 of the domains. In the remaining 2 domains, MO-CMA-MAE performed on par with the strongest baseline MOME, while outperforming the other baselines. 2. Background 2.1. Multi-Objective Optimization Multi-Objective Optimization (MOO) aims to find solutions that optimize various trade-offs among k non-aligned objectives f_{i}(\bm{x});i\in\{1,2,\ldots,k\} . Since multiple objectives are involved, when comparing two solutions \bm{x} and \bm{y} , \bm{y} only outperforms \bm{x} when it is as good as \bm{x} in all k objectives, and strictly better in at least one objective (we assume maximization for MOO throughout this work). This is formalized as strict dominance: (1) \bm{y}\succ\bm{x}\text{