Genetic Algorithm in Python source code - AI-Junkie tutorial (Python recipe) by David Adler

ActiveState Code (http://code.activestate.com/recipes/578128/)

from operator import itemgetter, attrgetter
import random
import sys
import os
import math
import re


# GLOBAL VARIABLES

genetic_code = {
  '0000':'0',
  '0001':'1',
  '0010':'2',
  '0011':'3',
  '0100':'4',
  '0101':'5',
  '0110':'6',
  '0111':'7',
  '1000':'8',
  '1001':'9',
  '1010':'+',
  '1011':'-',
  '1100':'*',
  '1101':'/'
  }

solution_found = False
popN = 100 # n number of chromos per population
genesPerCh = 75
max_iterations = 1000
target = 1111.0
crossover_rate = 0.7
mutation_rate = 0.05

"""Generates random population of chromos"""
def generatePop ():
  chromos, chromo = [], []
  for eachChromo in range(popN):
    chromo = []
    for bit in range(genesPerCh * 4):
      chromo.append(random.randint(0,1))
    chromos.append(chromo)
  return chromos

"""Takes a binary list (chromo) and returns a protein (mathematical expression in string)"""
def translate (chromo):
  protein, chromo_string = '',''
  need_int = True
  a, b = 0, 4 # ie from point a to point b (start to stop point in string)
  for bit in chromo:
    chromo_string += str(bit)
  for gene in range(genesPerCh):
    if chromo_string[a:b] == '1111' or chromo_string[a:b] == '1110': 
      continue
    elif chromo_string[a:b] != '1010' and chromo_string[a:b] != '1011' and chromo_string[a:b] != '1100' and chromo_string[a:b] != '1101':
      if need_int == True:
        protein += genetic_code[chromo_string[a:b]]
        need_int = False
        a += 4
        b += 4
        continue
      else:
        a += 4
        b += 4
        continue
    else:
      if need_int == False:
        protein += genetic_code[chromo_string[a:b]]
        need_int = True
        a += 4
        b += 4
        continue
      else:
        a += 4
        b += 4
        continue
  if len(protein) %2 == 0:
    protein = protein[:-1]
  return protein
  
"""Evaluates the mathematical expressions in number + operator blocks of two"""
def evaluate(protein):
  a = 3
  b = 5
  output = -1
  lenprotein = len(protein) # i imagine this is quicker than calling len everytime?
  if lenprotein == 0:
    output = 0
  if lenprotein == 1:
    output = int(protein)
  if lenprotein >= 3:
    try :
      output = eval(protein[0:3])
    except ZeroDivisionError:
      output = 0
    if lenprotein > 4:
      while b != lenprotein+2:
        try :
          output = eval(str(output)+protein[a:b])
        except ZeroDivisionError:
          output = 0
        a+=2
        b+=2  
  return output

"""Calulates fitness as a fraction of the total fitness"""
def calcFitness (errors):
  fitnessScores = []
  totalError = sum(errors)
  i = 0
  # fitness scores are a fraction of the total error
  for error in errors:
    fitnessScores.append (float(errors[i])/float(totalError))
    i += 1
  return fitnessScores

def displayFit (error):
  bestFitDisplay = 100
  dashesN = int(error * bestFitDisplay)
  dashes = ''
  for j in range(bestFitDisplay-dashesN):
    dashes+=' '
  for i in range(dashesN):
    dashes+='+'
  return dashes


"""Takes a population of chromosomes and returns a list of tuples where each chromo is paired to its fitness scores and ranked accroding to its fitness"""
def rankPop (chromos):
  proteins, outputs, errors = [], [], []
  i = 1
  # translate each chromo into mathematical expression (protein), evaluate the output of the expression,
  # calculate the inverse error of the output
  print '%s: %s\t=%s \t%s %s' %('n'.rjust(5), 'PROTEIN'.rjust(30), 'OUTPUT'.rjust(10), 'INVERSE ERROR'.rjust(17), 'GRAPHICAL INVERSE ERROR'.rjust(105))
  for chromo in chromos: 
    protein = translate(chromo)
    proteins.append(protein)
    
    output = evaluate(protein)
    outputs.append(output)
    
    try:
      error = 1/math.fabs(target-output)
    except ZeroDivisionError:
      global solution_found
      solution_found = True
      error = 0
      print '\nSOLUTION FOUND' 
      print '%s: %s \t=%s %s' %(str(i).rjust(5), protein.rjust(30), str(output).rjust(10), displayFit(1.3).rjust(130))
      break
    else:
      #error = 1/math.fabs(target-output)
      errors.append(error)
    print '%s: %s \t=%s \t%s %s' %(str(i).rjust(5), protein.rjust(30), str(output).rjust(10), str(error).rjust(17), displayFit(error).rjust(105))
    i+=1  
  fitnessScores = calcFitness (errors) # calc fitness scores from the erros calculated
  pairedPop = zip ( chromos, proteins, outputs, fitnessScores) # pair each chromo with its protein, ouput and fitness score
  rankedPop = sorted ( pairedPop,key = itemgetter(-1), reverse = True ) # sort the paired pop by ascending fitness score
  return rankedPop

""" taking a ranked population selects two of the fittest members using roulette method"""
def selectFittest (fitnessScores, rankedChromos):
  while 1 == 1: # ensure that the chromosomes selected for breeding are have different indexes in the population
    index1 = roulette (fitnessScores)
    index2 = roulette (fitnessScores)
    if index1 == index2:
      continue
    else:
      break

  
  ch1 = rankedChromos[index1] # select  and return chromosomes for breeding 
  ch2 = rankedChromos[index2]
  return ch1, ch2

"""Fitness scores are fractions, their sum = 1. Fitter chromosomes have a larger fraction.  """
def roulette (fitnessScores):
  index = 0
  cumalativeFitness = 0.0
  r = random.random()
  
  for i in range(len(fitnessScores)): # for each chromosome's fitness score
    cumalativeFitness += fitnessScores[i] # add each chromosome's fitness score to cumalative fitness

    if cumalativeFitness > r: # in the event of cumalative fitness becoming greater than r, return index of that chromo
      return i


def crossover (ch1, ch2):
  # at a random chiasma
  r = random.randint(0,genesPerCh*4)
  return ch1[:r]+ch2[r:], ch2[:r]+ch1[r:]


def mutate (ch):
  mutatedCh = []
  for i in ch:
    if random.random() < mutation_rate:
      if i == 1:
        mutatedCh.append(0)
      else:
        mutatedCh.append(1)
    else:
      mutatedCh.append(i)
  #assert mutatedCh != ch
  return mutatedCh
      
"""Using breed and mutate it generates two new chromos from the selected pair"""
def breed (ch1, ch2):
  
  newCh1, newCh2 = [], []
  if random.random() < crossover_rate: # rate dependent crossover of selected chromosomes
    newCh1, newCh2 = crossover(ch1, ch2)
  else:
    newCh1, newCh2 = ch1, ch2
  newnewCh1 = mutate (newCh1) # mutate crossovered chromos
  newnewCh2 = mutate (newCh2)
  
  return newnewCh1, newnewCh2

""" Taking a ranked population return a new population by breeding the ranked one"""
def iteratePop (rankedPop):
  fitnessScores = [ item[-1] for item in rankedPop ] # extract fitness scores from ranked population
  rankedChromos = [ item[0] for item in rankedPop ] # extract chromosomes from ranked population

  newpop = []
  newpop.extend(rankedChromos[:popN/15]) # known as elitism, conserve the best solutions to new population
  
  while len(newpop) != popN:
    ch1, ch2 = [], []
    ch1, ch2 = selectFittest (fitnessScores, rankedChromos) # select two of the fittest chromos
        
    ch1, ch2 = breed (ch1, ch2) # breed them to create two new chromosomes 
    newpop.append(ch1) # and append to new population
    newpop.append(ch2)
  return newpop
  
      
def configureSettings ():
  configure = raw_input ('T - Enter Target Number \tD - Default settings: ')
  match1 = re.search( 't',configure, re.IGNORECASE )
  if match1:
    global target
    target = input('Target int: ' )

def main(): 
  configureSettings ()
  chromos = generatePop() #generate new population of random chromosomes
  iterations = 0

  while iterations != max_iterations and solution_found != True:
    # take the pop of random chromos and rank them based on their fitness score/proximity to target output
    rankedPop = rankPop(chromos) 
    
    print '\nCurrent iterations:', iterations
    
    if solution_found != True:
      # if solution is not found iterate a new population from previous ranked population
      chromos = []
      chromos = iteratePop(rankedPop)
            
      iterations += 1
    else:
      break

  
  
  
  
    
if __name__ == "__main__":
    main()