gistfile1.py

# 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
			break	
	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.figure(1)
	pylab.grid(True)
	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)
	pylab.legend()
	pylab.show()

print 'Start program'
__plot__()
print 'End program'