I am trying to implement the Simulated Annealing (SA) algorithm to solve a random instance of the Traveling Salesman Problem (TSP) in python. In my code, I have a function that computes the total longitude of the tour, given a list with the route and the distance matrix. When I run my code I have the following error related to this function.
UnboundLocalError: local variable 't' referenced before assignment
My code es the following:
N=4
D=np.zeros([N,N])
random.seed(13)
for i in range(N):
for j in range(N):
D[i,j]=random.randint(15,100)
for i in range(N):
D[i,i]=10000
print("")
print("- Number of cities=",N)
print("")
print("- =")
print("- Distance matrix")
print(D)
#GENERATE ROUTES FUNCTION:
def generar_tour(N):
ruta=range(N)
ruta_obtenida=random.sample(ruta,len(ruta))
return ruta_obtenida
#Function for calculating the length of the route
def distancia_tour(ejemplo,D):
longitud=0
for t in range(len(ejemplo)-1):
longitud=longitud+D[ejemplo[t],ejemplo[t+1]]
longitud=longitud+D[ejemplo[t+1],ejemplo[0]]
return longitud
#SIMULATED ANNEALING ALGORITHM
T_inicial=5000
tour_inicial=generar_tour(N)
distancia_inicial=distancia_tour(tour_inicial,D)
print("TOUR INICIAL=",tour_inicial,"| LONGITUD TOUR=",distancia_tour(tour_inicial,D))
tour_actual=[]
tour_vecino=[]
distancia_vecino=0
distancias=[]
iteracion=[]
IT_max=1000
iterador=1
contar=1
while T_inicial>10**(-5):
while iterador>IT_max:
tour_vecino=generar_tour(N)
distancia_vecino=distancia_tour(tour_vecino,D)
if distancia_vecino-distancia_inicial<0:
tour_actual=tour_vecino
else:
if random.random()<math.exp(-(distancia_vecino-distancia_inicial)/T_inicial):
tour_actual=tour_vecino
iterador=iterador+1
T_inicial=0.9999*T_inicial
print("RUTA=",tour_actual,"|","DISTANCIA TOTAL=",distancia_tour(tour_actual,D),"|","TEMPERATURA ACTUAL=",T_inicial)
distancias.append(distancia_tour(tour_actual,D))
iteracion.append(contar)
contar=contar+1
plt.plot(contar,distancias,'b')
plt.show()
I had to search it on google, but using the most common solution as "global" and others don't work. Any ideas? I am sure that is not a hard problem, just I don't see it. Any hints? Thanks in advance and greetings from Chile.
As, Samuel Muldoon says in his answer, the error means that you tried to use t
before you set its value. The challenge in your code is that it's difficult to see how that could happen. It looks like you always set t
in the for
loop in distancia_tour
, so how could it not be set?
It turns out that, owing to an error in your code, you pass an empty list to your distancia_tour
function. The length of the empty list is 0 so your for
loop is effectively:
for t in range(-1):
...
range(-1)
returns an empty list, so there are no values to iterate over in the for
loop. t
is never given a value and you get the error when t
is referenced on the next line after the for
loop.
The reason it gets an empty list is that you initialize tour_actual
to an empty list and then don't change it's value because of an error in your while
statement. You have while iterador>IT_max:
, which never executes because iterador
is less than IT_max
. You probably meant to test for iterador < IT_max
.