Skip to content

Instantly share code, notes, and snippets.

Created Mar 26, 2010
What would you like to do?
# Simple generic algorithm
# Authors: Valeriya Guseva and Dmitrii Golub
# Date: March 2010
import numpy
import pylab
from math import *
from random import randint, random
# Constants
PC = numpy.arange(0.1, 1.1, 0.1) # Range of crossover probability
PM = numpy.arange(0.001, 0.004, 0.001) # Range of mutation probability
nr_pops = 20 # Number of populations
nr_gen_person = 100 # Number of persons in one generation
len_chr = 20 # Length of chromosome
def RandomGen():
def generate_person():
person = [randint(0,1) for i in range(len_chr)]
if reduce(lambda r, x: r + x, person) == len(person):
return generate_person()
return person
return [generate_person() for j in range(nr_gen_person)]
def RandomSelect(random_array):
segment_array = [0]
for i in random_array:
segment_array.append(segment_array[-1] + i)
r = random()
result = 0
for i in range(1, len(segment_array)):
if (r > segment_array[i-1]) and (r <= segment_array[i]):
result = i-1
return result
def WheelSelect(ft):
sum = reduce(lambda x, r: x + r, ft)
ft = map(lambda person: (person+.0)/sum, ft)
nr_parent1 = RandomSelect(ft)
nr_parent2 = nr_parent1
while (nr_parent2==nr_parent1):
nr_parent2 = RandomSelect(ft)
return nr_parent1, nr_parent2
def Crossover(parent1,parent2, crossover_prob):
if (random()<crossover_prob):
locus = randint(0, len(parent1)-1)
descendant1 = parent1[0:locus+1]+parent2[locus+1:]
descendant2 = parent1[locus+1:]+parent2[0:locus+1]
return descendant1,descendant2
return parent1, parent2
def Mutation (descendant, mutation_prob):
for i in descendant:
if (random()<mutation_prob):
i = (i+1)%2
return descendant
def Fitness(generation):
return map(lambda person: reduce(lambda sum, gen: sum + gen, person), generation)
def NewGen(prev_gen, crossover_prob, mutation_prob):
next_gen = []
ft = Fitness(prev_gen)
while len(next_gen)< nr_gen_person:
nr_parent1, nr_parent2 = WheelSelect(ft)
descendant1, descendant2 = Crossover(prev_gen[nr_parent1], prev_gen[nr_parent2], crossover_prob)
next_gen.append(Mutation(descendant1, mutation_prob))
next_gen.append(Mutation(descendant2, mutation_prob))
return next_gen
def Check(generation):
go_on = True
for person in generation:
if (reduce(lambda x, r: x + r, person) == len(person)):
go_on = False
return go_on
def Everage(crossover_prob,mutation_prob):
nr = 0
for i in range(nr_pops):
pop = [RandomGen()]
while Check(pop[-1]):
pop.append(NewGen(pop[-1], crossover_prob, mutation_prob))
nr = nr + len(pop)
return (nr+.0)/nr_pops
def __plot__():
pylab.ylabel("Everage number of generation, with all bit on chromosome")
pylab.xlabel("Crossover probability")
for j in range(len(PM)):
x = PC
y = [Everage(i, PM[j]) for i in PC]
pylab.plot(x, y,color = str((j*3+0.0)/10), label = 'Mutation probability='+str(PM[j]), linewidth = 2)
print 'Start program'
print 'End program'
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment