[Perl-AI] Perl Genetic Algorithm Module

Absolutely!

Let's defer that until the module is actually ready to put on CPAN, eh?

Some comments:

The class is hard-wired to only handle individuals which are bitvectors.
That is unnecessarily restrictive. In fact, the GA algorithm shouldn't
care about the internal representation of the individual. Make a
separate class for bitvector individuals; it can implement a some
necessary methods -- mutute, crossover, fitness -- which GA will then
call. GA itself should only implement the evolutionary process.
Also, consider making the generation process (creating the next gen
from the previous) a Strategy, since this could be rather more complex
than the simple "select/mutate/crossover" pipeline you've got now.
If you do that, then the strategy object would also be a good place
to store the parametrics (mutution prob., etc.).


How to handle identical individuals? Why is it a problem?

Is it really restrictive? As I said, I'm not really an expert in this field,
but the way I see it is that if the user wants more than a single bit to
represent a given feature, then he/she can still use the module the way it
is, but will have to do some manual high level grouping of the bits to get
the information needed. This leads me to think that maybe a multidimentional
bit vector can be implemented instead of the single dimentional one I have
right now.

What other representations can be used for the genetic string other than bit
vectors?
Let me see if I understand you correctly. I should have an
AI::Genetic::Individual class that handles the representation of each
individual. This class may or may not use bit vectors as an internal
representation. It also implements all the evolutionary methods. All the
AI::Genetic module itself does is to instantiate the individuals, and to
call their evolutionary methods according to what the user requested.

This approach seems more suitable (it doesn't need to change the API, but at
this point, I don't really care if it does), and lends itself quite nicely
to any additional extensions to the module.
So, a default strategy would be to evolve each generation according to the
current process (namely selection -> crossover -> mutation). But, there can
be other defined strategies, and the users should be able to create their
own simply by combining those three steps however they like. I like that!
I thought maybe I can improve the speed of the processing by eliminating
duplicates, but maybe it's not such a good idea. After all, if there are
many individuals with the same genes, then there is a reason for this and
this will favour them more in keeping their genes alive in generations to
come.

Thanks a lot for your input. And, please keep 'em comin' :)

Ala

Yes, it is restrictive. As a simple example: let's say I have a feature
which can have 128 distinct values. I need to allocate 8 bits for that,
which means that about 50% of the possible values obtained by
mutation/crossover will be invalid.
More critically, it means that the probability of mutating that feature
will not be m, but actually 1-((1-m)^b); that is, the probability is
"compounded" by the number of bits in the feature.
Similar predicament holds for crossover as well.

Another issue:
Currently you're doing multi-point crossover and considering the
invidual as a vector. These two are not mutually necessary.
If one desires multi-point crossover, the individual can be an unordered
set of features. OTOH, often we want the individual to be a vector so
that we can do 1- or 2-point crossover, exploiting (or just exploring :-)
Building Block effects.

As long as you do multi-point crossover, you already have that.

Anything symbolic.
Just because you *could* shoehorn it into a bitvector representation
doesn't mean you *should*. ;-)

Well, if you want to go OO (which is what I would do), you could make
AI::Genetic::Individual a base class for things like
AI::Genetic::BitvectorIndividual.
If you mean mutate/crossover/fitness -- yes.

Well, if you want to make it a default, I guess that's fine.
I think it would be sufficient to make it one of the predifined strategies
which the user can simply name.

Btw, I might suggest that genetic operations also be factored out from
the representation class(es) into Strategies, since you can have many
different ways of doing mutation/crossover/fitness on a bitvector.

Precisely. :-)


I'd be happy to help you code this stuff up, if you want.

Sorry to disappoint you, but it's been done already: it's provisionally
called OPEAL, it's at opeal.sourceforge.net, and, yes, it will be called
AI::Genetic or Algorithm::Genetic in the future, when it's finally
CPANified and uploaded.

It's been done also some more times: just do a search on Perl genetic
algorithms, and you'll find references, for instance, in Perlmonks...

Opeal is an open source project, so any suggestions and/or improvements
are also welcome, of course...

J

Ala Qumsieh wrote:

Possibly you missed the part where he said he wrote it to teach himself?
Sorry to dissapoint you.


----- Original Message -----
From: "Juan J. Merelo" <jmerelo@geneura.ugr.es>
To: "Ala Qumsieh" <qumsieh@cim.mcgill.ca>
Cc: "Perl AI" <perl-ai@perl.org>
Sent: Saturday, January 05, 2002 6:56 PM
Subject: Re: Perl Genetic Algorithm Module

And personally, I can't imagine anything more appropriate for GA
programming than a slew of competing GA modules.

Although this could be taken too far, giving a real meaning to the phrase
"code or die".

-- Mike F.

It's ok, I'm not disappointed :)
My main reason for coding the module is for learning. I think I will learn
more by coding and trying to figure out why my module behaves the way it is,
than by simply reading about the subject or running some one else's code. In
fact, I did learn already the significance of mutation in diversifying the
genetic population by turning mutation on and off and analyzing the results.

And, in the spirit of Perl itself, I feel compelled to offer anything I
write back to the Perl community regardless of whether something else
(perhaps much better) exists or not. After all, TMTOWTDI :)
Yes, I did a quick search before, and all I find where programs that utilize
genetic algorithms to do certain tasks. I didn't find any generic modules to
do the job.

Nor did I find anything on CPAN.
Great. I'll have a look at it once my experience in this field grows a bit
more. Perhaps I can contribute code/ideas to your module.

--Ala

Hi,


Mutation is the main variation operator in GAs, but there are many kind
of mutation operators; turning it off will probably do away with finding
the solution, but you can try changing the proportion of
mutation/crossover. The ideal is supposed to be ~ 20/80, but some
purists say it should be ~ 1/99. Genetic programming, actually, uses
only some very specific kind of mutations, and sparingly at that; it
makes up for lost diversity by creating a huge and diverse initial
population.


There's none, right. OPEAL comes closest to it, if only I find the time
to upload it.


That would be just great. Thanks!

J

There is no theoretical ideal.
Anyone who says there is is either wrong, or is speaking in the
context of some very specific experimental protocol.

Well, sure; so does GA. Flipping a bit is very specific, yes?

No, that's not true -- at least, no more so than for GA.
GP does not suffer from "loss of diversity" any more than GA.
I would contend that it suffers from the opposite problem;
without heuristic constraints, the genome space in GP is
effectively unbounded (since individuals can grow without bound).
One simple way to see this is to consider that in (standard) GA,
crossover never changes the shape of the genome; whereas in GP,
crossover can (in general) create genome shapes that had not
previously been seen.

You probably already know this, but I'd point out that before
you upload OPEAL to CPAN, you'll need to fix its naming scheme.
Almost all your modules have top-level names.

You are right... of course, there's no ideal, but the rule of thumb says
that mutation shouldn't be too high, or you're turning an EA into a
random search algorithm.



Yep, right.



It's usually bounded, right? Not theoretically, but most experiments
limit tree depth.


Let's say that it does in canonical, Goldberg-style, GA. In many
problems, nowadays, size-changing genomes are used (for instance,
evolving neural nets).



Of course they do; I don't want to commit to a namespace before knowing
which namespace it is. I have already proposed Algorithm::Evolutionary
and AI::Evolutionary or AI::EC (for Evolutionary Computation).

Which one would you vote for? Evolutionary computation is not purely an
artificial intelligence technique, that is why it's better to just leave
it in the Algorithm namespace.

J

Yes, sure. Unbounded Growth, Bad. :-)

Sure.

I would like to see a new top-level catetory created, EC::.
AI encompasses too much stuff, and what it includes is extremely
nebulous. In contrast, it's pretty easy to tell whether something
can be classified as evolutionary, yet the field is still huge.

Now keep in mind that if you have a framework (which I infer that you
do), you may need your own special space for modules which can't
reasonably be used outside the framework.
In other words, don't monopolize EC:: with 20 modules that all have
to work in concert... because I might want to drop a module or two
in EC:: and there should be no confusion.

Proposing a new TL namespace would be too big a change, and still,
evolutionary computation is a group of algorithms, so probably
Algorithm::EC would be a better choice, but then,
Algorithm::Evolutionary is just a good. If I was to to propose a new TL
namespace, I would go for something related to natural computation,
maybe NatComp:: , which would encompass all soft computing techniques
such as self-organization, complex systems, ant systems (and other
stigmergic systems), evolutionary computation, and so on... they overlap
a bit with AI, but are not entirely within it (although some people call
it subsymbolic artificial intelligence...).

J