·170· 智能系统学报 第3卷 冰晶计算的过程中添加“扰动”后的计算结果比参考 图5是通过扰动对路径进行了一些线性优化， 解高出的百分比，所谓的线性扰动，指的是运算代价 路径比较光顺饱和，没有剧烈的路径锯齿现象，消除 在时间复杂度小于O(km)的前提下，做一些额外的 了图4中偏下位置不是最佳连接点的路，径路径长 条件判断来改善冰晶的生长过程，降低路径的长度 度由7214缩短为6648（最优路径为6528），见图 “分形”表示对单一冰晶算法的计算结果做简单分 5,简单分形后路径比参考路径长度高出的比例小于 形，并做高次扰动后所获得的解 2.00%. 不难看出，蚂蚁、遗传等算法的平均比一般在 表3冰晶模型扰动前后的试验结果 5.00%以下，不考虑时间开销因素，迭代次数和迭代 Table 3 Results of the Crystal model 群体数目适当增加的话，计算的效果可能更好一点。 TSP 冰晶分形参考解 TSP冰晶分形参考解 冰晶算法通过增加线性扰动适当降低与最优值的差 att48224219 33523 Pb1173160862456892 距，最终的计算结果平均比为3.449%，这样的计算 A28011.33487 2586 P-763431.15108159 结果有一定的实用意义.高次扰动可以获得更好的 Bayg29 1.860.22 9074 Pr107 2.560.1944303 结果，但扰动次数增加到一定程度后，时间开销很 Berlin526322.68 7544 Pr12450302659030 大，运算结果却基本保持不变，目前主要通过寻找其 Ch1305.681.39 6110 P-13648921996772 他的线性扰动快速获取可行解」 Ch150 5.191.67 6532 Pr14433513458537 天然冰晶的形成过程是复杂的，是一个非平衡 D198 6233.24 15780 Pr1521.581.3173682 态的相变过程，热力环境的不同，生长驱动力的支 D493 8793.56 35002 Pr2261.4205980369 配，非平衡晶界偏聚以及降温速率，偏析，反偏析， D657 13.19484 48912 Pr26468903149135 晶间脆性等现象导致晶体生长形态的多样性，也导 D1291 16595.30 50801 P2999.1647348191 致TSP可行解的多样性 D165511.705.15 62128 P-439682301107217 D2103 5.974.80 80450 Pr100212.287.05259066 dantzig420.14014 699 Rat992.730991211 ds100013865.2018660188别Rat1958.145422323 eil51 1093209 430 Rat57511.104996773 176 5.87294 545 Rat78312.505218806 E101 4.83218 642 Rd1007.05315 7910 H417623254 11861 Rd40011.6944315281 FH14006323.02 20127 130415989.56252948 图4ch150无扰动路径 G2629.503.24 2378 18891589863316536 Fig 4 Undisturbed ch150 routing Gr96 5.86254 512 S704281.47678 Gr1204381.98 1666 Tp22510995233859 计算机模拟的冰晶可以对这些自然现象进行优 kroA1005.31004 21285 U15913.517.9742080 化，适当的扰动阀值对凝固过程进行枝晶破碎，晶粒 KoA1507.94271 26524 U5749.8848136905 细化和晶格重组，理论上获得一定的晶体完整性.跟 KoA2004.191.66 29368 U72411.6756941910 其他算法相比，冰晶计算结果是值得信赖的，U2319 KoB1503.311.17 26130 U106012.45572224094 中对2139个城市进行计算，结果为3.38%，其计算 KoB2007.82254 29437 U14321099516152970 过程的高效性、健壮性，为快速解决TSP问题提供 kroC1002711.31 20750 U1817129962157201 了一个良好的途径 kroD1002.731.4721294 U215214.1680464253 下面对ch150城市的TSP生成的轨迹作一下 kroE1004.962.67 22068 U23191024338234256 分析 Lin105 4160.54 14382 ulysses161.34012741087 图4是无扰动的路径，画圆圈处表示存在问题 Lin3189.463.73 42029 ulysses2204604675665 的路径，可以看出，一些路径显然不是很好：如左上 nrw137914.315.84 56638 vm108416757.53239297 角有一个很明显的锯齿.中偏下位置有一个点不是 Pb4429.584.7450783 Vm174816657.83336556 最佳连接.在其他数据的测试过程中，也发现了类似 注：“冰晶”的平均比为8006%，“分形”后为3.449% 的现象 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net冰晶计算的过程中添加“扰动”后的计算结果比参考 解高出的百分比 ,所谓的线性扰动 ,指的是运算代价 在时间复杂度小于 O ( kn) 的前提下 ,做一些额外的 条件判断来改善冰晶的生长过程 ,降低路径的长度. “分形”表示对单一冰晶算法的计算结果做简单分 形 ,并做高次扰动后所获得的解. 不难看出 ,蚂蚁、遗传等算法的平均比一般在 5100 %以下 ,不考虑时间开销因素 ,迭代次数和迭代 群体数目适当增加的话 ,计算的效果可能更好一点. 冰晶算法通过增加线性扰动适当降低与最优值的差 距 ,最终的计算结果平均比为 31449 % ,这样的计算 结果有一定的实用意义. 高次扰动可以获得更好的 结果 ,但扰动次数增加到一定程度后 ,时间开销很 大 ,运算结果却基本保持不变 ,目前主要通过寻找其 他的线性扰动快速获取可行解. 天然冰晶的形成过程是复杂的 ,是一个非平衡 态的相变过程 ,热力环境的不同 ,生长驱动力的支 配 ,非平衡晶界偏聚[9 ]以及降温速率 ,偏析 ,反偏析 , 晶间脆性等现象导致晶体生长形态的多样性 ,也导 致 TSP 可行解的多样性. 图 4 ch150 无扰动路径 Fig14 Undisturbed ch150 routing 计算机模拟的冰晶可以对这些自然现象进行优 化 ,适当的扰动阀值对凝固过程进行枝晶破碎 ,晶粒 细化和晶格重组 ,理论上获得一定的晶体完整性. 跟 其他算法相比 ,冰晶计算结果是值得信赖的 ,U2319 中对 2 139 个城市进行计算 ,结果为 3138 % ,其计算 过程的高效性、健壮性 ,为快速解决 TSP 问题提供 了一个良好的途径. 下面对 ch150 城市的 TSP 生成的轨迹作一下 分析. 图 4 是无扰动的路径 ,画圆圈处表示存在问题 的路径 ,可以看出 ,一些路径显然不是很好 :如左上 角有一个很明显的锯齿. 中偏下位置有一个点不是 最佳连接. 在其他数据的测试过程中 ,也发现了类似 的现象. 图 5 是通过扰动对路径进行了一些线性优化 , 路径比较光顺饱和 ,没有剧烈的路径锯齿现象 ,消除 了图 4 中偏下位置不是最佳连接点的路 ,径路径长 度由 7 214 缩短为 6 648 (最优路径为 6 528) ,见图 5 ,简单分形后路径比参考路径长度高出的比例小于 2100 %. 表 3 冰晶模型扰动前后的试验结果 Table 3 Results of the Crystal model TSP 冰晶 分形 参考解 TSP 冰晶 分形 参考解 att48 2124 2119 33523 Pcb1173 16108 6124 56 892 A280 11133 4187 2 586 Pr76 3143 1115 108 159 Bayg29 1186 0122 9 074 Pr107 2156 0119 44 303 Berlin52 6132 2168 7 544 Pr124 5103 0126 59 030 Ch130 5168 1139 6 110 Pr136 4189 2119 96 772 Ch150 5119 1167 6 532 Pr144 3135 1134 58 537 D198 6123 3124 15 780 Pr152 1158 1131 73 682 D493 8179 3156 35 002 Pr226 1142 0159 80 369 D657 13119 4184 48 912 Pr264 6189 0131 49 135 D1291 16159 5130 50 801 Pr299 9116 4173 48 191 D1655 11170 5115 62 128 Pr439 6182 3101 107 217 D2103 5197 4180 80 450 Pr1002 12128 7105 259 066 dantzig42 0114 0114 699 Rat99 2173 0199 1 211 dsj1000 13186 5120 18 660 188 Rat195 8114 5142 2 323 eil51 10193 2109 430 Rat575 11110 4199 6 773 Eil76 5187 2194 545 Rat783 12150 5121 8 806 Eil101 4183 2118 642 Rd100 7105 3115 7 910 Fl417 6123 2154 11 861 Rd400 11169 4143 15 281 Fl1400 6132 3102 20 127 Rl1304 15198 9156 252 948 Gil262 9150 3124 2 378 Rl1889 15189 8163 316 536 Gr96 5186 2154 512 St70 4128 1147 678 Gr120 4138 1198 1 666 Tsp 225 10199 5123 3 859 kroA100 5131 0104 21 285 U159 13151 7197 42 080 KroA150 7194 2171 26 524 U574 9188 4181 36 905 KroA200 4119 1166 29 368 U724 11167 5169 41 910 KroB150 3131 1117 26 130 U1060 12145 5172 224 094 KroB200 7182 2154 29 437 U1432 10199 5116 152 970 kroC100 2171 1131 20 750 U1817 12199 6121 57 201 kroD100 2173 1147 21 294 U2152 14116 8104 64 253 kroE100 4196 2167 22 068 U2319 10124 3138 234 256 Lin105 4116 0154 14 382 ulysses16 1134 0112 74 108 7 Lin318 9146 3173 42 029 ulysses22 0146 0146 75 665 nrw1379 14131 5184 56 638 vm1084 16175 7153 239 297 Pcb442 9158 4174 50 783 Vm1748 16165 7183 336 556 注“: 冰晶”的平均比为 81006 %“, 分形”后为 31449 %. ·170 · 智 能 系 统 学 报 第 3 卷