year:
paper: https://www.alphaxiv.org/overview/1504.04909v1
website:
code:
connections: quality diversity, Jeff Clune
Link to originalMotivation
MAP-Elites can been seen as part of the recent trend (…ok, maybe not that recent) in evolution algorithm community to favor exploration, i.e. focus on generating novel individuals even if they may not have the highest fitness. Lehman, J., & Stanley, K. O. (2008) famously demonstrated that in certain tasks with deceptive/delayed/sparse reward (maze navigation in this case), optimizing for novelty alone while neglecting performance can actually be a valid approach! It was also argued in Lehman, J., & Stanley, K. O. (2011) and Salimans, T., et al. (2017) that the density of high-performing solutions is often high enough and the reward structure deceptive to merit exploration over exploitation. The importance of exploration justifies the emergence a family of evolution algorithms called Quality-Diversity(QD) algorithms, which search for a set of high-performing and distinct solutions rather than just one best solution. MAP-Elites belongs to this family, and aside from MAP-Elites which explores the search space indirectly, another major sub-family of QD algorithm is represented by Novelty Search with Local Competition(NSLC), which actively optimizes for novelty along with fitness using multi-objective optimizer algorithms such as NSGA-II. - blog
Algorithm
Initialization
- Create an n-dim archive based on behavioral characterizations (discretized buckets)
- Initialize with random solutions until elites are found.
Main loop
- Pick two elites from the archive (randomly)
- Apply crossover and mutation
- Evaluate the new solution
- If new behavior or better fitness than the solution in a bucket, the solution becomes an elite
What behaviors you choose depends on what are you interested in / you need a hypothesis for that.
It could also be something like complexity of your network.
Often you also tweak it to see what falls out (Like with your fitneess function)
Works well in general with 2,3,4 behaviors.
There is follow-upp work where granularity of buckets is automatically determined.
Which?
“Illuminating the search space”: You see which pockets of the space yield high fitness.
Scaling MAP-Elites to Deep Neuroevolution
Todo