TSP, алгоритм застревает в локальном минимуме - PullRequest
Новая
       50

TSP, алгоритм застревает в локальном минимуме

3 голосов
/ 13 апреля 2019

Я изо всех сил пытаюсь реализовать программу, основанную на имитации отжига, для решения проблемы коммивояжера.Все решения, которые я получил, не удовлетворяют, и я понятия не имею, как улучшить мою реализацию.Очевидно, я не сосредотачиваюсь на тестах, а только на поиске визуально приемлемого кратчайшего пути.Если бы кто-нибудь мог просветить меня, я был бы благодарен.

# weight function, simple euclidean norm
def road(X,Y):
    sum = 0
    size = len(X) -1
    for i in range(0,size):
        sum +=math.sqrt((X[i]-X[i+1])**2 + (Y[i]-Y[i+1])**2)

    return sum   

def array_swap(X,Y,index_1,index_2):
    X[index_1],X[index_2] = X[index_2],X[index_1]
    Y[index_1],Y[index_2] = Y[index_2],Y[index_1]


def arbitrarty_swap(X,Y):
    ran = len(X)-1
    pick_1 = random.randint(0,ran)
    pick_2 = random.randint(0,ran)

    X[pick_1],X[pick_2] = X[pick_2],X[pick_1]
    Y[pick_1],Y[pick_2] = Y[pick_2],Y[pick_1]

    return pick_1, pick_2

N = 40

X = np.random.rand(N) * 100
Y = np.random.rand(N) * 100


plt.plot(X, Y, '-o')
plt.show()


best = road(X,Y)
X1 = X.copy()
Y1 = Y.copy()

#history of systems energy   
best_hist = []
iterations = 100000
T = 1.02
B = 0.999

for i in range(0,iterations):
    index_1, index_2 = arbitrarty_swap(X,Y)
    curr = road(X,Y)
    diff = (curr - best)
    if diff < 0 :
        best = curr
        best_hist.append(best)
        array_swap(X1,Y1,index_1,index_2)
    elif math.exp(-(diff)/T) > random.uniform(0,1):
        best_hist.append(curr)
        T *=B
    else:
        array_swap(X,Y,index_1,index_2)

https://i.stack.imgur.com/A6hmd.png

1 Ответ

5 голосов
/ 16 апреля 2019

Я не запускал ваш код, но я бы попробовал изменить реализацию SA.В настоящее время у вас есть 100 000 итераций в одном цикле.Я бы разбил это на две части.Внешний цикл контролирует температуру, а внутренний цикл работает по-разному.Примерно так (псевдокод): 

t=0; iterations=1000; repeat=1000
while t <= repeat:
    n = 0
    while n <=iterations:
        # your SA implementation.
        n += 1 # increase your iteration count in each temperature
    # in outer while, 
    t += 1
    T *= B
...