作业二：Hopfield、GA、ACO求解TSP问题

一、问题描述

TSP问题（Traveling Salesman Problem，旅行商问题），由威廉哈密顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出。问题描述如下：

有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只在一个城市逗留一次，最后回到出发的城市，问如何事先确定一条最短的线路已保证其旅行的费用最少？

为了简化问题，在本题中，假设所有城市都位于一个平面直角坐标系中，用(x , y)表示城市的坐标。本题随机生成了20个城市，他们的名称和位置如下：

城市信息

二、问题分析

TSP问题实质是找出一条最短的哈密尔顿回路，这是一类NPC问题。传统的算法贪心、DP等要么找不到最优解，要么时间空间开销太大，而启发式搜索算法可以在能够接受的时间内找到一个近似最优解。本实验分别通过Hopfield网络、GA算法、PSO粒子群算法这三种不同的启发式搜索算法解决TSP问题，求得最短路径。

三、运行环境

操作系统：Windows 10

工具环境：Python 3.5， tensorflow框架， matplotlib

四、Hopfield网络解TSP问题

1.算法描述

Hopfield神经网络是一种递归神经网络，由约翰·霍普菲尔德在1982年发明。Hopfield网络是一种结合存储系统和二元系统的神经网络。它保证了向局部极小的收敛，但收敛到错误的局部极小值（local minimum），而非全局极小（global minimum）的情况也可能发生。Hopfield网络也提供了模拟人类记忆的模型。

1.1 Hopfield网络的能量函数：

有输入：

$E=-\frac{1}{2} \sum_{i=0}^n\sum_{j=0}^n \omega _{ij} s_{i} s_{j}-\sum_{i=1}^nI_{i}s_{i}$

没有输入：

$E=-\frac{1}{2} \sum_{i=0}^n\sum_{j=0}^n\omega _{ij}s_{i}s_{j}=-\frac{1}{2} S^T\omega S$

1.2 吸引子Attractor

网络的一个稳定的状态，设计一个与系统对应的能量函数，如果存在一个系统使得对任何初始状态，能量函数都随时间连续下降，那么系统是稳定的。

1.3 利用Hopfield求解问题的一般方法

第一步：分析问题，得到求解问题的目标方程，将目标方程变为能量方程的形式。

第二步：优化网络，目标是使网络能量减小到吸引子Attractor状态

采用异步的变化，每次选择一个神经元改变状态，当网络能量减小时就接受这种状态改变，不断改变直到网络的能量趋于稳定，网络达到稳定状态。

2.问题表述

求解TSP旅行商问题相当于求解一个约束优化问题

第一步：将问题表示为图，图中的每个点代表城市，如果两个城市可达则有边相连

第二步：将问题转换为Hopfield网络的结构：用矩阵表示

矩阵示例

矩阵含义：元素 $x_{ij}$ 表示第j时刻经过第i个城市

约束：

① 每行只有一个神经元的状态为1

② 每列只有一个神经元的状态为1

③ 所有的激活的神经元的个数之和等于城市总数

第三步：采用拉格朗日构造能量方程

① 拉格朗日法构造目标函数

$Goal=\frac{A}{2}\sum_{i=1}^n \sum_{x=1}^n \sum_{j=1}^n s_{xi}d_{xy}(s_{y,i-1}+s_{y,i+1} )$

$C_{1} =\frac{B}{2}\sum_{x=1}^n \sum_{i=1}^n \sum_{j=1}^ns_{xi}s_{xj}$ ,表示每行只有一个神经元的状态为1

$C_{2}=\frac{C}{2}\sum_{i=1}^n \sum_{x=1}^n \sum_{j=1}^ns_{xi}s_{yi}$ ,表示每列只有一个神经元的状态为1

$C_{3}=\frac{D}{2}{(\sum_{x=1}^n \sum_{i=1}^ns_{xi}-n )}^2$ ,表示所有的激活的神经元的个数之和等于城市总数

$E=Goal+C_{1} +C_{2} +C_{3}$

② 将目标方程转换为Hopfield网络能量函数的形式，确定权重W和输入I

标准形式为：

$E=-\frac{1}{2} \sum_{i=0}^n\sum_{j=0}^n \omega _{ij} s_{i} s_{j}-\sum_{i=1}^nI_{i}s_{i}$

将目标方程转化为上述形式得到：

$E=-\frac{1}{2}\sum_{x=1}^n \sum_{i=1}^n \sum_{y=1}^n \sum_{j=1}^n s_{xi}\omega _{xi,yj}s_{yj}-\frac{1}{2}\sum_{x=1}^n \sum_{i=1}^nI_{xi}s_{xi}$

权重W：

$\omega _{xi,yj}=-Ad_{xy}(\delta _{i,j+1} +\delta _{i,j-1} )-B\delta _{xy}(1-\delta _{xy})-C\delta_{ij}(1-\delta_{xy}) -D(1-\delta_{ij})(1-\delta_{xy})$

输入I：

$I_{xi}=Dn$

其中，

$\delta_{xy}=1,x=y$ , $\delta_{xy}=0,x\neq y$

④ 由于上述能量方程E的形式比较复杂可以进行进一步优化，减少权值参数的个数，得到：

$E=\frac{B}{2}\sum_{x=1}^n(\sum_{i=1}^n s_{xi}-1 )^2+\frac{B}{2}\sum_{i=1}^n(\sum_{x=1}^n s_{yi}-1)^2+\frac{A}{2}\sum_{x=1}^n \sum_{y=1}^n \sum_{i=1}^n s_{xi}d_{xy}s_{y,i+1}$

其对应的状态的增量的表达式为

$\frac{du_{xi} }{t}=-\frac{dE}{dv_{xi}}=-B(\sum_{i=1}^nv_{xi}-1 )-B(\sum_{y=1}^nv_{yi}-1)-D\sum_{y=1}^n d_{xy}v_{y,i+1}$

3.算法流程

第一步：初始化Hopfield神经完了过的的权值A、D

第二步：计算城市之间的距离，形成距离矩阵 $D_{xy}$

第三步：初始化神经网络的输入状态 $U_{0}$ ，为城市时刻矩阵赋初值

$U_{xi}(t)=\frac{1}{2}U_{0}ln(n-1)+\delta _{xy}$ , $\delta _{xy}\in {0,1}$

第四步：计算状态的增量

$\Delta U=\frac{du_{xi} }{t}=-\frac{dE}{ds_{xi}}=-B(\sum_{i=1}^ns_{xi}-1 )-B(\sum_{y=1}^ns_{yi}-1)-D\sum_{y=1}^n d_{xy}s_{y,i+1}$

第五步：更新下一刻的输入状态

$U_{xi}(t+1)=U_{xi}(t)+\frac{dU_{xi}}{dt}\Delta t$

第五步：更新下一刻输出状态S，并计算当前的能量E

$S_{xi}(t)=\frac{1}{2}[1+tanh(\frac{U_{xi}(t)}{U_{0}})]$

$E=\frac{B}{2}\sum_{x=1}^n(\sum_{i=1}^n s_{xi}-1 )^2+\frac{B}{2}\sum_{i=1}^n(\sum_{x=1}^n s_{yi}-1)^2+\frac{A}{2}\sum_{x=1}^n \sum_{y=1}^n \sum_{i=1}^n s_{xi}d_{xy}s_{y,i+1}$

第六步：检查当前的输出状态S，是否满足约束

重复上述过程，直到达到最大迭代次数。

4.运行结果及分析

Hopfield结果

由于Hopfield网络在能量下降的过程中采用了贪心的策略，因此也容易收敛到局部最优解。