1st non-trivial program - gentle criticism requested

[Paul-Michael Agapow]

Hi y'all,

I'm experimenting with Python for a number of purposes (an embedded
language for simulations, a tool for exploring experimental data, a good
first programming language) and so I've cobbled together my first
non-trivial program. With some trepidation, I post it here in the hopes
that experts will be able to coach me in "The Python Way". I realise it
looks like C++ (my usual langauge), but criticisms of style would be
useful too.

Basically, it's a recreation of the "Methinks it is a weasel" simulation
detailed by Richard Dawkins in "The Blind Watchmaker". A population of
strings is compared vs. a target string and the "fittest" (the one that
most resembles the target) is used to form the next generation, with a
small chance. So it's a simple genetic algorithm.

thanks

p-m


--- program follows

"""
weasel.py

A simple program exploring the possibilities of using Python, esp. in
simulations, modelling the 'methinks it is a weasel' problem from
Richard Dawkins' "The Blind Watchmaker". The program flow is:

1. Init population of random individuals
2. Pick fittest individual
3. If the individual is the target:
   3a. Return
   3b. Else, breed new population from individual (mutation)
4. Goto 2. 

"""

#--- Includes

import whrandom
import string


#--- Module constants & variables

kDefTarget = "METHINKS IT IS LIKE A WEASEL"
kDefPopSize = 10;
kDefStepSize = 50;

gPopulation = [];                         # the weasels, as it were
gRng = whrandom.whrandom()                # random source
gTarget                                   # what fitness is measured
against
gNumGenerations                           # how many cycles did it take?
gAlphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ " # all possible symbols
gMutationRate                             # chance of a symbol flipping
gStepSize                                 # how often to report stats


#--- Module functions -----------------------------------------------

#--- Run

# Setup the variables and run
def run (size=kDefPopSize, target=kDefTarget, step=kDefStepSize):
   global gTarget, gNumGenerations, gStepSize, gMutationRate
   # initialise
   gTarget = target
   gNumGenerations = 0;
   gStepSize = step
   gMutationRate = 1.0/ (len(gTarget) + 1)
   initPop (size);
   # tell user the settings
   print "WEASEL in action:"
   print "-----------------"
   printStartParams();
   print "-----------------"
   # evolve until the end is reached
   while (0 == evolvePop (gStepSize)):
      if (0 == (gNumGenerations % kDefStepSize)):
         print "At generation", gNumGenerations
   # print end results
   print "-----------------"
   print "Reached target after ", gNumGenerations, "generations"
   printPop();
   return


#--- Setup

def initPop (popsize = 10):
   # Initialise the contents of the population
   # Note: do this or gPop is local and temporary!
   global gPopulation
   gPopulation = [];
   for i in range (popsize):
      theNewMember = MakeNewMember (len(gTarget))
      gPopulation.append (theNewMember)
   return

def MakeNewMember (chromsize = len(gTarget)):
   # For initing the population, generate a random string of symbols
   # Note: seems inefficient creating strings this way
   theNewString = "";
   while (len(theNewString) < chromsize):
      theNewString = theNewString + GetRandomSymbol()
   return theNewString
   

#--- Mutation

def MutateIndividual (theTargetIndiv):
   """Iterates over symbols of individual changing their 'genes'"""
   # Must be a faster way of doing this
   theNewIndiv = ""
   for theSymbol in theTargetIndiv:
      if (gRng.random() < gMutationRate):
         theNewSymbol = GetRandomSymbol()
      else:
         theNewSymbol = theSymbol
      theNewIndiv = theNewIndiv + theNewSymbol
   return theNewIndiv


def GetRandomSymbol ():
   """For the purposes of mutation, this selects a random symbol from
the alphabet"""
   # The global declaration isn't necessary as we don't assign to these
   # vars, but I'm doing it as a reminder
   global gRng, gAlphabet
   theSymbolIndex = gRng.randint(0, len(gAlphabet) - 1)
   return gAlphabet[theSymbolIndex]
   
      
#--- Evolve

# Evolve for a given number of time steps
def evolvePop (iNumSteps):
   global gNumGenerations
   for i in range (iNumSteps):
      if (evolveStep()):
         return 1
      else:
         gNumGenerations = gNumGenerations + 1
   return 0
   

# Evolve a single step
def evolveStep ():
   global gPopulation
   if (gTarget in gPopulation):
      return 1
   else:
      # calculate fitness
      theFitness = []
      for theIndiv in gPopulation:
         theFitness.append (calcFitness (theIndiv))   
      # select winner
      theWinnerIndex = findMax (theFitness)
      theWinner = gPopulation[theWinnerIndex]
      assert (theWinnerIndex <> None)
      # breed from winner
      for i in range(len(gPopulation)):
         gPopulation[i] = MutateIndividual (theWinner)
      return 0


def calcFitness (anIndiv):
   theFitness = 0
   for i in range (len(gTarget)):
      if (gTarget[i] == anIndiv[i]):
         theFitness = theFitness + 1;
   return theFitness

def findMax (iCollection):
   # Returns the index of the largest member of collection
   # Just a little bullet-proofing
   if (len(iCollection) == 0):
      return
   # Setup initial sensible values
   theMaxIndex = 0
   theMaxVal = iCollection[0];
   # Iterate over remainder of container
   # Inefficient to look at the first element again, but it will do
   for i in range(len(iCollection)):
      if (theMaxVal < iCollection[i]):
         theMaxVal = iCollection[i]
         theMaxIndex = i
   return theMaxIndex
   

#--- Output

# Print out the contents of the population
def printStartParams ():
   print "The target is", gTarget
   print "The mutation rate is", gMutationRate
   print "The alphabet is '" + gAlphabet + "'"
   print "The population size is", len(gPopulation)
   printPop()
   return
   
   
# Print out the contents of the population
def printPop ():
   print "The population is currently:"
   gPopulation.sort()
   theCount = 0;
   for theIndividual in gPopulation:
      if (theIndividual == gTarget):
         thePrefix = "*"
      else:
         thePrefix = ""
      theCount = theCount + 1
      thePrefix = thePrefix + repr(theCount) + " :"
      print string.rjust(thePrefix,8), theIndividual


#--- if this is called as a standalone script   

if (__name__ == "__main__"):
   run()
   
   
-- 
Paul-Michael Agapow (p.agapow at ic.ac.uk), Biology, Silwood Park
"The world is made of fire."