Testing Evolution – How I Did It

Muller's Foundry Screenshot - A Mutant That's Better Than the Original

This is part of a series: Testing Evolution

I’m writing this post mainly for anyone who wants to make their own version of my evolution simulator, to prove to themselves that I really got it right.  I’ll still try to make it accessible to non-geeks.

I figured out how to test evolution, now it was time to actually do it.  In this post, I’ll describe in detail the way that I wrote my evolution simulator.

Outline

Creatures and Algorithm

I started with the creatures.  Originally, I made a list (array) of strings. When the simulator ran, it would run (eval) each string as JavaScript.  If, at the end of each generation, the “soup” array had more creatures than the population limit allowed, the simulator would delete creatures until it got down to the population limit.  I later moved to using the Function() constructor for 2 reasons:

  1. To make it much harder for mutant code to break the simulator (Function(creature.source).call(somewhere_else) )
  2. So I could easily tell each creature where it was in the soup (its array index)

By default, creatures add copies of themselves to the top of the array.  When the population gets higher than the population limit, the simulator deletes creatures from the bottom of the array, so new creatures would displace the old, and there would be a constant struggle for survival.

I seeded the array with one creature.  The creature was a one-line, self-copying program:

soup.push(this);

When I tried this, I ran into a problem: the creatures would reliably devolve into a mass of random strings of text.  None of them did anything useful, and the simulator didn’t know when to call it quits.  I needed a way to tell when every creature had died out.  I could’ve had it consider any creature that threw an error to be dead, but I had read that error handling in JavaScript is slow.  Also, some creatures that successfully copy themselves might also throw an error afterward.  If I assumed that all dead creatures threw errors, I’d kill off those still-working creatures.

Instead, I gave each creature a simple job.  If they did their job, they were allowed to run.  If not, they weren’t.  Their job was to keep a variable named food above 0.  Each time that the simulator ran, it would check if their food was above 0.  If so, it would decrease their food by 1, and then run them.  If their food was 0 or below, it wouldn’t run them.  This worked very well, and also had the effect of making the creatures survive many times longer.

When I added this food requirement, I realized that it was best to reorganize each creature into objects, instead of strings.  My new creatures were objects that had at least 3 properties:

  • source
    Holds the source code
  • food
  • color
    I also decided that I wanted to require each creature to have a color, so I could distinguish between them more easily in the visualizer I added to it.  I punished any creatures that didn’t have a valid RGB color by setting their food to 0, effectively killing them.

My new creatures’ sources looked like this:

soup.push(this);

When I ran these new creatures, I found that JavaScript has an interesting quirk: it copies objects by reference.  Thus, every creature in the soup was really a reference to the original.  When one mutation hit any of them, every creature would die.  I rewrote the creature to create its child as a new object:

soup.push( {source: this.source, food: 1, color: "rgb(200,200,200)" } );

As of the writing of this post, this is the starting creature in my simulator.

Mutator

Each time a creature ran, there was a chance that it would mutate.  I made a fairly simplistic mutator that was reasonably efficient, while still mutating in a way similar to what happens in biology.  It currently can do 3 types of mutations:

  1. Insert a random character
  2. Delete a random character
  3. Change a random character to a random character

I’ll probably add these other kinds of mutations eventually:

  1. Copy a random chunk to a random place
  2. Move a random chunk
  3. Delete a random chunk
  4. Flip a random chunk
  5. Copy a random chunk to a random place and flip the copy
  6. Move and flip a random chunk to a random place

The mutator runs in a loop.  Each time, it “rolls the dice” to see if there’ll be a mutation.  If so, it does the mutation.  The effect is that the chance of a creature having one mutation is whatever rate the user picked, the chance of 2 mutations is 1/(mutation_rate2), and so on.  I did it this way because I figured that in the real world, something that causes many mutations might kill the creature outright.  The more mutations it causes, the more likely that the mutagen will kill.  So, for example, if a cosmic ray blasts a cell nucleus to bits, the cell might be able to reassemble it with many errors, but odds are that the blast will kill the cell.  I may change this in the future.

Dealing With Mutant Code

Mutant code has a nasty habit of breaking everything.  It destroys everything it touches.  If the original creature referenced the soup array, sooner or later, one of its descendents would get a mutation that would destroy it.  I’m not sure if it’s more biologically realistic to let it do that or prevent it, but I found it annoying.  The simulator makes a backup reference to each thing that the default creature might touch, and after each creature runs, it restores those backups.

Future Plans

My current to-do list for the simulator is:

  1. Rewrite much of the code using what I now know about computer programming.  In particular, I want to make it easy to port to node.js, by fully separating the core algorithm from the UI.  I also want to make the code more consistent.
  2. Fix all the current bugs.
  3. Rewrite the interface to use jQuery, the most popular JavaScript framework
  4. Improve the interface, so it works well on a phone and looks better
  5. Add support for node.js, so that it can run in either a browser, or in node.
  6. Replace the backup/restore simulator protector with one that makes the container objects for the simulator’s parts impossible to delete or overwrite.  I didn’t know that this was an option when I wrote the simulator.
  7. When running in node.js, give the option of dumping stats to a database, or even every creature in each generation.
    This’ll allow me to do some statistical analysis, and will be a good way to teach myself about databases and statistics.  In particular, I want to create a practical way to estimate the rate of evolution or devolution in either living things or self-copying programs.  Of course, I’ll have to first check if someone has already done this.
  8. Publish simulator on node.js’s repositories
  9. Make the core algorithm modular, such that I can easily change the rules without destroying previous work
  10. Add the ability to save/load the current configuration, in a way that will allow me keep a catalog of experiments done and re-run them later.

I don’t know when I’ll end up doing all these things.  Now that I’m in college, I expect that I’ll do most of them during the summer.

This is part of a series: Testing Evolution

Creative Commons License
Muller’s Foundry Screenshot by https://erikpopp.com/testing-evolution-how-i-did-it is licensed under a Creative Commons Attribution 4.0 International License.

Advertisements

4 thoughts on “Testing Evolution – How I Did It

What do you think?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s