智能优化方法作业中国城市TSP问题TS解法文档格式.docx
《智能优化方法作业中国城市TSP问题TS解法文档格式.docx》由会员分享，可在线阅读，更多相关《智能优化方法作业中国城市TSP问题TS解法文档格式.docx（13页珍藏版）》请在冰点文库上搜索。
第二章算法准备
2.1数据搜集
中国城市省会经纬度数据见“中国城市经纬度.txt”
2.2距离计算
地球是一个近乎标准的椭球体，它的赤道半径为6378.140千米，极半径为6356.755千米，平均半径6371.004千米。
如果我们假设地球是一个完美的球体，那么它的半径就是地球的平均半径，记为R。
如果以0度经线和0度纬线为基准，那么根据地球表面任意两点的经纬度就可以计算出这两点间的地表距离（这里忽略地球表面地形、海拔高度对计算带来的误差，仅仅是理论上的估算值）。
设第一点A的经纬度为（LonA,LatA），第二点B的经纬度为（LonB,LatB），按照0度经线的基准，东经取经度的正值（Longitude），西经取经度负值（-Longitude），北纬取90-纬度值（90-Latitude），南纬取90+纬度值（90+Latitude），则经过上述处理过后的两点被计为（MLonA,MLatA）和（MLonB,MLatB）。
那么根据三角推导或者三维空间向量数量积公式，可以得到计算两点距离的如下公式：
式一
这里，R和
单位是相同，如果是采用6371.004千米作为半径，那么
就是千米为单位。
特殊的，如果城市均分布在北半球（南半球只有澳洲才有意义）。
可以仅对经度作正负处理，而不对纬度作正负处理，公式可以变换如下：
式二
这里我们使用式二作为距离计算公式。
第三章算法设计
3.1解及目标函数的表达
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号城市为起始地点解[2,3,4,1]的目标值相同。
即每一个解都有n-1个和它相同的解，它们只是编码形式不同。
这相当于在这种采用自然数对解进行编码的方式，将解的空间扩大了n倍（n为城市个数）。
为了将解空间缩小，我们可以任意指定一个城市作为起始城市。
这样在以该城市为起始位置的解的空间中没有重复解。
因此，当我们随机得到一个初始解后，在接下来的邻域计算中不移动第一个城市。
然而，当迭代步骤过半的时候，这时候为了更新到更好的最优解，我们需要将解空间扩大n倍，因此这时候需要移动第一个城市，以便获得更大的邻域。
3.3禁忌表
3.3.1禁忌对象
禁忌对象大体分为三种方式，分别为：
解的移动、解、目标值。
这里分别讨论三种方式对算法的影响。
3.3.2禁忌表的编码形式
根据禁忌对象的不同，禁忌表的编码形式也不同。
3.3.3禁忌对象为解的移动
对于禁忌对象为解的移动，可以直接采样n×
n的矩阵进行编码。
其中表中i行j列上的元素表示i、j城市交换剩余被禁忌的次数。
禁忌表示意图如下：
其中n为城市个数。
可以看出该禁忌表同样为对称矩阵。
更新禁忌表时，首先将矩阵中大于零的数减一，然后再将新禁忌的交换步骤置为禁忌表长度即可。
3.3.4禁忌对象为目标值
对于禁忌对象为目标值的禁忌表，可以采用FIFO的队列表示。
相应的编码形式为一个一维数组。
数组长度为禁忌表的长度，其中索引最小的元素对应最新禁忌的目标值。
其中m为禁忌表长度。
当更新禁忌表时，将禁忌表中所有元素后移一位，最后一个元素移除，然后将新被禁忌的目标值放到禁忌表的最前面。
3.3.5禁忌对象为解
禁忌对象为解的禁忌表编码形式可以由两种，第一种是采用m×
其中m为禁忌表的长度，n为城市的个数。
这样表中的每一行表示一个解。
依然采用FIFO的编码形式即可。
上述这种编码形式占用的空间较大，而且相关操作实现也比较麻烦。
为了将二维禁忌表改成一维禁忌表，我们采用如下的编码方式：
假设其中的一个解为
，将其右乘以一个各个分量不相等的权值列向量
（这里取其为自然数序列，即
），即
易知，当q的各个分量不相等时。
和
是一一对应的关系。
所以我们可以将
作为该解的编码。
从而禁忌表的编码形式可以简化为一个一维的FIFO队列。
其中m为禁忌表的长度。
可以看出简化后的禁忌表编码和以目标值为对象的禁忌表编码形式相同，这也使编程实现的工作减少了许多。
3.4停止准则
停止准则采样固定的迭代次数。
第四章算法实现及分析
4.1编译环境及界面介绍
本次试验算法采用matlab进行实现。
matlab版本为R2013b.首先我们编写了一个m脚本文件进行调试（tsp_tabu.m）.在程序调试成功以后，为了方便讨论各个参数对算法的影响及对算法进行分析。
我们又编写了一个GUI界面（tsp_tabu_gui.fig）。
界面如下：
图2TSP算法GUI界面
在界面的左边参数设置区可以设置“迭代次数”（默认为3000）、t表长度（默认为35）。
在“禁忌对象”的下拉列表中一共有三个选项。
如下图所示：
图3禁忌对象下拉列表
当参数设置完毕后，点击开始运行按钮即可开始运行程序，下图是迭代过程中的运行情况：
图4GUI运行界面
在GUI运行的过程中，每当最优值改变时，均会在命令空间输出当前最优值和迭代的次数。
可以在命令空间来观测最优值的变化情况。
当程序运行完毕后，会在GUI界面显示目标值、运行时间以及路线图。
同时在命令空间也会输出最优值、最优解。
如果是因为所有邻域都被禁忌而停止，还会输出有关信息。
下面是GUI运行完毕时的画面：
图5GUI运行完毕时的画面
4.2算法分析
4.2.1迭代次数对算法的影响
通过几十次运行，我们发现当迭代次数大于1000次的时候。
最优解基本不发生改变，而当迭代次数大于2000次时，解变化的频率更少。
因此可以得出结论：
当迭代次数小于2000次时，最优值和迭代次数正相关。
而当迭代次数大于2000次时，最优解几乎不再随迭代次数而改变。
可能原因：
1.当经过1000次的迭代后，找到的解已经非常好了，因此很难再找到更好的解。
2.迭代运算进入了局部最优并无法循环出去。
4.2.2t表长度对算法的影响
这里以禁忌对象为“解的移动”，“迭代次数”为3000进行分析。
t表长度=10
下面为中间迭代过程中的最后部分数据：
迭代次数
155
180
181
1506
1562
最优值
19927
19838
19830
19788
17217
表1t表长度=10中间迭代数据
下图为最终结果：
图6t表长度=10最终结果
可以看出最终结果并不是很理想，而由中间迭代数据可以发现，当迭代次数为181的时候，很长一段时间最优解并没有更新，说明程序陷入了局部最优。
由算法设计部分，我们知道当迭代次数大于总次数的一半的时候，为了更新到更好的解，我们将邻域进行了扩大。
这才使得其能跳出局部最优值。
使得最优解更新了一次，然而t表长度还是太小，所以程序又会陷入另一个循环中。
因此得不到较好的解。
t表长度=35
2684
2200
2089
1557
1554
15621
16376
16858
16915
16996
表2t表长度=35中间迭代数据
下图为最终结果:
图7t表长度=35最终结果
可以看出解的结果非常理想。
事实上通我们多次运行得到的经验，当解的结果小于17000的时候就已经非常好了。
而通过中间迭代过程我们可以发现在1554次迭代的时候，结果已经小于17000了。
因此当禁忌表选择合适时，能够更好的使解逼近实际最优值。
t表长度=135
74
75
76
80
81
18044
17868
17730
17533
17254
表3t表长度=35中间迭代数据
图8t表长度=135最终结果
可以看出结果并不是很理想，由中间过程可以看出，当迭代次数大于81次的时候。
解的结果基本已经不再改变。
这时因为禁忌表过长，导致很难进行局部的细致搜索。
所以不容易找到更好的解。
4.2.3禁忌对象对解的影响
前面的研究分析主要是在禁忌对象为“解的移动”条件下，因此这里不再进行细致的讨论。
仅对另外两种禁忌对象进行分析。
下面是另外两种禁忌对象下，程序运行的结果：
图9禁忌对象为解的运行结果
图10禁忌对象为目标值的运行结果
这里选取t表长度为1000是为了说明突出它们和禁忌对象为“解的移动”之间的不同，即禁忌空间的大小。
禁忌对象为“解的移动”时，被禁忌的步骤总共也就在500个左右。
也就是说如果禁忌对象为“解的移动”时，如果设置的禁忌长度超过600，那么运行过程中一定会因为全部步骤被禁忌而停止。
但是如果禁忌对象为“解”或者“目标值”时，由于其禁忌空间非常大，所以很难出现全部解被禁忌的情况。
这使得我们禁忌表必须很长以保证禁忌表和禁忌空间一定的比例。
否则禁忌表对解的影响非常小。
因此后两种禁忌方式所需要的内存空间较大。
另外，经过多次运行，发现采用后两种禁忌对象，也很难得到较为理想的解。
因此得到结论，当禁忌对象为“解的移动”时，算法最为理想。
升级会员 