a "generic" problem
Sean Ross
I'm having a couple of issues with a program I'm developing:
I'm implementing a generic GeneticAlgorithm class. It holds a
pool of Chromosome objects. For each new generation, I need to
create a new pool. I will be subclassing the Chromosome class
to fit the needs of a particular problem set. So, when I make a
GeneticAlgorithm instance, its pool will be populated by
instances of the subclass. And, during the crossover phase of
my algorithm I will need to make new instances of that subclass.
What I would like to know is:
ISSUE 1:
"How do I construct new instances of a class
when I do not know the name of that class?"
For example, here's is how my crossover method currently works
def crossover(self, xover, select):
"""generates new pool using provided xover and selection method
This should generate a 'new' pool,
not replace chromos in the existing pool!
"""
for i in xrange(0, self.population, 2):
rand = random.random()
if rand < self.crossover_rate:
p1, p2, c1, c2 = self.selections(method=select)
xover(p1, p2, c1, c2)
for chromo in (c1, c2):
self.mutate(chromo)
else:
i-=2
Essentially, what this does is pick 4 members out of the population,
and replace two of them (c1,c2) via crossover with p1 and p2.
It does actually work, but, this is not what is meant to be done.
It should be more like this:
def crossover(self, xover, select):
"""generates new pool using provided xover and selection method"""
newpool = []
while len(newpool) < self.population:
rand = random.random()
if rand < self.crossover_rate:
p1, p2 = self.selections(method=select)
kids = xover(p1, p2)
for chromo in kids:
if chromo is not None:
self.mutate(chromo)
newpool.append(chromo)
newpool = newpool[:self.population] # maintain pop. size
So, inside xover() I would need to create 2(or more) new instances of
whichever class is currently populating the pool. For instance, this is what
my one-point crossover currently looks like:
def onepoint(self, p1, p2, c1, c2):
"creates offspring via one-point xover between mates"
pivot = random.choice(range(self.gene_length))
c1.gene = p1.gene[:pivot] + p2.gene[pivot:]
c2.gene = p2.gene[:pivot] + p1.gene[pivot:]
But this changes two existing members of the population, which is wrong.
It should be more like this:
def onepoint(self, p1, p2):
"creates offspring via one-point xover between mates"
pivot = random.choice(range(self.gene_length))
#
# create new instances c1, c2 of whichever class p1, p2 belong to
#
c1.gene = p1.gene[:pivot] + p2.gene[pivot:]
c2.gene = p2.gene[:pivot] + p1.gene[pivot:]
return c1, c2
On a slightly different issue:
My Chromosome class provides a staticmethod generatepool()
That returns a list of randomly initialized Chromosomes to
populate the GeneticAlgorithm's initial pool.
It looks like this:
def generatepool(population=100):
return [Chromosome() for chromo in xrange(population)]
generatepool = staticmethod(generatepool)
Unfortunately, for each subclass of chromosome, I need to
override this method, e.g.,
def generatepool(population=100):
return [SubClassName() for chromo in xrange(population)]
generatepool = staticmethod(generatepool)
It is used as follows:
Suppose I have subclassed Chromosome as follows:
class OneMax(Chromosome):
...
And subclassed GeneticAlgorithm as:
class OneMaxGa(GeneticAlgorithm):
...
Then, to make an instance of OneMaxGA, I would say:
species = OneMaxGA(OneMax.generatepool(), max_epoch=200)
And this would give me a GA with a pool of 100 OneMax chromosomes.
So,
ISSUE 2:
"How do I implement this method, so that I do not need to
override it for each sublass?"
And, finally, the Chromosome class keeps two class variables:
Chromosome.alphabet and Chromosome.length
Note: A chromosome holds a gene which is usually a bit string, but
can be a list of other types of tokens(or even a tree, in some cases).
Anyway, the alphabet is the list of possible tokens that can be used
to generate a chromosomes gene, and the Chromosome.length is the
length of the gene sequence for every Chromosome instance.
When I subclass the Chromosome class, I often need to change the
value of these two variables to fit the specific problem.
For instance, I had one alphabet that looked like:
Chromosome.alphabet = ((0,1),(1,0),(0,0))
And another that included all ascii characters.
Since I use these to generate random genes for my chromosomes in __init__(),
I need to change their values before I create instances of my subclasses.
ISSUE 3:
"Is there a way to overide the value of a class variable of the super
class
inside the inheriting class?"
Thanks for your help. If you require more examples, and/or the entire code,
let me know.
Sean
Carl Banks
> ISSUE 1:
> "How do I construct new instances of a class
> when I do not know the name of that class?"
Short answer: you can pass the class as an argument to the
GeneticAlgorithm __init__. To exemplify:
class GeneticAlgorithm:
def __init__(self,chromosome_class,anything_else)
self.chromosome_class = chromosome_class
...
def onepoint(self, p1, p2):
pivot = random.randrange(self.gene.length)
c1 = self.chromosome_class(p1.gene[:pivot] + p2.gene[pivot:])
c2 = self.chromosome_class(p2.gene[:pivot] + p1.gene[pivot:])
return c1, c2
Rather, I suggest another possibility: to make onepoint a method of
Chromosome, instead.
class Chromosome:
def onepoint(self,other):
klass = self.__class__
pivot = random.randrange(self.gene.length)
c1 = klass(self.gene[:pivot] + other.gene[pivot:])
c2 = klass(other.gene[:pivot] + self.gene[pivot:])
return c1, c2
Have your subclasses of Chromosome define a method xover which calls
the approproate crossover function:
class ShakespeareQuoteChromosome(Chromosome):
def xover(self,other):
return self.onepoint(other)
This saves you from having to pass xover into crossover. Maybe it's
not versatile enough for your needs, though.
[snip]
> On a slightly different issue:
> My Chromosome class provides a staticmethod generatepool()
> That returns a list of randomly initialized Chromosomes to
> populate the GeneticAlgorithm's initial pool.
>
> It looks like this:
>
> def generatepool(population=100):
> return [Chromosome() for chromo in xrange(population)]
> generatepool = staticmethod(generatepool)
>
> Unfortunately, for each subclass of chromosome, I need to
> override this method, e.g.,
>
> def generatepool(population=100):
> return [SubClassName() for chromo in xrange(population)]
> generatepool = staticmethod(generatepool)
>
[snip]
>
> "How do I implement this method, so that I do not need to
> override it for each sublass?"
If you pass the chromosome subclass as an argument to
GeneticAlgorithm, as I demonstrated above, the answer is to just make
generatepool a method of GeneticAlgorithm.
class GeneticAlgorithm:
def generatepool(population=100):
return [self.chromosome_class() for chromo in xrange(population)]
In fact, I think you should do this even if you take my advice and
make onepoint a method of Chromosome. Generating a population is an
operation of the genetic algorithm, not of the Chromosome, and it
ought to be a method of GeneticAlgorithm.
However, if you insist on making generatepool a method of Chromosome,
you should make it a classmethod instead of a staticmethod:
class Chromosome:
def generatepool(klass,population=100):
return [klass() for chromo in xrange(population)]
generatepool = classmethod(generatepool)
> And, finally, the Chromosome class keeps two class variables:
> Chromosome.alphabet and Chromosome.length
>
[snip]
>
> When I subclass the Chromosome class, I often need to change the
> value of these two variables to fit the specific problem.
>
> For instance, I had one alphabet that looked like:
> Chromosome.alphabet = ((0,1),(1,0),(0,0))
> And another that included all ascii characters.
>
> Since I use these to generate random genes for my chromosomes in __init__(),
> I need to change their values before I create instances of my subclasses.
>
> ISSUE 3:
> "Is there a way to overide the value of a class variable of the super
> class
> inside the inheriting class?"
Unless I misunderstand what you're asking, all you have to do is set
an attribute of the derived class, like so:
class Chromosome(object):
alphabet = ()
length = 0
class BaklavaRecipeChromosome(Chromosome):
alphabet = ('honey', 'orange', 'lemon', 'garlic')
BaklavaRecipeChromosome.length = 20
The one question you should ask yourself is whether you really need
alphabet and length to be variables of Chromosome? I would define
these only in my derived classes.
> Thanks for your help. If you require more examples, and/or the entire code,
> let me know.
You're welcome. No, you did a good job at including just the right
amount of detail. Only thing is, you should quote methods inside a
class definition, 'cause it's hard to figure out which class they
belong to.
I've done genetic algorithms in Python (genetic programming,
actually), and I've faced many of the design issues you have, so I
hope this advice helps.
--
CARL BANKS
Sean Ross
"Carl Banks" <imb...@aerojockey.com> wrote in message
news:R2A2a.8019$rE3...@nwrddc01.gnilink.net...
[snip]
>
> You're welcome. No, you did a good job at including just the right
> amount of detail. Only thing is, you should quote methods inside a
> class definition, 'cause it's hard to figure out which class they
> belong to.
>
> I've done genetic algorithms in Python (genetic programming,
> actually), and I've faced many of the design issues you have, so I
> hope this advice helps.
>
Yes, it does help, thank you. I actually figured out that I needed to use a
classmethod instead of a staticmethod on my own, but now that I see your
idea of having the GA generate its own pool, I've decided I like that
better. I'm not as certain about having the Chromosome define the xover
method. It's seems like a good idea. I'll consider it some more.
As for the class variables, yes, you're right that you just set an attribute
of the derived class. I'd already worked through that by now, but your
answer is still appreciated.
FYI, I'll be doing GP later this semester, I'd be intersted to hear what
sort of difficulties you encountered, if any, using Python for this task.
For instance, did you have the programs that were generated be Python
programs? I was thinking of using Python to generate the programs, but
perhaps to have the programs be in Scheme(which has a fairly simple syntax).
Although, then I'd have to figure out how to determine whether or not a
scheme program was good from within a Python program...
Oh well, I haven't given it a lot of thought yet.
Once again, thanks for your assistance,
Sean
Manuel Garcia
post, but I remember having a similar problem, so maybe this will
help...
(also I like to run code before I post, and in this case I haven't)
:-/
On Wed, 12 Feb 2003 15:46:06 -0500, "Sean Ross"
<frobozz_...@hotmail.com> wrote:
(edit)
> #
> # create new instances c1, c2 of whichever class p1, p2 belong to
> #
If you can get away with just copying p1 & p1, then:
import copy
c1 = copy.copy(p1)
c2 = copy.copy(p2)
Otherwise...
Every instance has the attribute __class__. Call this to run the
class's constructor:
c1 = p1.__class__()
c2 = p2.__class__()
>ISSUE 2:
>"How do I implement this method, so that I do not need to
>override it for each sublass?"
instead of using 'staticmethod', use 'classmethod'
'staticmethod' works like this:
class fake1():
def meth1(x,y,z):
print 'static %r' % (x+y+z,)
return 17
meth1 = staticmethod(meth1)
'classmethod' works like this:
class fake2():
def meth2(cls, x,y,z):
print '%s %r' % (cls.__name__, x+y+z)
return cls(x+y+z)
meth2 = classmethod(meth2)
My example doesn't make sense, but I hope you see the syntax
structure. Via the variable 'cls', you have access to the class
involved with method f. Both of these work, for staticmethod and
classmethod:
fake.meth(x,y,z)
a = fake()
a.meth(x,y,z)
What I am trying to say is that you don't even have to have an
instance to use a staticmethod or a classmethod, you can just run the
method from the class directly.
>ISSUE 3:
> "Is there a way to overide the value of a class variable of the super
>class
> inside the inheriting class?"
Is this what you mean?
class fake3():
attr1 = 17
attr2 = 19
class subfake1(fake3): pass
class subfake2(fake3):
attr2 = 23
No special steps to override! I may be misunderstanding you.
Hope this helps!
Manuel
Erik Max Francis
> ISSUE 1:
> "How do I construct new instances of a class
> when I do not know the name of that class?"
This is usually referred to as a "factory pattern." What you do is pass
in a thing that can generate the desired instances that you want. In
Python, the most obvious thing to do is to pass in the class that you
want, and then invoke the class with normal call conventions.
> ISSUE 2:
> "How do I implement this method, so that I do not need to
> override it for each sublass?"
Same way, probably; pass in the factory object that you plan to use.
> ISSUE 3:
> "Is there a way to overide the value of a class variable of the
> super
> class
> inside the inheriting class?"
Sure. When you have an instance of the class, refer to it like this:
instance.classAttribute,
e.g., self.classAttribute if you're actually in one of that instance's
methods.
and then just replace it in subclasses:
class C:
classAttribute = something
class D(C):
classAttribute = somethingElse
--
Erik Max Francis / m...@alcyone.com / http://www.alcyone.com/max/
__ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE
/ \ If you can't fight and you can't flee, flow.
\__/ Robert Elliot
Physics reference / http://www.alcyone.com/max/reference/physics/
A physics reference.
Carl Banks
> Yes, it does help, thank you. I actually figured out that I needed to use a
> classmethod instead of a staticmethod on my own, but now that I see your
> idea of having the GA generate its own pool, I've decided I like that
> better. I'm not as certain about having the Chromosome define the xover
> method. It's seems like a good idea. I'll consider it some more.
I'll explain my rationale for this a bit. Basically, crossover
operation depends on the inner details of a Chromosome. And if those
details change, you have to change the GeneticAlgorithm, too. (What
would happen if you stuck a tree in there?) It's usually best to
leave stuff that deals with Chromosome inner details in the
Chromosome.
Ideally, GeneticAlgorithm shouldn't need to know anything about the
details of the Chromosome, nor should the Chromosome need to know
anything about the details of the GeneticAlgorithm. And, if you have
any larger plans, it behooves to you try to keep stuff where it
belongs.
But, if you have no larger plans, and just want to experiment with
different crossover operations, it might be easier to just make it a
method of GeneticAlgorithm, as you did.
> FYI, I'll be doing GP later this semester, I'd be intersted to hear what
> sort of difficulties you encountered, if any, using Python for this task.
Not many, really. Python is a great language for this.
> For instance, did you have the programs that were generated be Python
> programs? I was thinking of using Python to generate the programs, but
> perhaps to have the programs be in Scheme(which has a fairly simple syntax).
Well, Scheme's fairly simple syntax won't buy you much; simple syntax
helps simplify input, but not really output. To illustrate, consider
that it's just as easy to output C code like this:
return "(%s+%s)" % (subtree[1], subtree[2])
as it is to output Scheme code like this:
return "(+ %s %s) % (subtree[1], subtree[2])
For one particular problem, I actually output the population as
Fortran code, compiled it into a Python module using distutils,
imported it, and ran it.
I recommend you output in a language that is efficient overall, and
has good error checking if you need that, and not worry too much about
a complicated syntax.
> Although, then I'd have to figure out how to determine whether or not a
> scheme program was good from within a Python program...
> Oh well, I haven't given it a lot of thought yet.
--
CARL BANKS
Sean Ross
I've reimplemented my classes as per your suggestions, however, there is a
problem. First, what the relevant code looks like:
class Chromosome:
alphabet = "01"
length = 40
def __init__(self, gene=None):
if gene == None:
gene = self.randomgene()
self.gene = gene
self.fit = self.fitness()
def fitness(self, target=None):
"override this method to evaluate chromosome fitness"
pass
[snip]
def onepoint(self, mate):
"creates offspring via one-point xover between mates"
klass = self.__class__
pivot = random.randrange(self.length)
c1 = klass(self.gene[:pivot] + mate.gene[pivot:])
c2 = klass(mate.gene[:pivot] + self.gene[pivot:])
return c1, c2
[snip]
class GeneticAlgorithm:
def __init__(self, chromosome_class, population=100,
crossover=0.85, mutate=0.01, max_epoch=0,
elitism = 0.0, target=None):
self.chromosome_class = chromosome_class
self.population = population
self.pool = self.generatepool()
...
[snip]
def generatepool(self):
return [self.chromosome_class() \
for chromo in xrange(self.population)]
def fitness(self, target=None):
"sets fitness for each chromosome in pool"
for chromo in self.pool:
chromo.fitness(self.target)
[snip]
class OneMax(Chromosome):
length = 30
def fitness(self, target=None):
self.fit = utils.sum([int(allele) for allele in self.gene])
[snip]
if __name__ == "__main__":
TARGET = '1'*30
species = OneMaxGA(OneMax, target=TARGET,
mutate=0.05, max_epoch=200)
[snip]
And, now, the problem:
When I run my algorithm and call species.fitness(), it calls the OneMax
fitness() for each chromosome in the pool, and a print statement in that
method showed that the value for self.fit was being set correctly.
However, when I inspect the species.pool, all of the OneMax instances have
self.fit=None.
e.g., here's a result from inside one of the xover methods to check
which class 'klass' represented; print before making c1, a print inside the
OneMax fitness function(which appears to be called as c1 is made)
and a print of c1 after it has been made.
klass: __main__.OneMax
making c1
self.fit 16
c1: <OneMax gene="011010001010111101011011100100" fitness=None>
I don't understand why c1's self.fit=16 inside it's self.fitness() call,
but afterward it equals None. It looks like the Chromosome fitness() method
is being called rather than the OneMax fitness() method.
Thanks for your help,
Sean
P.S. Once again, if you require more code to see what's going on, let me
know.
Erik Max Francis
> Not many, really. Python is a great language for this.
Indeed, I've been fiddling around with a stack-based genetic programming
system in Python that I haven't released yet but probably will at some
point.
--
Erik Max Francis / m...@alcyone.com / http://www.alcyone.com/max/
__ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE
/ \ Will I disappoint my future / If I stay
\__/ Sade
Bosskey.net: Return to Wolfenstein / http://www.bosskey.net/rtcw/
A personal guide to Return to Castle Wolfenstein.
Sean Ross
Thanks for your help.
Sean
Sean Ross
point, so I didn't realize it was necessary.
eic...@metacarta.com
"pychecker" will catch; I've found it very useful as I've been
learning, I'll be stuck on something and pychecker will point at a
bunch of things to be suspicious of, and I've actually seen it report
this one :-}