tsp的模拟退火算法.txt

神经网络中的tsp的模拟退火算法的matlab实现

TSP:设有n个城市和距离矩阵D=|dij|，其中dij表示城市i到城市j的距离，i,j=
1,2,...,n，则问题是要找一条遍访每个城市恰好一次的一条回路，且路径长度
最短。
算法如下：
(1)解空间S为{1，2，...,n}的所有循环排列的集合,S={(C1,...Cn)|(C1,...Cn)
为{1,2,...,n}的循环排列}，其中每一个循环排列表示遍访n个城市的一个回路，
Ci=j表示在第i次访问城市j,Cn+1=C1,初始解选取{1,2,...,n}。
(2)目标函数为遍访所有城市路径长度的最小值
　　　　　　　minf(C1,C2,...,Cn)=∑dCiCi+1  (i从1到n)
(3)通过分别或交替使用以下两种方法产生新解。
(i)2变换法　任选序号u和v，交换u与v之间的访问顺序，此时新路径为(不妨设
u<v) C1...Cu-1CvCv-1...Cu+1CuCv+1...Cn.
(ii)3变换法　任意选序号u,v,w,将u和v之间的路径插到w之后访问，对应新的
路径为(设u<=v<w)
　　　C1...Cu-1Cv+1...CwCu...CvCw+1...Cn.
在实际中经常将上述两种方法综合交替使用。
(4)相应于上述两种方法新解的代价函数的差分别是
　　　　△f=(dCu-1Cv +dCuCv+1 +∑dCiCi-1(i从u+1到n))-(dCu-1Cn +dCvCv+1
+∑dCi-1Ci(i从u+1到n))
   和  △f=(dCu-1Cv+1 +dCwCu +dCvCw+1)-(dCu-1Cu +dCvCv+1 +dCwCw+1).