Subject:
|
Re: Genetic programming (was "Re: IR camera?")
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Sat, 13 Feb 1999 04:56:35 GMT
|
Original-From:
|
Pam Durham <PDURHAM1@IX.NETCOM.nomorespamCOM>
|
Viewed:
|
1921 times
|
| |
|
|
Of course the chief problem with genetic algorithms is that they take a
tremendous amount of time to converge on an interesting solution.
Actually the problem isn't so much the time as the number trials.
Consider this:
You need to have enough genes in the pool to cover your problem space. You
problem space is defined by the number of variables you wish to optimize.
You get the number of variables by parameterizing the problem you are trying
to solve.
The more genes you have in your pool the richer and more diverse it is,
which will help you reach an optimal solution. The problems that you are
talking about such as a lego factory could have many hundreds of parameters.
Let's say you are able to narrow this down to several dozen. Say each
parameter is 1 byte. You would need several thousand genes in the pool to
converge on a solution.
In a genetic algorithm each gene must be evaluated by running a fitness
function against it. I would presume that this would be the ability of the
design to run a maze as was suggested below. This could take several
minutes to several hours to run for each gene. Say you limit it to 15
minutes. You would multiply 15 minutes by the number of genes in the pool
to get the amount of time to run one generation. My experience is that it
can take several thousand generations to converge on a good solution for
complex problems like these. This means that you could be looking at well
over 15,000,000 minutes to converge on a good robot design. (Of course this
isn't including the time it takes you to run down the maze, pick up the
robots and put them at the starting line again. :->)
This is why in the literature you see that the researchers all use
simulations. Simulations can be run against a fitness function
automatically and in the memory of the computer. If you have a
multiprocessor machine you can attain tremendous efficiencies.
But don't get me wrong, I think that there are some interesting things that
can be done with GA and Lego, just don't delude yourself. This is where an
RCX simulator would be handy. You could then do some Genetic Programming
and automatically evaluate the fitness.
Good luck,
Doug
-----Original Message-----
From: Bryan Beatty <bryan.beatty@autodesk.com>
To: lego-robotics@crynwr.com <lego-robotics@crynwr.com>
Date: Friday, February 12, 1999 1:19 PM
Subject: Genetic programming (was "Re: IR camera?")
> Mike Moran wrote:
> >
> > lego-robotics@crynwr.com (Pete Hardie) writes:
> > > Frex, let's say you have your factory, and each legobot carries its
> > > building instructions, and each
> > > is programmed to run a maze. You have the factory at the end, and it
> > > closes its doors after
> > > 10 legobots have entered. You will get fast maze running robots from
> > > this.
> > Don't be too sure. Unless you constrain it a lot you could get one or
> > two robots which travel fast enough to jam the door and the rest just • meander
> > on through becuase it's jammed open. This is perhaps a bit contrived but • I'd
> > be wary of making too specific statements of what a GA evolved system • will do;
> > too many people have got caught on this before. An example is one of Karl • Sims
> > creatures which was taking part in a GA which had maximim speed as the • main
> > metric: it's strategy was just to grow tall and then fall over hence • achieving
> > a maximum speed whilst falling over; I doubt if he would have been able • to
> > predict this given the seemingly reasonable constraints he placed on it.
>
> Genetic programming in general often exhibits unintended results,
> namely:
>
> 1. Unless you're very careful, it ends up optimizing for the special
> cases rather than the general class of problem you want to solve. In
> the above example, you're likely to end up with robots that can run that
> particular maze, but would be utterly lost in a different configuration.
>
> 2. Genetically programmed critters will find and exploit unintended
> weaknesses in your problem space-- they "cheat." The example you gave
> of tall critters falling over was an excellent one; they were exploiting
> a loophole in the rules for judging results. Another result that Karl
> Sims got was in an early version of his physical simulator that had a
> subtle bug in the collision-detection routines. His critters found and
> exploited that bug: they evolved a behavior in which by "spanking"
> themselves, they could propel themselves across his virtual universe at
> practically lightspeed.
> --
> Did you check the web site first?: http://www.crynwr.com/lego-robotics
--
Did you check the web site first?: http://www.crynwr.com/lego-robotics
|
|
1 Message in This Thread:
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
