我正在实施一个基于模拟退火的销售人员解决的问题。我得到的所有解决方案都不是令人满意的,我也不知道如何改进我的实现。显然,我不关注基准测试,而只是寻找视觉上可接受的最短路径。如果有人能启发我,我会很感激的。在
# 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)
我没有运行您的代码,但有一件事我会尝试更改SA实现。 目前,在一个循环中有100000次迭代。我会把它分成两半。外回路控制温度,内环在该温度下运行不同。类似这样(伪代码):
相关问题 更多 >
编程相关推荐