#
# 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()
