姓名学号
实验成
绩
华中师范大学计算机科学系
实验报告书
实验题目：基于Boltzmann Machine的模拟退火算法解决TSP问题课程名称：智能计算
主讲教师：沈显君
辅导教师：
课程编号：
班级：2011级硕士
实验时间：2011.12.27
实验题目
基于Boltzmann Machine的模拟退火算法解决TSP问题
实验环境
操作系统：Microsoft Windows XP Professional
编程平台：Microsoft Visual C++ 6.0
TSP问题
旅行商问题（TSP，Traveling Salesman Problem）是著名的组合优化问题之一。

可以描述如下：设n为城市数目，D=[d ij]为n*n的矩阵，d ij表示从城市i到城市j的距离，其中i，j=0,1,…,n-1，则TSP的解就是从某一城市出发经过所有城市恰好一次最后回到出发点的最短路径。

Boltzmann Machine
波尔兹曼机（Boltzmann Machine）是一种多层网络，由输入层，输出层和隐层构成，隐单元之间相互连接。

网络状态按照概率分布变化，网络中单元状态可取0,1两种值，每个单元的状态的转换是一随机函数。

如把状态的0或1看成拒绝或接受某一假设，则两者的连接强度可理解为两个假设之间的一致程度。

模拟退火(Simulated Annealing)
模拟退火算法借鉴了金属制品加工的退火过程，即为了提高金属制品的韧性和硬度将金属制品缓慢加热到一定温度，保持足够时间，然后以适宜速度冷却。

金属制品中的原子结构代表一种状态，每个状态对应一个能量，这是由原子
间的相对位置决定的。

当原子稳定于晶格时，金属坚固耐用。

此时对应最小能量状态。

若金属原子偏离晶格（其程度与温度有关），则会处于较高能量。

要消除此现象，可允许原子进行适当的热扰动( Thermal Agitation)并进行退火。

一开始温度较高时，此时物体内的原子就可高速自由运行，处于较高的能量状态。

但随着温度的下降，原子越来越趋于低能态，最后整个物体形成最低能量的基态。

把某类优化问题的求解过程与统计热力学的热平衡问题进行对比，试图通过模拟高温物体退火过程的方法，来找到优化问题的全局最优或近似全局最优解。

这就是模拟退火算法的思想来源。

实验思想
为了便于验证算法是否能求得全局最优解或近似全局最优解，本实验中TSP 问题设计如下：城市数为10，各个城市均匀地分布在一个单位圆上，分别记为C0、C1、C2、C3、C4、C5、C6、C7、C8、C9。

要求从任一城市出发，经过且只经过所有城市一次最后又回到出发点的最短路径。

易知这个问题的解为绕圆周一圈的路径，这样我们就可以据此判断算法是否能求出全局最优解或近似全局最优解。

我们假设任意两个不同的城市之间都有路径连接，各个城市之间的连通性和距离可以用矩阵Distance表示：
图1：Distance矩阵
由上图可知Distance矩阵总共有100个元素，每个元素表示的是某段路径的长度。

不难得出，TSP要求的路径肯定是从这100段路径中选择出来的若干段路
径组合而成的，且满足TSP问题的定义。

由此我们可以定义一个神经网络结构，由100个神经元组成，每个神经元分别与Distance矩阵中的每条路径对应，每个神经元的状态只能为1或0，1表示对应的路径被选中用于组成TSP的待考察路径，0表示对应的路径未被选中。

神经网络结构如下：
图2：神经网络结构
定义神经元i的状态为S i(i=0,1,...,99)，S i的取值为1或0，定义神经元i和神经元j的连接强度为W ij。

当i=j时，W ij=0，当i≠j时，W ij取特定值。

Θi定义为神经元i的阈值。

则网络的能量定义为：
模拟退火的步骤如下：
1.随机生成100个神经元的状态和初始温度；
2.在当前温度T下，随机改变各个神经元的状态，直到达到热平衡。

3.判断选中的各段路径是否组成符合TSP问题的路径。

如果符合则输出解，
否则降低温度，转到步骤2继续退火。

实验结果
……
参考文献
史忠植.智能科学[M].北京:清华大学出版社,2006
史忠植.神经网络[M].北京:高等教育出版社,2009
D.H. Ackley, G.
E. Hinton, T.J. Sejnowski(1985). A Learning Algorithm for Boltzmann Machines. Cognitive Science, 9, pp. 147-169。