a "generic" problem

Sean Ross frobozz_electric at hotmail.com
Wed Feb 12 21:46:06 CET 2003


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








More information about the Python-list mailing list