home/diploma/lws_root/3rdparty/pygene/population.py

"""
pygene/population.py - Represents a population of organisms
"""

import random
from random import randrange, choice
from math import sqrt

from organism import Organism, BaseOrganism

from xmlio import PGXmlMixin

class Population(PGXmlMixin):
    """
    Represents a population of organisms

    You might want to subclass this

    Overridable class variables:

        - species - Organism class or subclass, being the 'species'
          of organism comprising this population

        - initPopulation - size of population to randomly create
          if no organisms are passed in to constructor

        - childCull - cull to this many children after each generation

        - childCount - number of children to create after each generation

        - incest - max number of best parents to mix amongst the
          kids for next generation, default 10

        - numNewOrganisms - number of random new orgs to add each
          generation, default 0

        - initPopulation - initial population size, default 10

        - mutants - default 0.1 - if mutateAfterMating is False,
          then this sets the percentage of mutated versions of
          children to add to the child population; children to mutate
          are selected based on fitness

    Supports the following python operators:

        - + - produces a new population instances, whose members are
          an aggregate of the members of the values being added

        - [] - int subscript - returns the ith fittest member

    """
    # cull to this many children after each generation
    childCull = 20

    # number of children to create after each generation
    childCount = 10

    # max number of best parents to mix amongst the kids for
    # next generation
    incest = 5

    # parameters governing addition of random new organisms
    numNewOrganisms = 0 # number of new orgs to add each generation

    # set to initial population size
    initPopulation = 10

    # set to species of organism
    species = Organism

    # mutate this proportion of organisms
    mutants = 0.2

    # set this to true to mutate all progeny
    mutateAfterMating = True

    def __init__(self, *items, **kw):
        """
        Create a population with zero or more members

        Arguments:
            - any number of arguments and/or sequences of args,
              where each arg is an instance of this population's
              species. If no arguments are given, organisms are
              randomly created and added automatically, according
              to self.initPopulation and self.species

        Keywords:
            - init - size of initial population to randomly create.
              Ignored if 1 or more constructor arguments are given.
              if not given, value comes from self.initPopulation
            - species - species of organism to create and add. If not
              given, value comes from self.species
        """
        self.organisms = []

        if kw.has_key('species'):
            species = self.species = kw['species']
        else:
            species = self.species

        if kw.has_key('init'):
            init = self.initPopulation = kw['init']
        else:
            init = self.initPopulation


        if not items:
            for i in xrange(init):
                self.add(species())
        else:
            self.add(*items)

    def add(self, *args):
        """
        Add an organism, or a population of organisms,
        to this population

        You can also pass lists or tuples of organisms and/or
        populations, to any level of nesting
        """
        for arg in args:
            if isinstance(arg, tuple) or isinstance(arg, list):
                # got a list of things, add them one by one
                self.add(*arg)

            if isinstance(arg, BaseOrganism):
                # add single organism
                self.organisms.append(arg)

            elif isinstance(arg, Population):
                # absorb entire population
                self.organisms.extend(arg)
            else:
                raise TypeError(
                    "can only add Organism or Population objects")

        self.sorted = False

    def __add__(self, other):
        """
        Produce a whole new population consisting of an aggregate
        of this population and the other population's members
        """
        return Population(self, other)

    def getRandom(self, items=None):
        """
        randomly select one of the given items
        (or one of this population's members, if items
        not given).

        Favours fitter members
        """
        if items == None:
            items = self.organisms

        nitems = len(items)
        n2items = nitems * nitems

        # pick one parent randomly, favouring fittest
        idx = int(sqrt(randrange(n2items)))
        return items[nitems - idx - 1]

    def gen(self, nfittest=None, nchildren=None):
        """
        Executes a generation of the population.

        This consists of:
            - producing 'nchildren' children, parented by members
              randomly selected with preference for the fittest
            - culling the children to the fittest 'nfittest' members
            - killing off the parents, and replacing them with the
              children

        Read the source code to study the method of probabilistic
        selection.
        """
        if not nfittest:
            nfittest = self.childCull
        if not nchildren:
            nchildren = self.childCount

        children = []

        # add in some new random organisms, if required
        if self.numNewOrganisms:
            #print "adding %d new organisms" % self.numNewOrganisms
            for i in xrange(self.numNewOrganisms):
                self.add(self.species())

        # we use square root to skew the selection probability to
        # the fittest

        # get in order, if not already
        self.sort()
        nadults = len(self)

        n2adults = nadults * nadults

        # statistical survey
        #stats = {}
        #for j in xrange(nchildren):
        #    stats[j] = 0

        # wild orgy, have lots of children
        for i in xrange(nchildren):
            # pick one parent randomly, favouring fittest
            idx1 = idx2 = int(sqrt(randrange(n2adults)))
            parent1 = self[-idx1]

            # pick another parent, distinct from the first parent
            while idx2 == idx1:
                idx2 = int(sqrt(randrange(n2adults)))
            parent2 = self[-idx2]

            #print "picking items %s, %s of %s" % (
            #    nadults - idx1 - 1,
            #    nadults - idx2 - 1,
            #    nadults)

            #stats[nadults - idx1 - 1] += 1
            #stats[nadults - idx2 - 1] += 1

            # get it on, and store the child
            child1, child2 = parent1 + parent2

            # mutate kids if required
            if self.mutateAfterMating:
                child1 = child1.mutate()
                child2 = child2.mutate()

            children.extend([child1, child2])

        # if incestuous, add in best adults
        if self.incest:
            children.extend(self[:self.incest])

        for i, child in enumerate(children):
            #~ print 'child %s' % i
            child.prepare_fitness()

        children.sort()

        # and add in some mutants, a proportion of the children
        # with a bias toward the fittest
        if not self.mutateAfterMating:
            nchildren = len(children)
            n2children = nchildren * nchildren
            mutants = []
            numMutants = int(nchildren * self.mutants)

            if 1:
                for i in xrange(numMutants):
                    # pick one parent randomly, favouring fittest
                    idx = int(sqrt(randrange(n2children)))
                    #child = children[nchildren - idx - 1]
                    child = children[-idx]
                    mutant = child.mutate()
                    mutant.prepare_fitness()
                    mutants.append(mutant)
            else:
                for i in xrange(numMutants):
                    mutant = children[i].mutate()
                    mutant.prepare_fitness()
                    mutants.append(mutant)

            children.extend(mutants)
            children.sort()
        #print "added %s mutants" % numMutants

        # sort the children by fitness

        # take the best 'nfittest', make them the new population
        self.organisms[:] = children[:nfittest]

        self.sorted = True

        #return stats
    def __repr__(self):
        """
        crude human-readable dump of population's members
        """
        return str(self.organisms)

    def __getitem__(self, n):
        """
        Return the nth member of this population,
        which we guarantee to be sorted in order from
        fittest first
        """
        self.sort()
        return self.organisms[n]

    def __len__(self):
        """
        return the number of organisms in this population
        """
        return len(self.organisms)

    def fitness(self):
        """
        returns the average fitness value for the population
        """
        fitnesses = map(lambda org: org.get_fitness(), self.organisms)

        return sum(fitnesses)/len(fitnesses)

    def best(self):
        """
        returns the fittest member of the population
        """
        self.sort()
        return self[0]

    def sort(self):
        """
        Sorts this population in order of fitness, with
        the fittest first.

        We keep track of whether this population is in order
        of fitness, so we don't perform unnecessary and
        costly sorting
        """
        if not self.sorted:
            for organism in self.organisms:
                organism.prepare_fitness()
            self.organisms.sort()
            self.sorted = True

    # methods for loading/saving to/from xml

    def xmlDumpSelf(self, doc, parent):
        """
        Writes out the contents of this population
        into the xml tree
        """
        # create population element
        pop = doc.createElement("population")
        parent.appendChild(pop)

        # set population class details
        pop.setAttribute("class", self.__class__.__name__)
        pop.setAttribute("module", self.__class__.__module__)

        # set population params as xml tag attributes
        pop.setAttribute("childCull", str(self.childCull))
        pop.setAttribute("childCount", str(self.childCount))

        # dump out organisms
        for org in self.organisms:
            org.xmlDumpSelf(doc, pop)