While getting my masters I took a class called Linear Programming. Although I did not get an A, I wrote a pretty neat python script to demonstrate the Genetic Algorithm. I was helped out by these two sites: electricmonk.nl and lethain.com.
Brief History
Genetic Algorithms were first invented by John Holland in the 1960s. Holland’s goal was not to create algorithms which solved problems, but to study how evolutionary adaptation could be incorporated with digital computers genetic. This idea has lead to a heavily researched field of optimization, which has itself evolved far beyond Holland’s idea. A famous example of utilizing these techniques is NASA’s “evolved antenna” which a challenging set of antenna requirements was used to evolve complex antenna geometry. This antenna became the first evolved design to traverse space after it was used in the 2006 NASA mission Space Technology 5 Hornby2006.
Overview of the Procedure
The genetic algorithm is an optimization procedure that draws its methods from the evolutionary growth of natural creatures. This algorithm is part of a larger set of optimization techniques known as evolutionary algorithms. These algorithms imitate evolutionary growth by three operators genetic:
mutation
Traits not passed on by inheritance, but altered by the environment or other external factors. This is to constantly alter the genetic diversity.
selection
The likelihood of which the most fit of the population survive, due to more beneficial traits.
crossover
Similar to sexual reproduction, the amalgam of DNA from male and female parents to create a diverse offspring.
Goal of the code
We want this: wyurvpoujbn
To become this: optimization
I want to give the code a random string of letters which will evolve into the goal word optimization. Creating the random letters, which I will now call “creatures”, is done with this function:
def creature(length=12):
'''
Returns a creature in the population.
This creates a random string of letters length long.
'''
creature = list(''.join([random.choice(
string.ascii_lowercase) for n in range(length)]))
return creature
In order to assess the fitness of these creatures another function must be created. This function determines how far each creature’s letter deviates from the goal word’s letters, then summed. For example, the creature wyurvpoujbn has a fitness of 75. W is 8 letters away from O and Y is 9 letters from P, and so on. All these numbers are added together to give a fitness number; perfect fitness is 0.
| Creature | Goal | Distance |
|---|---|---|
| w | o | 8 |
| y | p | 9 |
| u | t | 1 |
| i | i | 0 |
| r | m | 5 |
| v | i | 13 |
| p | z | 10 |
| o | a | 14 |
| u | t | 1 |
| j | i | 1 |
| b | o | 13 |
| n | n | 0 |
| Fitness | 75 |
def fitness(creature, final='optimization'):
'''Returns a fitness value.
Calculates the fitness of the characters. Zero is perfect fitness.
'''
sums = np.array([])
n = len(final)
for i in range(n):
a_i = abs(ord(creature[i]) - ord(final[i]))
sums = np.append(sums,a_i)
total = np.sum(sums)
return total
The creatures need to be created in larger amounts so the function population does just that. The average fitness of the population also needs to be calculated and that is what pop_average does.
def population(amount):
'''Returns a population of creatures.
Creates a list of creatures.
'''
popul = []
for i in range(amount):
creature_i = creature()
popul.append(creature_i)
return popul
def pop_average(pop):
'''Returns average fitness of population.
Averages the fitness of the given population.
'''
n = len(pop)
aver = []
for i in range(n):
pop_i = fitness(pop[i])
aver.append(pop_i)
average = np.mean(aver)
return average
The main code is the actual “evolution” of the creatures. The code begins by mutating parent creature letters by replacing them with random letters. These mutated parents are ordered by fitness level then removing (killing) the least fit parents. Finally, new child creatures are created by mixing the letters of the surviving parents. The children replace the dead parents so there is always the same population size.
def evolve(pop, survive=0.2, mutation=3):
'''Returns an evolved population.
1. Randomly mutates the parents DNA, with random letters.
2. Orders the parents by fitness level.
3. Culls 'survive' of the population.
4. Breeds the parents to create children.
'''
m = len(pop[0])
n = len(pop)
par_length = len(pop[0])
pop_length = len(pop)
order = []
# Mutation
for i in range(mutation):
which_parents = random.sample(range(0,len(pop)), mutation)
letter_index = random.sample(range(0,m), mutation)
pop[which_parents[i]][letter_index[i]] = ''.join([random.choice(
string.ascii_lowercase)])
for i in range(n):
pop_i = fitness(pop[i])
order.append(pop_i)
index = sorted(range(len(order)), key=order.__getitem__)
parents = [pop[index[0]], pop[index[1]]]
survival = int(len(order) * survive)
if survival & 1:
survival += 1
not_dead = random.sample(range(2,n), survival)
for i in range(survival):
parents.append(pop[not_dead[i]])
# Breeding (from http://lethain.com/)
parents_amount = len(parents)
desired = len(pop) - parents_amount
children = []
while len(children) < desired:
male = randint(0, parents_amount-1)
female = randint(0, parents_amount-1)
if male != female:
male = parents[male]
female = parents[female]
half = int(len(male) / 2)
child = male[:half] + female[half:]
children.append(child)
parents.extend(children)
return parents
The evolve function must be run in a loop to perform, so here is an example:
p = population(100)
fitness_history0 = [pop_average(p),]
while True:
p = evolve(p)
if pop_average(p) < 1:
print(''.join(p[0]))
break
top_creature = ''.join(p[0])
print("Population Average: {}\n Top Creature: {}".format(pop_average(p),
top_creature))
fitness_history0.append(pop_average(p))
Running the code three times and plotting the populations, we can see how each one performed. The lines are labeled with the initial most fit creatures.
Created: 22 Nov 2016