论文部分内容阅读
摘要：蚁群算法是一种模拟进化算法，根据信息素更新策略的不同，蚁群系统模型分为蚁密系统、蚁量系统和蚁周系统。本文对三种模型的原理、特点进行研究，并通过仿真实验分析三种模型的性能及参数对其性能的影响，进而提出的参数优化规则，有利于蚁群算法在组合优化问题中的推广和应用。
关键词：蚁群算法；蚁密系统；蚁量系统；蚁周系统；信息素
中图分类号：TP301文献标识码：A文章编号：1009-3044(2007)05-11324-02
1 前言
蚁群算法(Ant Colony Algorithm)[1] 是20世纪90年代由意大利学者Dorigo M等首先提出并称之为蚁群系统（Ant Colony System）。它是一种基于种群的模拟进化算法，具有很强的全局优化能力和本质上的并行性。该算法用于解决TSP问题[2]、JSP问题[3]、QAP问题[4]，已取得了较好的结果。本文以TSP问题为例，通过仿真实验分析蚁群系统的性能及参数设置，最后归纳出一种参数优化规则，对蚁群系统的广泛应用具有重要的意义。
2 基本蚁群算法
TSP问题是一种典型的组合优化问题，下面我们就以平面上n个城市的TSP问题为例来说明蚁群算法模型[5,6]。
在算法开始时，m只蚂蚁按某种规则（如随机）置于n个城市上，位于城市i上的蚂蚁以p (t)为概率函数选择下一个城市。公式（1.1）给出蚂蚁k由城市i转移到j的概率。
其中，tabuk(k=1,2,…m)用来记录蚂蚁k当前所走过的城市，τij(t) 表示t时刻在城市i与j路径上的信息素浓度。ηij(t)表示蚂蚁从城市i转移到城市j的期望值。启发函数α和β反映了信息素和启发函数的相对重要性。
在每只蚂蚁走完一步或完成一次搜索循环后，要按一定规则对路径上的信息素进行更新。在t+n时刻，路经上的信息素可以按公式（1.2）的规则进行调整。
其中，ρ(0≤ρ<1)表示信息素挥发系数。Δτij(t)表示本次循环路径(i,j)上的信息素增量，Δτ (t)表示第k只蚂蚁在本次循环中留在路径(i,j)上的信息素。
2 蚁群系统模型
2.1 三种蚁群系统模型
在对不同性质的问题求解时，蚁群算法模型的定义也有所不同。根据信息素更新策略的不同，Dorigo M提出了三种不同的蚁群算法模型[7]，分别称为蚁密系统（Ant-Density System）、蚁量系统（Ant-Quantity System）和蚁周系统（Ant-Cycle System）。
在蚁密系统模型中，一只蚂蚁在经过路径(i,j)上释放的信息素增量为Q（Q为常量），如公式（2.1）所示。
在蚁量系统模型中，一只蚂蚁在经过路径（i,j）上释放的信息素增量为Q/dij，如公式（2.2）所示。
公式（2.2）中Q是常量，dij表示城市i、j之间的距离，信息素增量与路径 (i,j)的长度成反比。
在蚁周系统模型中，用Δτ (t,t+n)表示蚂蚁k所走过的路径上信息素增量，如公式（2.3）所示。
其中，(t,t+n)表示蚂蚁经过n步完成一次循环，Lk表示第k只蚂蚁在本次循环中所走的路径的总长度。信息素增量与具体的dij无关，只与Q和搜索路线有关。
2.2 蚁群系统模型对比
蚁密模型、蚁量模型与蚁周模型是在基本蚁群算法模型基础上，针对不同性质的应用而提出的，三种模型的状态转移概率计算方法相同，都充分利用了路径上的信息素及路径的启发信息。但在路径搜索过程中，路径上信息素的更新方式存在一定的差异，主要表现在以下几个方面：
(1)信息素增量不同。蚁密系统模型信息素增量为固定值Q；而在蚁量系统模型中，信息素增量的值为Q/dij，与路径 (i,j)的长度有关；在蚁周系统模型中，信息素增量为Q/Lk，它与具体的dij无关，只与Q和搜索路线有关。
(2)信息素更新时刻不同。蚁密模型和蚁量模型的信息素更新是在蚁群前进过程中进行的。蚂蚁每完成一步移动（从城市i到达城市j）后更新所有路径上的信息素；蚁周系统模型是在第k只蚂蚁完成一次路径搜索后，对每条路径(i,j)进行信息素的更新。
(3)信息素更新形式不同。蚁密模型和蚁量模型利用蚂蚁所走路径(i,j)上的信息进行更新，其信息素更新机制采用的是局部信息更新；蚁周系统模型的信息素增量与本次搜索的整体路径有关，因此属于全局信息更新。
3 蚁群系统模型的性能分析及参数优化
3.1 蚁群系统模型的性能分析
蚁密、蚁量和蚁周系统模型由于采用的信息素更新策略不同，性能存在一定的差异。信息素更新过程中，各参数的设置是影响结果的一个关键。下面通过仿真试验对三种模型在TSP问题求解中的性能表现进行分析。
蚁群算法中各参数α、β、ρ的作用是紧密耦合的，它们对算法性能起着关键作用。如果α、β、ρ的组合参数配置不当，会导致求解速度很慢且所得解质量特别差，因此，在仿真实验中α、β、ρ值的恰当选取对算法性能具有重要的影响。
本实验中的TSP数据来源于TSPLIB中的Oliver30TSP，采用1000次循环作为算法终止的条件，默认的参数设置为α＝1，β=1，ρ=0.3，Q=300，在得到备选路径概率的情况下，蚂蚁运用随机选择策略确定下一步要到达的城市。实验策略为对测试参数设置一组值，其他保持默认值，每组数据实验10次，取其平均值比较三类模型的性能。
被测试的值为：α∈{0,0.5,1,2,5}，β∈{0,1,2,5,10,20}，ρ∈{0.3,0.5,0.7,0.9}。
表1 蚁密系统实验结果
表2 蚁量系统实验结果
表3 蚁周系统实验结果
通过对以上实验结果的统计分析，得出在本实验中α、β、ρ三个参数的最佳配置段值。蚁密系统的最佳参数配置为：α=1，β=10，ρ=0.9；蚁量系统的最佳参数配置为：α=1，β=5，ρ=0.9；蚁周系统的最佳参数配置为：α=1，β=5，ρ=0.5。
通过进一步分析，可以得到以下结论：
(1)三种模型中，参数α=1时所得解的质量和稳定性都是最好的。
(2)三种模型中，β值在1~5之间逐渐增大，3种模型所得解质量越来越高。
(3)α与β的取值不当，可能导致早熟收敛，产生局部较优路径，而不是全局最优解。因此，启发信息和信息素轨迹强度的结合是十分必要的。
(4)在蚁密系统和蚁量系统中，ρ的值越大，解的质量越好，在蚁周系统中ρ在0.5左右结果比较好。
(5)三类模型对参数表现出了不同的敏感程度，但只有对ρ的敏感度最高，这也正是由于三种模型的信息素更新机制不同所造成的。
3.2 蚁群系统的参数优化
本文通过仿真实验测试了蚁密系统、蚁量系统和蚁周系统的性能。实验结果表明三种模型都能在一定程度上搜索到满足要求的解，但是参数的设置对解的质量有非常显著的影响，因此在实际应用中除了根据需要确定采用哪一种算法模型，还应优化参数的设置。
在保证能获得解前提下，为了提高计算速度，依据蚁群算法参数设置的规律，本文归纳出蚁群模型中优化参数设置的规则：“满足且最优组合”。
(1)首先根据经验设置参与实验的各参数α、β、ρ的取值范围，确定α、β、ρ的各参数段值；
(2)根据本文分析的参数设置规律，选取α、β、ρ的“满足”参数组合；
(3)通过淘汰实验法，去掉“满足”参数组合中的次优组合，确定α、β、ρ的“满足且最优”参数组合；
(4)对“满足且最优”组合进一步进行参数调整：平衡启发式因子，微调挥发因子；
(5)平衡启发式因子，调整信息启发式因子α、期望启发式因子β，确定二者比较恰当的组合参数值；
(6)挥发因子微调，根据解的趋势调整信息素挥发因子ρ的值。
通过以上步骤，可以在有限次数的实验中确定参数α、β、ρ参数设置，有效地保证实验结果的有效性。
4 结束语
蚁群系统模型的建立使得蚁群算法广泛地应用在组合优化、人工智能、通讯等多个领域。本文对三类模型进行分析研究，通过仿真实验分析了蚁群系统的性能及参数影响，并提出了优化参数设置的方法原则，对于解决不同规模的TSP问题具有一定的参考价值，对用蚁群系统模型解决其他领域的问题也具有一定的指导意义。
参考文献：
[1]M Dorigo,V Maniezzo,A Colorni.Ant System:Optimization by A Colony of cooperating Agents[J].IEEE Transactions on system,Man,and Cybemetics,Part B,1996,26(1).
[2]李勇,段正澄,动态蚁群算法求解TSP问题[M].计算机工程与应用,2003.10,3-106.
[3]A Coloni,M Dorigo,V Maniezzo.Ant system for Job-shop scheduling[J].Belgian J. of Operations Research Statistics and Computer Science,1994,34(1):39-53.
[4]Vittorio Maniezzo,Alerto Colorin.The ant system applied to the quadratic assignment problem. Knowledge and Data Engineering,IEEE Transactions on,11(5),september/October 1999.
[5]李士勇,蚁群算法及其应用[M].哈尔滨工业大学出版社,2004.9.
[6]张静乐,王世卿,王乐.具有新型遗传特征的蚁群算法[M].微计算机信息,2006.
[7]M Dorigo,V Maniezzo,A Colorni.Positive Feedback as a Search Strategy.Technical Report.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
关键词：蚁群算法；蚁密系统；蚁量系统；蚁周系统；信息素
中图分类号：TP301文献标识码：A文章编号：1009-3044(2007)05-11324-02
1 前言
蚁群算法(Ant Colony Algorithm)[1] 是20世纪90年代由意大利学者Dorigo M等首先提出并称之为蚁群系统（Ant Colony System）。它是一种基于种群的模拟进化算法，具有很强的全局优化能力和本质上的并行性。该算法用于解决TSP问题[2]、JSP问题[3]、QAP问题[4]，已取得了较好的结果。本文以TSP问题为例，通过仿真实验分析蚁群系统的性能及参数设置，最后归纳出一种参数优化规则，对蚁群系统的广泛应用具有重要的意义。
2 基本蚁群算法
TSP问题是一种典型的组合优化问题，下面我们就以平面上n个城市的TSP问题为例来说明蚁群算法模型[5,6]。
在算法开始时，m只蚂蚁按某种规则（如随机）置于n个城市上，位于城市i上的蚂蚁以p (t)为概率函数选择下一个城市。公式（1.1）给出蚂蚁k由城市i转移到j的概率。
其中，tabuk(k=1,2,…m)用来记录蚂蚁k当前所走过的城市，τij(t) 表示t时刻在城市i与j路径上的信息素浓度。ηij(t)表示蚂蚁从城市i转移到城市j的期望值。启发函数α和β反映了信息素和启发函数的相对重要性。
在每只蚂蚁走完一步或完成一次搜索循环后，要按一定规则对路径上的信息素进行更新。在t+n时刻，路经上的信息素可以按公式（1.2）的规则进行调整。
其中，ρ(0≤ρ<1)表示信息素挥发系数。Δτij(t)表示本次循环路径(i,j)上的信息素增量，Δτ (t)表示第k只蚂蚁在本次循环中留在路径(i,j)上的信息素。
2 蚁群系统模型
2.1 三种蚁群系统模型
在对不同性质的问题求解时，蚁群算法模型的定义也有所不同。根据信息素更新策略的不同，Dorigo M提出了三种不同的蚁群算法模型[7]，分别称为蚁密系统（Ant-Density System）、蚁量系统（Ant-Quantity System）和蚁周系统（Ant-Cycle System）。
在蚁密系统模型中，一只蚂蚁在经过路径(i,j)上释放的信息素增量为Q（Q为常量），如公式（2.1）所示。
在蚁量系统模型中，一只蚂蚁在经过路径（i,j）上释放的信息素增量为Q/dij，如公式（2.2）所示。
公式（2.2）中Q是常量，dij表示城市i、j之间的距离，信息素增量与路径 (i,j)的长度成反比。
在蚁周系统模型中，用Δτ (t,t+n)表示蚂蚁k所走过的路径上信息素增量，如公式（2.3）所示。
其中，(t,t+n)表示蚂蚁经过n步完成一次循环，Lk表示第k只蚂蚁在本次循环中所走的路径的总长度。信息素增量与具体的dij无关，只与Q和搜索路线有关。
2.2 蚁群系统模型对比
蚁密模型、蚁量模型与蚁周模型是在基本蚁群算法模型基础上，针对不同性质的应用而提出的，三种模型的状态转移概率计算方法相同，都充分利用了路径上的信息素及路径的启发信息。但在路径搜索过程中，路径上信息素的更新方式存在一定的差异，主要表现在以下几个方面：
(1)信息素增量不同。蚁密系统模型信息素增量为固定值Q；而在蚁量系统模型中，信息素增量的值为Q/dij，与路径 (i,j)的长度有关；在蚁周系统模型中，信息素增量为Q/Lk，它与具体的dij无关，只与Q和搜索路线有关。
(2)信息素更新时刻不同。蚁密模型和蚁量模型的信息素更新是在蚁群前进过程中进行的。蚂蚁每完成一步移动（从城市i到达城市j）后更新所有路径上的信息素；蚁周系统模型是在第k只蚂蚁完成一次路径搜索后，对每条路径(i,j)进行信息素的更新。
(3)信息素更新形式不同。蚁密模型和蚁量模型利用蚂蚁所走路径(i,j)上的信息进行更新，其信息素更新机制采用的是局部信息更新；蚁周系统模型的信息素增量与本次搜索的整体路径有关，因此属于全局信息更新。
3 蚁群系统模型的性能分析及参数优化
3.1 蚁群系统模型的性能分析
蚁密、蚁量和蚁周系统模型由于采用的信息素更新策略不同，性能存在一定的差异。信息素更新过程中，各参数的设置是影响结果的一个关键。下面通过仿真试验对三种模型在TSP问题求解中的性能表现进行分析。
蚁群算法中各参数α、β、ρ的作用是紧密耦合的，它们对算法性能起着关键作用。如果α、β、ρ的组合参数配置不当，会导致求解速度很慢且所得解质量特别差，因此，在仿真实验中α、β、ρ值的恰当选取对算法性能具有重要的影响。
本实验中的TSP数据来源于TSPLIB中的Oliver30TSP，采用1000次循环作为算法终止的条件，默认的参数设置为α＝1，β=1，ρ=0.3，Q=300，在得到备选路径概率的情况下，蚂蚁运用随机选择策略确定下一步要到达的城市。实验策略为对测试参数设置一组值，其他保持默认值，每组数据实验10次，取其平均值比较三类模型的性能。
被测试的值为：α∈{0,0.5,1,2,5}，β∈{0,1,2,5,10,20}，ρ∈{0.3,0.5,0.7,0.9}。
表1 蚁密系统实验结果
表2 蚁量系统实验结果
表3 蚁周系统实验结果
通过对以上实验结果的统计分析，得出在本实验中α、β、ρ三个参数的最佳配置段值。蚁密系统的最佳参数配置为：α=1，β=10，ρ=0.9；蚁量系统的最佳参数配置为：α=1，β=5，ρ=0.9；蚁周系统的最佳参数配置为：α=1，β=5，ρ=0.5。
通过进一步分析，可以得到以下结论：
(1)三种模型中，参数α=1时所得解的质量和稳定性都是最好的。
(2)三种模型中，β值在1~5之间逐渐增大，3种模型所得解质量越来越高。
(3)α与β的取值不当，可能导致早熟收敛，产生局部较优路径，而不是全局最优解。因此，启发信息和信息素轨迹强度的结合是十分必要的。
(4)在蚁密系统和蚁量系统中，ρ的值越大，解的质量越好，在蚁周系统中ρ在0.5左右结果比较好。
(5)三类模型对参数表现出了不同的敏感程度，但只有对ρ的敏感度最高，这也正是由于三种模型的信息素更新机制不同所造成的。
3.2 蚁群系统的参数优化
本文通过仿真实验测试了蚁密系统、蚁量系统和蚁周系统的性能。实验结果表明三种模型都能在一定程度上搜索到满足要求的解，但是参数的设置对解的质量有非常显著的影响，因此在实际应用中除了根据需要确定采用哪一种算法模型，还应优化参数的设置。
在保证能获得解前提下，为了提高计算速度，依据蚁群算法参数设置的规律，本文归纳出蚁群模型中优化参数设置的规则：“满足且最优组合”。
(1)首先根据经验设置参与实验的各参数α、β、ρ的取值范围，确定α、β、ρ的各参数段值；
(2)根据本文分析的参数设置规律，选取α、β、ρ的“满足”参数组合；
(3)通过淘汰实验法，去掉“满足”参数组合中的次优组合，确定α、β、ρ的“满足且最优”参数组合；
(4)对“满足且最优”组合进一步进行参数调整：平衡启发式因子，微调挥发因子；
(5)平衡启发式因子，调整信息启发式因子α、期望启发式因子β，确定二者比较恰当的组合参数值；
(6)挥发因子微调，根据解的趋势调整信息素挥发因子ρ的值。
通过以上步骤，可以在有限次数的实验中确定参数α、β、ρ参数设置，有效地保证实验结果的有效性。
4 结束语
蚁群系统模型的建立使得蚁群算法广泛地应用在组合优化、人工智能、通讯等多个领域。本文对三类模型进行分析研究，通过仿真实验分析了蚁群系统的性能及参数影响，并提出了优化参数设置的方法原则，对于解决不同规模的TSP问题具有一定的参考价值，对用蚁群系统模型解决其他领域的问题也具有一定的指导意义。
参考文献：
[1]M Dorigo,V Maniezzo,A Colorni.Ant System:Optimization by A Colony of cooperating Agents[J].IEEE Transactions on system,Man,and Cybemetics,Part B,1996,26(1).
[2]李勇,段正澄,动态蚁群算法求解TSP问题[M].计算机工程与应用,2003.10,3-106.
[3]A Coloni,M Dorigo,V Maniezzo.Ant system for Job-shop scheduling[J].Belgian J. of Operations Research Statistics and Computer Science,1994,34(1):39-53.
[4]Vittorio Maniezzo,Alerto Colorin.The ant system applied to the quadratic assignment problem. Knowledge and Data Engineering,IEEE Transactions on,11(5),september/October 1999.
[5]李士勇,蚁群算法及其应用[M].哈尔滨工业大学出版社,2004.9.
[6]张静乐,王世卿,王乐.具有新型遗传特征的蚁群算法[M].微计算机信息,2006.
[7]M Dorigo,V Maniezzo,A Colorni.Positive Feedback as a Search Strategy.Technical Report.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。