Identifying Necessary Components for Open-Ended Evolution

Anya Vostinar, Emily Dolson, Michael Wiser,
and Charles Ofria

OOE2 Workshop at Artificial Life XV, July 3rd, 2016


Have firefox? Follow along at goo.gl/g6fa2H.

Open-Ended Evolution is a huge concept

  • To make scientific progress, we need a way to approach it incrementally
  • Metrics of relative open-endedness allow this
  • Evolutionary activity statistics
  • Complexity barriers

Our approach

  • Last year we presented a suite of four metrics:
    • Change
    • Novelty
    • Ecology
    • Complexity
  • Here, we test these metrics in a simple, well-studied system: NK landscapes

NK Landscapes

  • Popular model for studying evolutionary dynamics in bitstrings
  • N = length of bitstring
  • K = Interaction among bits

NK Landscapes

  • Popular model for studying evolutionary dynamics in bitstrings
  • N = length of bitstring
  • K = Interaction among bits

N: 7 K: 0

1 0 1 1 1 0 0

NK Landscapes

  • Popular model for studying evolutionary dynamics in bitstrings
  • N = length of bitstring
  • K = Interaction among bits

N: 7 K: 0

1 0 1 1 1 0 0

Value Fitness Contribution
0 .4652
1 .7842

NK Landscapes

  • Popular model for studying evolutionary dynamics in bitstrings
  • N = length of bitstring
  • K = Interaction among bits

N: 7 K: 1

1 0 1 1 1 0 0

Value Fitness Contribution
00 .4652
01 .1254
10 .7841
11 .3292

NK Landscapes

  • Popular model for studying evolutionary dynamics in bitstrings
  • N = length of bitstring
  • K = Interaction among bits

N: 7 K: 2

1 0 1 1 1 0 0

Value Fitness Contribution Value Fitness Contribution
000 .4652 001 .9132
010 .4213 100 .2123
011 .8673 101 .5386
110 .3192 111 .6264

Filtering out noise

  • Evolution is an inherently noisy process
    • Not all parts of a genome contribute to its success
    • Many members of a population are the result of deleterious mutations

Filtering the genome

  • Determine the fitness effect of changing each site in genome
  • Build a “skeleton”" of informative sites

Filtering the genome

  • Determine the fitness effect of changing each site in genome
  • Build a “skeleton”" of informative sites

N: 6 K: 0

1 0 1 1 1 0

Bit Value 0 1 2 3 4 5
0 .4652 .1146 .1923 .8254 .5642 .9235
1 .9314 .4256 .5924 .2313 .0538 .7876

Filtering the genome

  • Determine the fitness effect of changing each site in genome
  • Build a “skeleton”" of informative sites

N: 6 K: 0

1 0 1 1 1 0

Bit Value 0 1 2 3 4 5
0 .4652 .1146 .1923 .8254 .5642 .9235
1 .9314 .4256 .5924 .2313 .0538 .7876

Filtering the genome

  • Determine the fitness effect of changing each site in genome
  • Build a “skeleton”" of informative sites

N: 6 K: 0

1 0 1 1 1 0

Bit Value 0 1 2 3 4 5
0 .4652 .1146 .1923 .8254 .5642 .9235
1 .9314 .4256 .5924 .2313 .0538 .7876

Filtering the genome

  • Determine the fitness effect of changing each site in genome
  • Build a “skeleton”" of informative sites

N: 6 K: 0

1  -  1 1 1 0

Bit Value 0 1 2 3 4 5
0 .4652 .1146 .1923 .8254 .5642 .9235
1 .9314 .4256 .5924 .2313 .0538 .7876

Filtering the genome

  • Determine the fitness effect of changing each site in genome
  • Build a “skeleton”" of informative sites

N: 6 K: 0

1  -  1 1 1 0

Bit Value 0 1 2 3 4 5
0 .4652 .1146 .1923 .8254 .5642 .9235
1 .9314 .4256 .5924 .2313 .0538 .7876

Filtering the genome

  • Determine the fitness effect of changing each site in genome
  • Build a “skeleton”" of informative sites

N: 6 K: 0

1  -  1  -  1 0

Bit Value 0 1 2 3 4 5
0 .4652 .1146 .1923 .8254 .5642 .9235
1 .9314 .4256 .5924 .2313 .0538 .7876

Filtering the genome

  • Determine the fitness effect of changing each site in genome
  • Build a “skeleton”" of informative sites

N: 6 K: 0

1  -  1  -   -  0

Bit Value 0 1 2 3 4 5
0 .4652 .1146 .1923 .8254 .5642 .9235
1 .9314 .4256 .5924 .2313 .0538 .7876

Filtering the genome

  • Determine the fitness effect of changing each site in genome
  • Build a “skeleton”" of informative sites

N: 6 K: 0

1  -  1  -   -  0

Bit Value 0 1 2 3 4 5
0 .4652 .1146 .1923 .8254 .5642 .9235
1 .9314 .4256 .5924 .2313 .0538 .7876

Filtering the population

  • Previous approaches:
    • Evolutionary activity statistics shadow run
    • Fossil record
  • We build on Bedau et. al.’s approach to the fossil record

Filtering the population

Metrics

Change

How much does the population composition change during an interval?

Novelty

How many entirely new strategies arise during an interval?

Ecology

How much does “meaningful” diversity increase during an interval?

Complexity

How much does the greatest individual complexity increase during an interval?

Transitions

Does the population undergo changes in what it means to be an individual?

Fitting them together

A simple example

Results

Change

Change

Change

Novelty

Novelty

Novelty

Ecology

Ecology

Ecology

Complexity

Complexity

Complexity

Conclusions

  • Metrics intuitively reflect evolutionary dynamics
  • By measuring the effects of different treaments, we can zero in on which conditions are necessary for open-ended evolution

Acknowledgements

Co-authors:

Funding sources:

Questions?