Last active
February 8, 2017 06:28
-
-
Save izgzhen/e975f888b7bd2130330a to your computer and use it in GitHub Desktop.
Genetic Algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
can you give me a description about paramMatrix?