Robotics Reference
In-Depth Information
The mutation process is designed to ensure that evolution does not
gravitate prematurely to a local summit. What happens is that a small
fraction of the genomes, selected at random, undergo a very slight mod-
ification (corresponding to mutation). Following the hill-climbing anal-
ogy, this part of the process can be thought of as short excursions for
exploration purposes, “looking around” the hilly area for a potentially
promising route to the global summit, rather than stagnating at a partic-
ular location from where it is impossible to see how to improve the next
generation.
The optimal solution at the end of the evolutionary process will be
the fittest member of the final generation of the population, which may
be the best possible solution or it may not. Thus the evolutionary meth-
ods employed in genetic algorithms do not guarantee to find the perfect
solution to a problem, or, expressed in hill-climbing terms, genetic al-
gorithms will not always find the highest peak in the area. But genetic
algorithms have been proven to be extremely effective in an enormous
variety of tasks, with a huge raft of success stories to their credit. One
classical problem in mathematics that has been solved with the help of
genetic algorithms is the so-called Travelling Salesman Problem.
30
An-
other success story is a program called GenJam,
31
developed by Al Biles,
that learns to play jazz solos. GenJam creates jazz improvisation “riffs”
(short, rhythmic phrases) and Biles tells the program whether each riff
is good or bad, thereby improving the program's fitness measure. After
much training, GenJam has become a formidable improvisation partner
for jazz musicians.
The most remarkable achievements of all in this field are, perhaps,
those from an offshoot application that is still in its infancy, a topic called
Genetic Programming. Imagine for a moment what would happen if, in-
stead of using genetic techniques to breed better and better solutions to a
problem (the algorithms), we were instead to employ the same techniques
to breed better and better computer programs. What an enormous power
that would give us! Instead of asking a robot to go away and find a so-
lution to a particular example of the Travelling Salesman problem, we
would be able to say it: “Here is the nature of the problem. Go away and
develop a computer program to solve all such problems.” A discussion of
30
A salesman must visit several cities once and only once. What route enables him to accomplish
this while travelling the shortest possible distance?
31
For Genetic Jammer.
