## Genetic algorithm

By  —

A genetic algorithm is a search technique based on the principle of evolution. It starts out with a random population of possible solutions (in this example: black&white grids). Each new generation, the fittest members of the population “mate” and create a new population of children. In this case, the fitness of a member is based on symmetry: “if I am a black square, is my horizontal and vertical mirror also a black square?”.

Here is a random member from the first generation: And here is the fittest member of the 60th generation of ancestors: Although we aren’t there yet you can clearly see the pattern arising in the last generation.

Source code:

```# Grid size.
rows = 15
cols = 15

#-----------------------------------------------------------------------------
# A grid represented as a DNA list of True/False values.
# True means black, False means white.
# There are cols*rows elements in the list.

# Obviously, in more complex versions a list could contain all sorts of things,
# as long as our fitness function knows how to compare them.

def dna():
""" Returns a list of True (1) or False (0) values.
"""
return [choice((True, False)) for i in range(rows*cols)]

#-----------------------------------------------------------------------------
# Draw grid command.

def draw_grid(dna, width=10):
for x in range(cols):
for y in range(rows):
is_filled = dna[x+y*cols]
fill(int(not is_filled))
rect(x*width, y*width, width, width)

#-----------------------------------------------------------------------------
# Grid symmetry functions.

def in_grid(i):
""" Is the element at position i within the bounds of the list?
"""
return i > 0 and i < rows*cols

def north(i) : return i-cols # element above
def south(i) : return i+cols # element below
def east(i)  : return i+1    # element to the left
def west(i)  : return i-1    # element to the right

def northeast(i) : return north(east(i))
def northwest(i) : return north(west(i))
def southeast(i) : return south(east(i))
def southwest(i) : return south(west(i))

def row_reflection(i):
""" Returns the list index of the element in the grid
that is horizontally symmetrical to this one.
For example:
0 1 2 3
4 5 6 7
row_reflection(4) returns 7
row_reflection(5) returns 6
"""
row = i/cols
col = i-row*cols
return row*cols + cols-col-1

def col_reflection(i):
"""
0 1 2 3
4 5 6 7
col_reflection(1) returns 5
col_reflection(7) returns 3
"""
row = i/cols
col = i-row*cols
return (rows-row-1)*cols + col

#-----------------------------------------------------------------------------
# GA functions.

def recombine(dna1, dna2, crossover=0.5):
""" Returns a list that combines the head of dna1 and the tail of dna2.
http://en.wikipedia.org/wiki/Crossover_(genetic_algorithm)
"""
i = int(len(dna1) * crossover)
return dna1[:i] + dna2[i:]

def fitness(dna):
""" Symmetry fitness.
Black elements in the grid that have a horizontal
and vertical reflection score better.
You can use the grid symmetry functions to create all sorts of fitness checks.
"""
score = 0
for i in range(len(dna)):
j = row_reflection(i)
if in_grid(j) and dna[j] == dna[i]:
score += 1
j = col_reflection(i)
if in_grid(j) and dna[j] == dna[i]:
score += 1
# Here's another fitness function that will converge to entirely black:
#if dna[i] == True:
#    score += 1
return score

def population(size=500):
""" Returns a collection of grid DNA lists.
"""
return [dna() for i in range(size)]

def sort_by_fitness(population):
""" The DNA lists with the highest fitness will be at the front.
"""
best = [(fitness(x), x) for x in population]
best.sort(reverse=True)
return best

def next_generation(population, top=0.7, determinism=0.8):
""" Returns a new population of children by recombination.
http://en.wikipedia.org/wiki/Genetic_algorithm
"""
# Roughly the fittest top 60% are allowed to reproduce.
# We say roughly, because good solutions may be cast aside.
# This keeps the population diverse, so it doesn't converge too fast
# (less fit DNA might have some portions that become interesting later on).
population = sort_by_fitness(population)
parents = list(population)
i = len(parents)
iterations = 0
while len(parents) > len(population)*top:
if random() < determinism:
parents.pop(i-1)
i -= 1
if i == 0:
i = len(parents)
# I don't like while-loops.
# They tend to run forever when there is a bug.
# If the loop has been going for 1,000,000 times,
# something must have gone wrong.
iterations += 1
if iterations > 1000000:
break
# Cross-combine pairs of parents to a new population of children.
children = []
for i in range(len(population)):
parent1 = choice(parents)
parent2 = choice(parents)
if parent1 == parent2:
parent2 = choice(parents)
children.append(recombine(parent1, parent2, crossover=random()))
return children

from random import seed
seed(0)

# We need some number-crunching power:
import psyco
psyco.full()

# The initial random population:
p = population(size=500)

# Process n generations:
for i in range(80):
p = next_generation(p, top=0.6, determinism=0.7)

# A list of scores for each member in the final population:
#print [score for score, x in sort_by_fitness(p)]

# The best solution in the final population:
draw_grid(p, width=20)```

Improvements

• bigger population size: more diversity = more potential
• less determinism: more randomness = slower convergence to local optimum
• more generations: human evolution took millions of years too