So a friend of mine introduced me to **Evolutionary Algorithms** a while back and I got some lecture notes passed onto me explaining the basics and a simple example in pseudo-code.

After a bit of work I’ve written up the queens example as an evolutionary algorithm in python. Here goes:

**The queens problem**

The following is the quote from wikipedia regarding the problem.

The eight queens puzzle is the problem of putting eight chess queens on an 8Ã—8 chessboard such that none of them is able to capture any other using the standard chess queen’s moves. The queens must be placed in such a way that no two queens would be able to attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.

The above image is one of the many solutions to the problem. Hint: if you are looking for many solutions once you have found one, all of its 4 rotations (if unique) are solutions too.

Check out the wikipedia article for more information

**Code**

This is the current code with medium amount of comments, I have also provided a heavily commented version for people with less python experience (scroll to bottom).

# -*- coding: utf-8 -*-
##################################################################
##################################################################
# QUEENS EXAMPLE
# - Program Type: Demonstration of Evolutionary alogorithms
# - Authour: Matthew Rollings
# - Date: 14/09/09
##################################################################
##################################################################
# Import randint from the random module
from random import randint
# Creates a array I just use for convenience
board=[1,2,3,4,5,6,7,8]
##################################################################
# FUNCTIONS
# Function to check amount of attacking queens
def check(array):
# Collisions represent number of attacking queens, starts at zero obv.
collisions=0
for i in range(1,9):
if i not in array:
print "DUPLICATE NUMBER ERROR - KILLING STUPID GENE" # Never happen ;)
return 0
# Total Collisions
# For each queen in the array
for i in range(0, 8):
col=0
# For every other queen in the array
for j in range(0, 8):
# avoids checking self vs self
if i!=j:
# if queen i is on a diagonal from queen j, then the
# difference in magnitude x-cord will equal the difference in
# the magnitude of the y-coord
if abs(board[i]-board[j])==abs(array[j]-array[i]):
# Sets a variable to tell the next part that a collision was detected
col=1
# If a collision was detected add one to collisions
if col==1:
collisions+=1
# Return 8-colllisions, so that 0 is bad (8 attacking queens) and 8 is good (no attacking queens)
return 8-collisions
# The reproduce function, takes two arguements, the two parents
def reproduce(array1, array2):
# FIRST BABY (mother first then father)
# Takes first half of mothers gene
baby=array1[0:4]
# Can't just add two halves as I will get duplicate numbers
for i in array2:
# add fathers genes going in order of numbers left
if i not in baby:
baby.append(i)
# Add a little variation by giving a percentage chance of mutation
if randint(0,100)>20:
baby=mutate(baby)
# Add the baby to the population and add its corresponding fitness
population.append(baby)
fitness.append(check(baby))
# SECOND BABY (arrays just swapped around, Father first then mother)
baby=array2[0:4]
for i in array1:
if i not in baby:
baby.append(i)
if randint(0,100)>20:
baby=mutate(baby)
population.append(baby)
fitness.append(check(baby))
# Mutate the array given to the function
def mutate(array1):
#Chooses two random places (WARNING CAN BE SAME POSITION)
a=randint(0,7)
b=randint(0,7)
# Swaps the two over (temporary var must be used (c))
c=array1[a]
array1[a]=array1[b]
array1[b]=c
return array1
# Prints the population and corresponding fitness to the screen
# Only used for debugging
def printpop():
# Prints the group
for i in range(0, len(population)):
print population[i],fitness[i]
##################################################################
# VARIABLES
# The size of the population (how many genes, more = faster convergance but more cpu + memory, fewer = opp.)
popsize=40
# The starting variation of the group because I havn't created a better method
# for starting off. I just add arrays of 1,2,3,4,5,6,7,8 to the population and
# give them the number of mutations between the following two values to make
# psudo random starting group
variation=[4,14]
# How many of the genes to kill each time in percentage, each dead gene will be replaced by a new child :)
die=0.40
# Kill limit is calculated from the above percentage
kill_limit=die*popsize
##################################################################
# MAIN
population=[]
fitness=[]
for i in range(0,popsize):
population.append([1,2,3,4,5,6,7,8])
a=0
while a<randint(variation[0],variation[1]):
a+=1
population[i]=mutate(population[i])
fitness.append(check(population[i]))
maxi=0
generations=1
while maxi!=8:
# Picks top # in group to be parents, kills rest
killed=0
# starting at the lowest fitness (0 and increasing untill kill limit reached)
x=0
while killed<kill_limit:
for i in range(0,popsize):
# Try is here to catch any errors
try:
if fitness[i]==x:
# This bit removes the crappy gene from the population and from fitness
population.pop(i)
fitness.pop(i)
# increases the kill counter
killed+=1
if killed==kill_limit:
break
except:
break
# increments fitness
x+=1
babies=0
cpop=len(population)-1 #current population
while babies<killed:
# produces two babies from two random parents (should prob give fittest parents preference)
reproduce(population[randint(0,cpop)],population[randint(0,cpop)])
babies+=2
generations+=1
# Looks for highest fitness in the group and checks if any have won!
maxi=0
for i in range(0,popsize):
if fitness[i]>maxi:
maxi=fitness[i]
if maxi==8:
print population[i]
break
print "Took",generations,"generations"

**Quick Analysis**

I did a very quick analysis keeping the kill off percentage at 0.4 and varying the population size to see the improvement on generations required before a solution is found. I’ve also added a link (scroll to bottom) to the .ods file I used to calculate this (and an excel .xls file for the windows chaps). Below is the graph I calculated for different population sizes and it looks like we would expect, decreasing as the population increases. I only did 10 averages for each point and there were some anomalies, which are to be expected with this method of programming as it essentially relies on random numbers so it is a bit noisey:

**Links**

Note the following might be more desirable to copy and pasting the above as they use tabs rather than spaces.

queens.py – The normal version

queens_commented.py – The heavily commented version.

evolutionary.ods – Analysis in ods format (open office)

evolutionary.xls – Analysis in excel format

If you have any corrections or suggestions please contact me.