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
