-
Notifications
You must be signed in to change notification settings - Fork 1
/
DNA.py
138 lines (125 loc) · 4.3 KB
/
DNA.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
from math import floor
from argparse import Namespace
import json
import numpy as np
VOWELS = 'aeiou'
class DNA:
def __init__(self, data):
self.__data = data[:]
self.__score = 0
@classmethod
def Random(cls, length, hints):
data = []
values = [x for x in range(length) if x not in hints.values()]
values = np.random.permutation(values).tolist()
for i in range(length):
if i not in hints:
data.append(values.pop(0))
else:
data.append(hints[i])
return cls(data)
def __ToJson(self):
return json.dumps(self, default=lambda o: o.__dict__, sort_keys=True, indent=4)
def WriteJson(self, path):
with open(path, 'w') as outfile:
json.dump(self.__ToJson(), outfile)
@staticmethod
def json2obj(data):
return json.loads(data, object_hook=lambda d: Namespace(**d))
@staticmethod
def ReadFromJson(path):
with open(path) as data_file:
param = DNA.json2obj(json.load(data_file))
return DNA(param.__data)
def __str__(self):
return ' '.join(str(x) for x in self.__data)
def CrossOver(self, other, mutationRate, hints):
n = len(self.__data)
#data = np.random.permutation(range(n)).tolist()
''''
if other.GetScore() > self.__score:
for i in range(n):
data[i] = other.__data[i]
else:
for i in range(n):
data[i] = self.__data[i]
'''
data = self.__data[:]
if (self.__score + other.GetScore()) > 0:
fromFirst = self.__score/ (self.__score + other.GetScore())
else:
fromFirst = 0.5
visited = [False] * n
pos = {}
for i in range(n):
if data[i] in pos:
print('Not permutation !! : ', data[i])
print(data)
exit(-1)
else:
pos[data[i]] = i
perm = np.random.permutation(range(n))
elements = n*(1-fromFirst)
cycles = []
for i in perm:
if (visited[i] == False):
j = i
cycle = []
while True:
visited[j] = True
cycle.append(j)
j = pos[other.__data[j]]
if i == j:
break
if (elements > n):
print('Infinite loop')
exit(-1)
if len(cycle) > 1:
cycles.append(cycle)
cycles.sort(key = lambda s: len(s))
for cycle in cycles:
for i in cycle:
data[i] = other.__data[i]
elements -= len(cycle)
if elements <= 0:
break
child = DNA(data)
child.Mutate(mutationRate, hints)
return child
def Mutate(self, mutationRate, hints):
n = len(self.__data)
for i in range(n):
if (np.random.rand() < mutationRate and (i not in hints)):
while True:
j = floor(np.random.rand() * n)
if j not in hints:
break
self.__data[i], self.__data[j] = self.__data[j], self.__data[i]
def decode(self, encoded):
decoded = []
for word in encoded:
newWord = ''
for value in word:
newWord = newWord + chr(self.__data[ord(value) - ord('a')] + ord('a'))
decoded.append(newWord)
return decoded
def GetScore(self):
return self.__score
def CalcFitness(self, encoded, wordsDict, bad, weights):
score = 0
totalLength = sum(len(word) for word in encoded)
for i, word in enumerate(self.decode(encoded)):
exist = False
for vowel in VOWELS:
if vowel in word:
exist = True
break
if exist == True:
if word in wordsDict:
score += (wordsDict[word]/len(word))*(len(word)/totalLength)*weights[i]*100
else:
score -= bad*(len(word)/totalLength)*weights[i]*100
else:
score = 0
break
self.__score = pow(max(0, score), 1)