genetic algorithm python

1
2from random import randint
3from random import random
4
5def newChar():
6    r = randint(63,122)
7    if r == 64:
8        r = ord(' ')
9    if r == 63:
10        r = ord('.')
11        
12    return chr(r)
13def mapit(i,m,M, a = 0, b = 1):
14    return (b - a)*(i - m)/(M-m)
15
16  
17  
18  class DNA:
19    def __init__(self, num):
20        self.num = num
21        self.genes = [newChar() for i in range(num)]
22        self.fitnes = 0
23    
24    def getPhrase(self):
25        s = ''
26        return s.join(self.genes)
27    
28    def calcFitness(self, target):
29        scor = 0
30        for idx, gen in enumerate(self.genes):
31            if gen == target[idx]:
32                scor += 1
33        self.score = scor/len(target)
34        return scor/len(target)
35    
36    def Reproduction(self, partner):
37        child = DNA(self.num)
38        midpoint = randint(0, len(self.genes))
39        for i in range(self.num):
40            if i < midpoint: 
41                child.genes[i] = self.genes[i]
42            else:
43                child.genes[i] = partner.genes[i]
44        return child
45    
46    def mutate(self, mutRate):
47        for i in range(self.num):
48            r = random()
49            if r < mutRate:
50                self.genes[i] = newChar()
51            
52        
53            
54        
55
56
57
58
59class Papulation:
60    def __init__(self, target, pmax, mutationRate, max_mat_pool = 1e5):
61        self.target = target
62        self.pmax = pmax
63        self.mutationRate = mutationRate
64        self.papulation = []
65        for i in range(pmax):
66            self.papulation.append(DNA(len(target)))
67        self.matinPool = []
68        self.bestfit = None
69        self.max_mat_pool = max_mat_pool
70        
71    def calcFitness(self):
72        for i in self.papulation:
73            i.calcFitness(self.target)
74    def naturalSelaction(self):
75        maxfit = 0
76        for i in self.papulation:
77            if i.score > maxfit:
78                maxfit = i.score
79                self.bestfit = i
80                
81        for i in self.papulation:
82            n  = int(mapit(i.score, 0, maxfit)*100)
83            for j in range(n):
84                self.matinPool.append(i)
85                
86    def died(self):
87        diff = int(len(self.matinPool) - self.max_mat_pool)
88        if diff > 0:
89            del self.matinPool[0:diff]
90                
91                
92    def newGenration(self):
93        for i in range(self.pmax):
94            partnarA = self.matinPool[randint(0,len(self.matinPool) -1)]
95            partnarB = self.matinPool[randint(0,len(self.matinPool) - 1)]
96            child = partnarA.Reproduction(partnarB)
97            child.mutate(self.mutationRate)
98            self.papulation[i] = child
99
100target = '''Hello world'''
101
102pmax = 1000
103mutationRate = 0.01
104genrations = 100
105
106k = 0
107p = Papulation(target,pmax, mutationRate)
108
109for i in range(genrations):
110    p.calcFitness()
111    p.naturalSelaction()
112    p.newGenration()
113    if p.bestfit.getPhrase() == target:
114        k+=1
115#         print('**gen: ', i, p.bestfit.getPhrase())
116    print('gin: ', i,  p.bestfit.getPhrase())
117    p.died()
118