Increasing Features in MAP-Elites Using an Age-Layered Population Structure
Andrew Pozzuoli, Brian J. Ross · 2023
The multi-dimensional archive of phenotypic elites (MAP-Elites) algorithm is a popular evolutionary algorithm which returns a highly diverse set of elite solutions. The population is separated into a grid-like feature space defined by user-specified feature dimensions where each cell of the grid corresponds to a unique behaviour combination. The algorithm is conceptually simple and effective at producing high-quality, diverse solutions, but it comes with a major limitation on its exploratory capabilities. With every added feature, the set of solutions grows exponentially, making high-dimensional feature spaces infeasible. This work proposes a way of increasing features with the novel Age-Layered MAP-Elites (ALME) algorithm where the population is separated into age-layers and each layer has its own feature space. By using different features in the layers, the population migrates up through the layers experiencing selective pressure towards different features. This algorithm is applied to a simulated intelligent agent environment where agents are controlled by genetic programming (GP) trees to observe interesting emergent behaviours in underexplored regions of the feature space. It is observed that ALME is capable of producing a high-quality and diverse set of solutions that is competitive with traditional MAP-Elites without the combinatorial explosion in the resulting number of solutions.