Yesterday i started exploring the genetic algorithms, and when i ended up with some basic theory, i tried to write simple GA on Python, that solves Diophantine equation. I'm new to Python and GAs, so please, don't judge my code strictly.
Problem
I cant get any result due to premature convergence (there is some no-return point (n-population), population[n] == population[n+i], where i is any integer. even the random mutatuion element cant change this, the generation is degradating very quickly)
GA is using crossover to breed, and weighted choice of parents.
- Q1: Is there any design mistakes in my code (below)?
- Q1.2: Do i need to add elitism?
- Q1.3: Do i need to change breed logic?
- Q2: Is there realy needed deep copy?
Code:
# -*- coding: utf-8 -*-
from random import randint
from copy import deepcopy
from math import floor
import random
class Organism:
#initiate
def __init__(self, alleles, fitness, likelihood):
self.alleles = alleles
self.fitness = fitness
self.likelihood = likelihood
self.result = 0
def __unicode__(self):
return '%s [%s - %s]' % (self.alleles, self.fitness, self.likelihood)
class CDiophantine:
def __init__(self, coefficients, result):
self.coefficients = coefficients
self.result = result
maxPopulation = 40
organisms = []
def GetGene (self,i):
return self.organisms[i]
def OrganismFitness (self,gene):
gene.result = 0
for i in range (0, len(self.coefficients)):
gene.result += self.coefficients[i]*gene.alleles[i]
gene.fitness = abs(gene.result - self.result)
return gene.fitness
def Fitness (self):
for organism in self.organisms:
organism.fitness = self.OrganismFitness(organism)
if organism.fitness == 0:
return organism
return None
def MultiplyFitness (self):
coefficientSum = 0
for organism in self.organisms:
coefficientSum += 1/float(organism.fitness)
return coefficientSum
def GenerateLikelihoods (self):
last = 0
multiplyFitness = self.MultiplyFitness()
for organism in self.organisms:
last = ((1/float(organism.fitness)/multiplyFitness)*100)
#print '1/%s/%s*100 - %s' % (organism.fitness, multiplyFitness, last)
organism.likelihood = last
def Breed (self, parentOne, parentTwo):
crossover = randint (1,len(self.coefficients)-1)
child = deepcopy(parentOne)
initial = 0
final = len(parentOne.alleles) - 1
if randint (1,100) < 50:
father = parentOne
mother = parentTwo
else:
father = parentTwo
mother = parentOne
child.alleles = mother.alleles[:crossover] + father.alleles[crossover:]
if randint (1,100) < 5:
for i in range(initial,final):
child.alleles[i] = randint (0,self.result)
return child
def CreateNewOrganisms (self):
#generating new population
tempPopulation = []
for _ in self.organisms:
iterations = 0
father = deepcopy(self.organisms[0])
mother = deepcopy(self.organisms[1])
while father.alleles == mother.alleles:
father = self.WeightedChoice()
mother = self.WeightedChoice()
iterations+=1
if iterations > 35:
break
kid = self.Breed(father,mother)
tempPopulation.append(kid)
self.organisms = tempPopulation
def WeightedChoice (self):
list = []
for organism in self.organisms:
list.append((organism.likelihood,organism))
list = sorted((random.random() * x[0], x[1]) for x in list)
return list[-1][1]
def AverageFitness (self):
sum = 0
for organism in self.organisms:
sum += organism.fitness
return float(sum)/len(self.organisms)
def AverageLikelihoods (self):
sum = 0
for organism in self.organisms:
sum += organism.likelihood
return sum/len(self.organisms)
def Solve (self):
solution = None
for i in range(0,self.maxPopulation):
alleles = []
#
for j in range(0, len(self.coefficients)):
alleles.append(randint(0, self.result))
self.organisms.append(Organism(alleles,0,0))
solution = self.Fitness()
if solution:
return solution.alleles
iterations = 0
while not solution and iterations <3000:
self.GenerateLikelihoods()
self.CreateNewOrganisms()
solution = self.Fitness()
if solution:
print 'SOLUTION FOUND IN %s ITERATIONS' % iterations
return solution.alleles
iterations += 1
return -1
if __name__ == "__main__":
diophantine = CDiophantine ([1,2,3,4],30)
#cProfile.run('diophantine.Solve()')
print diophantine.Solve()
I tried to change breed and weighted random choice logic but with no results. This GA supposed to be work, i dont know, what's wrong. I know that there are some GA libraries on Python, i'm trying to understand them at the moment - it seems that they are quite complex to me. Sorry for mistakes, english is not my native language. Thank you for your understanding.
NECROUPDATE: Store chromosomes in Gray Code, not in integer.