genetic algorithm python
from random import randint from random import random def newChar(): r = randint(63,122) if r == 64: r = ord(' ') if r == 63: r = ord('.') return chr(r) def mapit(i,m,M, a = 0, b = 1): return (b - a)*(i - m)/(M-m) class DNA: def __init__(self, num): self.num = num self.genes = [newChar() for i in range(num)] self.fitnes = 0 def getPhrase(self): s = '' return s.join(self.genes) def calcFitness(self, target): scor = 0 for idx, gen in enumerate(self.genes): if gen == target[idx]: scor += 1 self.score = scor/len(target) return scor/len(target) def Reproduction(self, partner): child = DNA(self.num) midpoint = randint(0, len(self.genes)) for i in range(self.num): if i < midpoint: child.genes[i] = self.genes[i] else: child.genes[i] = partner.genes[i] return child def mutate(self, mutRate): for i in range(self.num): r = random() if r < mutRate: self.genes[i] = newChar() class Papulation: def __init__(self, target, pmax, mutationRate, max_mat_pool = 1e5): self.target = target self.pmax = pmax self.mutationRate = mutationRate self.papulation = [] for i in range(pmax): self.papulation.append(DNA(len(target))) self.matinPool = [] self.bestfit = None self.max_mat_pool = max_mat_pool def calcFitness(self): for i in self.papulation: i.calcFitness(self.target) def naturalSelaction(self): maxfit = 0 for i in self.papulation: if i.score > maxfit: maxfit = i.score self.bestfit = i for i in self.papulation: n = int(mapit(i.score, 0, maxfit)*100) for j in range(n): self.matinPool.append(i) def died(self): diff = int(len(self.matinPool) - self.max_mat_pool) if diff > 0: del self.matinPool[0:diff] def newGenration(self): for i in range(self.pmax): partnarA = self.matinPool[randint(0,len(self.matinPool) -1)] partnarB = self.matinPool[randint(0,len(self.matinPool) - 1)] child = partnarA.Reproduction(partnarB) child.mutate(self.mutationRate) self.papulation[i] = child target = '''Hello world''' pmax = 1000 mutationRate = 0.01 genrations = 100 k = 0 p = Papulation(target,pmax, mutationRate) for i in range(genrations): p.calcFitness() p.naturalSelaction() p.newGenration() if p.bestfit.getPhrase() == target: k+=1 # print('**gen: ', i, p.bestfit.getPhrase()) print('gin: ', i, p.bestfit.getPhrase()) p.died()
