Matteo Landi

Here is an exercise I found around looking for some GA tutorials:

Given the digits 0 through 9 and the operators +, -, * and /, find a sequence that will represent a given target number. The operators will be applied sequentially from left to right as you read.

Here is my solution: it seems longer than the necessary but I decided to comment the code the more as possible.

Script Setting

We can modify these parameters to test different solutions.

# This value will be replaced by sys.argv[1].
TARGET = None

# The number of chromosomes contained in one population.
POPULATION_SIZE = 50

# Because a correct chromosome is composed by pairs of number and operators,
# you better choice an odd number of genes.
CHROMOSOME_SIZE = 11

# List of possible values a gene can assume.
GENES = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '+', '-', '*', '/']

# Define the probability used to apply the crossover operator to a chromosome.
CROSSOVER_PROBABILITY = 0.7

# Define the probability used to apply the mutation operator to a chromosome.
MUTATION_PROBABILITY = 0.7

# How often a message is shown on screen displaying the work in progress.
SHOW_EVOLUTION = 50

# the higher number we can represent using a chromosome which is a sequence of
# number, operator, number operator an so on.
MAX = 9**(math.ceil(CHROMOSOME_SIZE / 2))

# the lower number we can rapresent using a chromosome which is a sequence of
# number, operator, number operator and so on.
MIN = -MAX / 9

# the spread of the gaussian function used inside the fitness function, is
# based on normalization of the maximum distance between two possible
# solutions, and the number of chromosomes contained in a population.
GAUSSIAN_SPREAD = (MAX - MIN) / math.sqrt(POPULATION_SIZE)

Utility functions

Following, is a collection of functions used all around the script. In details we have a function which returns a shuffled version of a given sequence, one to purge a chromosome in order to make it look like a sequence of number/operator/number/operator an so on, one to evaluate the value of string represented by the chromosome, and finally the one which compute the fitness value of the given chromosome.

def randperm(seq):
  """Return a shuffled version of given sequence.
  Differently from the shuffle method from random module, the modifications are
  not made in place.

  """
  indices = range(len(seq))
  random.shuffle(indices)
  return [seq[i] for i in indices]

def purge_chromosome(chromosome):
  """Correct the given chromosome from syntactical errors.
  A correct sequence is composed by a number an operator a number and so on.

  """
  correct_chromosome = []
  next_num = True
  for item in chromosome:
    if next_num and item in ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']:
      correct_chromosome.append(item)
      next_num = False
    elif not next_num and item in ['+', '-', '*', '/']:
      correct_chromosome.append(item)
      next_num = True
  if next_num and correct_chromosome:
    correct_chromosome.pop()

  return correct_chromosome

def my_eval(command):
  """Evaluate the given command from left to right by not taking into account
  the precedences between arithmetical operators.

  """
  command = list(command)
  if not command:
    raise SyntaxError

  result = int(command.pop(0))
  while command:
    op = command.pop(0)
    other = int(command.pop(0))
    if op == '+':
      result += other
    if op == '-':
      result -= other
    if op == '*':
      result *= other
    if op == '/':
      result /= other
  return result

def fitness(chromosome):
  """Compute the fitness function of the given chromosome.
  @param chromosome the chromosome to evaluate.
  @return the fitness value if everything is ok, None otherwise. 

  """
  command = ''.join(purge_chromosome(chromosome))
  try:
    value = my_eval(command)
    if value == TARGET:
      return 1
    else:
      # use the gaussian function to compute the distance between the current
      # and the target solution
      return math.exp(-(TARGET - value)**2/GAUSSIAN_SPREAD)
  except SyntaxError:
    return 0
  except ZeroDivisionError:
    return 0

Class objects

I decided to create a couple of class for the representation of both the chromosomes and the population; in particular the Population class exports the method used to evolve such as the the selection, crossover and the mutation operators. There is a lot of python in these definitions:

class Chromosome(object):
  def __init__(self, **kwargs):
    """Create a new chromosome by specifying its value, and a method used to
    compute the fitness function. Here is the list of accepted keywords:

      data
      chromosome_size

    """
    if 'data' in kwargs:
      self.data = kwargs['data']
    else:
      data = []
      for _ in xrange(kwargs['chromosome_size']):
        data.append(random.choice(GENES))
      self.data = data

  def __len__(self):
    """Return the lenght of the chromosome.

    """
    return len(self.data)

  def __getitem__(self, i):
    """Return the i-th gene of the chromosome.

    """
    return self.data[i]

  def __setitem__(self, i, value):
    """Modify the i-th gene of the chromosome.

    """
    self.data[i] = value

  def __str__(self):
    """Display the chromosome on screen.

    """
    return ''.join(self.data)

class Population(object):
  def __init__(self, **kwargs):
    """Create a new population of chromosomes and set the paramenters which are
    going to be used during evolution. Here is a list of the accepted keywords:

      data
      chromosome_size
      population_size

    """
    data = []
    if 'data' in kwargs:
      data = kwargs['data']
    elif 'population_size' in kwargs:
      data = []
      for _ in xrange(kwargs['population_size']):
        data.append(Chromosome(**kwargs))
    self.data = data
    self.index = -1

  def roulette_wheel_selection(self, n):
    """Select one or more chromosomes from the population by using the roulette
    wheel proportional selection algorithm.
    @param n the number of chromosomes to extract.
    @return an array of selected chromosomes.

    """
    scores = map(fitness, self.data)
    total_score = sum(scores)

    selection = []
    for _ in xrange(n):
      probability = random.uniform(0, total_score)
      i = 0
      while probability > scores[i]:
        probability -= scores[i]
        i += 1
      selection.append(deepcopy(self.data[i]))

    return selection

  def crossover1(self, i, j, probability):
    """Apply the crossover operator on the i-th and j-th chromosomes with the
    given probability.  A signle random cut point is choosen.
    @return an array containing the new chromosomes.

    """
    if random.random() <= probability:
      point = random.randint(0, len(self.data[i]) - 1)
      datai = self.data[i][:point] + self.data[j][point:]
      dataj = self.data[j][:point] + self.data[i][point:]
      return [Chromosome(data=datai), Chromosome(data=dataj)]
    else:
      return []

  def mutate1(self, i, probability):
    """Mutate a gene of the i-th chromosome with a given probability.

    """
    data = self.data[i].data[:]
    if random.random() <= probability:
      point = random.randint(0, len(self.data[i]) - 1)
      data[point] = random.choice(GENES)
    return Chromosome(data=data)

  def __iadd__(self, other):
    """Add a one or more chromosomes to the population.

    """
    if isinstance(other, Chromosome):
      self.data.append(other)
    elif isinstance(other, list):
      self.data += other
    return self

  def __len__(self):
    """Return the number of chromosomes contained in the population.

    """
    return len(self.data)

  def __str__(self):
    """Display the population on screen.
    Display a chromosome per line.

    """
    return '\n'.join(map(str, self.data))

  def __iter__(self):
    """Make the object iterable.

    """
    return self

  def next(self):
    """Method invoked while iterating over the population of chromosomes.

    """
    if self.index == len(self.data) - 1:
      raise StopIteration
    self.index = self.index + 1
    return self.data[self.index]

Main

Finally we have the main function which evolve a random generated population in order to reach the goal:

def main(argv):
  if len(sys.argv) != 2:
    print 'Usage: %s ' % sys.argv[0]
    return 1

  global TARGET
  TARGET = float(sys.argv[1])

  pop = Population(population_size=POPULATION_SIZE,
                   chromosome_size=CHROMOSOME_SIZE)

  generation = 0
  while True:
    # evaluation
    if generation != 0 and not generation % SHOW_EVOLUTION:
      print 'Generation #%d' % generation
    for chromosome in pop:
      score = fitness(chromosome)

      if score == 1:
        print 'Success(#%d):' % generation,
        print ''.join(purge_chromosome(chromosome))
        return

    # selection
    pop_1 = Population(data=pop.roulette_wheel_selection(POPULATION_SIZE))

    # crossover
    pop_2 = Population()
    while len(pop_2) != POPULATION_SIZE:
      i = random.randint(0, POPULATION_SIZE - 1)
      j = random.randint(0, POPULATION_SIZE - 1)
      pop_2 += pop_1.crossover1(i, j, CROSSOVER_PROBABILITY)

    # mutation
    pop = Population()
    for i in xrange(len(pop_2)):
      pop += pop_2.mutate1(i, MUTATION_PROBABILITY)

    generation += 1

That's all! All you have to do right now, is to download the script and launch it by specifying a target number:

$ python find-the-sequence.py 666
Generation #50
Success(#85): 9*9-7*9