1. import copy
2. import random
3.  
4. import matplotlib.pyplot as plt
5. import numpy as np
6.  
7. from City import City
8. from Item import Item
9. from Thief import Thief
10.  
11.  
12. def loader(file_name):
13.     f = open(file_name, "r")
14.     contents = f.readlines()
15.     temp = contents[2].split("\t")
16.     dimentions = int(temp[temp.__len__() - 1])
17.  
18.     temp = contents[3].split("\t")
19.     number_of_items = int(temp[temp.__len__() - 1])
20.  
21.     temp = contents[4].split("\t")
22.     capacity_of_knapsack = int(temp[temp.__len__() - 1])
23.  
24.     temp = contents[5].split("\t")
25.     min_speed = float(temp[temp.__len__() - 1])
26.  
27.     temp = contents[6].split("\t")
28.     max_speed = float(temp[temp.__len__() - 1])
29.  
30.     cities = []
31.  
32.     for i in range(dimentions):
33.         temp = contents[10 + i].split("\t")
34.         city_index = int(temp[0])
35.         cord_x = float(temp[1])
36.         cord_y = float(temp[2])
37.  
38.         city = City(city_index, cord_x, cord_y)
39.         cities.append(city)
40.  
41.     for i in range(number_of_items):
42.         temp = contents[11 + dimentions + i].split("\t")
43.         index = int(temp[0])
44.         reward = int(temp[1])
45.         weight = int(temp[2])
46.         city_index = int(temp[3])
47.  
48.         item = Item(index, reward, weight)
49.  
50.         for city_object in cities:
51.             if city_object.index == city_index:
52.                 city_object.add_item(item)
53.  
54.     return cities, capacity_of_knapsack, min_speed, max_speed
55.  
56.  
57. def generate_first_thieves(capacity_of_knapsack, min_speed, max_speed, quantity_of_thieves):
58.     thieves = []
59.     for i in range(0, quantity_of_thieves):
60.         thief = Thief(capacity_of_knapsack, min_speed, max_speed)
61.         thieves.append(thief)
62.     return thieves
63.  
64.  
65. def calculate_thieves_distance(thieves):
66.     max = -np.inf
67.     min = np.inf
68.     for thief in thieves:
69.  
70.         # cities=[]
71.         # for city in thief.visited_cities:
72.         #     cities.append(city.index)
73.         # print(cities)
74.  
75.         temp_dist = 0
76.         temp_time = 0
77.         thief.temp_weight = 0
78.         thief.items_in_knapsack = []
79.         for i in range(len(thief.visited_cities)):
80.             best_profit = Item(-1, 0, -1)
81.  
82.             for item in thief.visited_cities[i].items:
83.                 # print(thief.visited_cities[i].index, "dupa", item.index)
84.                 if item.profitability > best_profit.profitability:
85.                     best_profit = item
86.             if thief.temp_weight + best_profit.weight <= thief.capasity_of_knapsack and best_profit.index != -1:
87.                 thief.items_in_knapsack.append(best_profit)
88.                 thief.temp_weight += best_profit.weight
89.  
90.             v_temp = thief.max_speed - thief.temp_weight * (
91.                     (thief.max_speed - thief.min_speed) / thief.capasity_of_knapsack)
92.  
93.             if i < len(thief.visited_cities) - 1:
94.                 temp_dist += np.sqrt(pow(thief.visited_cities[i + 1].cord_x - thief.visited_cities[i].cord_x, 2) + pow(
95.                     thief.visited_cities[i + 1].cord_y - thief.visited_cities[i].cord_y, 2))
96.                 temp_time += temp_dist / v_temp
97.             # print(np.sqrt(pow(2,thief.visited_cities[i+1].cord_x-thief.visited_cities[i].cord_x)+pow(2,thief.visited_cities[i+1].cord_x-thief.visited_cities[i].cord_y)))
98.             else:
99.                 temp_dist += np.sqrt(
100.                     pow(thief.visited_cities[0].cord_x - thief.visited_cities[i].cord_x, 2) + pow(
101.                         thief.visited_cities[0].cord_y -
102.                         thief.visited_cities[i].cord_y, 2))
103.                 temp_time += temp_dist / v_temp
104.  
105.         sum = 0
106.         for item in thief.items_in_knapsack:
107.             sum += item.reward
108.         thief.distanse = temp_dist
109.         thief.time = temp_time
110.         thief.fitness = sum - thief.time
111.  
112.         # print(temp_dist)
113.         # print(temp_time)
114.         # print("fitness",thief.fitness)
115.         if thief.fitness > max:
116.             max = thief.fitness
117.         if thief.fitness < min:
118.             min = thief.fitness
119.     return max, min
120.  
121.  
122. def set_thief_truck(thieves, cities):
123.     for thiev in thieves:
124.         for city in cities:
125.             thiev.visited_cities.append(city)
126.         random.shuffle(thiev.visited_cities)
127.  
128.  
129. def mutation(thieves, pm):
130.     new_pop = []
131.     for thief in thieves:
132.         rand = np.random.rand()
133.  
134.         if rand < pm:
135.             rand = int(np.random.rand() * len(thief.visited_cities) - 1)
136.             temp = copy.deepcopy(thief)
137.             temp.visited_cities[rand], temp.visited_cities[len(thief.visited_cities) - rand - 1] = \
138.                 thief.visited_cities[
139.                     len(
140.                         thief.visited_cities) - rand - 1], \
141.                 thief.visited_cities[
142.                     rand]
143.  
144.             new_pop.append(temp)
145.         else:
146.             new_pop.append(thief)
147.  
148.     return new_pop
149.  
150.  
151. def repair(thief, point, list):
152.     list2 = []
153.     for i in range(len(thief.visited_cities)):
154.         for city in list:
155.             if thief.visited_cities[i].index == city.index:
156.                 list.remove(city)
157.     for i in range(len(thief.visited_cities)):
158.         if i < point:
159.             list2.append(thief.visited_cities[i])
160.         else:
161.             for city in list2:
162.                 if city.index == thief.visited_cities[i].index:
163.                     new_city = list[0]
164.                     thief.visited_cities[i] = new_city
165.                     list.remove(list[0])
166.  
167.     return thief
168.  
169.  
170. def crossover(thief1, thief2):
171.     point = int(len(thief1.visited_cities) * (np.random.rand()))
172.     list = []
173.     for city in thief1.visited_cities:
174.         list.append(city)
175.  
176.     list2 = list.copy()
177.     for i in range(len(thief1.visited_cities)):
178.         if i >= point:
179.             temp = thief1.visited_cities[i]
180.             thief1.visited_cities[i] = thief2.visited_cities[i]
181.             thief2.visited_cities[i] = temp
182.     repair(thief1, point, list)
183.     repair(thief2, point, list2)
184.     cities = []
185.  
186.     return thief1, thief2
187.  
188.  
189. def calculate_data(thieves, pop):
190.     max, min = calculate_thieves_distance(thieves)
191.     data = []
192.     data.append(pop)
193.     data.append(max)
194.     avarage = 0
195.     for thief in thieves:
196.         avarage += thief.fitness
197.         # cities=[]
198.         # for city in thief.visited_cities:
199.         #     cities.append(city.index)
200.         # print(cities)
201.     avarage = avarage / pop_size
202.     data.append(avarage)
203.     data.append(min)
204.     return data
205.  
206.  
207. def compare_thieves(temps):
208.     best = temps[0]
209.     for thief in temps:
210.         if thief.fitness > best.fitness:
211.             best = thief
212.     return best
213.  
214.  
215. def select_population(thieves, tour_size, pop_size):
216.     # data=calculate_data(thieves,pop_size)
217.     # print("prze",data[2])
218.  
219.     new_population = []
220.     for i in range(pop_size):
221.         temps = []
222.         for j in range(tour_size):
223.             temps.append(thieves[int(np.random.rand() * pop_size)])
224.         best = compare_thieves(temps)
225.         new_population.append(best)
226.  
227.     # data = calculate_data(new_population, pop_size)
228.     # print("po",data[2])
229.  
230.     return new_population
231.  
232.  
233. def crossover_population(thieves, pop_size, px):
234.     new_pop = []
235.     while thieves.__len__() > 0:
236.         rand = random.randrange(0, thieves.__len__())
237.         new_pop.append(thieves[rand])
238.         del thieves[rand]
239.     numOfThieves = new_pop.__len__()
240.     numbers = []
241.     for i in range(numOfThieves):
242.         numbers.append(i)
243.  
244.     while numbers.__len__() > 0:
245.         rand1 = numbers.__len__() - 1
246.         rand2 = numbers.__len__() - 2
247.         thief_1 = new_pop[rand1]
248.         thief_2 = new_pop[rand2]
249.         if np.random.rand() < px:
250.             temp1, temp2 = crossover(thief_1, thief_2)
251.  
252.             new_pop[rand1] = temp1
253.             new_pop[rand2] = temp2
254.         del numbers[rand1]
255.         del numbers[rand2]
256.     return new_pop
257.  
258.  
259. def check_if_correct(thieves):
260.     for thief in thieves:
261.         cities = []
262.         for city in cities:
263.             cities.append(city.index)
264.     numbers = []
265.     for i in range(thieves.__len__()):
266.         numbers.append(i)
267.  
268.     for i in range(cities.__len__()):
269.         for j in range(numbers.__len__()):
270.             if i == j:
271.                 del numbers[j]
272.  
273.     return True
274.  
275.  
276. def generate_generations(thieves, pop_size):
277.     Px = 0.7
278.     pm = 0.01
279.     gen = 100
280.     tour_size = 5
281.  
282.     iterator = 0
283.     while iterator < gen:
284.         best_average = -np.inf
285.         print("iterator", iterator)
286.         iterator += 1
287.         thieves = select_population(thieves, tour_size, pop_size)
288.         thieves = mutation(thieves, pm)
289.         thieves = crossover_population(thieves, pop_size, Px)
290.  
291.         new_data = calculate_data(thieves, iterator + 1)
292.         all_data.append(new_data)
293.     print(all_data)
294.     return all_data
295.  
296.  
297. pop_size = 100
298. loader = loader("data/hard_0.ttp")
299. cities = loader[0]
300. thieves = generate_first_thieves(loader[1], loader[2], loader[3], pop_size)
301. set_thief_truck(thieves, cities)
302. max, min = calculate_thieves_distance(thieves)
303. data = []
304. data.append(0)
305. data.append(max)
306. avarage = 0
307. for thief in thieves:
308.     avarage += thief.fitness
309. avarage = avarage / pop_size
310. data.append(avarage)
311. data.append(min)
312. all_data = []
313. all_data.append(data)
314. new_table = generate_generations(thieves, pop_size)
315. all_data.append(new_table)
316. temp_average = []
317. empty_time = []
318. max_pop = []
319. min_pop = []
320. for i in range(len(all_data) - 1):
321.     temp_average.append(all_data[i][2])
322.     empty_time.append(i)
323.     max_pop.append(all_data[i][1])
324.     min_pop.append(all_data[i][3])
325.  
326. plt.plot(empty_time, temp_average)
327. plt.plot(empty_time, max_pop)
328. plt.plot(empty_time, min_pop)
329. plt.show()
330.