Back

Explore Courses Blog Tutorials Interview Questions
0 votes
2 views
in AI and Deep Learning by (50.2k points)

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.

1 Answer

0 votes
by (108k points)

There is a slight logic error in your code that is the parentTwo is slightly more likely to be the father than the mother. Even the odds would be randint (1,100) <= 50, not randint (1,100) < 50. Won't be what's causing the issue here.

Answering to your questions:

  • Your population size is really small. 40 are few for most problems. That will cause it to converge quickly.

  • Elitism will cause your population to converge faster, not slower.

  • Your WeightedChoice function appears to be rather inefficient if I'm reading it correctly. If you can improve on that, it should speed up the processing so you can increase the population size (and, seeing as I'm figuring your algorithm there is probably at least O(n^2), that'll be really important).

You can refer the following link for the code in python:

https://github.com/chovanecm/python-genetic-algorithm

Browse Categories

...