python genetic programming

http://www.freenet.org.nz/python/pygene/doc/

Package pygene

pygene is a library for genetic algorithms in python

It aims to be very simple to use, and suitable for people new to genetic
algorithms.
Submodules
gamete: Implements gametes, which are the result of splitting an
organism's genome in two, and are used in the organism's sexual
reproduction
gene: Implements a collection of gene classes
organism: Implements classes for entire organisms
population: pygene/population.py - Represents a population of
organisms
prog: Implements genetic programming organisms
xmlio: xmlio.py

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/199121

<code>
#
# genetic.py
#

import random

MAXIMIZE, MINIMIZE = 11, 22

class Individual(object):
alleles = (0,1)
length = 30
seperator = ''
optimization = MINIMIZE

def __init__(self, chromosome=None):
self.chromosome = chromosome or self._makechromosome()
self.score = None # set during evaluation

def _makechromosome(self):
"makes a chromosome from randomly selected alleles."
return [random.choice(self.alleles) for gene in range(self.length)]

def evaluate(self, optimum=None):
"this method MUST be overridden to evaluate individual fitness
score."
pass

def crossover(self, other):
"override this method to use your preferred crossover method."
return self._twopoint(other)

def mutate(self, gene):
"override this method to use your preferred mutation method."
self._pick(gene)

# sample mutation method
def _pick(self, gene):
"chooses a random allele to replace this gene's allele."
self.chromosome[gene] = random.choice(self.alleles)

# sample crossover method
def _twopoint(self, other):
"creates offspring via two-point crossover between mates."
left, right = self._pickpivots()
def mate(p0, p1):
chromosome = p0.chromosome[:]
chromosome[left:right] = p1.chromosome[left:right]
child = p0.__class__(chromosome)
child._repair(p0, p1)
return child
return mate(self, other), mate(other, self)

# some crossover helpers ...
def _repair(self, parent1, parent2):
"override this method, if necessary, to fix duplicated genes."
pass

def _pickpivots(self):
left = random.randrange(1, self.length-2)
right = random.randrange(left, self.length-1)
return left, right

#
# other methods
#

def __repr__(self):
"returns string representation of self"
return '<%s chromosome="%s" score=%s>' % \
(self.__class__.__name__,
self.seperator.join(map(str,self.chromosome)), self.score)

def __cmp__(self, other):
if self.optimization == MINIMIZE:
return cmp(self.score, other.score)
else: # MAXIMIZE
return cmp(other.score, self.score)

def copy(self):
twin = self.__class__(self.chromosome[:])
twin.score = self.score
return twin

class Environment(object):
def __init__(self, kind, population=None, size=100, maxgenerations=100,

crossover_rate=0.90, mutation_rate=0.01, optimum=None):
self.kind = kind
self.size = size
self.optimum = optimum
self.population = population or self._makepopulation()
for individual in self.population:
individual.evaluate(self.optimum)
self.crossover_rate = crossover_rate
self.mutation_rate = mutation_rate
self.maxgenerations = maxgenerations
self.generation = 0
self.report()

def _makepopulation(self):
return [self.kind() for individual in range(self.size)]

def run(self):
while not self._goal():
self.step()

def _goal(self):
return self.generation > self.maxgenerations or \
self.best.score == self.optimum

def step(self):
self.population.sort()
self._crossover()
self.generation += 1
self.report()

def _crossover(self):
next_population = [self.best.copy()]
while len(next_population) < self.size:
mate1 = self._select()
if random.random() < self.crossover_rate:
mate2 = self._select()
offspring = mate1.crossover(mate2)
else:
offspring = [mate1.copy()]
for individual in offspring:
self._mutate(individual)
individual.evaluate(self.optimum)
next_population.append(individual)
self.population = next_population[:self.size]

def _select(self):
"override this to use your preferred selection method"
return self._tournament()

def _mutate(self, individual):
for gene in range(individual.length):
if random.random() < self.mutation_rate:
individual.mutate(gene)

#
# sample selection method
#
def _tournament(self, size=8, choosebest=0.90):
competitors = [random.choice(self.population) for i in range(size)]
competitors.sort()
if random.random() < choosebest:
return competitors[0]
else:
return random.choice(competitors[1:])

def best():
doc = "individual with best fitness score in population."
def fget(self):
return self.population[0]
return locals()
best = property(**best())

def report(self):
print "="*70
print "generation: ", self.generation
print "best: ", self.best

---------------------------------------------------------------------
#
# onemax.py - useage example
#
# the fittest individual will have a chromosome consisting of 30 '1's
#

import genetic

class OneMax(genetic.Individual):
optimization = genetic.MAXIMIZE
def evaluate(self, optimum=None):
self.score = sum(self.chromosome)
def mutate(self, gene):
self.chromosome[gene] = not self.chromosome[gene] # bit flip

if __name__ == "__main__":
env = genetic.Environment(OneMax, maxgenerations=1000, optimum=30)
env.run()
</code>