''' 连续型——Hopfield神经网络求解TSP 1、初始化权值（A,D,U0） 2、计算N个城市的距离矩阵dxy 3、初始化神经网络的输入电压Uxi和输出电压Vxi 4、利用动力微分方程计算：dUxi/dt 5、由一阶欧拉方法更新计算：Uxi(t+1) = Uxi(t) + dUxi/dt * step 6、由非线性函数sigmoid更新计算：Vxi(t) = 0.5 * (1 + th(Uxi/U0)) 7、计算能量函数E 8、检查路径是否合法 ''' import numpy as np from matplotlib import pyplot as plt # 代价函数（具有三角不等式性质） def price_cn(vec1, vec2): return np.linalg.norm(np.array(vec1) - np.array(vec2)) def calc_distance(path): dis = 0.0 for i in range(len(path) - 1): dis += distance[path[i]][path[i+1]] return dis # 得到城市之间的距离矩阵 def get_distance(citys): N = len(citys) distance = np.zeros((N, N)) for i, curr_point in enumerate(citys): line = [] [line.append(price_cn(curr_point, other_point)) if i != j else line.append(0.0) for j, other_point in enumerate(citys)] distance[i] = line return distance # 动态方程计算微分方程du def calc_du(V, distance): a = np.sum(V, axis=0) - 1 # 按列相加 b = np.sum(V, axis=1) - 1 # 按行相加 t1 = np.zeros((N, N)) t2 = np.zeros((N, N)) for i in range(N): for j in range(N): t1[i, j] = a[j] for i in range(N): for j in range(N): t2[j, i] = b[j] # 将第一列移动到最后一列 c_1 = V[:, 1:N] c_0 = np.zeros((N, 1)) c_0[:, 0] = V[:, 0] c = np.concatenate((c_1, c_0), axis=1) c = np.dot(distance, c) return -A * (t1 + t2) - D * c # 更新神经网络的输入电压U def calc_U(U, du, step): return U + du * step # 更新神经网络的输出电压V def calc_V(U, U0): return 1 / 2 * (1 + np.tanh(U / U0)) # 计算当前网络的能量 def calc_energy(V, distance): t1 = np.sum(np.power(np.sum(V, axis=0) - 1, 2)) t2 = np.sum(np.power(np.sum(V, axis=1) - 1, 2)) idx = [i for i in range(1, N)] idx = idx + [0] Vt = V[:, idx] t3 = distance * Vt t3 = np.sum(np.sum(np.multiply(V, t3))) e = 0.5 * (A * (t1 + t2) + D * t3) return e # 检查路径的正确性 def check_path(V): newV = np.zeros([N, N]) route = [] for i in range(N): mm = np.max(V[:, i]) for j in range(N): if V[j, i] == mm: newV[j, i] = 1 route += [j] break return route, newV # 可视化画出哈密顿回路和能量趋势 def draw_H_and_E(citys, H_path, energys): fig = plt.figure() # 绘制哈密顿回路 ax1 = fig.add_subplot(121) plt.xlim(0, 7) plt.ylim(0, 7) for (from_, to_) in H_path: p1 = plt.Circle(citys[from_], 0.2, color='red') p2 = plt.Circle(citys[to_], 0.2, color='red') ax1.add_patch(p1) ax1.add_patch(p2) ax1.plot((citys[from_][0], citys[to_][0]), (citys[from_][1], citys[to_][1]), color='red') ax1.annotate(s=chr(97 + to_), xy=citys[to_], xytext=(-8, -4), textcoords='offset points', fontsize=20) ax1.axis('equal') ax1.grid() # 绘制能量趋势图 ax2 = fig.add_subplot(122) ax2.plot(np.arange(0, len(energys), 1), energys, color='red') plt.show() if __name__ == '__main__': citys = np.array([[2, 6], [2, 4], [1, 3], [4, 6], [5, 5], [4, 4], [6, 4], [3, 2]]) distance = get_distance(citys) N = len(citys) # 设置初始值 A = N * N D = N / 2 U0 = 0.0009 # 初始电压 step = 0.0001 # 步长 num_iter = 10000 # 迭代次数 # 初始化神经网络的输入状态（电路的输入电压U） U = 1 / 2 * U0 * np.log(N - 1) + (2 * (np.random.random((N, N))) - 1) # 初始化神经网络的输出状态（电路的输出电压V） V = calc_V(U, U0) energys = np.array([0.0 for x in range(num_iter)]) # 每次迭代的能量 best_distance = np.inf # 最优距离 best_route = [] # 最优路线 H_path = [] # 哈密顿回路 # 开始迭代训练网络 for n in range(num_iter): # 利用动态方程计算du du = calc_du(V, distance) # 由一阶欧拉法更新下一个时间的输入状态（电路的输入电压U） U = calc_U(U, du, step) # 由sigmoid函数更新下一个时间的输出状态（电路的输出电压V） V = calc_V(U, U0) # 计算当前网络的能量E energys[n] = calc_energy(V, distance) # 检查路径的合法性 route, newV = check_path(V) if len(np.unique(route)) == N: route.append(route[0]) dis = calc_distance(route) if dis < best_distance: H_path = [] best_distance = dis best_route = route [H_path.append((route[i], route[i + 1])) for i in range(len(route) - 1)] print('第{}次迭代找到的次优解距离为：{}，能量为：{}，路径为：'.format(n, best_distance, energys[n])) [print(chr(97 + v), end=',' if i < len(best_route) - 1 else '\n') for i, v in enumerate(best_route)] if len(H_path) > 0: draw_H_and_E(citys, H_path, energys) else: print('没有找到最优解') 

输出结果：
第176次迭代找到的次优解距离为：23.731，能量为：281.06，路径为：
g,a,b,h,f,e,c,d,g
第410次迭代找到的次优解距离为：23.5193，能量为：204.084，路径为：
g,c,b,e,f,a,d,h,g
第643次迭代找到的次优解距离为：21.9907，能量为：506.847，路径为：
g,c,b,a,f,e,d,h,g
第684次迭代找到的次优解距离为：20.202，能量为：334.284，路径为：
c,a,b,g,f,e,d,h,c
第2313次迭代找到的次优解距离为：19.5117，能量为：515.27，路径为：
a,c,b,g,e,f,h,d,a
第2904次迭代找到的次优解距离为：19.5113，能量为：320.447，路径为：
c,b,g,e,f,h,d,a,c
第3389次迭代找到的次优解距离为：16.3433，能量为：340.075，路径为：
a,d,g,e,f,h,b,c,a
第4370次迭代找到的次优解距离为：15.5055，能量为：145.053，路径为：
d,g,e,f,h,c,b,a,d
第8157次迭代找到的次优解距离为：14.8867，能量为：213.135，路径为：
g,f,h,c,b,a,d,e,g

讯享网