Yesterday I started exploring the genetic algorithms, and when I ended up with some basic theory, I tried to write simple GA on Python, which solves the Diophantine equation. I'm new to Python and GAs, so please, don't judge my code strictly.
Problem
I can't get any result due to premature convergence (there is some no-return point (n-population), population[n] == population[n+i], where i is an integer. even the random mutation element cant change this, the generation is degrading very quickly)
GA is using the crossover to breed and weighted the choice of parents.
Q1: Are 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 really needed a 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 don't 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 the Gray Code, not an integer.