-
Notifications
You must be signed in to change notification settings - Fork 0
/
tsp_net.py
260 lines (232 loc) · 9.09 KB
/
tsp_net.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
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
"""
TSP using Hopfield network
Note that the state is a 3x3 matrix where each row represents a city and each
column represents a step in the trip.
we wil use i and j to iterate over the rows and X and Y to iterate over the columns
Each synapse is represented by a 4D matrix J[X][i][Y][j]
where X and Y are the self.road_map (this side ->) and i and j are the steps in the trip (downwards)
valid state is a state representing a valid path through the self.road_map
I II III
2 to X
1 to Y
3 to Z
"""
import numpy as np
from hopfield import Hopfield
from tsp_map import Map
from tsp_energy import TSPEnergy
from tsp_weights import A, B, C, D
def Kronecker_delta(i, j):
return 1 if i == j else 0
class TSPNet(Hopfield):
def __init__(self, road_map: Map):
self.road_map = Map()
print(self.road_map.city_set)
self.N = len(self.road_map.city_set)
self.days = [str(i) for i in range(1, self.N + 1)]
self.s = self.get_random_state()
self.J = self.get_synaptic_matrix_with_constraints()
self.neurons = self.s.flatten()
def get_random_state(self):
return np.random.choice([0, 1], size=(self.N, self.N))
def get_route(self, s=None):
if s is None:
s = self.s
route = []
for i, day in enumerate(self.days):
for X, city in enumerate(self.road_map):
if s[X][i] == 1:
route.append(city)
return route
def is_stable(self, s=None):
"""
for the TSP, a state is stable if it represents a valid path through the self.road_map
"""
# check if the state is a valid path through the self.road_map
# meaning each row has only one 1 - not more and not less
if s is None:
s = self.s
for X in range(self.N):
if sum(s[X]) != 1:
return False
# check if each column has only one 1 - not more and not less
for i in range(self.N):
if sum(s[:, i]) != 1:
return False
return True
def getLocalField(self, X, i=None, s=None, J=None):
"""
Returns the local field of neuron i.
hᵢ = Σjᵢⱼ•sⱼ(t)
"""
local_field = 0
if J is None:
J = self.J
if s is None:
s = self.s
# change to x and y from X based on colls
if i is None:
X, i = divmod(X - 1, 3)
for Y in range(2):
for j in range(2):
local_field += J[X][i][Y][j] * s[Y][j]
return local_field
def get_energy(self, s=None, map=None) -> float:
energy = 0
if s is None:
s = self.s
else:
# change to suitable matrix if s is a 1D array
print(s)
s = s.reshape((self.N, self.N))
with TSPEnergy(self.road_map) as tsp_energy:
energy = tsp_energy.get_energy_with_constraints(s)
return energy
def reset(self):
# synapses don't change
self.s = np.random.choice([0, 1], size=(self.N, self.N))
self.neurons = self.s.flatten()
def next_state(self, s=None, map=None):
"""
Calculate the next state of the network
"""
self.road_map.take_snapshot(self.get_route(self.s))
iterations = 5 * self.N * self.N * self.N
history = []
for _ in range(iterations):
X, i = np.random.randint(self.N, size=2)
before = self.s[X][i]
self.update_state(X, i, self.s)
print(
f"X={X}, i={i}, before={before} => after={self.s[X][i]}, energy={self.get_energy(self.s)}"
)
if self.get_energy(s) < 1:
break
history.append(self.get_energy(self.s))
if len(history) > 2 and history[-1] == history[-2]:
break
self.neurons = self.s.flatten()
self.road_map.take_snapshot(self.get_route(self.s))
return self.s
def next_state_all(self, s=None, map=None):
"""
Calculate the next state of the network
"""
if s is None:
s = self.s
new_s = s.copy()
self.print_synaptic_matrix()
for X, city in enumerate(self.road_map):
for i, day in enumerate(self.days):
field = 0
for Y, city2 in enumerate(self.road_map.city_set.copy()):
for j, day2 in enumerate(self.days):
field += self.J[X][i][Y][j] * s[Y][j]
print(f"{self.J[X][i][Y][j]}*{s[Y][j]}", end=" ")
print()
print(f" bias = {self.J[X][i][i][self.N]}*{s[X][i]}")
print(
f"(J{city}{day},bias + {field}) = {field + self.J[X][i][i][self.N]}\n"
)
new_s[X][i] = 1 if (self.J[X][i][i][self.N] + field > 0) else 0
self.neurons = new_s.flatten()
self.s = new_s
print(f"END: {self.get_energy_with_constraints_and_weights(new_s)}")
return s
def get_synaptic_matrix_with_constraints(self) -> np.ndarray:
"""
Calculate the synaptic matrix based on the custom Energy function
with constraints designed for the TSP.
"""
J = np.zeros((self.N, self.N, self.N, self.N + 1)) # +1 for the bias
map_copy = self.road_map.city_set.copy()
for X, city in enumerate(self.road_map):
for i, day in enumerate(self.days):
for Y, city2 in enumerate(map_copy):
for j, day2 in enumerate(self.days):
print(f"J{city}{day},{city2}{day2}")
J[X][i][Y][j] = (
-A * Kronecker_delta(X, Y) *
(1 - Kronecker_delta(i, j))
- B * Kronecker_delta(i, j) *
(1 - Kronecker_delta(X, Y))
- C
- D
* self.road_map[city][city2]
* (Kronecker_delta(i - 1, j) + Kronecker_delta(i + 1, j))
)
print(f"J{city}{day},{city2}{day2}: {J[X][i][Y][j]}")
# Add the bias synapse to every neuron in the next layer
J[X][i][Y][self.N] = 2 * self.N * C
# flatten the synaptic matrix for the gui
# Suppose 'weights' is your 4D numpy array
self.weights = np.random.rand(100, 100)
for X in range(self.N):
for i in range(self.N):
for Y in range(self.N):
for j in range(self.N):
self.weights[X * self.N + i][Y *
self.N + j] = J[X][i][Y][j]
# # add bias
# self.weights[X * self.N + i][self.N * self.N] = J[X][i][i][self.N]
print(f"weigh shape: {self.weights.shape}")
self.print_synaptic_matrix(J)
return J
def get_energy_with_constraints_and_weights(self, s=None, map=None) -> float:
"""
This method is used to test weather the energy function is implemented correctly
in the synaptic matrix
"""
energy = 0
if s is None:
s = self.s
else:
# change to 3x3 matrix if s is a 1D array
s = s.reshape((self.N, self.N))
print(s)
with TSPEnergy(self.road_map) as tsp_energy:
energy = tsp_energy.get_energy_with_constraints(s)
return energy
def print_synaptic_matrix(self, J=None):
"""
Print the synaptic matrix
"""
if J is None:
J = self.J
for X, city in enumerate(self.road_map):
for i, day in enumerate(self.days):
for Y, city2 in enumerate(self.road_map.city_set.copy()):
for j, day2 in enumerate(self.days):
print(
f"J{city}{day},{city2}{day2}: {J[X][i][Y][j]:4}", end=" ")
# print bias
print(f"J{city}{day},bias: {J[X][i][i][self.N]}")
print("")
def get_energy_using_weight(self, s, map=None, only_dot_product=False) -> float:
"""
Calculate the energy of a state
"""
energy = 0
J = self.J
for X in range(self.N):
for i in range(self.N):
for Y in range(self.N):
for j in range(self.N):
energy += J[X][i][Y][j] * s[X][i] * s[Y][j]
if only_dot_product:
return energy
return -energy * 0.5
def update_state(self, X, i, s=None, J=None) -> int:
"""
Update the state s by flipping the value of the neuron (i, j)
"""
field = 0
if J is None:
J = self.J
if s is None:
s = self.s
for Y in range(self.N):
for j in range(self.N):
field += J[X][i][Y][j] * s[Y][j]
s[X][i] = 1 if field + J[X][i][i][self.N] > 0 else 0
return s[X][i]