智能系统学报 第2卷 为了进一步验证本文算法的有效性，在TSP问 3 实验结果 题典型范例上进行了大量的实验.表2是不同算法 本节对新算法的性能进行测试，并将测试结果 运行得到的实验结果.在表2中，最优解是指获得的 与基本的ACS算法及PDACO算法进行了比较.实 最短路径长度，进化代数是指当得到表2中的结果 验中所使用的多个TSP问题的数据来源于 时，蚂蚁的周游代数(10次实验的平均取整).从结 TSPLIB标准库(http://elib.zib.de/pub/mp 果可见，对于oliver30问题，3种算法都能得到最优 testdata/tsp/.tsplib/tsplib.html).算法用 解，但所需要的迭代次数和运行时间各不相同，ACS Visual C++语言编程实现，实验的参数均通过实 算法的迭代次数和运行时间最大，PDACO算法的 验确定，表1为获得下面实验结果所使用的参数表. 迭代次数和运行时间较ACS算法有明显改进，而本 文算法在迭代次数和运行时间上又有进一步的改 表1不同TSP范例所使用的参数配置 进.类似地，在其他3个问题上本文算法在迭代次数 Table 1 Para meter deployments used in experiments 和运行时间上都有显著的改进.而且，在较少的进化 for several TSP problems 代数和较短的运行时间内，本文算法在oliver.30、 TSP问题的 实验时使用的参数 bays29、dantzig42问题上都得到了各自的最优解， 典型范例1.pQQ' a B 在berlin52问题上也得到了更接近于最优解的结 oliver.300.856001.5305510.4/8 果 表3为不同算法在各种TSP问题上的单次运 bays290.856002.030.5510.4w8 行时间比较，从实验结果可以看出：正如在算法计算 复杂度中所分析的那样，由于PDACO算法和本文 dantzig420.854502.040.510.48 算法都包含扩散模型的建立与计算，故单次迭代的 berlin52 0.8 57002.54055 1 0.4四8 运行时间都较ACS算法有所增加，而本文算法与 PDACO算法相比，由于具有相当的单次计算复杂 度，故在单次迭代的运行时间上非常接近， 表2 各种ISP问题上不同算法的结果比较 Table 2 Comparison of results among different algorithms for several TSP problems ACS算法 PDACO算法 本文算法 问题的 典型范例 最优解 得到的 所需进 运行时 得到的 所需进 运行时 得到的 所需进 运行时 最优解 化代数 间/s 最优解 化代数 间/s 最优解 化代数 间/s oliver30 423.74 423.74 830 1245 423.74 76.00 3.8 423.74 1.68 bays292020.002034.00 955 13.30 2028.00 132.00 5.6 2020.00 46 2.00 dantzig42699.00714.00 896 37.60 712.00 174.00 23.1 699.00 61 8.20 berlin:527542.007681.45 1754 147.307663.59316.00 90.2 7544.37 82 23.80 表3不同算法在各种SP问题上的单次运行时间比较 Table 3 Comparison of time consumption of a single cycle among different algorithms for several TSP problems ACS算法 PDACO算法 本文算法 问题的 典型范例 最优解 每次迭代的 每次迭代的 每次迭代的 得到的最优解 得到的最优解 得到的最优解 运行时间/s 运行时间/s 运行时间/s oliver30 423.74 423.74 0.01500 423.74 0.05000 423.74 0.05100 bays292020.00 2034.00 0.01393 2028.00 0.04242 2020.00 0.04348 dantig42 699.00 714.00 0.04196 712.00 0.13276 699.00 0.13443 berlin527542.00 7681.45 0.08398 7663.59 0.28544 7544.37 0.29024 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net3 实验结果 本节对新算法的性能进行测试 ,并将测试结果 与基本的 ACS 算法及 PDACO 算法进行了比较. 实 验中 所 使 用 的 多 个 TSP 问 题 的 数 据 来 源 于 TSPL IB 标 准 库 ( http :/ / elib. zib. de/ p ub/ mp2 testdata/ tsp/ tsplib/ tsplib. html ) . 算 法 用 Visual C + + 语言编程实现 ,实验的参数均通过实 验确定 ,表 1 为获得下面实验结果所使用的参数表. 表 1 不同 TSP 范例所使用的参数配置 Table 1 Parameter deployments used in experiments for several TSP problems TSP 问题的 典型范例 实验时使用的参数 1 - ρ Q Q′ α β q0 ω γ θ oliver30 018 5 600 115 3 0155 1 014 π/ 8 bays29 018 5 600 210 3 0155 1 014 π/ 8 dantzig42 018 5 450 210 4 015 1 014 π/ 8 berlin52 018 5 700 215 4 0155 1 014 π/ 8 为了进一步验证本文算法的有效性 ,在 TSP 问 题典型范例上进行了大量的实验. 表 2 是不同算法 运行得到的实验结果. 在表 2 中 ,最优解是指获得的 最短路径长度 ,进化代数是指当得到表 2 中的结果 时 ,蚂蚁的周游代数 (10 次实验的平均取整) . 从结 果可见 ,对于 oliver30 问题 ,3 种算法都能得到最优 解 ,但所需要的迭代次数和运行时间各不相同 ,ACS 算法的迭代次数和运行时间最大 ,PDACO 算法的 迭代次数和运行时间较 ACS 算法有明显改进 ,而本 文算法在迭代次数和运行时间上又有进一步的改 进. 类似地 ,在其他 3 个问题上本文算法在迭代次数 和运行时间上都有显著的改进. 而且 ,在较少的进化 代数和较短的运行时间内 ,本文算法在 oliver30、 bays29、dantzig42 问题上都得到了各自的最优解 , 在 berlin52 问题上也得到了更接近于最优解的结 果. 表 3 为不同算法在各种 TSP 问题上的单次运 行时间比较 ,从实验结果可以看出 :正如在算法计算 复杂度中所分析的那样 ,由于 PDACO 算法和本文 算法都包含扩散模型的建立与计算 ,故单次迭代的 运行时间都较 ACS 算法有所增加 ,而本文算法与 PDACO 算法相比 ,由于具有相当的单次计算复杂 度 ,故在单次迭代的运行时间上非常接近. 表 2 各种 TSP 问题上不同算法的结果比较 Table 2 Comparison of results among different algorithms for several TSP problems 典型范例 问题的 最优解 ACS 算法 PDACO 算法 本文算法 得到的 最优解 所需进 化代数 运行时 间/ s 得到的 最优解 所需进 化代数 运行时 间/ s 得到的 最优解 所需进 化代数 运行时 间/ s oliver30 423174 423174 830 12145 423174 76100 318 423174 33 1168 bays29 2 020100 2 034100 955 13130 2 028100 132100 516 2 020100 46 2100 dantzig42 699100 714100 896 37160 712100 174100 2311 699100 61 8120 berlin52 7 542100 7 681145 1 754 147130 7 663159 316100 9012 7544137 82 23180 表 3 不同算法在各种 TSP问题上的单次运行时间比较 Table 3 Comparison of time consumption of a single cycle among different algorithms for several TSP problems 典型范例 问题的 最优解 ACS 算法 PDACO 算法 本文算法 得到的最优解 每次迭代的 运行时间/ s 得到的最优解 每次迭代的 运行时间/ s 得到的最优解 每次迭代的 运行时间/ s oliver30 423174 423174 01015 00 423174 01050 00 423174 01051 00 bays29 2 020100 2 034100 01013 93 2 028100 01042 42 2 020100 01043 48 dantig42 699100 714100 01041 96 712100 01132 76 699100 01134 43 berlin52 7 542100 7 681145 01083 98 7 663159 01285 44 7 544137 01290 24 ·6 · 智 能 系 统 学 报 第 2 卷