TSP，算法陷入局部最小值 [英] TSP, algorithm gets stuck in local minimum

问题描述

我正在努力实现基于模拟退火的程序来解决旅行商问题.我得到的所有解决方案都不令人满意，我也不知道如何改善实施.显然，我不是在关注基准，而只是在寻找视觉上可接受的最短路径.如果有人能启发我，我将不胜感激.

I am struggling to implement a program based on simulated annealing to solve the traveling salesman problem. All solutions I got are not satisfying and i have no clue how to improve my implementation. Obviously I'm not focusing on benchmarks, but only on finding the visually acceptable shortest path. If anyone might enlighten me I would be thankful.

# 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

推荐答案

我没有运行您的代码，但是我尝试做的一件事就是更改SA实现. 当前，一个循环中有100,000次迭代.我会将其分为两部分.外环控制温度，而内环在该温度下运行不同.这样的东西(伪代码):

I didn't run your code, but one thing I'd try is changing the SA implementation. Currently, you have 100,000 iterations in one loop. I would break that into two. The outer loop controls the temperature and the inner loop is different runs in that temperature. Something like this (pseudo code):

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

这篇关于TSP，算法陷入局部最小值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！