Genetic Algorithm

ga.py

# Genetics Algorithm's Implementation in Python
# How did this algorithm work?
# init -> iterate until certain condition -> output every generation
# iterate: select parents -> crossover -> mutation -> a new generation
#
# Core: How to encode your optimization problem into a string, i.e. chromosome?
#	    Which selection method would your apply? Tournament selection or roulette selection?

# How to realize the child breeding? Every pair of parent will breed a pair of children, which are the outcome of crossover effect.

# Use Object-Oriented Programming which is easy in Python

# The optimization I try to solve is to find solutions for equations, so the solution is composed of four elements' values as integers
# I will try to code the integers in order as a whole, i.e. the chromosome of individual
# The solution integer will be restricted in range 0 to 99: so the chromosome will be like 01039256, means x1 = 1, x2 = 3 ...

# Author: Zhen Zhang (izgzhen@gmail.com)

import random

class GA(object):
	def __init__(self, instance):
		self.instance = instance

	def run(self):
		population = self.instance.initializePopulation();
		while 1:
			fitness_population = [ (self.instance.getFitness(individual), individual) for individual in population ]
			if self.instance.showAndCheck(fitness_population):
				break;
			population = self.changePopulation(fitness_population);

	def changePopulation(self, fitness_population):
		parentsGenerator = self.instance.selectParents(fitness_population)
		allChildren = []
		while len(allChildren) < len(fitness_population):
			parents = next(parentsGenerator) # Next yielded pair of parents

			if random.random() > self.instance.getCrossThreshold():
				children = self.instance.crossover(parents) # Assigned the crossovered chromosome to children
			else:
				children = parents

			for child in children:
				if random.random() > self.instance.getMutationThreshold():
				 	allChildren.append(self.instance.mutate(child))
				else:
				 	allChildren.append(child)

		return allChildren[:len(fitness_population)] # May exceed

class rules(object):
	def __init__(self, gradeFunction, maxLoopsNum, error, populationSize, crossThreshold, mutationThreshold):
		self.counter = 0
		self.maxLoopsNum = maxLoopsNum
		self.error = error
		self.populationSize = populationSize
		self.crossThreshold = crossThreshold
		self.mutationThreshold = mutationThreshold
		self.gradeFunction = gradeFunction

	def getMutationThreshold(self):
		return self.mutationThreshold

	def getCrossThreshold(self):
		return self.crossThreshold

	def initializePopulation(self):
		population = [];
		for i in range(self.populationSize):
			population.append(str(random.randint(0, 99999999)))
		return population

	def decode(self, individual):
		solutions = []
		individual = int(individual)
		for i in range(4):
			solutions.append(individual % 100)
			individual /= 100
		return solutions

	def getFitness(self, individual):
		# Decode the individual (chromosome) and calculate the fitness
		return - abs(self.gradeFunction(self.decode(individual)))

	def showAndCheck(self, fitness_population):
		self.counter += 1
		best = list(sorted(fitness_population))[-1] # Last Individual
		print "Generation", self.counter, "Best solution:", self.decode(best[1]), "with fitness:", best[0]

		return (self.counter > self.maxLoopsNum) or (best[0] >= self.error)

	def selectParents(self, fitness_population):
		# Construct a iterator here
		# Use Tournament Selection
		while 1:
			parent1 = self.tournament(fitness_population)
			parent2 = self.tournament(fitness_population)
			yield (parent1, parent2)

	def crossover(self, parents):
		parent1, parent2 = parents
		
		start = random.randint(1, len(parent1) - 2)
		end = random.randint(1, len(parent1) - 2)

		if start > end:
			start, end = end, start

		child1 = parent1[:start] + parent2[start:end] + parent1[end:]
		child2 = parent2[:start] + parent1[start:end] + parent2[end:]

		return (child1, child2)

	def mutate(self, child):
		pos = random.randint(0, len(child) - 1)
		child = list(child)
		child[pos] = chr(random.randint(ord('0'), ord('9')))

		return ''.join(child)

	def tournament(self, fitness_population):
		fit1, ch1 = fitness_population[random.randint(0, len(fitness_population) - 1)]
		fit2, ch2 = fitness_population[random.randint(0, len(fitness_population) - 1)]

		return ch1 if fit1 > fit2 else ch2 # This is far more elegant then C language style

def calVector(paramVector):
	return lambda xVector: abs(sum(param * x for param, x in zip(paramVector, xVector)))

def calMatrix(paramMatrix):
	return lambda xVector: sum(calVector(paramVector)(xVector) for paramVector in paramMatrix)

paramMatrix = [ [1, 1, -2, 2], 
	         [2, 2, -3, 4],
		 [3, -3, 4, -2],
		 [-1, 2, 3, 1] ]

GA(rules(calMatrix(paramMatrix), 100, 0,  200, 0.5, 0.2)).run() # gradeFunction, maxLoopsNum, error, populationSize, crossThreshold, mutationThreshold

can you give me a description about paramMatrix?