-
Notifications
You must be signed in to change notification settings - Fork 1
/
qlearning.py
executable file
·207 lines (167 loc) · 5.63 KB
/
qlearning.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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#!/usr/bin/python
import random
import sys
import math
def Generate(size, cilj, tip='gusta', raspon=(0, 0)):
"""
size - broj stanja u dijagramu
cilj - index ciljnog cvora, brojeci od nule. Nagrada je automatski postavljena na 100
tip - tip matrice koja se generira.
'gusta' - <default>
stanja mogu biti povezana sa svim stanjima, ali je mala vjerovatnost
da bude povezana sa stanjima koja su daleko
'duga' - stanja mogu biti povezana samo sa nekoliko najblizih stanja
raspon - ureden par cijelih brojeva (a, b)
vrijedonsti matrice a su iz segmenta [a, b]
Funkcija vraca matricu nagrada sljedeceg formata:
- ako stanja x i y nisu spojena, m(x, y) = -inf
- ako jesu spojena, m(x, y) = z iz [a, b]
"""
matrica = []
#popunjavam matricu sa -inf
for i in range(size):
redak = []
for j in range(size):
redak.append(float('-inf'))
matrica.append(redak)
broj_elementa = random.sample(range(1, 3), 1);
if tip == 'gusta':
puni_elementi = random.sample(range(size), broj_elementa[0])
if tip == 'duga':
puni_elementi = random.sample(range(1, 8), broj_elementa[0])
for j in puni_elementi:
matrica[0][j] = random.randint(raspon[0], raspon[1])
matrica[j][0] = matrica[0][j]
for i in range(1, size):
broj_elementa = random.sample(range(1, 3), 1);
if tip == 'gusta':
puni_elementi = random.sample(range(i + 1), min(broj_elementa[0], size - i - 1))
if tip == 'duga':
puni_elementi = random.sample(range(i + 1, min(i+8, size)), min(broj_elementa[0], size - i - 1))
elementi_prije = random.sample(range(max(i-2, 0), i), 1)
for j in elementi_prije:
matrica[i][j] = random.randint(raspon[0], raspon[1])
matrica[j][i] = matrica[i][j]
for j in puni_elementi:
matrica[i][j] = 0
matrica[j][i] = matrica[i][j]
for i in range(size):
matrica[i][i] = float('-inf')
matrica[cilj][cilj] = 100
for i in range(size):
if matrica[i][cilj] != float('-inf'):
matrica[i][cilj] = 100
return matrica
def ToString(matrica):
"""
Sprema matricu u jedan string, redovi su odvojeni znakom '\n', a
elementi reda zarezom
"""
f = ','.join(map(lambda s: str(s), redak)) + '\n'
def AdjacencyMatrix(matrica):
"""
Iz matrice generira matricu susjeda koja se moze koristit za crtanje
grafova softverima kao sto su SAGE ili Mathematica.
"""
dobra_matrica = []
for redak in matrica:
dobri_redak=[]
for broj in redak:
if broj == float('-inf'):
dobri_redak.append(0)
else:
dobri_redak.append(1)
dobra_matrica.append(dobri_redak)
return dobra_matrica
def dobri(red):
ret = []
for i in range(0, len(red)):
if red[i] != float('-inf'):
ret.append(i)
return ret
def Parse(cijeliFajl):
"""
Iz stringa koji sadrzi informacije o dijagramu stanja, koji je spremljen
kao niz vrijednosti odvojenih zarezom, a redovi su odvojeni znakom '\n',
generira se matrica koja se moze korisiti za ucenje.
"""
R = [map(lambda x: float(x), s.split(',')) for s in cijeliFajl.split()]
return R
def Imp(x, n=7):
"""
Improved Matrix Print (tm)
Ispisuje matricu u oku ugodnom formatu.
"""
for red in x:
print '\t'.join(map(lambda s: str(s)[:n], red))
def LearnQ(R, gamma, kraj, bench=False):
"""
Vraca matricu Q
R - matrica nagrada
gamma - koeficient
kraj - ciljni cvor, brojeci od 0
bench - False <default>
True - uz matricu Q vraca i broj izvrsenih epizoda i broj koraka algoritma
kao uredjenu trojku
"""
size = len(R)
# inicijaliziram Q na 0
Q = []
for red in R:
qr = []
for broj in red:
qr.append(0.0)
Q.append(qr)
broj_epizoda = 0
broj_koraka = 0
while abs(Q[kraj][kraj] - 100/(1-gamma)) > 0.00001:
broj_epizoda += 1
s = random.randint(0, size - 1)
while True:
broj_koraka += 1
indeks = dobri(R[s])
if len(indeks) == 0:
break
r = random.choice(indeks)
Q[s][r] = R[s][r] + gamma * max(Q[r])
if s == kraj:
break
s = r
if bench:
return (Q, broj_epizoda, broj_koraka)
return Q
def FindPath(Q, poc, kraj):
"""
Vraca listu cvorova koji tvore najkraci put od cvora poc do cvora kraj, prema
matrici Q.
Q - matrica Q
poc - pocetni cvor, brojeci od 0
kraj - ciljni cvor, brojeci od 0
"""
size = len(Q)
# racuna najbolji put
put = []
put.append(poc)
s = poc
while s != kraj:
s = Q[s].index(max(Q[s]))
put.append(s)
return put
def main():
if len(sys.argv) != 4:
print sys.argv[0], 'dat', 'poc', 'cilj'
print '\tdat - ime datoteke u koju je spremljena ulazna matrica'
print '\tpoc - pocetni cvor, moze biti bilo koji'
print '\tcilj - ciljni cvor, mora biti u skladu s ulaznom matricom'
sys.exit(1)
filename = sys.argv[1]
poc = int(sys.argv[2])
kraj = int(sys.argv[3])
f = open(filename, 'rU')
cijeliFajl = f.read()
R = Parse(cijeliFajl)
Q = LearnQ(R, 0.8, kraj)
P = FindPath(Q, poc, kraj)
print ' -> '.join(map(str, P))
if __name__=='__main__':
main()