ANN: pygene - genetic algorithms package

Discussion in 'Python' started by aum, Dec 6, 2005.

  1. aum

    aum Guest

    Hi all,

    I looked at a few genetic algorithms/genetic programming packages for
    Python, and found them somewhat convoluted, complicated and
    counter-intuitive to use.

    So I've written a genetic algorithms package which I hope will be more
    approachable to beginners.

    The first release of pygene is up at:
    http://www.freenet.org.nz/python/pygene

    The package includes full api documentation, and an implementation of
    the travelling salesman problem, plus a couple of simpler cases.

    --

    Cheers
    aum
     
    aum, Dec 6, 2005
    #1
    1. Advertising

  2. aum wrote:

    > I looked at a few genetic algorithms/genetic programming packages for
    > Python, and found them somewhat convoluted, complicated and
    > counter-intuitive to use.
    >
    > So I've written a genetic algorithms package which I hope will be more
    > approachable to beginners.
    >
    > The first release of pygene is up at:
    > http://www.freenet.org.nz/python/pygene
    >
    > The package includes full api documentation, and an implementation of
    > the travelling salesman problem, plus a couple of simpler cases.


    I only scanned through the API documentation, but it looks like only
    genetic algorithms are supported, not full genetic programming. Is this
    not the case?

    I've been planning on releasing my stack-based genetic programming
    system Psi (implemented in Python) at some point in the future, FYI.

    --
    Erik Max Francis && && http://www.alcyone.com/max/
    San Jose, CA, USA && 37 20 N 121 53 W && AIM erikmaxfrancis
    When in doubt, win the trick.
    -- Edmund Hoyle
     
    Erik Max Francis, Dec 6, 2005
    #2
    1. Advertising

  3. aum

    aum Guest

    On Mon, 05 Dec 2005 23:45:30 -0800, Erik Max Francis wrote:

    > I only scanned through the API documentation, but it looks like only
    > genetic algorithms are supported, not full genetic programming.


    Correct. Organisms of a species have a fixed genome.

    > I've been planning on releasing my stack-based genetic programming
    > system Psi (implemented in Python) at some point in the future, FYI.


    Has it got an approachable API? Good doco? Examples understandable by
    newbies? Hope so. There's a lot of good software that gets ruined because
    insufficient work has been put in to its usability and comprehensibility.

    --

    Cheers
    aum
     
    aum, Dec 6, 2005
    #3
  4. aum

    malv Guest

    How is your package different from a nn package? Is this an addon for
    genetic programming or does it include the standard nn components as
    well, such as backprop etc?
    Not being very familiar with genetic programming, forgive me my naive
    question, I could not immediately find the answer.
    Thank you,
    malv
     
    malv, Dec 6, 2005
    #4
  5. aum wrote:

    > Correct. Organisms of a species have a fixed genome.


    My bad, you had mentioned in the announcement that you had looked at
    genetic programming systems but didn't claim that pygene was itself a
    genetic programming system. I misread that; my apologies.

    >> I've been planning on releasing my stack-based genetic programming
    >> system Psi (implemented in Python) at some point in the future, FYI.

    >
    > Has it got an approachable API? Good doco? Examples understandable by
    > newbies? Hope so. There's a lot of good software that gets ruined because
    > insufficient work has been put in to its usability and comprehensibility.


    That's what I'm working on while polishing it for release. It's also
    the case that a well-designed class hierarchy will help folks understand
    the tools that are available to them. "Understandable by newbies" isn't
    all that a high a priority for me when writing complex software; what's
    useful is writing software that's easily used by someone familiar with
    the general concepts, familiar with programming, and familiar with the
    language that the project is implemented in. You can't teach all things
    simultaneously; I'm not sure creating a genetic programming (or genetic
    algorithms) system that's useful to "newbies" (whatever that means) is
    even a useful goal in and of itself.

    --
    Erik Max Francis && && http://www.alcyone.com/max/
    San Jose, CA, USA && 37 20 N 121 53 W && AIM erikmaxfrancis
    As far as I'm concerned, being any gender is a drag.
    -- Patti Smith
     
    Erik Max Francis, Dec 6, 2005
    #5
  6. aum

    Peter Hansen Guest

    aum wrote:
    > On Mon, 05 Dec 2005 23:45:30 -0800, Erik Max Francis wrote:
    >>I only scanned through the API documentation, but it looks like only
    >>genetic algorithms are supported, not full genetic programming.

    >
    > Correct. Organisms of a species have a fixed genome.


    I've done just enough work in genetic algorithms (and a token amount in
    genetic programming) to be perplexed by this comment. Are you
    suggesting that genetic programming is somehow not related to genetic
    algorithms?

    My understanding is that (said perhaps somewhat simplistically) genetic
    programming is an application of genetic algorithms in which the genomes
    are treated as describing the structure of a program whose execution
    basically results in the fitness level for that genome.

    If that's a reasonably accurate statement (or, I suppose, even if it's
    not), would you please clarify how your "fixed genome" comment relates
    to any of this?

    -Peter
     
    Peter Hansen, Dec 7, 2005
    #6
  7. Peter Hansen wrote:

    > I've done just enough work in genetic algorithms (and a token amount in
    > genetic programming) to be perplexed by this comment. Are you
    > suggesting that genetic programming is somehow not related to genetic
    > algorithms?
    >
    > My understanding is that (said perhaps somewhat simplistically) genetic
    > programming is an application of genetic algorithms in which the genomes
    > are treated as describing the structure of a program whose execution
    > basically results in the fitness level for that genome.
    >
    > If that's a reasonably accurate statement (or, I suppose, even if it's
    > not), would you please clarify how your "fixed genome" comment relates
    > to any of this?


    You're not replying to me, but I'm the one that elicited that comment.
    (I was originally asking the question because I misinterpreted the first
    sentence of his announcement about pygene to mean that pygene was a
    genetic programming system, but that was never his claim.)

    A genetic algorithm involves manipulating "programs" which consist of a
    fixed amount of homogeneous data, for instance, an array of neural
    network weights, or the coefficients to an equation. Genetic
    programming involves manipulating general programs, usually as some form
    of tree. The classic model for genetic programming, from Koza, is where
    the programs to be manipulated are Lisp s-expressions.

    pygene implemented a genetic algorithm system, not genetic a programming
    system, hence his response. It was only my interpretation of his
    introductory comment that led anyone to believe otherwise.

    --
    Erik Max Francis && && http://www.alcyone.com/max/
    San Jose, CA, USA && 37 20 N 121 53 W && AIM erikmaxfrancis
    Men live by forgetting -- women live on memories.
    -- T.S. Eliot
     
    Erik Max Francis, Dec 7, 2005
    #7
  8. aum

    Peter Hansen Guest

    Erik Max Francis wrote:
    > You're not replying to me, but I'm the one that elicited that comment.
    > (I was originally asking the question because I misinterpreted the first
    > sentence of his announcement about pygene to mean that pygene was a
    > genetic programming system, but that was never his claim.)
    >
    > A genetic algorithm involves manipulating "programs" which consist of a
    > fixed amount of homogeneous data, for instance, an array of neural
    > network weights, or the coefficients to an equation. Genetic
    > programming involves manipulating general programs, usually as some form
    > of tree. The classic model for genetic programming, from Koza, is where
    > the programs to be manipulated are Lisp s-expressions.


    Okay, good, I already knew all that then, except perhaps that key word
    "fixed".

    Perhaps I've long been using the wrong label, but I've been doing what
    I've considered to be "genetic algorithms" and yet working with
    sometimes variable amounts of sometimes heterogeneous data. I've just
    considered it to be more sophisticated than the "coefficients in an
    equation" class of genetic algorithms, but perhaps I've been operating
    in a gray area between mainstream genetic algorithms and genetic
    programming.

    The genomes are certainly not source, nor translatable to source or AST
    or anything resembling such, in any computer language. Neither,
    however, could they be described as heterogenous, and for some problems
    I've been varying the quantity of genetic material in my genomes. Thus
    my preoccupation with that "fixed".

    -Peter
     
    Peter Hansen, Dec 7, 2005
    #8
  9. Peter Hansen wrote:

    > Okay, good, I already knew all that then, except perhaps that key word
    > "fixed".
    >
    > Perhaps I've long been using the wrong label, but I've been doing what
    > I've considered to be "genetic algorithms" and yet working with
    > sometimes variable amounts of sometimes heterogeneous data. I've just
    > considered it to be more sophisticated than the "coefficients in an
    > equation" class of genetic algorithms, but perhaps I've been operating
    > in a gray area between mainstream genetic algorithms and genetic
    > programming.
    >
    > The genomes are certainly not source, nor translatable to source or AST
    > or anything resembling such, in any computer language. Neither,
    > however, could they be described as heterogenous, and for some problems
    > I've been varying the quantity of genetic material in my genomes. Thus
    > my preoccupation with that "fixed".


    Well, as I'm sure you suspect, there's no "official" definition of
    either term, and there aren't many rigorous definitions in any case.
    Coefficients in a function or weights in a neural network are classic
    examples of a genetic algorithm, but those aren't the only things that
    would be considered genetic algorithms, although obviously at some point
    you'd get into some question about what they were. That there are a
    fixed number of "genes" to be manipulated in general algorithms is also
    not set in stone (though it is typical). For instance, you might be
    looking for a function of the form

    sum_i^n a_i x^i

    where it might make sense to have n vary in a genetic algorithm system.

    As a complete distinct example, if you're talking about a virtual
    machine architecture like Redcode (for Core Wars) with mutation applied
    (VENUS is an example of this kind of investigation from the early
    1990s), then that would probably be considered genetic algorithms, not
    genetic programming. A general distinction (though not the only one)
    might be that with genetic algorithms, the manipulation of the data is
    uniform and completely without reference to its internal makeup. In
    genetic programming, care has to be taken to preserve program legitimacy.

    If you went into detail I could probably tell you whether or not what
    you're doing is "obviously" a genetic algorithm, or "obviously" an
    instance of genetic programming, or somewhere in between. Without
    internal structure it's probably more likely closer to genetic algorithms.

    Not that distinction is that big to begin with; both use very similar
    concepts in order to get from a random population of programs to a
    solution that is ideally fit (if possible), including many of the
    genetic operators (like mutation or crossover) and the way that programs
    are tested for fitness and how fit or unfit individuals are selected for
    or against for a new population. That being said, for many problems, it
    seems that genetic programming has a greater ability to produce
    solutions to much more complex problems (where often you do not even
    know the high-level form that they will take -- something you need to
    decide to put together a genetic algorithm).

    Recent developments, with stack-based languages like those used by
    Spector, have allowed the introduction of types naturally into genetic
    programming, which has a great deal of promise for allowing even more
    involves solutions to complex problems.

    --
    Erik Max Francis && && http://www.alcyone.com/max/
    San Jose, CA, USA && 37 20 N 121 53 W && AIM erikmaxfrancis
    I want to know God's thought; the rest are details.
    -- Albert Einstein
     
    Erik Max Francis, Dec 7, 2005
    #9
  10. aum

    aum Guest

    On Tue, 06 Dec 2005 22:44:39 -0800, Erik Max Francis wrote:

    > Peter Hansen wrote:
    >
    >> Okay, good, I already knew all that then, except perhaps that key word
    >> "fixed".


    One thing I should say here is that pygene is a collection of
    inter-related classes for populations, organisms, gametes and genes.

    Users are encouraged to subclass off these to address the
    problems they're trying to solve.

    For instance, the BaseGene class is completely agnostic about the actual
    data contained in the gene. Any BaseGene subclass only has to implement
    the methods:
    - __add__ - produce phenotype effect of combining a given gene pair
    - mutate - apply a random mutation to the gene
    - randomValue - set the gene's value to a legal random value

    As for the gene's value - as long as the above 3 methods are supplied in a
    subclass, the gene can hold any object - just as long as one's Organism
    subclass' '.fitness()' method can understand what the gene class'
    '.__add__()' method returns.

    A Gene subclass could even hold an AST for a program to be generated.

    It wasn't my original intention to support genetic programming, but in
    theory at least, pygene could be extended into a GP system.

    Hmm, it's tempting to try a bit of GP, perhaps initially generating
    code for a tiny language like BrainFuck, then work up to Forth, Factor and
    beyond.

    --

    Cheers
    aum
     
    aum, Dec 7, 2005
    #10
  11. aum

    Peter Hansen Guest

    Erik Max Francis wrote:
    > If you went into detail I could probably tell you whether or not what
    > you're doing is "obviously" a genetic algorithm, or "obviously" an
    > instance of genetic programming, or somewhere in between. Without
    > internal structure it's probably more likely closer to genetic algorithms.


    You're certainly correct there. The leap to GP is much farther than my
    stuff is from GA.

    >... for many problems, it
    > seems that genetic programming has a greater ability to produce
    > solutions to much more complex problems (where often you do not even
    > know the high-level form that they will take -- something you need to
    > decide to put together a genetic algorithm).


    I agree, and I look forward to seeing Psi some time, if just to help me
    learn more in the area. Thanks again for the comments.

    -Peter
     
    Peter Hansen, Dec 7, 2005
    #11
  12. Peter Hansen wrote:

    > You're certainly correct there. The leap to GP is much farther than my
    > stuff is from GA.


    I'm curious what sort of heterogeneous data setup you had.

    > I agree, and I look forward to seeing Psi some time, if just to help me
    > learn more in the area. Thanks again for the comments.


    Sure thing. Obviously I'll post an announcement here when it's ready.

    --
    Erik Max Francis && && http://www.alcyone.com/max/
    San Jose, CA, USA && 37 20 N 121 53 W && AIM erikmaxfrancis
    Heaven and Hell / Is on Earth
    -- Salt-n-Pepa
     
    Erik Max Francis, Dec 7, 2005
    #12
  13. malv wrote:

    > How is your package different from a nn package? Is this an addon for
    > genetic programming or does it include the standard nn components as
    > well, such as backprop etc?
    > Not being very familiar with genetic programming, forgive me my naive
    > question, I could not immediately find the answer.


    No one answered your question, so I will: Neural networks and genetic
    algorithms/programming are not closely related. A neural network is a
    model comprising a network of artificial neurons, and signals propagate
    from inputs, through the neurons of the network (which typically
    consists of several layers), and finally to the outputs. Algorithms
    exist to allow neural networks to be trained, so that given a set of
    inputs and desired outputs, one can iteratively come up with a neural
    network (of sufficient complexity) that satisfies that criterion.
    Neural networks can be used for things like pattern recognition and the
    like.

    Genetic algorithms/programming is an approach whereby you can start with
    a population of random programs, apply artificial selection by keeping
    those that do better at a task than others and genetic modification like
    mutation and crossover (simulation sexual reproduction) to create
    diversity, ultimately resulting (hopefully) in programs that are adept
    at the task.

    They could be used in conjunction with one another (for instance, a
    genetic algorithm where the program is represented by an array of neural
    network weights), but beyond intermixing ideas they really aren't related.

    --
    Erik Max Francis && && http://www.alcyone.com/max/
    San Jose, CA, USA && 37 20 N 121 53 W && AIM erikmaxfrancis
    I never could have predicted / That I'd feel this way
    -- India Arie
     
    Erik Max Francis, Dec 9, 2005
    #13
  14. aum

    malv Guest

    Thank you kindly, Erik.
    malv
     
    malv, Dec 9, 2005
    #14
  15. malv wrote:

    > Thank you kindly, Erik.


    Sure thing.

    --
    Erik Max Francis && && http://www.alcyone.com/max/
    San Jose, CA, USA && 37 20 N 121 53 W && AIM erikmaxfrancis
    It is only the poor who are forbidden to beg.
    -- Anatole France
     
    Erik Max Francis, Dec 9, 2005
    #15
  16. aum

    eXt Guest

    Erik Max Francis wrote:
    > Sure thing. Obviously I'll post an announcement here when it's ready.

    I'm really happy to see that someone is working on Python based GP
    implementation :) I'm currently trying to get into GP world (I'm the GP
    newbie you talked about :p) and, as I'm a Python programmer, I look
    towards Python based solutions. Unfortunately there are no active Python
    GP projects (maybe except Pyro, but I'm not sure how GP is implemented
    there) so I'm forced to play with Java based systems, which isn't what I
    like.

    Are you able to give any approximated date of PSI release?

    Cheers


    --
    eXt
     
    eXt, Dec 10, 2005
    #16
  17. eXt wrote:

    > I'm really happy to see that someone is working on Python based GP
    > implementation :) I'm currently trying to get into GP world (I'm the GP
    > newbie you talked about :p) and, as I'm a Python programmer, I look
    > towards Python based solutions. Unfortunately there are no active Python
    > GP projects (maybe except Pyro, but I'm not sure how GP is implemented
    > there) so I'm forced to play with Java based systems, which isn't what I
    > like.
    >
    > Are you able to give any approximated date of PSI release?


    Unfortunately I can't give a precise date. If I have the time, a
    polished working system with at least the basics should only take a week
    or so to finish up. Unfortunately, I have a big deadline coming up in
    my day job, so I'm probably not going to get much time to work on it for
    the next week or two. Hopefully I'll have a basic system ready by New
    Year's, but I can't really make any promises. The best way to encourage
    me to get it done is probably to keep me talking about it :).

    --
    Erik Max Francis && && http://www.alcyone.com/max/
    San Jose, CA, USA && 37 20 N 121 53 W && AIM erikmaxfrancis
    You are my martyr / I'm a vestige of a revolution
    -- Lamya
     
    Erik Max Francis, Dec 10, 2005
    #17
  18. aum

    eXt Guest

    Erik Max Francis wrote:
    > Unfortunately I can't give a precise date. If I have the time, a
    > polished working system with at least the basics should only take a week
    > or so to finish up. Unfortunately, I have a big deadline coming up in
    > my day job, so I'm probably not going to get much time to work on it for
    > the next week or two. Hopefully I'll have a basic system ready by New
    > Year's, but I can't really make any promises.

    Sure, I understand You :). Thanks for answer.

    > The best way to encourage
    > me to get it done is probably to keep me talking about it :).

    As I did :)


    --
    eXt
     
    eXt, Dec 10, 2005
    #18
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Thuswise Webmaster
    Replies:
    0
    Views:
    833
    Thuswise Webmaster
    Jun 28, 2003
  2. aum
    Replies:
    1
    Views:
    351
  3. Xiao Jianfeng

    genetic algorithms package for python ?

    Xiao Jianfeng, Aug 31, 2006, in forum: Python
    Replies:
    2
    Views:
    478
    placid
    Sep 1, 2006
  4. placid
    Replies:
    2
    Views:
    250
    placid
    Nov 15, 2007
  5. John Ladasky
    Replies:
    5
    Views:
    901
    John Ladasky
    Aug 3, 2008
Loading...

Share This Page