Novelty-driven Cooperative Coevolution

Cooperative coevolutionary algorithms (CCEAs) rely on multiple coevolving popula-tions for the evolution of solutions composed of coadapted components. CCEAs allow, for instance, the evolution of cooperative multiagent systems composed of heteroge-neous agents, where each agent is modelled as a component of the solution. Previous works have, however, shown that CCEAs are biased towards stability: the evolution-ary process tends to converge prematurely to stable states instead of (near-)optimal solutions. In this study, we show how novelty search can be used to avoid the counter-productive attraction to stable states in coevolution. Novelty search is an evolutionary technique that drives evolution towards behavioural novelty and diversity, rather than exclusively pursuing a static objective. We evaluate three novelty-based approaches that rely on, respectively (i) the novelty of the team as a whole, (ii) the novelty of the agents ’ individual behaviour, and (iii) the combination of the two. We compare the proposed approaches with traditional fitness-driven cooperative coevolution, in three simulated multirobot tasks. Our results show that team-level novelty scoring is the most effective approach, significantly outperforming fitness-driven coevolution at multiple levels. Novelty-driven cooperative coevolution can substantially increase the potential of CCEAs, while maintaining a computational complexity that scales well with the number of populations