Python TSP Berlin 52 with Simulated Annealing

Question

I want to know what this function does:

def Recocido(tour1 = []):
    # tour1 = tour1[:]
    izquierda = random.randrange(len(tour1))
    derecha = 0
    while(True):
        derecha = random.randrange(len(tour1))
        if (derecha != izquierda):
            #tour1[izquierda], tour1[derecha] = tour1[derecha], tour1[izquierda]
            break
    return tour1

I'm doing this function to "anneal" the tour1 but I'm not sure if I'm doing it well. I'm especially tangled at the commented lines (#), can someone help me please to know what I'm doing!? Or better, if I'm doing it well?

edited:

this is my SA part:

tamañoTour = len(matriz)
inicioTour = []
inicioTour = Tour(tamañoTour)
print(inicioTour)
costoTourInicio = PesoTour(inicioTour, matriz)
print(costoTourInicio)

nuevoTour = []
temp = 1000000000
#i = 0

while(temp > 0.000000001):
    for j in range(40):

        nuevoTour = Recocido(inicioTour)
        #print(nuevoTour)
        costoNuevoTour = PesoTour(nuevoTour, matriz)
        #print(costoNuevoTour)
        if (costoNuevoTour < costoTourInicio):
            inicioTour = nuevoTour
            #temp = temp*0.99
        else:
            numero = random.random()
            deltaZ = costoNuevoTour - costoTourInicio
            prob = math.exp(-(deltaZ/temp))
            if (numero < prob):
                inicioTour = nuevoTour
                #temp = temp*0.99

    #i += 1
    temp = temp*0.99

#print(inicioTour)
print(nuevoTour)
#print(costoTourInicio)
print(costoNuevoTour)
#print(i)

matriz is a 52x52 array, well is the distances between parts of berlin52 http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/

and the other functions are:

def Tour(tamaño):
    tour1 = []
    for i in range(tamaño):
        while(not False):
            valor = random.randrange(tamaño)
            if valor not in tour1:
                tour1.append(valor)
                break
    return tour1

def PesoTour(tour1 = [], matriz = [[]]):
    valor = 0
    i = 0
    while(i < len(tour1)):
        if (i == len(tour1) - 1):
            valor = valor + matriz[tour1[i]][tour1[0]]
        else:
            valor = valor + matriz[tour1[i]][tour1[i+1]]
        i += 1
    return valor

thats it, thanks for the comments.

Answer 1

As it is, this function generates a few random numbers and then stops. If you uncomment the commented lines, it creates a copy of the input with two random elements swapped (or loops forever if the input has only 1 element, or raises an exception if the input is empty). Here's a line-by-line breakdown:

# The default argument here is useless.
def Recocido(tour1 = []):

    # Make a copy of the list.
    tour1 = tour1[:]

    # Pick a random index.
    izquierda = random.randrange(len(tour1))

    # Unnecessary.
    derecha = 0

    while(True):

        # # Pick another random index
        derecha = random.randrange(len(tour1))

        # If it's not the same index you picked the first time,
        if (derecha != izquierda):

            # swap the elements of the copy at the two indices,
            tour1[izquierda], tour1[derecha] = tour1[derecha], tour1[izquierda]

            # and stop looping.
            break

    return tour1

(I hope this is only one part of your simulated annealing program, because this is not simulated annealing. There is no function to optimize, no cooling schedule, and no probabilistic rejection of state changes.)

If you're trying to write a function that returns a copy of an input list with two random elements swapped, you could clean it up as follows:

# No default argument - you'd never want to use the default.
def with_random_swap(lst):
    # Use random.sample to pick two distinct random indices.
    index1, index2 = random.sample(xrange(len(lst)), 2)
    copy = lst[:]
    copy[index1], copy[index2] = copy[index2], copy[index1]
    return copy