An official website of the United States government
Quality-diversity (QD) algorithms search for a set of good solutions which cover a space as defined by behavior metrics. This simultaneous focus on quality and diversity with explicit metrics sets QD algorithms apart from standard single- and multi-objective evolutionary algorithms, as well as from diversity preservation approaches such as niching. These properties open up new avenues for artificial intelligence in games, in particular for procedural content generation. Creating multiple systematically varying solutions allows new approaches to creative human-AI interaction as well as adaptivity. In the last few years, a handful of applications of QD to procedural content generation and game playing have been proposed; we discuss these and propose challenges for future work.
more »
« less
Covariance Matrix Adaptation MAP-Annealing: Theory and Experiments
Single-objective optimization algorithms search for the single highest quality solution with respect to an objective. Quality diversity (QD) optimization algorithms, such as Covariance Matrix Adaptation MAP-Elites (CMA-ME), search for a collection of solutions that are both high quality with respect to an objective and diverse with respect to specified measure functions. However, CMA-ME suffers from three major limitations highlighted by the QD community: prematurely abandoning the objective in favor of exploration, struggling to explore flat objectives, and having poor performance for low-resolution archives. We propose a new QD algorithm, CMA MAP-Annealing (CMA-MAE), and its differentiable QD variant, CMA-MAE via a Gradient Arborescence (CMA-MAEGA), that address all three limitations. We provide theoretical justifications for the new algorithm with respect to each limitation. Our theory informs our experiments, which support the theory and show that CMA-MAE achieves state-of-the-art performance and robustness on standard QD benchmark and reinforcement learning domains.
more »
« less
- PAR ID:
- 10605641
- Publisher / Repository:
- Association for Computing Machinery (ACM)
- Date Published:
- Journal Name:
- ACM Transactions on Evolutionary Learning and Optimization
- Volume:
- 5
- Issue:
- 1
- ISSN:
- 2688-3007
- Format(s):
- Medium: X Size: p. 1-53
- Size(s):
- p. 1-53
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
To maximize indoor daylight, design projects commonly use commercial optimization tools to find optimum window configurations. However, experiments show that such tools either fail to find the optimal solution or are very slow to compute in certain conditions.This paper presents a comparative analysis between a gradient-free optimization technique, Covariance Matrix Adaptation Evolution Strategy (CMA-ES), and the widely used Genetic Algorithm (GA)-based tool, Galapagos, to optimize window parameters to improve indoor daylight in six locations across different latitudes. A novel combination of daylight metrics, sDA, and ASE, is proposed for single-objective optimization comparison. Results indicate that GA in Galapagos takes progressively more time to converge, from 11 minutes in southernmost to 11 hours in northernmost latitudes, while runtime for CMA-ES is consistently around 2 hours. On average, CMA-ES is 1.5 times faster than Galapagos, while consistently producing optimal solutions. This paper can help researchers in selecting appropriate optimization algorithms for daylight simulation based on latitudes, runtime, and solution quality.more » « less
-
Cussens, James; Zhang, Kun (Ed.)The importance of designing proteins, such as high affinity antibodies, has become ever more apparent. Computational Protein Design can cast such design problems as optimization tasks with the objective of maximizing K*, an approximation of binding affinity. Here we lay out a graphical model framework for K* optimization that enables use of compact AND/OR search algorithms. We designed an AND/OR branch-and-bound algorithm, AOBB-K*, for optimizing K* that is guided by a new K* heuristic and can incorporate specialized performance improvements with theoretical guarantees. As AOBB-K* is inspired by algorithms from the well studied task of Marginal MAP, this work provides a foundation for harnessing advancements in state-of-the-art mixed inference schemes and adapting them to protein design.more » « less
-
This paper introduces a generalized spatial regionalization problem, namely, PRUC ( P -Regions with User-defined Constraint) that partitions spatial areas into homogeneous regions. PRUC accounts for user-defined constraints imposed over aggregate region properties. We show that PRUC is an NP-Hard problem. To solve PRUC, we introduce GSLO (Global Search with Local Optimization), a parallel stochastic regionalization algorithm. GSLO is composed of two phases: (1) Global Search that initially partitions areas into regions that satisfy a user-defined constraint, and (2) Local Optimization that further improves the quality of the partitioning with respect to intra-region similarity. We conduct an extensive experimental study using real datasets to evaluate the performance of GSLO. Experimental results show that GSLO is up to 100× faster than the state-of-the-art algorithms. GSLO provides partitioning that is up to 6× better with respect to intra-region similarity. Furthermore, GSLO is able to handle 4× larger datasets than the state-of-the-art algorithms.more » « less
-
null (Ed.)This paper introduces a new system to design constructive level generators by searching the space of constructive level generators defined by Marahel language. We use NSGA-II, a multi-objective optimization algorithm, to search for generators for three different problems (Binary, Zelda, and Sokoban). We restrict the represen- tation to a subset of Marahel language to push the evolution to find more efficient generators. The results show that the generated generators were able to achieve good performance on most of the fitness functions over these three problems. However, on Zelda and Sokoban they tend to depend on the initial state than modifying the map.more » « less
