Download and view my resume (PDF)

Monday, September 28, 2009

Simple Genetic Algorithm In Python

Following is a simple genetic algorithm written in python. A genetic algorithm uses a model of genetic evolution to find solutions to a problem which are increasingly good, until they reach a threshold of goodness. A population of beginning organisms experiences mutations and selections so that organisms with positive mutations are selected over organisms without positive mutations, or with negative mutations.

This algorithm solves a straightforward problem: finding a string. Each organism starts off with a string of correct length but having only spaces. In each generation, some of the organisms will experience mutations, which in this algorithm means one or more of the characters in their string is randomly changed. Organisms are then allowed to breed a certain number of times, then the fitness of each organism is calculated and the most fit organisms live on to the next generation. In this algorithm, the overall population count is kept steady from generation to generation, and fitness is calculated by how many characters an organism shares in common with a target string.

You can modify the parameters of this algorithm by controlling the numberOfOrganisms, chanceOfMutation, numberOfMutations, and matesPerGen. You can also change the target string to be longer, shorter, or just different; but make sure that the 'blank' string is exactly the same length, or this algorithm won't be able to finish.

I am learning python using this script, so it may not be in model python code style.

import random


chars = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D',
'E', 'F', 'G', 'H', 'I', 'J',
'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
'U', 'V', 'W', 'X', 'Y', 'Z',
'1', '2', '3', '4', '5', '6', '7', '8', '9', '0',
' ', ',', '.']

numberOfOrganisms = 50;
chanceOfMutation = 3 # one chance in this many
numberOfMutations = 3 # up to this many, if mutations are selected to happen at all
matesPerGen = 3; # each organism produces this many offspring for the next generation
target = """All legislative Powers herein granted shall be vested in a Congress of the United States"""
blank = """ """
lenTarget = len(target);

class organism:
fitness = 0
value = blank

def __cmp__( self, other ):
return cmp( other.fitness, self.fitness )

# an organism mates with another organism by comparing the chars of their values
# if the chars are equal, the offspring gets that char
# if they are not equal, the offspring gets one or the other, randomly
def mate( self, other ):
retCell = organism()
retCell.value = ""
for i in range(0,len(self.value)):
if self.value[i] == other.value[i]:
retCell.value += self.value[i]
elif random.randint(0,1) == 0:
retCell.value += self.value[i]
else:
retCell.value += other.value[i]
retCell.evaluateFitness( target )
return retCell

# this function may mutate the value of the organism in random places
def maybeMutate( self ):
if( random.randint( 0, chanceOfMutation ) == 0 ):
for i in range(random.randint(0,numberOfMutations)):
insertLoc = random.randint(0, len(self.value)-1)
self.value = self.value[0:insertLoc] + chars[random.randint(0, len(chars)-1)] + self.value[insertLoc+1:]
self.evaluateFitness( target )

# an organism's fitness is equal to the number of chars it shares with the target
def evaluateFitness( self, target ):
self.fitness = 0
for j in range(0,len(self.value)):
if self.value[j] == target[j]:
self.fitness += 1;
return self.fitness

def beginMutations( cells ):
keepGoing = True
iterations = 0
highestFitness = 0 # also an index into fitnessIterations
fitnessIterations = []

while( keepGoing ):
# a fresh next generation
iterations += 1
nextGenCells = []

# mutate the cells into a new arary
# evaluate the fitness of the mutated cells
for cell in cells:
cell.maybeMutate()
cell.evaluateFitness( target )

# mate all the cells into a new generation
# this will produce matesPerGen*len(cells) next-gen cells
for cell1 in cells:
for i in range(0, matesPerGen):
cell2 = cells[random.randint(0, len(cells)-1)]
childCell = cell1.mate( cell2 )
childCell.evaluateFitness( target )
nextGenCells.append( childCell )

# select cells into the next generation
nextGenCells.sort()

cells = nextGenCells[0:numberOfOrganisms]
if( cells[0].fitness > highestFitness ):
print "* new most fit *"
highestFitness = cells[0].fitness
for i in range( len( fitnessIterations ), highestFitness ):
fitnessIterations.append( iterations )

print "%d Most fit: %d of %d ~ %s" % (iterations, cells[0].fitness, lenTarget, cells[0].value)

#print "Selected next generation:"
for cell in cells:
#print cell.value, cell.fitness
if(cell.fitness == lenTarget):
print "!! In iteration %d found target %s" % (iterations, cell.value)
keepGoing = False

print "History of progress:"
for ind in range(len(fitnessIterations)):
print ind, fitnessIterations[ind]

# initialize the ecosystem and begin the mutations
starterCells = []
for i in range( numberOfOrganisms ):
starterCells.append( organism() )

beginMutations( starterCells )

No comments:

Post a Comment