Robotics Reference
In-Depth Information
fitness can be more accurately estimated, perhaps by calculating its aver-
age performance over all the sample problems.
Once each program in the population has been assigned its fitness
value, a new population of programs is created by choosing the fitter
programs (those that performed best), making copies of them and then
creating pairs of new programs from pairs of existing programs, using
the same crossover idea employed in genetic algorithms and applying the
crossover process at a not-quite-randomly chosen point within each pro-
gram of a pair. The crossover process creates new programs by combining
parts of existing parent programs. The choice of crossover points is not
made entirely at random, as that would often result in logical sections
of a program being broken up. Instead the choice is a random selection
made from those points in programs where one logical section of the
program begins and another ends. In this way entire logical sections are
swapped about, thereby always resulting in programs that conform to the
rules of the programming language. And because programs are chosen
to be part of a crossover process with a probability based on their fit-
ness, the offspring programs, those created by crossover, are much more
likely to contain parts from promising programs than parts from pro-
grams that performed poorly in the most recent test run. Once two new
programs have been created by crossover, two of the less fit programs are
eliminated from the population, in order to keep the total size of the
population constant.
The final step in each iteration of the evolution process is to create
some programs by mutation, again in a very similar way to that employed
in genetic algorithms. The mutation process in genetic programming is
performed by randomly selecting a crossover point in one program rather
than in two, and then deleting the next logical section of that program
and growing a new section to replace it. Each of the programs in the
new population is then set to execute its given task and the result of the
best performing program is tested to see whether it is a solution or close
to a solution to the problem. If the best performing program is deemed
to be good enough, the evolution process terminates; otherwise a fresh
iteration begins and the whole process is repeated.
Self-Reproducing Hardware
The work of Rodney Brooks at MIT and at his company iRobot have
encouraged others to investigate self-reproducing hardware. Similar re-
