智能优化方法作业中国城市TSP问题TS解法文档格式.docx

1、第二章 算法准备2.1 数据搜集中国城市省会经纬度数据见“中国城市经纬度.txt”2.2 距离计算地球是一个近乎标准的椭球体，它的赤道半径为6378.140千米，极半径为 6356.755千米，平均半径6371.004千米。如果我们假设地球是一个完美的球体，那么它的半径就是地球的平均半径，记为R。如果以0度经线和0度纬线为基准，那么根据地球表面任意两点的经纬度就可以计算出这两点间的地表距离（这里忽略地球表面地形、海拔高度对计算带来的误差，仅仅是理论上的估算值）。设第一点A的经纬度为（LonA, LatA），第二点B的经纬度为（LonB, LatB），按照0度经线的基准，东经取经度的正值（Lon

2、gitude），西经取经度负值（-Longitude），北纬取90-纬度值（90- Latitude），南纬取90+纬度值（90+Latitude），则经过上述处理过后的两点被计为（MLonA, MLatA）和（MLonB, MLatB）。那么根据三角推导或者三维空间向量数量积公式，可以得到计算两点距离的如下公式： 式一这里，R和单位是相同，如果是采用6371.004千米作为半径，那么就是千米为单位。特殊的，如果城市均分布在北半球（南半球只有澳洲才有意义）。可以仅对经度作正负处理，而不对纬度作正负处理，公式可以变换如下： 式二这里我们使用式二作为距离计算公式。第三章 算法设计3.1 解及目标函

3、数的表达3.1.1 解的编码解的编码按照城市先后读取顺序依次编码为1,2,n为总城市个数。这样任意一个解可以表示为1到n的一个组合。3.1.2 初始解的产生初始解的产生采样随机的方式，及随机的产生一个1到n的自然数组合作为初始解。3.1.3 评价函数的构造评价函数根据解的排列方式由距离矩阵相应元素求和得出。3.1.4 距离矩阵距离矩阵的i行j列元素表示城市i到城市j的距离。显然，这里距离矩阵为对称矩阵。3.2 邻域移动方式邻域移动方式这里采样2-opt的方式，即两两交换。事实上，对于TSP问题某一个解的目标值和该解的起始位置无关。即1,2,3,4这个以1号城市为起始地点解的目标值与以2号城市为

4、起始地点解2,3,4,1的目标值相同。即每一个解都有n-1个和它相同的解，它们只是编码形式不同。这相当于在这种采用自然数对解进行编码的方式，将解的空间扩大了n倍（n为城市个数）。为了将解空间缩小，我们可以任意指定一个城市作为起始城市。这样在以该城市为起始位置的解的空间中没有重复解。因此，当我们随机得到一个初始解后，在接下来的邻域计算中不移动第一个城市。然而，当迭代步骤过半的时候，这时候为了更新到更好的最优解，我们需要将解空间扩大n倍，因此这时候需要移动第一个城市，以便获得更大的邻域。3.3禁忌表3.3.1 禁忌对象禁忌对象大体分为三种方式，分别为：解的移动、解、目标值。这里分别讨论三种方式对算

5、法的影响。3.3.2 禁忌表的编码形式根据禁忌对象的不同，禁忌表的编码形式也不同。3.3.3 禁忌对象为解的移动对于禁忌对象为解的移动，可以直接采样nn的矩阵进行编码。其中表中i行j列上的元素表示i、j城市交换剩余被禁忌的次数。禁忌表示意图如下：其中n为城市个数。可以看出该禁忌表同样为对称矩阵。更新禁忌表时，首先将矩阵中大于零的数减一，然后再将新禁忌的交换步骤置为禁忌表长度即可。3.3.4 禁忌对象为目标值对于禁忌对象为目标值的禁忌表，可以采用FIFO的队列表示。相应的编码形式为一个一维数组。数组长度为禁忌表的长度，其中索引最小的元素对应最新禁忌的目标值。其中m为禁忌表长度。当更新禁忌表时，将

6、禁忌表中所有元素后移一位，最后一个元素移除，然后将新被禁忌的目标值放到禁忌表的最前面。3.3.5 禁忌对象为解禁忌对象为解的禁忌表编码形式可以由两种，第一种是采用m其中m为禁忌表的长度，n为城市的个数。这样表中的每一行表示一个解。依然采用FIFO的编码形式即可。上述这种编码形式占用的空间较大，而且相关操作实现也比较麻烦。为了将二维禁忌表改成一维禁忌表，我们采用如下的编码方式：假设其中的一个解为，将其右乘以一个各个分量不相等的权值列向量（这里取其为自然数序列，即），即易知，当q的各个分量不相等时。和是一一对应的关系。所以我们可以将作为该解的编码。从而禁忌表的编码形式可以简化为一个一维的FIFO队

7、列。其中m为禁忌表的长度。可以看出简化后的禁忌表编码和以目标值为对象的禁忌表编码形式相同，这也使编程实现的工作减少了许多。3.4停止准则停止准则采样固定的迭代次数。第四章 算法实现及分析4.1编译环境及界面介绍本次试验算法采用matlab进行实现。matlab版本为R2013b.首先我们编写了一个m脚本文件进行调试（tsp_tabu.m）.在程序调试成功以后，为了方便讨论各个参数对算法的影响及对算法进行分析。我们又编写了一个GUI界面（tsp_tabu_gui.fig）。界面如下：图2 TSP算法GUI界面在界面的左边参数设置区可以设置“迭代次数”（默认为3000）、t表长度（默认为35）。在

8、“禁忌对象”的下拉列表中一共有三个选项。如下图所示：图3 禁忌对象下拉列表当参数设置完毕后，点击开始运行按钮即可开始运行程序，下图是迭代过程中的运行情况：图4 GUI运行界面在GUI运行的过程中，每当最优值改变时，均会在命令空间输出当前最优值和迭代的次数。可以在命令空间来观测最优值的变化情况。当程序运行完毕后，会在GUI界面显示目标值、运行时间以及路线图。同时在命令空间也会输出最优值、最优解。如果是因为所有邻域都被禁忌而停止，还会输出有关信息。下面是GUI运行完毕时的画面：图5 GUI运行完毕时的画面4.2 算法分析4.2.1 迭代次数对算法的影响通过几十次运行，我们发现当迭代次数大于1000

9、次的时候。最优解基本不发生改变，而当迭代次数大于2000次时，解变化的频率更少。因此可以得出结论：当迭代次数小于2000次时，最优值和迭代次数正相关。而当迭代次数大于2000次时，最优解几乎不再随迭代次数而改变。可能原因：1.当经过1000次的迭代后，找到的解已经非常好了，因此很难再找到更好的解。2.迭代运算进入了局部最优并无法循环出去。4.2.2 t表长度对算法的影响这里以禁忌对象为“解的移动”，“迭代次数”为3000进行分析。t表长度 = 10下面为中间迭代过程中的最后部分数据：迭代次数15518018115061562最优值1992719838198301978817217表1 t表长度

10、=10中间迭代数据下图为最终结果：图6 t表长度=10最终结果可以看出最终结果并不是很理想，而由中间迭代数据可以发现，当迭代次数为181的时候，很长一段时间最优解并没有更新，说明程序陷入了局部最优。由算法设计部分，我们知道当迭代次数大于总次数的一半的时候，为了更新到更好的解，我们将邻域进行了扩大。这才使得其能跳出局部最优值。使得最优解更新了一次，然而t表长度还是太小，所以程序又会陷入另一个循环中。因此得不到较好的解。t表长度 = 35268422002089155715541562116376168581691516996表2t表长度=35中间迭代数据下图为最终结果:图7 t表长度=35最终结

11、果可以看出解的结果非常理想。事实上通我们多次运行得到的经验，当解的结果小于17000的时候就已经非常好了。而通过中间迭代过程我们可以发现在1554次迭代的时候，结果已经小于17000了。因此当禁忌表选择合适时，能够更好的使解逼近实际最优值。t表长度 = 13574757680811804417868177301753317254表3 t表长度=35中间迭代数据图8 t表长度=135最终结果可以看出结果并不是很理想，由中间过程可以看出，当迭代次数大于81次的时候。解的结果基本已经不再改变。这时因为禁忌表过长，导致很难进行局部的细致搜索。所以不容易找到更好的解。4.2.3禁忌对象对解的影响前面的研

12、究分析主要是在禁忌对象为“解的移动”条件下，因此这里不再进行细致的讨论。仅对另外两种禁忌对象进行分析。下面是另外两种禁忌对象下，程序运行的结果：图9 禁忌对象为解的运行结果图10 禁忌对象为目标值的运行结果这里选取t表长度为1000是为了说明突出它们和禁忌对象为“解的移动”之间的不同，即禁忌空间的大小。禁忌对象为“解的移动”时，被禁忌的步骤总共也就在500个左右。也就是说如果禁忌对象为“解的移动”时，如果设置的禁忌长度超过600，那么运行过程中一定会因为全部步骤被禁忌而停止。但是如果禁忌对象为“解”或者“目标值”时，由于其禁忌空间非常大，所以很难出现全部解被禁忌的情况。这使得我们禁忌表必须很长以保证禁忌表和禁忌空间一定的比例。否则禁忌表对解的影响非常小。因此后两种禁忌方式所需要的内存空间较大。另外，经过多次运行，发现采用后两种禁忌对象，也很难得到较为理想的解。因此得到结论，当禁忌对象为“解的移动”时，算法最为理想。