Ask Alex Mohr about genetic algorithms ...

Unless otherwise stated, all original content on this site is licensed under your choice of the GNU FDL or the Creative Commons ShareAlike License.

GNU FDL Creative Commons License

A genetic algorithm robot maker

This program tries to evolve robots. It displays its progress using SDL. It was inspired by a program written by Travis Bemann, a cool OCaml guru who hangs out at the UPL. A screenshot is below.

screenshot of robots and hearts

The situation in my program is as follows. On a plane (actually the surface of a torus since it wraps around) we have a number of robots and some hearts. The robots eat the hearts to become healthy (think video game hearts). A robot eats a heart by running over it; when that happens, a new heart is generated elsewhere. Each of the robots has some primitive sensors that let it ‘look’ in eight directions and get an idea of how far away the nearest heart is in that direction. If the nearest heart is too far away, a robot can’t see it at all. Based on this information, a robot decides how to move according to a ‘program’. A robot can turn left or right and move forward. The robots have no state; they can only base their movement decisions on the input of their sensors at that instant. The robots have an internal random number generator so their programs can be non-deterministic.

The program initially randomly places robots and hearts. The robots start with totally random programs. The program runs the robots for a little while, then tallies up how many hearts each one got. The program of the robot that got the most hearts is copied and a random, slight modification is made. This mutated program is then given to the robot that got the fewest hearts. Next the robots and hearts are repositioned and everything is run again.

The robots in the first few generations act erratically. Some sit in one place, others go in circles or just straight ahead. After only ten or twenty generations we notice they begin to bump into hearts more. They still appear to move more or less aimlessly, however. To test how well this system works, I hand coded a program for a robot before running the evolution for an extended period. Much to my delight, I found that the evolving robots eventually did better than my hand coded one!

Here is a graph showing the progress of the robots during one run of the program.

graph of robot evolution progress

The x-axis is the generation, and y-axis is the average number of hearts each robot ate in that generation. The red line is the average number of hearts my hand coded robot would eat.

It’s easier to see what’s going on if we use a log scale for the generation number.

graph of robot evolution progress

I ran the evolution for a bit longer than is shown, but the robots didn’t seem to get any better.

I tried looking at the programs of the successful robots that evolved, but they were incomprehensible. I suppose if you studied them hard you would be able to figure why they tend to work, but upon initial inspection they appear to have no rhyme or reason. The programs seemed to contain a lot irrelevant computation mixed in with the parts that actually make it work.

Sometimes I wonder if this situation is similar to the situation of trying to understand the human brain/mind. I imagine looking at the mind on many different levels:

intuitive notion of human behavior
chemistry (of neurons)

The bottom levels are well understood. We can do a pretty good job of describing the functioning of neurons with mathematical models and comprehensible rules. We also can say things when looking at the top levels. It is hard to make concrete statements at that level, but we can certainly pick apart human behavior and describe it.

But what about all the levels in between? These are mysterious. Really, the question on my mind at the moment is ‘Are there even levels in between?’. In that question, I use the word ‘levels’ to mean a degree of abstraction from which the system can be viewed and understood to some extent. Maybe the whole thing just works, and there isn’t really any simple way of understanding how. Maybe nature doesn’t design things the way an engineer would.

With the evolved robots we can also understand at the low-level and at the high-level. At the low-level, we can look at each operator in their programs and understand how it works. At the high-level, we can say the robots tend to go toward hearts. But, unlike in my hand coded robot, it’s hard to see what’s happening in between.