Max
1/28/2008 12:44:00 AM
On Jan 27, 7:25 pm, Steven D'Aprano <st...@REMOVE-THIS-
cybersource.com.au> wrote:
> 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
This is a lot of the information I was looking for. I especially
appreciate the sample code. I'll be able to hack something together
with this. Thanks.