I've got some code, I'm doing for my classes. The idea is is that I solve a traveling salesman search with tabu search. what I have already done in my code is to randomly generate a list of cities (based on input from user - how many cities does he want to have, the question that program asks in the beginning) with their own set of coordinates (X and Y), and I can calculate distance between each of them (I assume, that salesman can simply go straight from one city to another).
what I have problem is, is the tabu search. My idea is to have a default path, that goes just by visiting all the cities in order, they were generated (line 47, variable name: domyslne). then i get it, i swap two random cities on it, and calculate the length of that route as well. and here is the tricky part: i can't get my head around getting the tabu and all the conditions, i want (it will be probably a set of nested loops). I would like to get 2 tables: tabu (where i store X last combinations checked) and tabulen (which stores length of a respective path in tabu table). next i render a new route and calculate it's length. if tabu already reached it's max size X, and the length of the new route is less, then highest value currently stored, we remove that highest value from tabu list, and replace it with the new, the one that i've just rendered. in the end, after Y loops of such command (currently set at 6 by default, but i'm thinking about doing it like the number of cities squared or something), I get the shortest route from tabu table and present it as a solution. i'm not sure how to make it work properly, and i hope i can get some help here. thank you very much in advance!
import math
from pprint import pprint
from random import *
def odleglosci(a1, a2, b1, b2):
w1 = a1 - b1 # wspolrzedne X (roznica)
w2 = a2 - b2 # wspolrzedne Y (roznica)
w1k = w1 * w1 # kwadrat wwspolrzednych X
w2k = w2 * w2 # kwadrat wspolrzednych Y
suma = w1k + w2k # suma kwadratow
return round(math.sqrt(suma), 2) # pierwiastek z sumy kwadratow, zaokraglony do 2 miejsca po przecinku
def path_length(cities, path):
cities_pairs = zip(path, path[1:])
consecutive_distances = [odleglosci(cities[a][0], cities[a][1], cities[b][0], cities[b][1]) for (a, b) in
cities_pairs]
return round(sum(consecutive_distances), 2)
def generate_city_coordinates(cities_count):
axis_range = range(cities_count * 5)
return tuple(zip(sample(axis_range, cities_count), sample(axis_range, cities_count)))
def calculate_distances(city_coordinates):
result = []
for city in city_coordinates:
city_distances = []
for other_city in city_coordinates:
distance = odleglosci(city[0], city[1], other_city[0], other_city[1])
city_distances.append(distance)
result.append(city_distances)
return result
if __name__ == '__main__':
ilosc = int(input("Podaj ilosc miast:"))
wielkosc = 10 * ilosc
miasta = generate_city_coordinates(ilosc)
domyslne = [] # domyslna sciezka
domyslneniep = domyslne # domyslne niepelne, bez powtorzonego pierwszego elementu na ostatnim miejscu
for i in range(0, ilosc):
domyslne.append(i)
domyslne.append(domyslne[0])
print("Domyslna sciezka:")
print(domyslne)
print("wspolrzedne miast:")
print(miasta)
print("odleglosci miedzy miastami:")
wszodl = calculate_distances(miasta) # wszystkie odleglosci
pprint(wszodl)
print("dlugosc domyslnej sciezki:")
print(path_length(miasta, domyslne))
tabu = []
tabulen = []
tabu.append(domyslne)
iteracje = 6 # ilosc iteracji algorytmu TABU
for i in range(1, iteracje):
g = randint(0, ilosc - 1)
j = randint(0, ilosc - 1)
while (j == g):
j = randint(0, ilosc - 1) # dwie rozne wartosci, do zamieniania na liscie
print("G:", g, "J:", j)
nowatablica = domyslneniep
nowatablica[g], nowatablica[j] = nowatablica[j], nowatablica[g]
ost = int(len(nowatablica)) - 1
nowatablica[ost] = nowatablica[0]
print(nowatablica)
print(path_length(miasta, nowatablica))
Ok, so I've figured this out. Here is the correct code to replace at the point, wher tabu table is declared