Grokbase Groups Perl ai January 2002
FAQ

Search Discussions

  • John Douglas Porter at Jan 4, 2002 at 6:45 pm

    Ala Qumsieh wrote:
    Recently, I started reading about GAs, and thought that the best way to
    learn is to actually write a Perl module, and play around with it.
    Absolutely!

    For lack of a better name, I called it AI::Genetic, but I'm open to
    change if someone has a better suggestion. Of course, any other
    suggestions/flames/improvements are more than welcome :)
    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?

    --
    John Douglas Porter

    I no longer love the color of your sweaters.
  • Ala Qumsieh at Jan 4, 2002 at 7:27 pm

    John Porter writes:

    The class is hard-wired to only handle individuals which are
    bitvectors.
    That is unnecessarily restrictive. In fact, the GA algorithm
    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?
    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.
    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.
    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.).
    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!
    How to handle identical individuals? Why is it a problem?
    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
  • John Douglas Porter at Jan 4, 2002 at 9:30 pm

    Ala Qumsieh wrote:
    John Porter writes:
    The class is hard-wired to only handle individuals which are
    bitvectors. That is unnecessarily restrictive.
    Is it really restrictive? ... 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.
    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.

    This leads me to think that maybe a multidimentional
    bit vector can be implemented instead of the single dimentional one I have
    right now.
    As long as you do multi-point crossover, you already have that.

    What other representations can be used for the genetic string other than bit
    vectors?
    Anything symbolic.
    Just because you *could* shoehorn it into a bitvector representation
    doesn't mean you *should*. ;-)

    Let me see if I understand you correctly. I should have an
    AI::Genetic::Individual class that handles the representation of each
    individual.
    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.
    It also implements all the evolutionary methods.
    If you mean mutate/crossover/fitness -- yes.

    So, a default strategy would be to evolve each generation according to the
    current process (namely selection -> crossover -> mutation). ...
    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.

    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.
    Precisely. :-)


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

    --
    John Douglas Porter

    I no longer love the color of your sweaters.
  • Juan J. Merelo at Jan 5, 2002 at 4:20 pm
    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:
    Hi all,

    Recently, I started reading about GAs, and thought that the best way to
    learn is to actually write a Perl module, and play around with it.

    The module is attached to this email. Please bear in mind that I am new
    to this area, so the module is still in early alpha mode. There is a
    test.pl script included which shows how to use the module. Also, the
    module is documented in POD, so run perldoc on it to get more info.

    For lack of a better name, I called it AI::Genetic, but I'm open to
    change if someone has a better suggestion. Of course, any other
    suggestions/flames/improvements are more than welcome :)

    Enjoy,
    Ala

    --
    PPSN2002 => http://ppsn2002.ugr.es
    Home => http://geneura.ugr.es/~jmerelo
    Tutorial Perl => http://granavenida.com/perl
  • Pete Sergeant at Jan 5, 2002 at 4:24 pm
    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

    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:
    Hi all,

    Recently, I started reading about GAs, and thought that the best way to
    learn is to actually write a Perl module, and play around with it.

    The module is attached to this email. Please bear in mind that I am new
    to this area, so the module is still in early alpha mode. There is a
    test.pl script included which shows how to use the module. Also, the
    module is documented in POD, so run perldoc on it to get more info.

    For lack of a better name, I called it AI::Genetic, but I'm open to
    change if someone has a better suggestion. Of course, any other
    suggestions/flames/improvements are more than welcome :)

    Enjoy,
    Ala

    --
    PPSN2002 => http://ppsn2002.ugr.es
    Home => http://geneura.ugr.es/~jmerelo
    Tutorial Perl => http://granavenida.com/perl
  • Michael Fragassi at Jan 5, 2002 at 6:59 pm
    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.

    On Sat, 5 Jan 2002, Pete Sergeant wrote:

    Possibly you missed the part where he said he wrote it to teach himself?
    Sorry to dissapoint you.
  • Ala Qumsieh at Jan 6, 2002 at 1:07 am

    Juan J. Merelo writes:

    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 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 :)
    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...
    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.
    Opeal is an open source project, so any suggestions and/or
    improvements
    are also welcome, of course...
    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
  • Juan J. Merelo at Jan 6, 2002 at 7:21 am
    Hi,

    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.

    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.

    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.

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

    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.

    That would be just great. Thanks!

    J
  • John Douglas Porter at Jan 7, 2002 at 10:26 pm

    Juan J. Merelo wrote:
    The ideal is supposed to be ~ 20/80, but some
    purists say it should be ~ 1/99.
    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.

    Genetic programming, actually, uses
    only some very specific kind of mutations,
    Well, sure; so does GA. Flipping a bit is very specific, yes?

    [GP] makes up for lost diversity by creating a huge and diverse initial
    population.
    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.

    OPEAL comes closest to it, if only I find the time
    to upload it.
    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.

    --
    John Douglas Porter

    I no longer love the color of your sweaters.
  • Juan J. Merelo at Jan 9, 2002 at 6:59 pm

    John Douglas Porter wrote:

    Juan J. Merelo wrote:
    The ideal is supposed to be ~ 20/80, but some
    purists say it should be ~ 1/99.
    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.

    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.

    Genetic programming, actually, uses
    only some very specific kind of mutations,
    Well, sure; so does GA. Flipping a bit is very specific, yes?


    Yep, right.


    [GP] makes up for lost diversity by creating a huge and diverse initial
    population.
    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).

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

    One simple way to see this is to consider that in (standard) GA,

    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).

    OPEAL comes closest to it, if only I find the time
    to upload it.
    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.


    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
  • John Douglas Porter at Jan 9, 2002 at 7:52 pm

    Juan J. Merelo wrote:
    It's usually bounded, right? Not theoretically, but most experiments
    limit tree depth.
    Yes, sure. Unbounded Growth, Bad. :-)

    nowadays, size-changing genomes are used (for instance,
    evolving neural nets).
    Sure.

    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.
    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.


    --
    John Douglas Porter

    I no longer love the color of your sweaters.
  • Juan Julian Merelo Guervos at Jan 10, 2002 at 8:30 am

    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.
    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.
    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

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupai @
categoriesperl
postedJan 4, '02 at 5:30p
activeJan 10, '02 at 8:30a
posts13
users6
websiteperl.org

People

Translate

site design / logo © 2021 Grokbase