Python TSP Berlin 52 с имитацией отжига

Я хочу знать, что делает эта функция:

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

Я делаю эту функцию, чтобы "отжечь" тур1, но я не уверен, что у меня это хорошо получается. Я особенно запутался в прокомментированных строках (#), может кто-нибудь помочь мне узнать, что я делаю!? Или лучше, если я делаю это хорошо?

отредактировано:

это моя часть SA:

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 — это массив 52x52, а также расстояния между частями berlin52 http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/

и другие функции:

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

это так, спасибо за комментарии.


python-3.x python python-2.7 simulated-annealing
person Menticolcito    schedule 26.08.2013    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Как бы то ни было, эта функция генерирует несколько случайных чисел, а затем останавливается. Если вы раскомментируете закомментированные строки, он создаст копию ввода с двумя переставленными случайными элементами (или зациклится навсегда, если ввод имеет только 1 элемент, или вызовет исключение, если ввод пуст). Вот построчная разбивка:

# 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

(Надеюсь, это только часть вашей программы имитации отжига, потому что это не имитация отжига. Здесь нет функции для оптимизации, нет расписания охлаждения и нет вероятностного отклонения изменений состояния.)

Если вы пытаетесь написать функцию, которая возвращает копию входного списка с двумя переставленными случайными элементами, вы можете очистить ее следующим образом:

# 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
person user2357112 supports Monica    schedule 26.08.2013
comment
да, это просто функция, вероятностная часть выполнена, но я не получаю желаемого результата, он слишком высок по сравнению с реальным ответом. посмотрите на отредактированный вопрос. - person Menticolcito; 26.08.2013
comment
@Menticolcito: Ну, я вижу несколько проблем с неэффективностью и изобретением велосипедов. Tour должен просто вызвать random.shuffle для создания случайного начального тура, а PesoTour должен использовать цикл for. Однако после первоначального прочтения я не вижу никаких очевидных проблем с правильностью. nuevoTour в конце будет иметь бесполезное значение, а inicioTour нужно правильно оптимизировать. - person user2357112 supports Monica; 26.08.2013