Python Genetic Algorithm

Discussion in 'Python' started by Max, Jan 27, 2008.

  1. Max

    Max Guest

    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. I envision the chromosomes as subclasses
    of an abstract Individual class, perhaps all in the same module. I'm
    just having trouble envisioning how this would be coded at the
    population level. 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.

    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.
    I'm hoping there's some similar trick to accomplish what I want to do
    with chromosomes - or maybe I'm going about this completely the wrong
    way, trying to get Python to do something it's not made for. Any help/
    feedback would be wonderful.

    Thanks,
    Max Martin
    Max, Jan 27, 2008
    #1
    1. Advertising

  2. Max wrote:
    > 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. I envision the chromosomes as subclasses
    > of an abstract Individual class, perhaps all in the same module. I'm
    > just having trouble envisioning how this would be coded at the
    > population level. 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.
    >

    I'm not sure I'm following you here. So a "chromosome" is bit of
    functionality, right? So basically it is a function. So my advice would
    be to write these functions and store it to the "indivuals"-list like so:

    class Population(object):
    def __init__(self, *individuals):
    self.individuals = list(individuals)

    Then you can say:
    p = Population(indiv1, indiv2, indiv3)
    for individual in p.individual:
    individual(whatever_your_problem)

    (Don't know if this is the way GA's are supposed to work)

    You can also create callable classes (that is, classes that implement
    the __call__ method), and use instances of these as the individuals. For
    example you can create a Permutation class that returns a permutation
    (defined in it's __init__()) when it's __call__ method is called. (Am I
    making sense?)

    This is just generic advice, maybe this helps and maybe it doesn't at
    all. :)



    > 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.
    > I'm hoping there's some similar trick to accomplish what I want to do
    > with chromosomes - or maybe I'm going about this completely the wrong
    > way, trying to get Python to do something it's not made for. Any help/
    > feedback would be wonderful.
    >

    This isn't too bad, but for such things dictionaries are your Go-To
    datatype. Just have a dictionary of xover-functions handy and call the
    thusly:

    crossover_function = Crossover.function[xover]


    > Thanks,
    > Max Martin

    If that helps :)

    regards
    /W
    Wildemar Wildenburger, Jan 27, 2008
    #2
    1. Advertising

  3. Max

    Steven Clark Guest

    Why not make chromosome itself a class?

    class BasicChromosome(object):
    def __init__(self, data):
    self.data = data

    def crossover(self):
    [stuff here]

    You can subclass this as needed, altering the crossover method as necessary.

    ....perhaps I didn't understand your question.
    -Steven

    On Jan 27, 2008 6:35 PM, Wildemar Wildenburger
    <> wrote:
    > Max wrote:
    > > 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. I envision the chromosomes as subclasses
    > > of an abstract Individual class, perhaps all in the same module. I'm
    > > just having trouble envisioning how this would be coded at the
    > > population level. 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.
    > >

    > I'm not sure I'm following you here. So a "chromosome" is bit of
    > functionality, right? So basically it is a function. So my advice would
    > be to write these functions and store it to the "indivuals"-list like so:
    >
    > class Population(object):
    > def __init__(self, *individuals):
    > self.individuals = list(individuals)
    >
    > Then you can say:
    > p = Population(indiv1, indiv2, indiv3)
    > for individual in p.individual:
    > individual(whatever_your_problem)
    >
    > (Don't know if this is the way GA's are supposed to work)
    >
    > You can also create callable classes (that is, classes that implement
    > the __call__ method), and use instances of these as the individuals. For
    > example you can create a Permutation class that returns a permutation
    > (defined in it's __init__()) when it's __call__ method is called. (Am I
    > making sense?)
    >
    > This is just generic advice, maybe this helps and maybe it doesn't at
    > all. :)
    >
    >
    >
    > > 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.
    > > I'm hoping there's some similar trick to accomplish what I want to do
    > > with chromosomes - or maybe I'm going about this completely the wrong
    > > way, trying to get Python to do something it's not made for. Any help/
    > > feedback would be wonderful.
    > >

    > This isn't too bad, but for such things dictionaries are your Go-To
    > datatype. Just have a dictionary of xover-functions handy and call the
    > thusly:
    >
    > crossover_function = Crossover.function[xover]
    >
    >
    > > Thanks,
    > > Max Martin

    > If that helps :)
    >
    > regards
    > /W
    >
    > --
    > http://mail.python.org/mailman/listinfo/python-list
    >
    Steven Clark, Jan 28, 2008
    #3
  4. Max

    Max Guest

    On Jan 27, 6:35 pm, Wildemar Wildenburger
    <> wrote:
    > Max wrote:
    > > 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. I envision the chromosomes as subclasses
    > > of an abstract Individual class, perhaps all in the same module. I'm
    > > just having trouble envisioning how this would be coded at the
    > > population level. 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.

    >
    > I'm not sure I'm following you here. So a "chromosome" is bit of
    > functionality, right? So basically it is a function. So my advice would
    > be to write these functions and store it to the "indivuals"-list like so:
    >
    > class Population(object):
    > def __init__(self, *individuals):
    > self.individuals = list(individuals)
    >
    > Then you can say:
    > p = Population(indiv1, indiv2, indiv3)
    > for individual in p.individual:
    > individual(whatever_your_problem)
    >
    > (Don't know if this is the way GA's are supposed to work)
    >
    > You can also create callable classes (that is, classes that implement
    > the __call__ method), and use instances of these as the individuals. For
    > example you can create a Permutation class that returns a permutation
    > (defined in it's __init__()) when it's __call__ method is called. (Am I
    > making sense?)
    >
    > This is just generic advice, maybe this helps and maybe it doesn't at
    > all. :)
    >
    > > 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.
    > > I'm hoping there's some similar trick to accomplish what I want to do
    > > with chromosomes - or maybe I'm going about this completely the wrong
    > > way, trying to get Python to do something it's not made for. Any help/
    > > feedback would be wonderful.

    >
    > This isn't too bad, but for such things dictionaries are your Go-To
    > datatype. Just have a dictionary of xover-functions handy and call the
    > thusly:
    >
    > crossover_function = Crossover.function[xover]
    >
    > > Thanks,
    > > Max Martin

    >
    > If that helps :)
    >
    > regards
    > /W


    This is definitely useful information, but I don't think I explained
    chromosomes very well.

    A chromosome is a choice of representation. So let's say your problem
    is diagnosis, so a representation of a solution will be a list of
    diagnoses (e.g. Disease1 = yes, Disease2 = no, Disease3 = yes, etc.).
    Your chromosome choice could be a bitstring, in which the previous
    solution would = 101, or it could be a list of floats to represent the
    probability that you have Disease x, etc. So a chromosome is like a
    choice of representation. In the case of humans, the chromosome is,
    well, chromosomes.
    Max, Jan 28, 2008
    #4
  5. Max

    Max Guest

    On Jan 27, 7:01 pm, "Steven Clark" <> wrote:
    > Why not make chromosome itself a class?
    >
    > class BasicChromosome(object):
    > def __init__(self, data):
    > self.data = data
    >
    > def crossover(self):
    > [stuff here]
    >
    > You can subclass this as needed, altering the crossover method as necessary.
    >
    > ...perhaps I didn't understand your question.
    > -Steven
    >
    > On Jan 27, 2008 6:35 PM, Wildemar Wildenburger
    >
    > <> wrote:
    > > Max wrote:
    > > > 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. I envision the chromosomes as subclasses
    > > > of an abstract Individual class, perhaps all in the same module. I'm
    > > > just having trouble envisioning how this would be coded at the
    > > > population level. 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.

    >
    > > I'm not sure I'm following you here. So a "chromosome" is bit of
    > > functionality, right? So basically it is a function. So my advice would
    > > be to write these functions and store it to the "indivuals"-list like so:

    >
    > > class Population(object):
    > > def __init__(self, *individuals):
    > > self.individuals = list(individuals)

    >
    > > Then you can say:
    > > p = Population(indiv1, indiv2, indiv3)
    > > for individual in p.individual:
    > > individual(whatever_your_problem)

    >
    > > (Don't know if this is the way GA's are supposed to work)

    >
    > > You can also create callable classes (that is, classes that implement
    > > the __call__ method), and use instances of these as the individuals. For
    > > example you can create a Permutation class that returns a permutation
    > > (defined in it's __init__()) when it's __call__ method is called. (Am I
    > > making sense?)

    >
    > > This is just generic advice, maybe this helps and maybe it doesn't at
    > > all. :)

    >
    > > > 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.
    > > > I'm hoping there's some similar trick to accomplish what I want to do
    > > > with chromosomes - or maybe I'm going about this completely the wrong
    > > > way, trying to get Python to do something it's not made for. Any help/
    > > > feedback would be wonderful.

    >
    > > This isn't too bad, but for such things dictionaries are your Go-To
    > > datatype. Just have a dictionary of xover-functions handy and call the
    > > thusly:

    >
    > > crossover_function = Crossover.function[xover]

    >
    > > > Thanks,
    > > > Max Martin

    > > If that helps :)

    >
    > > regards
    > > /W

    >
    > > --
    > >http://mail.python.org/mailman/listinfo/python-list


    This is sort of what I'm trying to do. The super class would be
    Individual, and subclasses would be BitStringIndividual,
    IntIndividual, PermutationIndividual...etc. I just am feeling lost as
    to how I'm going to implement my Population class, because when a
    Population is initially created, it's going to fill itself up with
    individuals by creating them, so it's going to need to know which
    class it's creating instances of (which will be input when creating
    the population somehow; I'm just not sure how to implement this).
    Max, Jan 28, 2008
    #5
  6. 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
    Steven D'Aprano, Jan 28, 2008
    #6
  7. Max

    Max Guest

    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.
    Max, Jan 28, 2008
    #7
  8. Max

    Terry Reedy Guest

    "Max" <> wrote in message
    news:...
    | 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. I envision the chromosomes as subclasses
    | of an abstract Individual class, perhaps all in the same module. I'm
    | just having trouble envisioning how this would be coded at the
    | population level. 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.
    |
    | 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.
    | I'm hoping there's some similar trick to accomplish what I want to do
    | with chromosomes - or maybe I'm going about this completely the wrong
    | way, trying to get Python to do something it's not made for. Any help/
    | feedback would be wonderful.

    'Python genetic algorithm' returns 25000 hits with Google.
    But here is what I would do without looking at them.

    Start with the Individual base class and common methods, some virtual (not
    implemented). An example of a virtual method would be the
    crossover(self,other) method, since its implementation depends on the
    concrete chromosome implementation. Make subclasses with concrete
    chromosome types (initialized in .__init__). For each, implement the
    methods that depend on that type. In particular, the mutate(self, args)
    and crossover(self,other, args) methods.

    For the Population class, give __init__ an 'individual' parameter and
    store it as an attribute. If you want, check that it
    'issubclass(Individual)'. To add members to the population, call the
    stored subclass. To operate on the population, write Population methods.
    There should not depend on the particular chromosome implementations. To
    operate on the members within the Population methods, call their Individual
    methods. b = a.mutate(args); c = a.crossover(b, args).

    I see two ways to deal with scoring the fitness of individuals within a
    Population instance. Once is to write a particular fitness function, pass
    it to the Population init to save as an attribute, and then call as needed.
    The other is to subclass an Individual subclass, give it that funtion
    fitness method, and pass that subsubclass to Population. The difference is
    between having Population methods calling self.fitness(some_member) versus
    some_member.fitness().

    I hope this is helpful for getting started.

    Terry Jan Reedy
    Terry Reedy, Jan 28, 2008
    #8
  9. Max

    Max Guest

    On Jan 27, 8:01 pm, "Terry Reedy" <> wrote:
    > "Max" <> wrote in message
    >
    > news:...
    > | 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. I envision the chromosomes as subclasses
    > | of an abstract Individual class, perhaps all in the same module. I'm
    > | just having trouble envisioning how this would be coded at the
    > | population level. 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.
    > |
    > | 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.
    > | I'm hoping there's some similar trick to accomplish what I want to do
    > | with chromosomes - or maybe I'm going about this completely the wrong
    > | way, trying to get Python to do something it's not made for. Any help/
    > | feedback would be wonderful.
    >
    > 'Python genetic algorithm' returns 25000 hits with Google.
    > But here is what I would do without looking at them.
    >
    > Start with the Individual base class and common methods, some virtual (not
    > implemented). An example of a virtual method would be the
    > crossover(self,other) method, since its implementation depends on the
    > concrete chromosome implementation. Make subclasses with concrete
    > chromosome types (initialized in .__init__). For each, implement the
    > methods that depend on that type. In particular, the mutate(self, args)
    > and crossover(self,other, args) methods.
    >
    > For the Population class, give __init__ an 'individual' parameter and
    > store it as an attribute. If you want, check that it
    > 'issubclass(Individual)'. To add members to the population, call the
    > stored subclass. To operate on the population, write Population methods.
    > There should not depend on the particular chromosome implementations. To
    > operate on the members within the Population methods, call their Individual
    > methods. b = a.mutate(args); c = a.crossover(b, args).
    >
    > I see two ways to deal with scoring the fitness of individuals within a
    > Population instance. Once is to write a particular fitness function, pass
    > it to the Population init to save as an attribute, and then call as needed.
    > The other is to subclass an Individual subclass, give it that funtion
    > fitness method, and pass that subsubclass to Population. The difference is
    > between having Population methods calling self.fitness(some_member) versus
    > some_member.fitness().
    >
    > I hope this is helpful for getting started.
    >
    > Terry Jan Reedy


    Yeah, I looked up some of those GAs, but talking with people about
    code helps me a lot more than looking at other code. I know it's
    strange for a programmer to prefer social interaction, but...just
    something about how I'm wired.

    This sounds a lot like what I was thinking of doing. In particular, I
    was planning on having the problem's program itself (which would
    create an instance of a GA to optimize something) specify the fitness
    function and pass it upwards to the population (or maybe to the GA,
    which contains a population).

    Thanks for the help.
    Max, Jan 28, 2008
    #9
  10. On Mon, 28 Jan 2008 00:35:51 +0100, Wildemar Wildenburger wrote:

    > Max wrote:
    >> 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. I envision the chromosomes as subclasses of
    >> an abstract Individual class, perhaps all in the same module. I'm just
    >> having trouble envisioning how this would be coded at the population
    >> level. 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.
    >>

    > I'm not sure I'm following you here. So a "chromosome" is bit of
    > functionality, right? So basically it is a function. So my advice would
    > be to write these functions and store it to the "indivuals"-list like
    > so:


    No, a chromosome is a bit of *data*: a noun, not a verb. Read these bits
    again:

    "Individuals HAVE what's called a chromosome - a SPECIFICATION of what it
    contains. For example, common chromosomes are BIT STRINGS, ..."

    Emphasis added. Sorry for the shouting.

    Some background which may help you understand what the OP is asking for.

    Genetic Algorithms simulate biological genetic process for problem
    solving. The basic idea is this: suppose you can find a way to encode
    possible solutions to a problem as a sequence in some sense. e.g. a
    sequence of Yes/No decisions might be 011001. That's the "Chromosome" the
    OP is talking about. Furthermore, suppose you can mutate such a solution:
    011001 might become 011011. Then, so long as some relatively common
    assumptions hold, you can zero in on a good solution by starting with a
    bad solution and incrementally improving it:

    * start with a lot of bad or mediocre solutions
    * pick the best solution in the population
    * make lots of copies
    * mutate the copies slightly
    * now pick the best solution of them

    Repeat until done.

    The analogy is with the process of evolution, only very much simplified.

    Such GAs are capable of finding solutions which people have never thought
    of. Sometimes those solutions are baroque and virtually unintelligible.
    Sometimes they're amazingly simple.

    In one famous case, a hardware GA actually found a working electrical
    circuit which was not only smaller than any similar circuit that human
    engineers had found, but according to a naive understanding of
    electronics, it shouldn't have worked at all! It contained an open
    circuit, but removing the open circuit stopped the rest from working.


    --
    Steven
    Steven D'Aprano, Jan 28, 2008
    #10
  11. Steven D'Aprano wrote:
    >> I'm not sure I'm following you here. So a "chromosome" is bit of
    >> functionality, right? So basically it is a function. So my advice would
    >> be to write these functions and store it to the "indivuals"-list like
    >> so:

    >
    > No, a chromosome is a bit of *data*: a noun, not a verb. Read these bits
    > again:
    >
    > "Individuals HAVE what's called a chromosome - a SPECIFICATION of what it
    > contains. For example, common chromosomes are BIT STRINGS, ..."
    >

    Oh, OK. I *sort of* got this. Sort of. My reasoning was that these
    functions would return their associated "representation" upon being
    called. Which makes not much sense, especially after your explanation.



    > Some background which may help you understand what the OP is asking for.
    >
    > [snip little GA-intro]
    >

    Thanks Steven, that sure was useful. I think I now have a new toy
    hammer. I'm sure I'll see myself looking for toy nails everywhere over
    the next few weeks.

    :)
    /W
    Wildemar Wildenburger, Jan 28, 2008
    #11
  12. Max

    wes Guest

    Max,

    def GeneticNextGen(self):
    numsets = len(self.WtSets)
    numwts = len(self.WtSets[0].Lis)

    self.WtSets.sort(CompByCurrentFitness)
    index_lis = []
    K = 100.0

    N = float(numwts)

    #if RISE(slope) is too high, concentration occurs too fast and
    #you lose many quickly

    RISE = -0.01*K
    RUN = N - 1.0
    m = RISE/RUN
    for i in range( numsets ):
    x = float(i)
    numin = int(m * x + K)
    for k in range(numin):
    index_lis.append( i )

    new_wtset_list = WtSetListClass()

    while len(new_wtset_list.WtSets) < numsets:
    #split in a number of placeses
    splitPoints = [] #empty list of places where dna's are crossed
    numSplitPoints = random.randint( 2, 4 ) #number of places to cross at(not to hot & not to cold)
    while len(splitPoints) < numSplitPoints: #get required num of points at random
    split_pt = random.randint( 0, numwts - 1 )
    if split_pt not in splitPoints:
    splitPoints.append(split_pt)

    i1 = random.choice( index_lis ) #get two old weight sets at random from a biased list
    while( 1 ):
    i2 = random.choice( index_lis )
    if i2 <> i1:
    break
    wts1 = self.WtSets[ i1 ]
    wts2 = self.WtSets[ i2 ]

    list1 = wts1.Lis[0:] #just size new weight sets
    list2 = wts1.Lis[0:]

    flip = False #copy into new weight sets from old alternating the
    for k in range(len(wts1.Lis)): # the source on 2 to 4 flip points
    if k in splitPoints:
    flip = not flip

    if flip:
    list1[k] = wts2.Lis[k]
    list2[k] = wts1.Lis[k]
    else:
    list1[k] = wts1.Lis[k]
    list2[k] = wts2.Lis[k]

    split_pt1 = random.choice(splitPoints) #capture a place to mutate at low probabilty

    x = random.randint( 0, 1000 ) #.1 % of time mutate at boundry
    if x == 5:
    list1[ split_pt1 ] = RandomFloat(LOWWT,HIGHWT)
    list2[ split_pt1 ] = RandomFloat(LOWWT,HIGHWT)

    wt = WtSetClass( list1 )
    wt.FoldParentFitnesses( wts1,wts2 )
    new_wtset_list.WtSets.append( wt )
    if len(new_wtset_list.WtSets) < numsets:
    wt = WtSetClass( list2 )
    wt.FoldParentFitnesses( wts1,wts2 )
    new_wtset_list.WtSets.append( wt )
    x = random.randint(0,10000)
    if x == 5:
    new_wtset_list.RandomizeRandomWt() #0.01% of time made an entire new random wt
    self.WtSets = new_wtset_list.WtSets
    wes, Jan 28, 2008
    #12
  13. Max

    Max Guest

    On Jan 27, 7:25 pm, Steven D'Aprano <st...@REMOVE-THIS-
    cybersource.com.au> wrote:
    > 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.
    >


    Okay, I'm getting into the thick of things, and I want to make sure
    I'm implementing this correctly. I have a module Individual.py which
    contains the abstract class Individual and the class BitString. My
    population __init__ takes chromosome as a parameter, and checks:

    if chromosome is not issubclass(Individual):
    raise Exception("Chromosome type must be a subclass of
    Individual.")

    Then it creates individuals as instances of chromosome (x =
    chromosome(params)). I'm pretty sure this is all right - what I'm
    wondering is, when actually creating a population, would I pass
    Individual.BitString as a parameter? That's what I have now.

    I have similar worries about my selection scheme. Right now I have the
    function rouletteWheel defined as a member of Population, so I pass
    the selector to my GA class as Population.rouletteWheel (making sure I
    have Population imported). I just want to ensure that this is correct.
    Max, Jan 28, 2008
    #13
  14. Sir,

    Have you ever worked with Gene Expression Programming????


    David Blubaugh






    -----Original Message-----
    From: Wildemar Wildenburger [mailto:]
    Sent: Monday, January 28, 2008 7:24 AM
    To:
    Subject: Re: Python Genetic Algorithm

    Steven D'Aprano wrote:
    >> I'm not sure I'm following you here. So a "chromosome" is bit of
    >> functionality, right? So basically it is a function. So my advice
    >> would be to write these functions and store it to the
    >> "indivuals"-list like
    >> so:

    >
    > No, a chromosome is a bit of *data*: a noun, not a verb. Read these
    > bits
    > again:
    >
    > "Individuals HAVE what's called a chromosome - a SPECIFICATION of what


    > it contains. For example, common chromosomes are BIT STRINGS, ..."
    >

    Oh, OK. I *sort of* got this. Sort of. My reasoning was that these
    functions would return their associated "representation" upon being
    called. Which makes not much sense, especially after your explanation.



    > Some background which may help you understand what the OP is asking

    for.
    >
    > [snip little GA-intro]
    >

    Thanks Steven, that sure was useful. I think I now have a new toy
    hammer. I'm sure I'll see myself looking for toy nails everywhere over
    the next few weeks.

    :)
    /W


    This e-mail transmission contains information that is confidential and may be privileged. It is intended only for the addressee(s) named above. If you receive this e-mail in error, please do not read, copy or disseminate it in any manner. If you are not the intended recipient, any disclosure, copying, distribution or use of the contents of this information is prohibited. Please reply to the message immediately by informing the sender that the message was misdirected. After replying, please erase it from your computer system. Your assistance in correcting this error is appreciated.
    Blubaugh, David A., Jan 28, 2008
    #14
  15. Blubaugh, David A. wrote:
    > Have you ever worked with Gene Expression Programming????
    >

    No.

    Why?

    /W
    Wildemar Wildenburger, Jan 28, 2008
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. SNAKE

    genetic algorithm

    SNAKE, Nov 4, 2003, in forum: C++
    Replies:
    2
    Views:
    329
    Allan Bruce
    Nov 4, 2003
  2. Sean Ross

    OT: Genetic Algorithm Recipe Bug Fix

    Sean Ross, Jul 3, 2003, in forum: Python
    Replies:
    6
    Views:
    341
    Andrew Dalke
    Jul 18, 2003
  3. Replies:
    4
    Views:
    299
    Steven D'Aprano
    Feb 1, 2008
  4. Robo
    Replies:
    4
    Views:
    161
    Peter Hickman
    Dec 15, 2004
  5. n/a
    Replies:
    2
    Views:
    103
Loading...

Share This Page