python - TSP，算法陷入局部最小值

Question

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

# 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)

/image/A6hmd.png

Answer 1

我没有运行您的代码，但我会尝试的一件事是更改 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