论文部分内容阅读
摘 要：蚁群算法是一种智能仿生算法，以TSP为例分析蚁群算法中的参数设置情况，蚁群算法中的参数较多，不同的参数组合都影响着蚁群算法的全局收敛性和收敛速度，同时也是蚁群算法研究的难点，且至今为止都没有完整的理论支持，只能依靠学者的经验或者大量的数据实验。该文主要通过仿真实验，依据每个参数对蚁群算法的最优路径的影响，最终得出每个参数较为合理的取值范围。且以TSP为例有较好的实用价值。
关键词：蚁群算法;参数设置;TSP
中图分类号：TP301.6 文献标识码：A 文章编号：2096-4706（2020）22-0095-05
Research on Parameter Setting in Ant Colony Algorithm
——Take TSP as an Example
XIANG Yongjing
（College of Information Engineering，Tongren Polytechnic College，Tongren 554300，China）
Abstract：Ant colony algorithm is an intelligent bionic algorithm，taking TSP as an example，the parameter setting of ant colony algorithm is analyzed. There are many parameters in ant colony algorithm，the different parameter combinations affect the global convergence and convergence speed of ant colony algorithm，and also the difficulty of ant colony algorithm research. So far there is no complete theoretical support，can only rely on the experience of scholars or a large number of data experiments. This paper mainly through simulation experiments，according to the impact of each parameter on the optimal path of the ant colony algorithm，and finally get a reasonable value range for each parameter. Taking TSP as an example，it has good practical value.
Keywords：ant colony algorithm;parameter setting;TSP
0 引 言
蟻群算法是受自然界蚂蚁的启发而得到的一种智能启发式算法，该算法具有良好的寻优能力、拓展性强、并行性和鲁棒性，其应用较为广泛，并且该算法在解决离散问题的同时也可以针对连续的问题，且均可以得到较好的解。本文是在基于蚁群算法求解最优旅游路径的研究课题中，发现蚁群算法的复杂性，而算法解的优劣很大程度上取决于算法中的参数设置，参数的选择决定着算法的最优解和收敛速度。并且没有相关完整的可行性参考文献提供参考，而这也是此算法进一步突破的关键点。故有本篇研究，为的是在使用蚁群算法寻求最优路径时参数选择有所依据，同时也为其他使用者在参数设置时提供一定的依据和参考。并且找到蚁群算法参数的合理范围，对于进一步推进蚁群算法的研究有重要的意义。
1 蚁群算法的基本理论
蚁群算法（Ant Colony Optimization，ACO），又称蚂蚁算法，是由Dorigo和Colorni等人提出的，得益于蚂蚁个体在寻找食物时，个体之间的相互协作运行方式所影响。以TSP为例，其主要思想是：假设有n个城市，m只蚂蚁，这m只蚂蚁能够以一定的概率来选择下一个城市，（t）为t时刻第k只蚂蚁从城市i到访问城市j的概率：
其中，τij（t）为t时刻路径（i，j）上的信息素含量;ηij（t）为t时刻路径（i，j）上的能见度，即路径（i，j）的启发信息，一般将其设为ηij=1/dij其中，dij为城市i到j之间的距离;allowedk为蚂蚁k下一步可以访问的城市;α为启发因子，表示信息素的相对重要程度（α≥0）;β为期望因子，表示能见度的重要性（β≥0）。并且蚂蚁在走过的这条线路上留下相应的信息素为：
其中，ρ为信息素的挥发系数（0<ρ<1），1-ρ为信息素的残留系数， 为蚂蚁k在路径（i，j）上留下的信息素含量，Δτij为一次循环结束，所有走过路径（i，j）上的蚂蚁留下的信息素的和。对于 的设置，Dorigo等给出了三种不同的计算方法，分别是ant-cycle、ant-quantity和ant-density模型，根据学者们的研究经验，ant-cycle模型即全局信息模型在求解过程中优于另外两个模型。ant-cycle模型为：
最终得到一条较优的链接n个城市的线路。
2 蚁群算法的参数分析
在蚁群算法中，需要设置大量的参数，参数的设置对算法的收敛速度和寻优能力均有影响，而且这些参数的设置至今没有完整的理论支持，只能依靠大量的实验测试和相关学者的经验来参考取舍，如文献[6]和大多数学者主要是以数据eil51 TSP为例，对ant-cycle的各个参数设置进行试验研究分析;文献[5]则是以数据TSP30为研究对象，对其中的参数设置进行研究分析。上述研究分别是针对不同规模的数据进行分析，没有通用的参考性。本文将从横向不同规模的数据和纵向单个数据来比较分析，利用TSPLIB测试库的实验数据为对象，主要对蚂蚁总数m、启发因子α、信息素挥发系数ρ和期望因子β进行分析。在研究参数对蚁群算法的性能时，统一采用的模型是ant-cycle模型，运行20次取平均和最小值。测试集有bayg29，berlin52、eil76和eil101，它们的城市规模分别为29、52、76和101。对于ant-cycle模型大多数学者认为最好的实验结果是m=n，0≤α≤5，0≤β≤5，0.10≤ρ≤0.99。 2.1 分析蚂蚁总数m
在蚁群算法中，主要是依靠蚂蚁对节点进行选择，信息的交流与协作，然后在更新信息素，从而得到较优解，其中是将蚂蚁分布在不同的城市上。在处理问题时，增加m的值时，会增加蚁群算法的全局搜索能力，但若m的值过大则会影响算法信息素的正反馈机制，从而导致收敛速度变慢，但若m的值过小，将加快算法的收敛速度，但容易陷入局部最优且全局搜索能力也会减弱。故需选择适当m值。文献[1]表明，当蚂蚁数目远远大于城市数量即m>>n时，再增加蚂蚁量对算法的性能有一定的提高，但效果不是很明显。杜衡吉[4]研究得出，当m∈[0.75n，1.50n]时（其中n为城市数量），既可以保证算法的收敛速度，也可以得到较好的解，且此结果与文献[2，3]一致。针对4组数据，固定m的取值，其他参数设置如表1所示。
图1是各测试集最优路径和蚂蚁数目之间的关系图，从图1可以看出，当蚂蚁数目很小的时候，算法不能得到最优解且其不稳定，当蚂蚁数目逐渐增加，能得到最优解且其波动的范围较小，但也可以发现如果蚂蚁数目大于城市数目之后仍持续增加，其最优解并没有得到较好的改善，反而增加了算法的运算量，降低了收敛速度。其中上面4组数据的最佳取值范围分别是m∈[0.85n，1.20n]、m∈[0.80n，1.20n]、m∈[0.80n，1.20n]和m∈[0.70n，n]。故可以总结为，当城市规模小于100时，m∈[0.85n，1.20n]即可得到较优的结果，当大于100后，m∈[0.70n，n]既可得到较优的结果，也可加快收敛速度，即螞蚁数目应取小于数据规模的值。
2.2 分析启发因子α
启发因子α反映的是蚂蚁在选择路径时信息素τij（t）的相对重要程度，其大小是信息素对蚂蚁选择路径的指导强度，也是蚂蚁在搜索路径中随机性的强度。α越大，表明前面积累的信息量对蚂蚁有很强的指导作用，随机性减弱，收敛速度加快，易陷入局部最优。反之，则随机性增强，收敛速度减慢，无法体现正反馈机制。陈文卓[5]研究表明，在n为30的情况下，当α∈[0.5，1.0]时，算法的整体性能较好;而文献[4，6]得出，在n为51的情况下，α∈[1.0，3.0]时，算法的整体性能较好。固定α的取值范围α=1.0：0.5：10.0，其他参数设置如表2所示。
在确定蚂蚁数目和启发式因子的范围的情况下，由以上理论和图2的仿真实验可知，启发式因子α过大或者过小都对算法的搜索和寻优造成不利的影响。对于上面4张图其α的最佳取值范围分别是α∈[1.0，4.5]、α∈[1.0，5.0]、α∈[1.0，3.0]和α∈[1.0，2.5]，即α的取值范围一般在α∈[1.0，3.0]时能取得较优的值。
2.3 分析期望因子β
期望因子β反映的是蚂蚁在选择路径时启发信息ηij（t）的相对重要程度，其大小是距离的倒数，反映了先验知识对蚂蚁选择路径的指导作用，也是蚂蚁在搜索路径中的确定性的因素。其值的大小影响着算法性能的优劣。文献[4]得出，算法在β∈{3，4，5}时，性能较好。文献[6]得出，在β∈{2，4}时效果较好，文献[5]得出，在β∈{2，3，4，5}时性能较好。固定期望因子β的取值范围为β=0.0：0.5：20.0，其他参数设置如表3所示。
由图3的仿真实验和以上理论可知，期望因子β是不宜过大也不宜过小，从图3可以看出，当β大于一定值时其波动性未发生明显的变化，说明其他的参数在影响着β的波动范围。通过图3中的四张图期望因子的最佳取值范围分别是β∈[1.0，2.5]、β∈[1.0，4.5]、β∈[1.0，4.5]和β∈[2，6]。
2.4 分析信息素挥发系数ρ
信息素挥发系数ρ表示信息素在路径上随着时间逐渐挥发的程度，随着迭代次数的增加，信息素将会累计。1-ρ表示信息素挥发之后剩下的部分信息素，值的大小间接反映了蚂蚁个体之间相互关系的强弱。ρ值过大，则路径上的信息素挥发就越多，这条路径上的信息素浓度就越淡，减小了蚂蚁之间的协作性，增强了算法的随机性和全局搜索能力;ρ值过小，路径上挥发的信息素较少，留下较多的信息素，增强了蚂蚁之间的协作，算法的正反馈机制加强，随机性减弱。对于这个参数几乎不同的作者得出的结果都不相同，分别有ρ∈{0.1，0.15，[0.3，0.5]，[0.5，0.8]}。固定信息素挥发系数ρ的取值范围ρ=0.00：0.05：0.95，其他参数的设置如表4所示。
由图4的仿真实验和以上理论可知，ρ值太大或者太小都会影响算法的全局搜索能力。通过图4可以看出，测试集bayg29的最佳取值范围为ρ∈[0.4，0.7]，测试集berlin52的最佳取值范围是ρ∈[0.3，0.7]，测试集eil76的最佳取值点为0.85，而测试集eil101的最佳取值点则为0.75。
3 结 论
在蚁群算法中，参数设置的优劣直接决定算法的性能。本文对蚁群算法的基本原理和仿真实验来分析参数的设置问题。得出结论：对于蚂蚁数目m，当城市规模小于100时，m∈[0.85n，1.20n]，当大于100时，m∈[0.70n，n]算法性能较好，且m 参考文献：
[1] 叶家琪，符强，贺亦甲，等.基于聚类集成的蚁群算法求解大规模TSP问题 [J].计算机与现代化，2020（2）：31-35.
[2] 杜玉红，张岩，赵焕峰.基于参数优化蚁群算法的机器人路径规划研究 [J].现代制造工程，2020（9）：7-14.
[3] 四川旅游学院.基于模糊蚁群算法的旅游线路优化方法：CN201911035554.4 [P].2019-10-29.
[4] 杜衡吉，李勇.蚁群算法中参数设置对其性能影响的研究 [J].现代计算机（专业版），2012（13）：3-7.
[5] 陈文卓，刘萍，姜丰，等.基于参数组合优化的救援机器人蚁群算法研究 [J].华北科技学院学报，2020，17（1）：71-76.
[6] 黄少荣.蚁群算法的参数选择研究 [J].电脑知识与技术，2010，6（20）：5588-5590.
作者简介：向永靖（1992—），女，侗族，贵州凯里人，讲师，硕士研究生，主要研究方向：数理统计、机器学习。
关键词：蚁群算法;参数设置;TSP
中图分类号：TP301.6 文献标识码：A 文章编号：2096-4706（2020）22-0095-05
Research on Parameter Setting in Ant Colony Algorithm
——Take TSP as an Example
XIANG Yongjing
（College of Information Engineering，Tongren Polytechnic College，Tongren 554300，China）
Abstract：Ant colony algorithm is an intelligent bionic algorithm，taking TSP as an example，the parameter setting of ant colony algorithm is analyzed. There are many parameters in ant colony algorithm，the different parameter combinations affect the global convergence and convergence speed of ant colony algorithm，and also the difficulty of ant colony algorithm research. So far there is no complete theoretical support，can only rely on the experience of scholars or a large number of data experiments. This paper mainly through simulation experiments，according to the impact of each parameter on the optimal path of the ant colony algorithm，and finally get a reasonable value range for each parameter. Taking TSP as an example，it has good practical value.
Keywords：ant colony algorithm;parameter setting;TSP
0 引 言
蟻群算法是受自然界蚂蚁的启发而得到的一种智能启发式算法，该算法具有良好的寻优能力、拓展性强、并行性和鲁棒性，其应用较为广泛，并且该算法在解决离散问题的同时也可以针对连续的问题，且均可以得到较好的解。本文是在基于蚁群算法求解最优旅游路径的研究课题中，发现蚁群算法的复杂性，而算法解的优劣很大程度上取决于算法中的参数设置，参数的选择决定着算法的最优解和收敛速度。并且没有相关完整的可行性参考文献提供参考，而这也是此算法进一步突破的关键点。故有本篇研究，为的是在使用蚁群算法寻求最优路径时参数选择有所依据，同时也为其他使用者在参数设置时提供一定的依据和参考。并且找到蚁群算法参数的合理范围，对于进一步推进蚁群算法的研究有重要的意义。
1 蚁群算法的基本理论
蚁群算法（Ant Colony Optimization，ACO），又称蚂蚁算法，是由Dorigo和Colorni等人提出的，得益于蚂蚁个体在寻找食物时，个体之间的相互协作运行方式所影响。以TSP为例，其主要思想是：假设有n个城市，m只蚂蚁，这m只蚂蚁能够以一定的概率来选择下一个城市，（t）为t时刻第k只蚂蚁从城市i到访问城市j的概率：
其中，τij（t）为t时刻路径（i，j）上的信息素含量;ηij（t）为t时刻路径（i，j）上的能见度，即路径（i，j）的启发信息，一般将其设为ηij=1/dij其中，dij为城市i到j之间的距离;allowedk为蚂蚁k下一步可以访问的城市;α为启发因子，表示信息素的相对重要程度（α≥0）;β为期望因子，表示能见度的重要性（β≥0）。并且蚂蚁在走过的这条线路上留下相应的信息素为：
其中，ρ为信息素的挥发系数（0<ρ<1），1-ρ为信息素的残留系数， 为蚂蚁k在路径（i，j）上留下的信息素含量，Δτij为一次循环结束，所有走过路径（i，j）上的蚂蚁留下的信息素的和。对于 的设置，Dorigo等给出了三种不同的计算方法，分别是ant-cycle、ant-quantity和ant-density模型，根据学者们的研究经验，ant-cycle模型即全局信息模型在求解过程中优于另外两个模型。ant-cycle模型为：
最终得到一条较优的链接n个城市的线路。
2 蚁群算法的参数分析
在蚁群算法中，需要设置大量的参数，参数的设置对算法的收敛速度和寻优能力均有影响，而且这些参数的设置至今没有完整的理论支持，只能依靠大量的实验测试和相关学者的经验来参考取舍，如文献[6]和大多数学者主要是以数据eil51 TSP为例，对ant-cycle的各个参数设置进行试验研究分析;文献[5]则是以数据TSP30为研究对象，对其中的参数设置进行研究分析。上述研究分别是针对不同规模的数据进行分析，没有通用的参考性。本文将从横向不同规模的数据和纵向单个数据来比较分析，利用TSPLIB测试库的实验数据为对象，主要对蚂蚁总数m、启发因子α、信息素挥发系数ρ和期望因子β进行分析。在研究参数对蚁群算法的性能时，统一采用的模型是ant-cycle模型，运行20次取平均和最小值。测试集有bayg29，berlin52、eil76和eil101，它们的城市规模分别为29、52、76和101。对于ant-cycle模型大多数学者认为最好的实验结果是m=n，0≤α≤5，0≤β≤5，0.10≤ρ≤0.99。 2.1 分析蚂蚁总数m
在蚁群算法中，主要是依靠蚂蚁对节点进行选择，信息的交流与协作，然后在更新信息素，从而得到较优解，其中是将蚂蚁分布在不同的城市上。在处理问题时，增加m的值时，会增加蚁群算法的全局搜索能力，但若m的值过大则会影响算法信息素的正反馈机制，从而导致收敛速度变慢，但若m的值过小，将加快算法的收敛速度，但容易陷入局部最优且全局搜索能力也会减弱。故需选择适当m值。文献[1]表明，当蚂蚁数目远远大于城市数量即m>>n时，再增加蚂蚁量对算法的性能有一定的提高，但效果不是很明显。杜衡吉[4]研究得出，当m∈[0.75n，1.50n]时（其中n为城市数量），既可以保证算法的收敛速度，也可以得到较好的解，且此结果与文献[2，3]一致。针对4组数据，固定m的取值，其他参数设置如表1所示。
图1是各测试集最优路径和蚂蚁数目之间的关系图，从图1可以看出，当蚂蚁数目很小的时候，算法不能得到最优解且其不稳定，当蚂蚁数目逐渐增加，能得到最优解且其波动的范围较小，但也可以发现如果蚂蚁数目大于城市数目之后仍持续增加，其最优解并没有得到较好的改善，反而增加了算法的运算量，降低了收敛速度。其中上面4组数据的最佳取值范围分别是m∈[0.85n，1.20n]、m∈[0.80n，1.20n]、m∈[0.80n，1.20n]和m∈[0.70n，n]。故可以总结为，当城市规模小于100时，m∈[0.85n，1.20n]即可得到较优的结果，当大于100后，m∈[0.70n，n]既可得到较优的结果，也可加快收敛速度，即螞蚁数目应取小于数据规模的值。
2.2 分析启发因子α
启发因子α反映的是蚂蚁在选择路径时信息素τij（t）的相对重要程度，其大小是信息素对蚂蚁选择路径的指导强度，也是蚂蚁在搜索路径中随机性的强度。α越大，表明前面积累的信息量对蚂蚁有很强的指导作用，随机性减弱，收敛速度加快，易陷入局部最优。反之，则随机性增强，收敛速度减慢，无法体现正反馈机制。陈文卓[5]研究表明，在n为30的情况下，当α∈[0.5，1.0]时，算法的整体性能较好;而文献[4，6]得出，在n为51的情况下，α∈[1.0，3.0]时，算法的整体性能较好。固定α的取值范围α=1.0：0.5：10.0，其他参数设置如表2所示。
在确定蚂蚁数目和启发式因子的范围的情况下，由以上理论和图2的仿真实验可知，启发式因子α过大或者过小都对算法的搜索和寻优造成不利的影响。对于上面4张图其α的最佳取值范围分别是α∈[1.0，4.5]、α∈[1.0，5.0]、α∈[1.0，3.0]和α∈[1.0，2.5]，即α的取值范围一般在α∈[1.0，3.0]时能取得较优的值。
2.3 分析期望因子β
期望因子β反映的是蚂蚁在选择路径时启发信息ηij（t）的相对重要程度，其大小是距离的倒数，反映了先验知识对蚂蚁选择路径的指导作用，也是蚂蚁在搜索路径中的确定性的因素。其值的大小影响着算法性能的优劣。文献[4]得出，算法在β∈{3，4，5}时，性能较好。文献[6]得出，在β∈{2，4}时效果较好，文献[5]得出，在β∈{2，3，4，5}时性能较好。固定期望因子β的取值范围为β=0.0：0.5：20.0，其他参数设置如表3所示。
由图3的仿真实验和以上理论可知，期望因子β是不宜过大也不宜过小，从图3可以看出，当β大于一定值时其波动性未发生明显的变化，说明其他的参数在影响着β的波动范围。通过图3中的四张图期望因子的最佳取值范围分别是β∈[1.0，2.5]、β∈[1.0，4.5]、β∈[1.0，4.5]和β∈[2，6]。
2.4 分析信息素挥发系数ρ
信息素挥发系数ρ表示信息素在路径上随着时间逐渐挥发的程度，随着迭代次数的增加，信息素将会累计。1-ρ表示信息素挥发之后剩下的部分信息素，值的大小间接反映了蚂蚁个体之间相互关系的强弱。ρ值过大，则路径上的信息素挥发就越多，这条路径上的信息素浓度就越淡，减小了蚂蚁之间的协作性，增强了算法的随机性和全局搜索能力;ρ值过小，路径上挥发的信息素较少，留下较多的信息素，增强了蚂蚁之间的协作，算法的正反馈机制加强，随机性减弱。对于这个参数几乎不同的作者得出的结果都不相同，分别有ρ∈{0.1，0.15，[0.3，0.5]，[0.5，0.8]}。固定信息素挥发系数ρ的取值范围ρ=0.00：0.05：0.95，其他参数的设置如表4所示。
由图4的仿真实验和以上理论可知，ρ值太大或者太小都会影响算法的全局搜索能力。通过图4可以看出，测试集bayg29的最佳取值范围为ρ∈[0.4，0.7]，测试集berlin52的最佳取值范围是ρ∈[0.3，0.7]，测试集eil76的最佳取值点为0.85，而测试集eil101的最佳取值点则为0.75。
3 结 论
在蚁群算法中，参数设置的优劣直接决定算法的性能。本文对蚁群算法的基本原理和仿真实验来分析参数的设置问题。得出结论：对于蚂蚁数目m，当城市规模小于100时，m∈[0.85n，1.20n]，当大于100时，m∈[0.70n，n]算法性能较好，且m
[1] 叶家琪，符强，贺亦甲，等.基于聚类集成的蚁群算法求解大规模TSP问题 [J].计算机与现代化，2020（2）：31-35.
[2] 杜玉红，张岩，赵焕峰.基于参数优化蚁群算法的机器人路径规划研究 [J].现代制造工程，2020（9）：7-14.
[3] 四川旅游学院.基于模糊蚁群算法的旅游线路优化方法：CN201911035554.4 [P].2019-10-29.
[4] 杜衡吉，李勇.蚁群算法中参数设置对其性能影响的研究 [J].现代计算机（专业版），2012（13）：3-7.
[5] 陈文卓，刘萍，姜丰，等.基于参数组合优化的救援机器人蚁群算法研究 [J].华北科技学院学报，2020，17（1）：71-76.
[6] 黄少荣.蚁群算法的参数选择研究 [J].电脑知识与技术，2010，6（20）：5588-5590.
作者简介：向永靖（1992—），女，侗族，贵州凯里人，讲师，硕士研究生，主要研究方向：数理统计、机器学习。