Evolving Boids

An experiment in natural selection and flocking behavior.

Posted by Rupert Deese on January 14, 2015

Why are living things so complex?

Living things exhibit many complex behaviors, on a spectrum ranging from behaviors that seem instinctual, to those that seem intelligent. Scientific evidence suggests that these behaviors arise from Darwinian evolution. Evolution refers to the change of a species of living thing (dogs, cats, elephants, elm trees, yeast) over time. The mechanism for this change is natural selection.

Natural Selection

Living things on earth are complex products of their ancestors, their contemporaries, and their environments, so it would be incorrect to ascribe the appearance or behavior of any living thing to any one mechanism. However, biologists have identified that the development and maintenance of all living things on earth is controlled by a molecule called DNA.

The DNA of every organism consists of a unique sequence of base pairs, containing instructions that are read by the organism's cells. This unique sequence of base pairs is called a genome. This genome encodes a collection of traits which all together are called the organism's phenotype. When living things reproduce, they pass their genotype on to their offspring. If the reproduction is sexual, then the offspring's genotype is a blend of the two parents' genotypes. The offspring genotype is also subject to mutation, which makes small, random changes to it. Thus the offspring's genotype (and consequently phenotype) will be inherited from its parents.

A living thing's phenotype largely determines the way it interacts with its environment, including whether it will live long enough to reproduce. We call an organism's ability to reproduce its fitness. Fitter organisms will contribute more offspring to the population than others, making their genotypes more common in the population. Since these genotypes produce phenotypes that were fitter in the first place, this tends to increase the fitness of the population overall, as long as the environment doesn't change too much. This is the core of natural selection.

The Blind Watchmaker

Biologists all agree that natural selection created every variety of living thing that has existed. This claim may seem unbelievable: there is so much diversity, complexity, absurdity, and beauty in the natural world! Natural selection seems as impossible as a blind watchmaker, assembling beautiful creatures that can grow hundreds of feet tall, live at the bottom of the ocean, or communicate over hundreds of miles, all in the name of this boring concept of fitness. Furthermore, nobody has been able to show that natural selection could have produced all the living things that we see. In order to do that, we would need to know things about the environments, populations, and chance occurrences of the distant past (billions of years ago!) that are impossible to know.

Even so, natural selection doesn't have to be taken on faith. There are many different kinds of evidence that support it, and a lot of people happy to explain them. But I think that the funnest way to learn about natural selection is to watch it happen right in front of you.

Creating a Model for Natural Selection

If natural selection really does work, then we should be able to watch it happen if we create the right conditions. We'll need:

  • living things that can reproduce and pass traits on to their offspring
  • an environment that favors some traits over others

The Living Things

We'll call our living things "boids." (Like "birds," only in a thick New Jersey accent.) Our boids are little black dots, living in two dimensions. They are born, they move around their 2D world, and they die. The boids have some physical limitations: they have a top speed and a top acceleration, and they can't stop moving. Most importantly, the only things that they are aware of are the other boids near them.

No HTML5 Canvas support :( A boid and its visible neighborhood.

Genotype and Phenotype

The phenotype of a boid is the way it moves, in response to its own movements and those of neighboring boids. This phenotype is encoded into a genotype with five individual genes. Each gene is a decimal number. These genes determine how the boid moves (changes its acceleration), in response to five different properties of itself and its environment. The genes and the properties they control the response to are as follows:

  1. the boid's acceleration
  2. the boid's velocity
  3. the difference between the boid's acceleration and its neighbors' accelerations
  4. the difference between the boid's velocity and its neighbors' velocities
  5. the difference between the boid's position and its neighbors' positions
The boid genome.

Specifically, the boid decides its new acceleration at every moment using the following formula:

The boids' governing equation.

Reproduction

Boids reproduce sexually. (Let's not go into the details.) Every new boid inherits its genome from a combination of two parents' genomes, using a mechanism called crossover. After the two parents are chosen, a crossover point is chosen randomly. The new boid gets the genes to the left of the crossover point from one parent, and the genes to the right of the crossover point from the other. For example, if the crossover point was between genes 2 and 3, the new boid would get genes 1 and 2 from one parent, and genes 3, 4, and 5 from the other. After crossover, every gene in the new genome is randomly mutated by a small amount.

To simplify reproduction in our little boid-world, a new boid is born whenever a boid dies. The parents of this new boid are chosen randomly from the set of all boids that have at least one neighbor. The new boid is born into the world at a random location.

The Environment

Our environment is a tough place for a boid. If two boids collide with one another, both boids die. In addition, boids without any neighbors are not safe: if a boid isn't near any other boids, it has a one-in-twelve chance of dying at any moment.

Our environment has no boundaries: although we will see it as a 2D rectangle, the top edge wraps around to the bottom edge, and the left edge to the right edge, making it a continuous space.

A Boid Experiment

Now that our boids are fleshed out in our imaginations, let's bring them to life and see what happens!

Hypothesis

As far as we can tell, the boids and their environment have all the right conditions for natural selection. So if we set loose some actual boids, we would hope to see natural selection take effect on the boid population. What would be evidence of natural selection? We know that natural selection tends to increase fitness in the population as long as the environment doesn't change, and our environment is constant. Also, we know that if fitness is increasing, genotypes similar to the fittest genotype must be becoming more common. If natural selection is happening, then:

  • the phenotype (visible movement) of the boids will change over time
  • the average fitness of the boid population will increase over time
  • the average genotype of the boid population will approach the most fit genotype, over time

Procedure

In order to check our hypotheses, we'll create a boid-world to observe. The boid-world below initially contains 120 boids, all with the same null genome. This genome corresponds to a phenotype of no response to anything. The world will exist for around 3 minutes, and then start over again. The graphs show information about the average genome and fitness of the boids.

The top two graphs contain information about the current boid-world above, as it runs. The graph on the upper left shows the value of each gene in the average boid genome. The graph on the upper right shows the average age of all boids currently living. The x-axis represents time. Once the world starts over, the contents of the top two graphs is added to the graphs below them. The bottom graphs show the final top graphs of every past boid-world.

Watch the boids for a while, or just leave this page open in the background for 10 minutes or so, to gather results from a few separate boid worlds.

The Boid-World
This text is displayed if your browser does not support HTML5 Canvas.
Current Genome
No canvas support :(
Current Fitness
No canvas support :(
All Genomes
No canvas support :(
All Fitnesses
No canvas support :(

Observations

If you've let our little experiment run for a while, you've probably noticed that:

  • The behavior of the boids, which looks random when a world begins, looks different after a few minutes. More interestingly, the boids develop very similar behavior in every successive world! Personally, their behavior reminds me of birds flocking.
  • In every world, the average age of living boids increases over time.
  • The average genome doesn't stay the same, and the final values of certain genes, especially genes 3 and 4, tend to be the same in every world.

Conclusions

Let's remind ourselves of our three hypotheses:

  • the phenotype (visible movement) of the boids will change over time
  • the average fitness of the boid population will increase over time
  • the average genotype of the boid population will approach the most fit genotype, over time

What does the boid experiment say about our hypotheses? The conclusions are yours to draw, but I'll leave you with a few of my own thoughts.

Visible Behavior

Our first hypothesis involved observing the boids to see if their behavior changed over time. "Changed" is a very qualitative measure, but some qualitative measures are very powerful and intuitive for us humans. For example, you probably don't need a microscope to tell if something is alive or not. You can just tell somehow. How would you describe the boids' behavior, at the beginning of each world and at the end?

Measuring Fitness

In the boid-world, boid parents are chosen randomly amongst living boids. Therefore, The only way for a boid to increase its number of offspring is to stay alive for as long as possible, to increase the number of times it is chosen! So, the average age of living boids might be a good measure of the boids' average fitness.

The Fittest Boid Genotype

I don't know of a way to figure out what the fittest boid genotype is, even though I might have some intuition about it. What do you think? Even if we don't know what the fittest genotype is, if different boid worlds seem to be heading to the same genotype, and the average fitness in all of those worlds is increasing, what can we conclude?

Repeatability

There is a lot of randomness in the boid-world: random starting configuration, random selection of parents, crossover, and mutation. Is it surprising that the boid-world consistently develops in the same way? If the development of many separate boid worlds is the same, does that give us more confidence that our observations are valid?

If it walks like a duck...

We've taken a small journey exploring the idea of natural selection, and how it might relate to living things on earth. I hope you've enjoyed it--I certainly did. If the way the boids behaved seems at all lifelike to you, I think it's interesting to ask the question:

"What does it mean for something to be alive?"

If natural selection is at work amongst the living things on this planet, and you saw natural selection work on the boids, what is the difference between boids and the things that we usually call "living?" Certainly DNA-based life is more complex, but is that what matters? The boids changed over time to become more fit in their environment, and complex behavior emerged from chaotic behavior. Might that be what life is about?

As the saying goes, "if it walks like a duck, swims like a duck, and quacks like a duck, call it a duck."

Further Investigation

  • This project is entirely on GitHub. Suggestions, questions, comments, and contributions are welcome.
  • Craig Reynold's original paper on programing flocking behavior
  • Harry Brundage's blog post on pre-programmed flocking behavior.
  • Artficial Life by Steven Levy, an excellent book which sparked my interest this area to begin with.
  • Probably Approximately Correct, a recent book about our modern mathematical and computational understanding of learning and evolution, written by Leslie Valiant, who somewhat invented the field.
  • Richard Dawkins' The Ancestor's Tale, the authoritative story from the natural selection perspective of evolution.
  • Of course, you don't have to buy the books! Online, natural selection and artificial life are good places to start.