Illustration of Constructive Neutral Evolution


(Andy Walsh) #1

Inspired by a conversation elsewhere, I’ve started working on a evolutionary computation project. The first goal is to illustrate how constructive neutral evolution works, although it may have other useful applications. I thought folks here might be interested in it as well.

Scenario: I’ve created a simple game for 1 or more ‘players’ who have to clear a room of targets/enemies. The actions of the players are encoded in a genome and are thus fully determined before the game begins. Player actions are followed in sequence until the room is cleared or until the end of the genome is reached. The score is the total number of successful hits on targets/enemies.

Available actions include ‘move 1 step’ and ‘attack’. Either action is accompanied by a direction: up/down/left/right.

Inspiration: The game was originally conceived as a simulation of the X-Men’s Danger Room, where the X-Men train to hone their superpowers and their teamwork. It makes the programming more fun for me, and perhaps it provides a nice hook for some. If you’re not familiar with the X-Men, you can just think of it as a game as described above.

What It Looks Like: Here is a 1 player version with a random genome. He starts in the lower right; his targets are the four pink/purple robots. Notice that he does not score any points but does lose most of his health.

SoloCyclopsRandomStart

Now we can mutate the genome and see if it produces a score as good or better for the player. If it does, we keep it and mutate again. If not, we go back to the prior genome and mutate it again. Via this adaptive evolution, we can get a genome that allows the player to get a perfect score.

SoloCyclopsEvolvedSolution

Now so far, all we’ve demonstrated is yet another example of a genetic algorithm optimizing an objective function. What about neutral evolution?


(Andy Walsh) #2

Neutral Evolution Now let’s add some additional players. At first, they make no contributions to the final score. They are just bystanders while player 1 completes the whole room.

TeamStartOnlyCyclops

Then we let their genomes mutate, only requiring that collectively they maintain the same score. What can then happen over time is that some of the other players start scoring points. Subsequently, player 1 develops mutations such that he can no longer get a perfect score by himself. All of these mutations are neutral with respect to the team score in the room. And we go from a 1 component solution to a 4 component solution, which is more complex. Yet the fitness function does not select for more components, and the individual mutations that allowed the other players to score points were not selectively advantageous either. The increase in complexity occurs purely by neutral drift.

TeamStartCNE


(Andy Walsh) #3

For those who prefer data to animations, we can look at how our players individually perform on the task over subsequent generations. Their team score remains the same in each case, but we can also run them through the game individually and see how they do. Over time, the score for player 1 (Cyclops) goes down so that he no longer can get a perfect score alone, while the scores of Iceman and Jubilee go up. (Jean Grey cannot score points directly, but can deactivate robots to prevent her teammates from losing health.)

Each chart shows the distribution of scores across 64 trials at 64-generation increments. The red dot and bars represent the mean score +/- 1 standard deviation. The blue dot is the median score. Similar results are seen if all 4 players have the same attack action.


(James McKay) #4

Looks interesting. Do you have any code that you can put up on GitHub for us to check out?


(Andy Walsh) #5

At the moment, interested parties are welcome to take a look at the Javascript code I wrote for a proof-of-concept web page demo. (JS code: http://faithacrossthemultiverse.com/DangerRoom.js Web page: http://faithacrossthemultiverse.com/DangerRoom.html)

I ultimately intend to organize into a more formal software package of some kind, at which point there will definitely be a GitHub page or equivalent. One of the reasons I’m sharing it is that I’m actually curious what would be the most helpful format. If left to my own devices, I am likely to turn it into an R package, because that’s what I’m most familiar with. But perhaps some other kind of application/library/module would be more appropriate. I’m especially interested to know what would make it useful as a teaching resource.


(system) closed #6

This topic was automatically closed 6 days after the last reply. New replies are no longer allowed.