31 Days – Genetic Programming

We’re most of the way through August’s 31 Days of Wonder and I haven’t even told you about one of the coolest things I’ve ever heard of.

Genetic programming is a method of writing software in which the code is evolved rather than intelligently designed. The author does not write code to solve a particular problem, but constructs a system in which bits of code are randomly swapped about and mutated to form thousands of programs that compete with each other to solve the problem.

It’s important to realize that the program as it comes out of the brain of its author is totally stupid. It is not equipped to solve or do anything. Yet, through mutations, recombinations and survival-of-the-fittest tournaments, a solution emerges.

The video below is an example: simulated fish swimming around to get food. Each fish is powered by a program that has only four inputs:

  1. His direction.
  2. His velocity.
  3. The distance to the closest piece of food.
  4. The direction to that piece of food (an angle).

And only two things come out of its brain:

  1. How fast to flap his right flipper.
  2. How fast to flap his left flipper.

Initially, the input statistics are combined using a random assortment of arithmetic operators to produce the outputs. For example, the speed of the right flipper might be given by

R = (2 * fish-direction / velocity + velocity / angle-to-closest-food) * 100 + 1

and the left by

L = square-root(velocity) + 25 / distance-to-closest-food + angle-to-closest-food

In other words, total nonsense. The crucial point is that at no time does the human programmer say to himself, “Now what would be a sensible way to get from the inputs to the outputs?” In other words, there is no intelligent design(One could contend that the entire system is intelligently designed even if the simulated life is not. On the other hand, how much intelligence is really built into a system that just throws things together randomly, with occasional mistakes/mutations? And the idea of survival of the fittest is a tautology.)

Each fish has its own distinct random equations. At each generation, the equations from the fish that are most successful at finding food are randomly chopped up, mutated and recombined. This simulates the process of sexual reproduction, with the fittest individuals surviving to breed and recombine their genes, possibly with a few mutations thrown in. (Mutations are actually rare in genetic programming, just as they are in real life. Most of the evolution comes from the reassortment of existing material.)

With that background, I hope you enjoy the video.

Isn’t it amazing how fish that start out so stupid evolve to look so purposeful? And that they do so with no external intelligence applied beyond (a) an algorithm that randomly recombines “genetic material” and (b) the pressure of natural selection?

Here’s another fun one in which a simulated human evolves the ability to stand. The details are not given but my educated guess is that inputs are the force gravity exerts on each segment of the human, and the position of each segment. The output is the angle of each joint. An individual’s fitness seems to be measured by the average distance his head is from the ground during a fixed measuring period. Only the best human from each generation is shown. It’s almost touching to watch him struggle.

There are many more videos like this on YouTube and elsewhere. Search for genetic programming, virtual evolution, or similar terms.

If you’d like to learn more, a free yet comprehensive place to start is A Field Guide to Genetic Programming, available at that link or from Amazon.

Enjoy and wonder!

Leave a Reply

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