模拟退火之TSP问题1.doc

（货郎担问题：TravellingSalesmanProblem，简记为TSP)TSP问题描述如下：设有n个城市，用数码1,,n代表.城市和城市之间的距离为．TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短.求解TSP的模拟退火算法模型可描述如下：（1）解空间解空间S是遍访每个城市恰好一次的所有回路，是{1，，n}的所有循环排列的集合，即为的排列}.表示在第I次访问第j个城市，并记以及初始解可选为(1，，n).（2）目标函数目标函数即为访问所有城市的路径总长度或称为代价函数的最小值，即求解(6.1.1)其中.(6.1.1)的求解通过迭代来完成,每一次迭代,需要完成下面三个任务:(3)产生新解新解一般按照某种规则对序号实现变换得到,下面介绍分别或交替采用的三种变换过程.=1\*GB3①2变换法随机生成两个序号,交换上述序号之间的访问顺序,此时新路径变为（6.1.2）=2\*GB3②3变换法随机生成三个序号,将之间的序号插入到序号之后再来访问,对应的新路径为（6.1.3）=3\*GB3③逆转中间或者逆转两端变换法随机产生两个序号，若，则对应新的路径为（6.1.4）如果是,则对应的新路径为（6.1.5）也可以采用其他的变换方法，有些变换有独特的优越性，有时也将它们交替使用，得到一种更好方法.(4)代价函数差设将路径变为新路径，则代价函数差为（6.1.6）例如，相应于（6.1.2）的代价函数差为（6.1.7）特别地，当问题具有对称性时，对应矩阵为对称矩阵，此时，，（6.1.7）可以简化为（5）接受准则（6.1.8）为简单计，讨论二维平面上的TSP问题，其距离矩阵满足对称性以及三角不等式：当退火过程完成以后，由变量形参p输出的数值即为近似最短路径，而为对应的最短路长度