Enhancements to Constrained Novelty Search: Two-Population Novelty Search for Generating Game Content

Antonios Liapis, Georgios N. Yannakakis, Julian Togelius

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review


Novelty search is a recent algorithm geared to explore search spaces without regard to objectives; minimal criteria novelty search is a variant of this algorithm for constrained search spaces. For large search spaces with multiple constraints,
however, it is hard to find a set of feasible individuals that is both large and diverse. In this paper, we present two new methods of novelty search for constrained spaces, Feasible-Infeasible Novelty Search and Feasible-Infeasible Dual Novelty Search. Both algorithms keep separate populations of feasible and infeasible individuals, inspired by the FI-2pop genetic algorithm. These algorithms are applied to the problem of creating diverse and feasible game levels, representative of a large class of important problems in procedural
content generation for games. Results show that the new algorithms under certain conditions can produce larger and more diverse sets of feasible strategy game maps than existing algorithms. However, the best algorithm is contingent on
the particularities of the search space and the genetic operators used. It is also shown that the proposed enhancement of offspring boosting increases performance in all cases.
TitelGECCO '13 Proceedings of the fifteenth annual conference on Genetic and evolutionary computation conference
Antal sider8
ForlagAssociation for Computing Machinery
ISBN (Trykt)978-1-4503-1963-8
StatusUdgivet - 2013


Dyk ned i forskningsemnerne om 'Enhancements to Constrained Novelty Search: Two-Population Novelty Search for Generating Game Content'. Sammen danner de et unikt fingeraftryk.