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
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422# -- File: genetic_algorithm.py --
# Author: vzbf32
# Creation Date: 2017-12-19 20:04
# Purpose: This script performs a genetic algorithm on city data to find optimum tours.
import random
import read_tour
from time import time
import sys
class TourManager:
# Holds our cities 1,...,n
destination_cities = []
# Holds our city distances in a 2D array
cities2d = [[]]
def add_city(self, city: int):
"""
Adds a destination city.
:param city:
:return:
"""
self.destination_cities.append(city)
def get_city(self, index: int):
"""
Returns a city.
:param index:
:return:
"""
return self.destination_cities[index]
def number_of_cities(self):
return len(self.destination_cities)
def set_cities2d(self, list2d):
TourManager.cities2d = list2d
def reset(self):
TourManager.cities2d = [[]]
class Tour:
def __init__(self, tour=None):
"""
Initialises our tour.
:param tour:
"""
# Holds our list of cities.
self.tour = []
# Cache
self.fitness = 0
self.distance = 0
if tour is not None:
self.tour = tour
else:
# Construct a blank tour
tm = TourManager()
for i in range(tm.number_of_cities()):
self.tour.append(None)
def generate_individual(self):
"""
Creates a random individual.
:return:
"""
# Loop through all our destination cities and add them to our tour
tm = TourManager()
for city_index in range(tm.number_of_cities()):
self.set_city(city_index, tm.get_city(city_index))
# Randomly reorder the tour
random.shuffle(self.tour)
def get_city(self, tour_position):
"""
Gets a city from the tour
:param tour_position:
:return:
"""
return self.tour[tour_position]
def set_city(self, tour_position, city):
"""
Sets a city in a certain position within a tour.
:param tour_position:
:param city:
:return:
"""
self.tour[tour_position] = city
# If the tour's been altered, we need to reset the fitness and distance
self.fitness = 0
self.distance = 0
def get_fitness(self):
"""
Gets the tour's fitness
:return:
"""
if self.fitness == 0:
self.fitness = 1.0 / self.get_distance()
return self.fitness
def get_distance(self):
"""
Gets the total distance of the tour.
:return:
"""
if self.distance == 0:
tour_distance = 0
# Loop through our tour's cities
for city_index in range(self.tour_size()):
tm = TourManager()
tour_distance += tm.cities2d[self.get_city(city_index)][self.get_city((city_index+1)%self.tour_size())]
self.distance = tour_distance
return self.distance
def tour_size(self):
"""
Get number of cities on our tour.
:return:
"""
# print(len(self.tour))
return len(self.tour)
def contains_city(self, city):
"""
Check if the tour contains a city.
:param city:
:return:
"""
return city in self.tour
def __str__(self):
return str(self.tour)
def get_raw_tour(self):
return self.tour
class Population:
def __init__(self, population_size, initialise):
"""
Construct a population.
:param population_size:
:param initialise:
"""
# Holds population of tours
self.tours = [None for i in range(population_size)]
# If we need to initialise a population of tours, do so
if initialise:
# Loop and create individuals
for i in range(self.population_size()):
new_tour = Tour()
new_tour.generate_individual()
self.save_tour(i, new_tour)
def save_tour(self, index, tour):
"""
Saves a tour.
:param index:
:param tour:
:return:
"""
self.tours[index] = tour
def get_tour(self, index):
"""
Gets a tour.
:param index:
:return:
"""
return self.tours[index]
def get_fittest(self):
"""
Gets the best tour in the population.
:return:
"""
fittest = self.tours[0]
# Loop through individuals to find the fittest
for i in range(1, self.population_size()):
if fittest.get_fitness() <= self.get_tour(i).get_fitness():
fittest = self.get_tour(i)
return fittest
def population_size(self):
"""
Returns population size.
:return:
"""
return len(self.tours)
class GA:
# GA Parameters
MUTATION_RATE = 0.035
TOURNAMENT_SIZE = 10
ELITISM = True
def evolve_population(self, pop):
"""
Evolves a population over one generation.
:param pop:
:return:
"""
new_population = Population(pop.population_size(), False)
# Keep our best individual if elitism is enabled
elitism_offset = 0
if self.ELITISM:
new_population.save_tour(0, pop.get_fittest())
elitism_offset = 1
# Crossover population
# Loop over new population's size and create individuals from current population
for i in range(elitism_offset, new_population.population_size()):
# Select parents
parent1 = self.tournament_selection(pop)
parent2 = self.tournament_selection(pop)
# Crossover parents
child = self.crossover(parent1, parent2)
# Add child to new population
new_population.save_tour(i, child)
# Mutate the population a bit to add some new genetic material
for i in range(elitism_offset, new_population.population_size()):
self.mutate(new_population.get_tour(i))
return new_population
def crossover(self, parent1, parent2):
"""
Applies crossover to a set of parents and creates offspring
:param parent1:
:param parent2:
:return:
"""
# Create a new child tour
child = Tour()
# Get start and end sub tour positions for parent1's tour
start_pos = int(random.random() * parent1.tour_size())
end_pos = int(random.random() * parent1.tour_size())
# Loop and add the sub tour from parent1 to our child
for i in range(child.tour_size()):
# If our start position is less than the end position
if start_pos < end_pos and i > start_pos and i < end_pos:
child.set_city(i, parent1.get_city(i))
# Else if our start position is larger
elif start_pos > end_pos:
if not (i < start_pos and i > end_pos):
child.set_city(i, parent1.get_city(i))
# Loop through parent2's city tour
for i in range(parent2.tour_size()):
# If child doesn't have the city, add it
if not child.contains_city(parent2.get_city(i)):
# Loop to find a spare position in the child's tour
for j in range(child.tour_size()):
if child.get_city(j) is None:
child.set_city(j, parent2.get_city(i))
break
return child
def mutate(self, tour):
"""
Mutate a child using swap mutation.
:param tour:
:return:
"""
for tour_pos_1 in range(tour.tour_size()):
# Apply mutation rate
if random.random() < self.MUTATION_RATE:
# Get a second random position in the tour
tour_pos_2 = int(tour.tour_size() * random.random())
# Get the cities at target position in tour
city1 = tour.get_city(tour_pos_1)
city2 = tour.get_city(tour_pos_2)
# Swap them around
tour.set_city(tour_pos_2, city1)
tour.set_city(tour_pos_1, city2)
def tournament_selection(self, pop):
"""
Selects candidate tour for crossover.
:param pop:
:return:
"""
# Create a tournament population
tournament = Population(self.TOURNAMENT_SIZE, False)
# For each place in the tournament, get a random candidate tour and add it
for i in range(self.TOURNAMENT_SIZE):
random_id = int(random.random() * pop.population_size())
tournament.save_tour(i, pop.get_tour(random_id))
# Get the fittest tour
fittest = tournament.get_fittest()
return fittest
class TSP_GA:
def __init__(self, file_name):
# Read our city distances from file and store them in TourManager
# (True, name, size, cities)
tm = TourManager()
tm.reset()
success, name, size, cities2d = read_tour.get_cities(file_name)
if not success:
print("UNSUCCESSFUL")
print(success)
print(name)
print(size)
print(cities2d)
quit()
else:
print(cities2d)
tm.set_cities2d(cities2d)
# Generate a list of city numbers
for i in range(1, size+1):
tm.add_city(i)
#####
# Simulate a load of times
#####
best_distance = 1000000
best_solution = []
best_output = ""
num_simulations = 6
t_00 = time()
for j in range(num_simulations):
# Initialise population
pop = Population(200, True)
print()
print()
print("### SIMULATION NO.", j+1, "for", file_name, "###")
print("Initial distance:", pop.get_fittest().get_distance())
t0 = time()
# Evolve population for N generations
print("Running...")
N = 1000
ga = GA()
pop = ga.evolve_population(pop)
for i in range(1,N+1):
if i % (N/10) == 0:
print("Completed: " + str(int(100*i/N)) + "% of this simulation, " + "roughly " + str(int( 100*j/num_simulations )) + "% completed overall")
pass
pop = ga.evolve_population(pop)
# Print final results
t1 = time()
print("Finished")
print("Final distance:", pop.get_fittest().get_distance())
print("Solution:")
solution = pop.get_fittest().get_raw_tour()
print(solution)
print("Took " + str(round(t1 - t0, 3)) + " seconds")
# If we have the best tour so far
if pop.get_fittest().get_distance() < best_distance:
best_distance = pop.get_fittest().get_distance()
best_solution = solution
# Make output string
output = "NAME = " + name + ",\nTOURSIZE = " + str(size) + ",\nLENGTH = " + str(pop.get_fittest().get_distance()) + ",\n"
for i in range(len(solution)):
output += str(solution[i]) + ","
# Remove the final comma
output = output[:-1]
print("\n---FILE OUTPUT---")
print(output)
print("---END OF FILE---")
best_output = output
t_11 = time()
print()
print("-----")
print("BEST DISTANCE:", best_distance)
print("BEST SOLUTION:", best_solution)
print("TIME TAKEN:", str(round(t_11 - t_00, 3)) + " seconds")
print("BEST OUTPUT:")
print(best_output)
print("-----")
output_file_name = sys.argv[2]
f = open(output_file_name, "w")
f.write(best_output)
f.close()
if __name__ == "__main__":
print()
print()
print()
print()
print("###############################################################")
print("###############################################################")
print("###############################################################")
print("###############################################################")
print("###### WORKING ON " + sys.argv[1] + " ######")
print("###############################################################")
print("###############################################################")
print("###############################################################")
print("###############################################################")
print("GA.MUTATION_RATE =", GA.MUTATION_RATE)
print("###############################################################")
print()
tsp_ga = TSP_GA(sys.argv[1])