Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
An experimental evolutionary algorithm
from __future__ import print_function
from itertools import izip
from random import shuffle, sample, randint
from math import sqrt
try:
range = xrange
except NameError:
pass
class EqualSumGrid(object):
"""
Construct n x n matrix such that;
* each cell will be filled with numbers from 1 to n ^ 2
* sum of each row and column will be equal to sum(range(n**2)) / n
Genetic Algorithm will be utilized to find the solution.
"""
def __init__(self, rowlabels, collabels):
"""
len(rowlabels) and len(collabels) should be equal
rowlabels[i] + collabels[i] should be valid and hashable
"""
assert len(rowlabels) == len(collabels)
self.rowlabels = rowlabels
self.collabels = collabels
self.dim = len(rowlabels)
self.squares = [a+b for a in rowlabels for b in collabels]
self.sumtarget = sum(range(1, self.dim**2+1)) / self.dim
# each row and column is said to be a unit
self.rows = [[r+c for c in collabels] for r in rowlabels]
self.columns = [[r+c for r in rowlabels] for c in collabels]
self.units = self.rows + self.columns
self.population = None
def randompopulation(self, populationsize):
"""
Initialize a random populations with size populationsize. random.shuffle will be used to shuffle range(1, m*n+1)
"""
population = []
genomes = list(range(1,self.dim**2+1))
for i in range(populationsize):
shuffle(genomes)
population.append(dict(izip(self.squares, genomes)))
return population
def costs(self, population):
"""
Return a list of costs. costs[i] is cost of population[i]
Each row and column is said to be a unit.
(sum(unit) - sum(1..n^2) / n) ^ 2 is a squared residual
costs[i]["SSR"] = sum(squaredresiduals)
"""
costs = []
for individual in population:
errorterms = {}
for unit in self.units:
errorterms[str(unit)] = (self.sumtarget - sum(v for k,v in individual.items() if k in unit)) ** 2
errorterms["SSR"] = sqrt(sum(errorterms.values())) # take square root to normalize
costs.append(errorterms)
return costs
def geneticsearch(self, maxgenerations = 100, populationsize = 40, limit=0, verbose=False):
population = self.randompopulation(populationsize)
costs = self.costs(population)
found = False
bestcost = -1
solution = None
for i in range(maxgenerations):
SSRS = [c["SSR"] for c in costs]
oldcost, bestcost = bestcost, min(SSRS)
prevsolution, solution = solution, population[SSRS.index(bestcost)]
print(i, bestcost)
if bestcost <= limit:
found = True
break
# if oldcost == bestcost:
# break
if verbose:
print("Generation",i)
print("Population size", len(population))
print("best fit cost", min(c["SSR"] for c in costs))
population = self.nextgeneration(population, costs)
# print(population)
costs = self.costs(population)
if not found and verbose:
print("Couldnt find solution")
print("Best fit:")
self.visualize(solution)
elif verbose:
print("Solution in {} generations".format(i))
self.visualize(solution)
return solution, found, i
def nextgeneration(self, population, costs):
"""
Picks best 1/4 of population, they survive to next generation
Randomly mutates them 3 time, and add this to new generation too.
Best one will get extra mutations
"""
popfitness = sorted(izip(population, costs), key=lambda x: x[1]["SSR"])
elites = popfitness[:len(population) / 4]
nextgen = []
nextgen.extend(x[0] for x in elites)
# Random swap 2 squares
for individual, _ in elites:
for unit in sample(self.units, 2):
new_individual = {k:v for k,v in individual.iteritems()}
values = [new_individual[s] for s in unit]
for square, value in izip(unit, values[1:]):
new_individual[square] = value
new_individual[unit[-1]] = values[0]
nextgen.append(new_individual)
# Shift a row or column
for individual, _ in elites:
new_individual = {k:v for k,v in individual.iteritems()}
s1, s2 = sample(self.squares, 2)
new_individual[s1], new_individual[s2] = new_individual[s2], new_individual[s1]
nextgen.append(new_individual)
king, cost = popfitness[0]
# Find 2 rows that has biggest error
r1, r2 = (x[0] for x in sorted(((r[0][0], cost[str(r)]) for r in self.rows), key=lambda x: x[1], reverse=True)[:2])
# Find 2 columns that has biggest error
c1, c2 = (x[0] for x in sorted(((c[0][1], cost[str(c)]) for c in self.columns), key=lambda x: x[1], reverse=True)[:2])
# Swap and add
new_individual = {k:v for k, v in king.iteritems()}
new_individual[r1+c1], new_individual[r2+c2] = new_individual[r2+c2], new_individual[r1+c1]
nextgen.append(new_individual)
new_individual = {k:v for k, v in individual.iteritems()}
new_individual[r1+c2], new_individual[r2+c1] = new_individual[r2+c1], new_individual[r1+c2]
nextgen.append(new_individual)
return nextgen
def nextgenerationold(self, population, costs):
"""
Population size increases with each generation
Populate next generation by mutating selected individuals.
1 / 8 of population survives to next generation
3 / 4 of population mutates to next generation
(1 / 8) - 1 of the population crosses-over to next generation
1 random guy appears in each generation
Mutation type 1:
* Select len(population) / 2 individual with smallest costs
* For each such individual;
* select two rows R1, R2 and two columns C1, C2 that has biggest row errors
* swap R1, C1 with R2, C2 (newborn)
* swap R1, C2 with R2, C1 (newborn)
Mutation type 2:
* select a unit with smallest error term.
* if it is a row, rotate it to right
* if it is a column, rotate it to left
CrossOver:
* select two alpha males
* select len(population) / 4 females
* each alpha males makes 2 cross-overs with half of females
** Crosover rule
*** Select random number of genes to be crossed over
*** For each gene in female, find corresponding gene position in male
*** Swap current gene with gene in found position
*** repeat for other females
"""
popfitness = sorted(izip(population, costs), key=lambda x: x[1]["SSR"])
nextgen = [x[0] for x in popfitness[:len(population) / 8 ]]
### MUTATION 1 ###
for individual, cost in popfitness[:(len(population) * 3 / 16)]:
# Find 2 rows that has biggest error
r1, r2 = (x[0] for x in sorted(((r[0][0], cost[str(r)]) for r in self.rows), key=lambda x: x[1], reverse=True)[:2])
# Find 2 columns that has biggest error
c1, c2 = (x[0] for x in sorted(((c[0][1], cost[str(c)]) for c in self.columns), key=lambda x: x[1], reverse=True)[:2])
# Swap and add
new_individual = {k:v for k, v in individual.iteritems()}
new_individual[r1+c1], new_individual[r2+c2] = new_individual[r2+c2], new_individual[r1+c1]
nextgen.append(new_individual)
new_individual = {k:v for k, v in individual.iteritems()}
new_individual[r1+c2], new_individual[r2+c1] = new_individual[r2+c1], new_individual[r1+c2]
nextgen.append(new_individual)
### MUTATION 2 ###
for individual, cost in popfitness[:(len(population) * 3 / 8)]:
new_individual = {k:v for k, v in individual.iteritems()}
bestunit = min(cost.items(), key= lambda x: x[1])
# print(bestunit[0])
squares = eval(bestunit[0])
values = [new_individual[s] for s in squares]
for square, value in izip(squares, values[1:]):
new_individual[square] = value
new_individual[squares[-1]] = values[0]
nextgen.append(new_individual)
### Cross-Over ###
numexpectedchildren = (len(population) / 8) - 1 # 1 individual will be added at random
elites = popfitness[:len(population) / 4]
for i in range(numexpectedchildren):
female, male = (x[0] for x in sample(elites, 2))
newborn = {k:v for k, v in female.iteritems()}
tobecrossed = sample(self.squares, randint(1, self.dim**2))
for gene in tobecrossed:
for g, value in male.iteritems():
if value == female[gene]:
newposition = g
break
newborn[gene], newborn[newposition] = newborn[newposition], newborn[gene]
nextgen.append(newborn)
nextgen.extend(self.randompopulation(1))
return nextgen
def visualize(self, array):
" Print given mxn array to stdout"
# Create header line
print(" ", end="")
for k in self.collabels:
print(" {} ".format(k), end="")
print()
for r in self.rowlabels:
print("{} |".format(r), end="")
for c in self.collabels:
print(" {} ".format(array[r+c]), end="")
print()
if __name__ == "__main__":
import pickle
def runs(obj, times=100, maxgenerations = 1000, populationsize=50):
solutions = []
for i in range(times):
_, found, generations = obj.geneticsearch(maxgenerations=maxgenerations, populationsize=populationsize)
if not found:
generations += 1
solutions.append(generations)
if not found:
print("Trial {}: Couldnt find solution".format(i+1))
else:
print("Trial {}: Found solution in {} generations".format(i+1,generations))
return solutions
a = EqualSumGrid("ABCDEFGHIJ","0123456789")
import sys
try:
oldstdout = sys.stdout
f = open("1010-downto2.csv","w")
sys.stdout = f
a.geneticsearch(maxgenerations=1000, populationsize=300, limit=5)
finally:
sys.stdout = oldstdout
f.close()
"""
print("3x3")
a = EqualSumGrid("ABC","123")
solutions = runs(a)
with open("3.solutions","w") as f:
pickle.dump(solutions, f)
print("4x4")
a = EqualSumGrid("ABCD","1234")
solutions = runs(a)
with open("4.solutions","w") as f:
pickle.dump(solutions, f)
print("5x5")
a = EqualSumGrid("ABCDE","12345")
solutions = runs(a)
with open("5.solutions","w") as f:
pickle.dump(solutions, f)
print("6x6")
a = EqualSumGrid("ABCDEF","123456")
solutions = runs(a)
with open("6.solutions","w") as f:
pickle.dump(solutions, f)
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment