The Role of Stepping Stones in MAP-Elites: Insights from Search Trajectory Networks

MAP-Elites (ME) is a quality-diversity optimization algorithm designed to generate a diverse collection of high-performing solutions to complex problems by leveraging “stepping stones”. Stepping stones have been defined as intermediate solutions that, while not necessarily optimal themselves, contribute to the development of more effective final outcomes. A deeper understanding of the role of stepping stones in evolutionary optimization would be beneficial. To address this gap, we employ search trajectory networks (STNs), an analytical and visualization tool for studying the behavior of optimization algorithms. We refine the notion of stepping stones by incorporating the idea of betweenness centrality in networks. We consider a robotic navigation task with various controller representations (polynomials, artificial neural networks, and symbolic formulae encoded as trees), comparing the ME search process with that of a genetic algorithm, while also evaluating the differences across representations. Our findings show clearer evidence of stepping stones in ME, particularly when using more “direct” and “local” representations.