Python Genetic Algorithm

[Steven D'Aprano]

On Sun, 27 Jan 2008 15:09:52 -0800, Max wrote:

> Hi all. I'm just getting introduced to Python (mostly through Dive Into
> Python), and I've decided to use it for a project where I have to write
> my own Genetic Algorithm. Even if you don't know about GAs, you might be
> able to help with an issue I'm having. I'm just starting the project
> off, so I'm still in the conceptual phase, and I'm stuck on how I'm
> going to be able to implement something.
> 
> In GAs, you operate on a Population of solutions. Each Individual from
> the Population is a potential solution to the problem you're optimizing,
> and Individuals have what's called a chromosome - a specification of
> what it contains. For example, common chromosomes are bit strings, lists
> of ints/floats, permutations...etc. I'm stuck on how to implement the
> different chromosomes. I have a Population class, which is going to
> contain a list of Individuals.Each individual will be of a certain 
> chromosome.

Presumably all the individuals in the same population need to have the 
same kind of chromosome (differing only in the specific genes).


> I envision the chromosomes as subclasses of an abstract
> Individual class, perhaps all in the same module.

How would that work? Shouldn't the different kinds of chromosomes 
(strings, lists of ints, etc.) be subclasses of an abstract Chromosome 
kind?

What you need to think of is the difference between Is-A and Has-A 
relationships. An individual Has A chromosome, so you want a relationship 
something like this:


class Individual(object):
    def __init__(self):
        self.chromosome = get_chromosome()


On the other hand, something like a string chromosome Is A chromosome, 
and so is a list-of-ints Chromosome:

class Chromosome(object):
    pass  # abstract class

class StringChromosome(Chromosome):
    pass  # implement extra/different functionality

class ListIntsChromosome(Chromosome):
    pass 



> I'm just having
> trouble envisioning how this would be coded at the population level.

There are so many ways... here's one possibility that doesn't even use a 
Population class.


chromosome = StringChromosome  # the class, not an instance
default_genes = "GATACATATGGATTAGGGACCACTAC"
size = 100
population = []
for i in range(size):
    genes = chromosome(default_genes)
    genes.mutate()
    population.append(Individual(genes))

I'm sure you can modify that to work on a class instance basis.


> Presumably, when a population is created, a parameter to its __init__
> would be the chromosome type, but I don't know how to take that in
> Python and use it to specify a certain class.

Just pass the class itself. For example:

# Define a class.
class Parrot(object):
    pass

x = "Parrot"  # x is the NAME of the class
y = Parrot  # y is the CLASS itself
z = Parrot()  # z is an INSTANCE of the class

You can use the class as a object, exactly the same as you can use a dict 
or a string or a float or any other object. y() will create a new Parrot 
instance exactly the same way that Parrot() would.


Here's one possibility:

class Population(object):
    def __init__(self, size=1000, chromosome_type=StringChromosome):
        individuals = []
        for i in xrange(size):
            genes = chromosome_type()  # create new set of genes
            x = Individual(genes)  # add them to a new individual
            individuals.append(x)  # and store it in the population
        self.individuals = individuals

        

> I'm doing something similar with my crossover methods, by specifying
> them as functions in a module called Crossover, importing that, and
> defining
> 
> crossover_function = getattr(Crossover, "%s_crossover" % xover)
> 
> Where xover is a parameter defining the type of crossover to be used.


The only time you need something like that is when you need to go from 
user-input (a string) to a binary object (e.g. a class, a function...). 
Suppose you read the crossover type from a text config file, or user 
input:

import Crossover
xover = raw_input("Enter a crossover type: valid values are X, Y, Z: ")
crossover_function = getattr(Crossover, "%s_crossover" % xover)

Instead of passing the string xover around as a parameter, you use it 
*once* to get the actual function object itself, and pass that around.

Another alternative is to define something like this in the Crossover 
module, assuming you have three functions xcrossover etc.:

user_map = {"X": xcrossover, "Y": ycrossover, "Z": zcrossover}

Again, use it once to get the function object from the user input.



Hope this helps, 



-- 
Steven