sites/hobo11.nerdland.org/coursework/20062/achtung/src/pygene/population.py

   1 """
   2 pygene/population.py - Represents a population of organisms
   3 """
   4
   5 import random
   6 from random import randrange, choice
   7 from math import sqrt
   8
   9 from organism import Organism, BaseOrganism
  10
  11 from xmlio import PGXmlMixin
  12
  13 class Population(PGXmlMixin):
  14     """
  15     Represents a population of organisms
  16
  17     You might want to subclass this
  18
  19     Overridable class variables:
  20
  21         - species - Organism class or subclass, being the 'species'
  22           of organism comprising this population
  23
  24         - initPopulation - size of population to randomly create
  25           if no organisms are passed in to constructor
  26
  27         - childCull - cull to this many children after each generation
  28
  29         - childCount - number of children to create after each generation
  30
  31         - incest - max number of best parents to mix amongst the
  32           kids for next generation, default 10
  33
  34         - numNewOrganisms - number of random new orgs to add each
  35           generation, default 0
  36
  37         - initPopulation - initial population size, default 10
  38
  39         - mutants - default 0.1 - if mutateAfterMating is False,
  40           then this sets the percentage of mutated versions of
  41           children to add to the child population; children to mutate
  42           are selected based on fitness
  43
  44     Supports the following python operators:
  45
  46         - + - produces a new population instances, whose members are
  47           an aggregate of the members of the values being added
  48
  49         - [] - int subscript - returns the ith fittest member
  50
  51     """
  52     # cull to this many children after each generation
  53     childCull = 20
  54
  55     # number of children to create after each generation
  56     childCount = 100
  57
  58     # max number of best parents to mix amongst the kids for
  59     # next generation
  60     incest = 10
  61
  62     # parameters governing addition of random new organisms
  63     numNewOrganisms = 0 # number of new orgs to add each generation
  64
  65     # set to initial population size
  66     initPopulation = 10
  67
  68     # set to species of organism
  69     species = Organism
  70
  71     # mutate this proportion of organisms
  72     mutants = 0.1
  73
  74     # set this to true to mutate all progeny
  75     mutateAfterMating = True
  76
  77     def __init__(self, *items, **kw):
  78         """
  79         Create a population with zero or more members
  80
  81         Arguments:
  82             - any number of arguments and/or sequences of args,
  83               where each arg is an instance of this population's
  84               species. If no arguments are given, organisms are
  85               randomly created and added automatically, according
  86               to self.initPopulation and self.species
  87
  88         Keywords:
  89             - init - size of initial population to randomly create.
  90               Ignored if 1 or more constructor arguments are given.
  91               if not given, value comes from self.initPopulation
  92             - species - species of organism to create and add. If not
  93               given, value comes from self.species
  94         """
  95         self.organisms = []
  96
  97         if kw.has_key('species'):
  98             species = self.species = kw['species']
  99         else:
 100             species = self.species
 101
 102         if kw.has_key('init'):
 103             init = self.initPopulation = kw['init']
 104         else:
 105             init = self.initPopulation
 106
 107         if not items:
 108             for i in xrange(init):
 109                 self.add(species())
 110
 111     def add(self, *args):
 112         """
 113         Add an organism, or a population of organisms,
 114         to this population
 115
 116         You can also pass lists or tuples of organisms and/or
 117         populations, to any level of nesting
 118         """
 119         for arg in args:
 120             if isinstance(arg, tuple) or isinstance(arg, list):
 121                 # got a list of things, add them one by one
 122                 self.add(*item)
 123
 124             if isinstance(arg, BaseOrganism):
 125                 # add single organism
 126                 self.organisms.append(arg)
 127
 128             elif isinstance(arg, Population):
 129                 # absorb entire population
 130                 self.organisms.extend(arg)
 131             else:
 132                 raise TypeError(
 133                     "can only add Organism or Population objects")
 134
 135         self.sorted = False
 136
 137     def __add__(self, other):
 138         """
 139         Produce a whole new population consisting of an aggregate
 140         of this population and the other population's members
 141         """
 142         return Population(self, other)
 143
 144     def getRandom(self, items=None):
 145         """
 146         randomly select one of the given items
 147         (or one of this population's members, if items
 148         not given).
 149
 150         Favours fitter members
 151         """
 152         if items == None:
 153             items = self.organisms
 154
 155         nitems = len(items)
 156         n2items = nitems * nitems
 157
 158         # pick one parent randomly, favouring fittest
 159         idx = int(sqrt(randrange(n2items)))
 160         return items[nitems - idx - 1]
 161
 162     def gen(self, nfittest=None, nchildren=None):
 163         """
 164         Executes a generation of the population.
 165
 166         This consists of:
 167             - producing 'nchildren' children, parented by members
 168               randomly selected with preference for the fittest
 169             - culling the children to the fittest 'nfittest' members
 170             - killing off the parents, and replacing them with the
 171               children
 172
 173         Read the source code to study the method of probabilistic
 174         selection.
 175         """
 176         if not nfittest:
 177             nfittest = self.childCull
 178         if not nchildren:
 179             nchildren = self.childCount
 180
 181         children = []
 182
 183         # add in some new random organisms, if required
 184         if self.numNewOrganisms:
 185             #print "adding %d new organisms" % self.numNewOrganisms
 186             for i in xrange(self.numNewOrganisms):
 187                 self.add(self.__class__())
 188
 189         # we use square root to skew the selection probability to
 190         # the fittest
 191
 192         # get in order, if not already
 193         self.sort()
 194         nadults = len(self)
 195
 196         n2adults = nadults * nadults
 197
 198         # statistical survey
 199         #stats = {}
 200         #for j in xrange(nchildren):
 201         #    stats[j] = 0
 202
 203         # wild orgy, have lots of children
 204         for i in xrange(nchildren):
 205             # pick one parent randomly, favouring fittest
 206             idx1 = idx2 = int(sqrt(randrange(n2adults)))
 207             parent1 = self[-idx1]
 208
 209             # pick another parent, distinct from the first parent
 210             while idx2 == idx1:
 211                 idx2 = int(sqrt(randrange(n2adults)))
 212             parent2 = self[-idx2]
 213
 214             #print "picking items %s, %s of %s" % (
 215             #    nadults - idx1 - 1,
 216             #    nadults - idx2 - 1,
 217             #    nadults)
 218
 219             #stats[nadults - idx1 - 1] += 1
 220             #stats[nadults - idx2 - 1] += 1
 221
 222             # get it on, and store the child
 223             child1, child2 = parent1 + parent2
 224
 225             # mutate kids if required
 226             if self.mutateAfterMating:
 227                 child1 = child1.mutate()
 228                 child2 = child2.mutate()
 229
 230             children.extend([child1, child2])
 231
 232         # if incestuous, add in best adults
 233         if self.incest:
 234             children.extend(self[:self.incest])
 235
 236         children.sort()
 237
 238         # and add in some mutants, a proportion of the children
 239         # with a bias toward the fittest
 240         if not self.mutateAfterMating:
 241             nchildren = len(children)
 242             n2children = nchildren * nchildren
 243             mutants = []
 244             numMutants = int(nchildren * self.mutants)
 245
 246             if 1:
 247                 for i in xrange(numMutants):
 248                     # pick one parent randomly, favouring fittest
 249                     idx = int(sqrt(randrange(n2children)))
 250                     #child = children[nchildren - idx - 1]
 251                     child = children[-idx]
 252                     mutants.append(child.mutate())
 253             else:
 254                 for i in xrange(numMutants):
 255                     mutants.append(children[i].mutate())
 256
 257             children.extend(mutants)
 258
 259         #print "added %s mutants" % numMutants
 260
 261         # sort the children by fitness
 262         children.sort()
 263
 264         # take the best 'nfittest', make them the new population
 265         self.organisms[:] = children[:nfittest]
 266
 267         self.sorted = True
 268
 269         #return stats
 270     def __repr__(self):
 271         """
 272         crude human-readable dump of population's members
 273         """
 274         return str(self.organisms)
 275
 276     def __getitem__(self, n):
 277         """
 278         Return the nth member of this population,
 279         which we guarantee to be sorted in order from
 280         fittest first
 281         """
 282         self.sort()
 283         return self.organisms[n]
 284
 285     def __len__(self):
 286         """
 287         return the number of organisms in this population
 288         """
 289         return len(self.organisms)
 290
 291     def fitness(self):
 292         """
 293         returns the average fitness value for the population
 294         """
 295         fitnesses = map(lambda org: org.fitness(), self.organisms)
 296
 297         return sum(fitnesses)/len(fitnesses)
 298
 299     def best(self):
 300         """
 301         returns the fittest member of the population
 302         """
 303         self.sort()
 304         return self[0]
 305
 306     def sort(self):
 307         """
 308         Sorts this population in order of fitness, with
 309         the fittest first.
 310
 311         We keep track of whether this population is in order
 312         of fitness, so we don't perform unnecessary and
 313         costly sorting
 314         """
 315         if not self.sorted:
 316             self.organisms.sort()
 317             self.sorted = True
 318
 319     # methods for loading/saving to/from xml
 320
 321     def xmlDumpSelf(self, doc, parent):
 322         """
 323         Writes out the contents of this population
 324         into the xml tree
 325         """
 326         # create population element
 327         pop = doc.createElement("population")
 328         parent.appendChild(pop)
 329
 330         # set population class details
 331         pop.setAttribute("class", self.__class__.__name__)
 332         pop.setAttribute("module", self.__class__.__module__)
 333
 334         # set population params as xml tag attributes
 335         pop.setAttribute("childCull", str(self.childCull))
 336         pop.setAttribute("childCount", str(self.childCount))
 337
 338         # dump out organisms
 339         for org in self.organisms:
 340             org.xmlDumpSelf(doc, pop)
 341
 342
 343