Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > ANN: pygene - genetic algorithms package

Reply
Thread Tools

ANN: pygene - genetic algorithms package

 
 
aum
Guest
Posts: n/a
 
      12-06-2005
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


 
Reply With Quote
 
 
 
 
Erik Max Francis
Guest
Posts: n/a
 
      12-06-2005
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.velocityreviews.com/forums/(E-Mail Removed) && 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
 
Reply With Quote
 
 
 
 
aum
Guest
Posts: n/a
 
      12-06-2005
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


 
Reply With Quote
 
malv
Guest
Posts: n/a
 
      12-06-2005
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

 
Reply With Quote
 
Erik Max Francis
Guest
Posts: n/a
 
      12-06-2005
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 && (E-Mail Removed) && 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
 
Reply With Quote
 
Peter Hansen
Guest
Posts: n/a
 
      12-07-2005
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

 
Reply With Quote
 
Erik Max Francis
Guest
Posts: n/a
 
      12-07-2005
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 && (E-Mail Removed) && 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
 
Reply With Quote
 
Peter Hansen
Guest
Posts: n/a
 
      12-07-2005
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

 
Reply With Quote
 
Erik Max Francis
Guest
Posts: n/a
 
      12-07-2005
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 && (E-Mail Removed) && 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
 
Reply With Quote
 
aum
Guest
Posts: n/a
 
      12-07-2005
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 Brain****, then work up to Forth, Factor and
beyond.

--

Cheers
aum


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Genetic programming: pygene, pygp, AST, or (gasp) Lisp? John Ladasky Python 5 08-03-2008 10:55 AM
genetic algorithms package for python ? Xiao Jianfeng Python 2 09-01-2006 06:54 AM
genetic algorithms Jelle Feringa / EZCT Architecture & Design Research Python 0 02-25-2005 02:03 PM
Genetic Algorithms & Security Bharat Bhushan Computer Security 1 06-30-2003 02:43 PM
ANN: TOGA (Timetables Optimised with Genetic Algorithms) v 0.01 Thuswise Webmaster Python 0 06-28-2003 04:13 PM



Advertisments