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