蚁群算法的参数选择研究

摘要：蚁群算法由于具有鲁棒性，并行分布性，执行简单，解决了许多复杂优化和NP-难问题，展现出良好的优化性能和广阔的发展前景，但算法性能很大程度上取决于参数的设置，对初始值的依赖性强。该文在介绍蚁群算法原理的基础上，详细分析算法各个控制参数对算法性能的影响，并从人工设置和自适应调整两方面对参数选择方法做了比较和总结。

关键词：蚁群算法；参数选择；人工设置；自适应调整

中图分类号：TP312文献标识码：A文章编号：1009-3044(2010)20-5588-03

Study on Parameter Selection of Ant Colony Algorithm

HUANG Shao-rong

(Department of Information Management, Guangdong Justice Police Vocational College, Guangzhou 510520, China)

Abstract: Ant colony algorithm (ACA) is a new stochastic optimization algorithm which shows many excellent characters and has succeeded in solving many difficult optimization problems and NP-hard problems. The parameters have an important role in the result of ant colony algorithm. This paper introduces the theory of ACA based on Traveling Salesman Problem (TSP), analyses the function and influence of parameters in ACA, and then introduces the methods of parameters selection in two ways: set the parameters manually and adjust the parameters adaptively. At last, it has compares and summarizes each method.

Key words: ant colony algorithm; parameter selection; manually set; adaptively adjust

如何为元启发式算法设置合理的参数是启发式算法理论和应用研究的一个重要方向。蚁群算法作为最成功的元启发式算法之一，优化性能很大程度上依赖于参数的设置，但要对其参数进行最优设置是一项复杂的工作，往往需要经过大量的测试，这成为蚁群算法进一步推广应用的一个瓶颈。

1 基本蚁群算法

蚁群算法是由Colorni、Dorigo和Maniezzo于20世纪90年代初通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式仿生进化算法[1]。由于蚁群算法具有分布性、并行性、全局性、鲁棒性强等特点，已经在求解NP-难问题和众多应用问题中显示出良好的优化性能和发展潜力。

以TSP问题为例，采用常用的any-cycle模型，简单阐述蚁群算法的基本原理：

设有m只蚂蚁，每只蚂蚁访问n个城市，规定蚂蚁走合法路线，除非周游完成，不允许转到已访问城市。初始时刻，各路径的信息量τij(0)相等，m只蚂蚁被放置到不同的城市上。蚂蚁k（k=1,2...,m）在运动过程中，根据各条路径上信息量和前方路径的长短决定转移方向，Pkij (t)表示在t时刻蚂蚁k由城市i转移到j的概率：

(1)

其中：

allowed k―蚂蚁k下一步允许转移到的城市集合，随k的行进而改变；

τij(t)―t时刻路径（i,j）上的信息量；

α―信息启发式因子；

β―期望启发式因子；

ηij(t)―城市i转到j的期望程度，一般取：ηij(t)=1/dij（dij表示相邻两个城市的距离）；

当蚂蚁k完成周游后，根据式(2)-(4)更新蚂蚁访问过的每一条边上的信息素：

τij(t+n)=(1-ρ)・τij(t)+ Δτij(t) (2)

(3)

(4)

其中：

ρ―信息素挥发系数；

Δτij(t)―本次循环中路径(i,j)上的信息量增量；

Δτkij(t)―蚂蚁k本次循环中在路径(i,j)上留下的信息素数量；

Lk―蚂蚁k环游一周的路径长度；

Q―信息素强度因子，常量。

众多的研究已经表明蚁群算法具有很强的发现较好解的能力，但作为启发式概率型优化算法，蚁群算法存在着早熟收敛，对参数依赖性强的缺点。对于不同版本的蚁群算法或具体的应用问题，甚至不同的具体实例，算法需要不同的参数设置来获取最优的性能。传统对参数的设置是根据应用者有限的经验习惯人为地调整，往往需要做大量的数据测试，不仅耗费时间而且影响了算法最优性能的发挥，成为蚁群算法应用的一大缺陷。

2 控制参数对算法性能的影响[2]

蚁群算法含有一系列对算法性能有重要影响的控制参数，包括：

1）启发式因子α和β：α表示信息素的重要性，反映了蚁群在运动过程中所残留的信息量在指导蚁群搜索中的相对重要程度。α越大，信息素在路径选择上所起作用越大，蚂蚁选择以前走过路径的可能性就越大，搜索的随机性减弱；α越小，易使蚁群算法过早陷入局部最优。当α=0时，将不会利用信息素信息，搜索降为贪婪搜索。

β表示能见度的重要性，反映了启发式信息在指导蚁群搜索过程中的相对重要程度。这些启发式信息表现为寻优过程中先验性、确定性因素。β越大，城市之间距离对路径选择所起作用越大，蚂蚁在局部点上选择局部最短路径的可能性越大，虽然加快了收敛速度，但减弱了随机性，易于陷入局部最优。当β=0时，将忽略对有吸引力的解的显式倾向，算法等同于性能较差的简单蚁群优化（SACO）。

α和β决定了以往的搜索经验和问题的固有启发信息之间的相对重要性，出现在绝大部分的蚁群算法中，对算法性能的影响至关重要，是最重要的两个参数。由于α和β是在信息素浓度和启发式信息之间取得平衡的转移概率Pkij的两大决定因子，通过调节α和β可以很好地处理探索--开发之间的关系。

2）信息素挥发系数ρ：模仿人类记忆特点，随着新信息的增加，旧的信息将逐步忘却、削弱，故引入ρ表示信息素的挥发率，为了防止信息的无限积累，ρ的取值范围设定为[0,1]。

ρ的大小直接关系到蚁群算法的全局搜索能力及其收敛速度；ρ增大，则信息素挥发加快，对过去的历史经验不太敏感，突出最近路径上留下的信息对选择的影响。

相应地，用1-ρ表示信息的残留系数。1-ρ反映了蚂蚁个体之间相互影响的强弱，其大小对蚁群算法的收敛性能影响非常大。在0.1-0.99范围内，1-ρ与迭代次数近似成正比，这是由于1-ρ很大，路径上的残留信息占主导地位，信息正反馈作用相对较弱，搜索的随机性增强，因而蚁群算法的收敛速度慢。若1-ρ较小时，正反馈作用占主导地位，搜索的随机性减弱，导致收敛速度快，但易陷于局部最优。

3）信息素强度因子Q：Q表示蚂蚁循环一周或一个过程释放在所经路径上的信息素总量。在一定程度上影响处算法的收敛速度，Q越大，则每次蚂蚁经过所留下的信息素越多，在已遍历路径上信息素的累积越快，加强蚁群搜索时的正反馈性，有助于算法的快速收敛。

4）蚂蚁数量m：蚁群算法成功在于多只蚂蚁的共同协作行为，通过释放信息素，蚂蚁之间相互传递有关搜索空间的经验与知识。对同一规模的处理问题，m越大，即蚂蚁数量多，会提高蚁群算法的全局搜索能力和稳定性，但数量过多会导致大量曾被搜索过的路径上的信息量变化趋于平均，信息正反馈作用减弱，随机性增强，收敛速度变慢。反之，如果m越小，即蚂蚁数目太少，会使从来未被搜索到的解上的信息量减小到接近于0，全局搜索的随机性减弱，虽然提高了收敛速度，但算法稳定性差，出现早熟现象。另一个就是对计算复杂度的影响，使用的蚂蚁越多，需要建立的路径就越多，对信息素释放的计算也就越多。

3 参数选择

控制参数直接影响算法的性能，包括找到的解的质量及其计算开销。参数选择在算法应用中显得尤其重要，为了提高算法的性能，必须优化相关的控制参数。自从Dorigo等对AS系统中的参数下选取进行了初步研究[3]以来，很多学者在实验基础上进行了深入研究并提供了一些参数设置参考值和优化参数值的启发式方法。

1）人工设置参数：叶志伟等对α、β和ρ这三个对算法的影响较大的参数的最优配置进行了研究，得出：在any-cycle模型中，α=1，β=5，ρ=0.5时，算法性能最优；ant-density模型中，α=1，β=10，ρ=0.1时，算法性能最优；ant-quantity模型中，α=1，β=5，ρ=0.001时，算法性能最优[4]；而蒋玲艳等在分析了这三个参数不同组合对算法性能的影响基础上，总结出参数设置规则：当α∈[0.1,0.3]，β∈[3,6]，ρ∈[0.01,0.3]时，算法总体上有较好的性能，不易早熟，而且所需的迭代次数较少[5]。

对于所有参数（α、β、ρ、Q、m），段海滨提出了调整步骤[6]：首先根据“城市规模/蚂蚁数目≈1.5”的原则确定蚂蚁数目m；然后粗调取值范围较大的α、β和Q；最后微调取值范围较小的ρ。詹士昌等指出当α∈[1,5]，β∈[1,5]，ρ=0.3，Q=100， （n为城市规模）时基本蚁群算法能较快地求得最优解[7]。张毅等则提出了最优的算法参数组合为：α=1、β=5、ρ=0.6、Q=1000、m=城市规模。在该算法参数设置原则下，基本蚁群算法对任意TSP问题总能比较快速地求得全局最优解[8]。

人工设置参数需要大量的数据测试，蚁群中的所有蚂蚁均采用相同的参数，而且只能为算法设定一个合适的初始参数，而不能在执行过程中随时调整参数，影响了算法的性能。

2）自适应调整参数：针对人工设置参数的局限，学者们提出了自适应地调整参数的改进算法，主要是利用蚁群算法具有容易与其它优化算法或局部搜索算法结合的优点，在蚁群算法中混合其它启发式算法以对其参数进行训练和优化，主要有：

① 运用遗传算法优化蚁群算法的控制参数[9]：利用遗传算法快速性、随机性、全局收敛性的特点，每条染色体代表蚁群算法的一个参数值集合，通过选择、交叉和变异等操作不断优化蚁群算法参数。

② 运用粒子群优化算法优化蚁群算法的控制参数[10]：粒子群优化算法具有非常快地逼迫最优解的速度，可以有效对蚁群算法的控制参数进行优化。粒子被表示成一个多维的实数编码串，代表蚁群算法的一个参数值集合，再引入适应度函数并结合粒子群算法得到各参数的最优组合。

③ 运用差分演化算法优化蚁群算法的控制参数：将蚁群算法的参数作为差分演化算法解空间的向量元素，自适应地寻找蚁群算法最优参数组合的同时求解问题的最优解。

在蚁群算法中引入其它启发式算法的混合算法，不仅使蚁群算法有效摆脱了对参数设置的依赖，而且克服了早熟收敛的缺点，大大提高了算法发现最优解的能力，具有更好的全局优化性能。

此外，研究者还提出了根据蚁群算法的不同进化阶段或当连续几代进化后的最优解没有明显变化时，自适应调整参数，以提高最优解的求解质量的改进方案[11]。这类改进算法能够有效提高算法的优化性能，但这些方法并不是通用的，只能使用于特定的算法模型或针对特定的问题。

4 小结

蚁群算法作为一种随机算法，其性能很大程度上受算法参数的影响，好的参数可以使算法快速收敛于优质解，而参数设置不当，将导致算法找到的解质量差，容易陷于局部最优，并且收敛速度慢甚至不收敛。由于蚁群算法参数空间的庞大性和各参数之间的关联性，很难设置最优参数组合以使蚁群算法优化性能最佳，至今还没有完善的理论依据，没有参数选择方面的公式可循，通常根据经验而定。因此，对蚁群算法的参数进行深入分析，了解参数之间的关联，提出好的参数设置方案，以便更合理地设置参数或者自适应地调整参数是非常有意义的，不仅能有效地提高算法的优化性能，而且完善了算法的理论研究，进一步推广蚁群算法在优化领域上的应用。

参考文献：

[1] Colorni A,Dorigo M,Maniezzo V.Distributed Optimization by Ant Colonies[C]//The First European Conference on Artificial Life.France: Elsevier,1991:134-142.

[2] 汪定伟.智能优化方法[M].北京:高等教育出版社,2007.

[3] Dorigo M,Maniezzo V,Colorni A.Ant system: optimization by a Colony of Cooperating Agents[J].IEEE Transactions on System,Man and Cybernetics,1996,26(1):29-41.

[4] 叶志伟,郑肇葆.蚁群算法中参数α,β,ρ设置的研究-以TSP问题为例[J].武汉大学学报,2004,29(7):597-601.

[5] 蒋玲艳,张军,钟树鸿.蚁群算法的参数分析[J].计算机工程与应用,2007,43(20):31-36.

[6] 段海滨.蚁群算法原理及应用[M].北京:科学出版社,2005.

[7] 詹士昌,徐婕,吴俊.蚁群算法中关键参数的选择[J].科技通报,2003,19(5):381-386.

[8] 张毅,梁艳春.蚁群算法中求解参数最优选择[J].分析计算机应用研究,2007(8).

[9] Botee H,Bonabeau E.Evolving Ant Colony Optimization[J].Complex Systems,1998,1(2):149-159.

[10] 闵克学,郭宏伟,张毅,等.基于蚁群和粒子群优化的混合算法求解TSP问题[J].吉林大学学报信息科学版,2006,24(4):402-405.

[11] 刘立东,蔡淮.自适应调整α，β参数的蚁群算法[J].计算机工程与设计,2007,28(20):4995-4997.