3.4 参数设置和数值实验分析

本节用TSPLIB中的TSP算例来测试FGPACO算法。沿用TSPLIB中的记法，算例中的数字表示城市的数目（算例ft70的城市数目是70，算例kro124p是个例外，它的城市数目是100）。在实现算法时，用一张表记录已经选用的城市，而用另一张表记录未被选用的城市。

3.4.1 参数设置

算法中涉及的参数有信息素的初始值、奖励级别数、最大级别数M、参数β和τmax。下面分析参数对算法性能的影响。在实验中，只改变一个参数，而保持其他参数不变。在对算例测试时，β=5，信息素的初始值取为最大值的1/2。算法运行10次，迭代次数为2500，蚂蚁数为25。函数g（x）=。

1）最大级别数M

表3-2给出了M取不同值时的实验结果。由表中的结果可见，在M等于10000时，平均值较大。这时M值较大而奖励级别数小导致信息素变化小，算法表现出盲目随机性。因此，在M较大时，r2应取较大的数。对于算例eil51, M取其他4个数值时，偏差很小；对于算例ry48p, M取值为50、100、1000时，偏差很小。结果表明，有限个级别能保证算法收敛到较好的结果，并且算法具有较好的鲁棒性。

2）信息素上界τmax

τmax是影响算法性能的一个重要的量。如果其取值较大，则算法可能停滞；而如果其取值过小，则会减弱算法的开发能力。表3-3给出了τmax不同时的实验结果。由表中结果可见，当N≤τmax≤6N时，两个算例的偏差都小于1%。而当τmax取值为10、1000或者3000时，偏差较大。尤其是算例ry48p的实验结果，在当τmax取值为10或3000时，偏差都大于2.0%。

3）奖励级别数r2

在前面的分析中已经知道M较大时，r2应取较大的数，反之，M较小时，r2应取较小的数。表3-4给出了r2不同时的实验结果。r2较小的两个算例结果较好。但算例eil51表明r2越小，结果不一定越好。

图3-1是在信息素上界τmax=50、最大级别数M=50、奖励级别数r2=3时，算例ry48p的实验结果（因为前500次迭代已找到较好的解，仅给出前500次迭代结果）。由图3-1可见，算法收敛速度较快，并且表现出较好的搜索能力。

图3-2是在信息素上界τmax=50、最大级别数M=50、奖励级别数r2=3时的算例eil51实验结果（同样地，仅给出前500次迭代结果）。由图3-2可见，“锯齿”较多，这意味着算法能较快地搜索到更好的解。这再一次表明算法具有较好的搜索能力。

3.4.2 与其他改进蚁群算法的比较

依照文献[5]中提议的方式进行测试和比较，每个算例构造10000 kN次解，对于TSP, k=1，对于ATSP, k=2, N表示城市数目。奖励级别数r2=3，最大级别数M=50。下面比较FGPACO与MMAS、MMAS+pts（具有信息素平滑机制的MMAS）、ACS、AS的性能，后3类算法的参数设置与数据引自文献[5]。前4个算例中，在ft70和kro124p算例中，。由表3-5可知，ft70算例结果与最优结果很接近，对于其他算例，FGPACO算法比其他算法的平均结果好。结果表明算法是有效的，且算法不易于早熟收敛。