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, ie behavioral diversity.

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 an 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$

Demonstration

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 is similar to multi-objective optimization: maximize objective function and novelty metric
Similar to multi-modal optimization: find many different good solutions
Focus on finding niches at the same time or stored in an archive
Mahfoud, Samir W. Niching methods for genetic algorithms. Diss. University of Illinois at Urbana-Champaign, 1995.
Preuss, Mike. Multimodal optimization by means of evolutionary algorithms. Springer International Publishing, 2015.
Combination with QD a current topic
The difference: quality diversity search is divergent, looking for new behaviors

Exercise

Discuss with your project team about a behavior characterization for agents in your game. Try to come up with multiple behavior characterizations and consider what a diversity of these characterizations would lead to in terms of game strategy. Consider the computational cost of keeping an archive and comparing to this archive over time. Finally, report the results of your discussion in Discord.