Evolutionary Computation
Behavior and Novelty
Evolving programs and networks
These individuals have a behavior.
O'Reilly, Una-May, and Erik Hemberg. "Introduction to genetic programming." Proceedings of the Genetic and Evolutionary Computation Conference Companion. 2019.
Evolution of behavior
Similar genes, different behaviors
Mouret, J-B., and Stéphane Doncieux. "Encouraging behavioral
diversity in evolutionary robotics: An empirical study."
Evolutionary computation 20.1 (2012): 91-133.
Evolution of behavior
Different genes, similar behaviors
Mouret, J-B., and Stéphane Doncieux. "Encouraging behavioral
diversity in evolutionary robotics: An empirical study."
Evolutionary computation 20.1 (2012): 91-133.
Behavior Space
Mouret, J-B., and Stéphane Doncieux. "Encouraging behavioral
diversity in evolutionary robotics: An empirical study."
Evolutionary computation 20.1 (2012): 91-133.
Evaluating behavior
Evolutionary fitness:
Sum total reward or final outcome over an episode
Measuring behavior
How do we define the distance between two behaviors?
Gomez, Faustino J. "Sustaining diversity using behavioral information distance." Proceedings of the 11th Annual conference on Genetic and evolutionary computation. 2009.
Population diversity
We need to encourage diversity in the behavior space, i.e., behavioral diversity.
Behavior Characterization
Behavior Characterization
$F(i) = \sqrt{(x_i-x_{final})^2+(y_i-y_{final})^2}$
Behavior Characterization
$dist(i, j) = \sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$
Behavior characterization for a map:
Final position
Novelty Search
- During evolution, keep a behavior archive
- For each individual $x$, find $k$ nearest neighbors $\mu$ in current population or behavior archive
- Calculate average distance $\rho(x) = \frac{1}{k}\sum_{i=0}^k dist(x, \mu_i)$
- if $\rho(x) > \rho_{\texttt{min}}$, add $x$ to the archive
- Select individuals based on $\rho$
Lehman, Joel, and Kenneth O. Stanley. "Abandoning objectives: Evolution through the search for novelty alone." Evolutionary computation 19.2 (2011): 189-223.
Open-Ended Evolution
Ackley, David H., and Elena S. Ackley. "The ulam programming language for artificial life." Artificial life 22.4 (2016): 431-450.
Novelty Search with Local Competition
- Includes objective function fitness in evaluation
- Same base as novelty search
- When calculating $\rho(x)$, compare $x$ and $k$ nearest neighbors on objective fitness function $F$
- Local competition objective: $\Sigma_{i=0}^k [ F(x_i) > F(k) ]$
- NSGA-II with local competition objective and $\rho$
Lehman, Joel, and Kenneth O. Stanley. "Evolving a diversity of virtual creatures through novelty search and local competition." Proceedings of the 13th annual conference on Genetic and evolutionary computation. 2011.
Novelty Search with Local Competition
Quality diversity
Cully, Antoine, and Yiannis Demiris. "Quality and diversity optimization: A unifying modular framework." IEEE Transactions on Evolutionary Computation 22.2 (2017): 245-259.
Multi-modal Optimization & Quality Diversity
- Multi-modal optimization:
→ Find many different high-quality solutions (multiple optima) - Quality Diversity (QD):
→ Maximize performance and behavioral diversity - Key concept: niches
→ Different regions of the behavior space
→ Solutions stored in an archive - Relation to multi-objective optimization:
→ Objective: performance
→ Additional pressure: novelty / diversity - Main difference:
→ QD is divergent
→ Explicitly searches for new behaviors, not just optima
Mahfoud (1995), Preuss (2015) — Niching and multimodal optimization are key foundations of QD
Exercise
Gridworld Treasure Hunt
- Agents move in a 2D grid
- Goal: collect as many treasures as possible
- Constraints:
- Limited time (e.g., 100 steps)
- Obstacles / walls
- Optional enemies or traps
Questions:
- Propose 1-2 behavior characterizations for your agents
- What kinds of diverse strategies would they produce?
- What is the cost of maintaining and comparing an archive?
