第2期 周蓝海，等：TSP冰晶算法 ·171· 用其轨道行为的不可预测性，对系统初始状态极端 敏感的依赖性，，来获得具有混沌态特征的TSP路 径并获得了可信的成绩.很多自然界中的物理明显 地是以分形的形式生成的，分支重复地分裂产生更 小的分支，，特别是最原始的植物，像地衣、苔藓、 海藻，看起来都像分形，冰晶生长也是一样的.总的 来说，这一方法和试验的结果还是可取的 4结束语 针对TSP问题，采用冰晶算法进行了路径生成 图5ch150简单分形后路径 试验，简单分形扰动后试验结果的平均比一般在 Fig.5 Fractal ch152 routiag 4.00%以下，对TSP问题的求解比较有效，并且冰 晶算法的较低时间复杂度和计算的可并行性保证了 它求解的高效性 同时也可看出，该算法得到的可行解都具有一 个特点：就是路径围出一个单连通区域，实际上 TSP问题的解显然没有此限制，也就是说该算法在 TSP问题整个解空间的一个子空间中寻找可行解， 而最（次）优解是不是就在这个子空间中有待进一步 验证，如果不是，即便加入扰动，也不能从根本上解 决该问题，得到的结果只是一般意义上的可行解. 目前还不能证明该算法的有效程度，可以参考 的是：支撑树加完美匹配算法是到目前为止所见到 的，具有最好性能保证的多项式时间近似算法山 其时间复杂度为O(m),其路径长度满足STM() (a)TSPLIB提供的 (b)冰品算法计算结果 A.5OPT(),STM()表示该算法找到环游的 Gr202参考解 权，OPT()表示最优环游权.而其他贪婪算法一般 图6Gr202参考路径 时间复杂度为O()所得环游的权不会大于最优环 Fig.6 Gr202 referenced routing 游权的2倍 在时间开销上，这里不做详细比较.在普通的 对于有疑问的路径，简单分析一下TSPL IB提 PC机上，包含路径图像动态显示的时间开销在内， 供的Gr202参考解，见图6(a)所示，该路径长度为 冰晶算法在小于1s的时间可以轻松地计算500个 550,路径不存在交叉，整体结构紧凑，不存在明显的 城市的TSP问题，而以速度和可靠性著称的弹性网 路径问题，相对比较饱和光滑，但不足的是路径中保 络时间开销接近120s.其他算法，如蚂蚁算法就更 留了一条很长的边，并且由于该边的出现导致路径 长一些 的右上角出现了一个锯齿，如圆圈标记所示 冰晶算法是一种对自然智能简单的模拟，试验 冰晶算法的计算结果见图6(b)所示，跟参考解 数据的有限和单一特征的模拟，使得试验结果存在 不同的地方比较明显，主要是保留了2条比较长的 一定的不足，同时，也看到随着城市数量的增加，计 边，如圆圈标记所示.整体比较光滑，局部存在的路 算的结果与参考解的比例有增大的趋向，进一步的 径缺陷人脑比较难识别，路径长度为495，比 实验表明它受线性扰动强度和扰动范围的影响，当 TSPL IB提供的参考路径短10%. 城市数量增加后，通过增大线性扰动O(k)中的系 通过对68个TSPL IB不同数据的测试分析，平 数k一般可以获得更好的解，“分形”可有效降低该 均比的分布情况比较均衡，ulysses16获得了 情况下获得可行解的难度.目前，冰晶算法在降低时 0.12%的成绩.随线性约束的增加，计算结果不断降 间开销、降低空间开销提高准确度所碰到的主要障 低，采用分形思想来实现对冰晶生长过程的扰动，利 碍是跟计算几何相关的问题没有得到很好解决，下 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net对于有疑问的路径 ,简单分析一下 TSPL IB 提 供的 Gr202 参考解 ,见图 6 (a) 所示 ,该路径长度为 550 ,路径不存在交叉 ,整体结构紧凑 ,不存在明显的 路径问题 ,相对比较饱和光滑 ,但不足的是路径中保 留了一条很长的边 ,并且由于该边的出现导致路径 的右上角出现了一个锯齿 ,如圆圈标记所示. 冰晶算法的计算结果见图 6 (b) 所示 ,跟参考解 不同的地方比较明显 ,主要是保留了 2 条比较长的 边 ,如圆圈标记所示. 整体比较光滑 ,局部存在的路 径缺 陷 人 脑 比 较 难 识 别 , 路 径 长 度 为 495 , 比 TSPL IB 提供的参考路径短 10 %. 通过对 68 个 TSPL IB 不同数据的测试分析 ,平 均比 的 分 布 情 况 比 较 均 衡 , ulysses16 获 得 了 0112 %的成绩. 随线性约束的增加 ,计算结果不断降 低 ,采用分形思想来实现对冰晶生长过程的扰动 ,利 用其轨道行为的不可预测性 ,对系统初始状态极端 敏感的依赖性[9 ] ,来获得具有混沌态特征的 TSP 路 径并获得了可信的成绩. 很多自然界中的物理明显 地是以分形的形式生成的 ,分支重复地分裂产生更 小的分支[10 ] ,特别是最原始的植物 ,像地衣、苔藓、 海藻 ,看起来都像分形 ,冰晶生长也是一样的. 总的 来说 ,这一方法和试验的结果还是可取的. 4 结束语 针对 TSP 问题 ,采用冰晶算法进行了路径生成 试验 ,简单分形扰动后试验结果的平均比一般在 4100 %以下 ,对 TSP 问题的求解比较有效 ,并且冰 晶算法的较低时间复杂度和计算的可并行性保证了 它求解的高效性. 同时也可看出 ,该算法得到的可行解都具有一 个特点 : 就是路径围出一个单连通区域 ,实际上 TSP 问题的解显然没有此限制 ,也就是说该算法在 TSP 问题整个解空间的一个子空间中寻找可行解 , 而最(次) 优解是不是就在这个子空间中有待进一步 验证 ,如果不是 ,即便加入扰动 ,也不能从根本上解 决该问题 ,得到的结果只是一般意义上的可行解. 目前还不能证明该算法的有效程度 ,可以参考 的是 :支撑树加完美匹配算法是到目前为止所见到 的 ,具有最好性能保证的多项式时间近似算法[11 ] , 其时间复杂度为 O ( n 3 ) ,其路径长度满足 STM (Ι) ≤115 OPT (Ι) , STM (Ι) 表示该算法找到环游的 权 ,OPT(Ι) 表示最优环游权. 而其他贪婪算法一般 时间复杂度为 O( n 2 ) 所得环游的权不会大于最优环 游权的 2 倍. 在时间开销上 ,这里不做详细比较. 在普通的 PC 机上 ,包含路径图像动态显示的时间开销在内 , 冰晶算法在小于 1 s 的时间可以轻松地计算 500 个 城市的 TSP 问题 ,而以速度和可靠性著称的弹性网 络时间开销接近 120 s. 其他算法 ,如蚂蚁算法就更 长一些. 冰晶算法是一种对自然智能简单的模拟 ,试验 数据的有限和单一特征的模拟 ,使得试验结果存在 一定的不足 ,同时 ,也看到随着城市数量的增加 ,计 算的结果与参考解的比例有增大的趋向 ,进一步的 实验表明它受线性扰动强度和扰动范围的影响 ,当 城市数量增加后 ,通过增大线性扰动 O ( k n) 中的系 数 k 一般可以获得更好的解 “, 分形”可有效降低该 情况下获得可行解的难度. 目前 ,冰晶算法在降低时 间开销、降低空间开销、提高准确度所碰到的主要障 碍是跟计算几何相关的问题没有得到很好解决 ,下 第 2 期 周蓝海 ,等 : TSP 冰晶算法 ·171 ·