Managing Diversity and Many Objectives in Evolutionary Design

Abstract

This thesis proposes a new approach to evolving a diversity of high-quality solutions for problems having many objectives. Mouret and Clune's MAP-Elites algorithm has been proposed as a way to evolve an assortment of diverse solutions to a problem. We extend MAP-Elites in a number of ways. Firstly, we introduce a many-objective strategy called sum-of-ranks, which enables problems with many objectives (4 and more) to be considered in the MAP. Secondly, we enhance MAP-Elites by extending it with multiple solutions per "grid" cell (the original MAP-Elites saves only a single solution per cell). A few different ways of selecting cell members for reproduction are also considered. We test the new MAP-Elites strategies on the evolutionary art application of image generation. Using procedural textures, genetic programming is used with upwards of 15 lightweight image features to guide fitness. The goal is to evolve images that share image features with a given target image. Our experiments show that the new MAP-Elites algorithms produce a large number of diverse solutions of varying quality. The extended MAP-Elites algorithm is also statistically competitive compared to vanilla GP in this application domain.