论文部分内容阅读
[摘要]首先简述蚁群算法的基本原理和特点，然后介绍具有代表性的改进算法和蚁群算法的应用领域，最后对蚁群算法未来的研究方向和发展趋势进行展望。
[关键词]蚁群算法 模拟进化 组合优化
中图分类号：029 文献标识码：A 文章编号：1671－7597(2009)0210050－01
一、蚊群算法基本原理
蚁群算法的基本思想是模仿蚂蚁间通过在路径上释放信息素进行交流，并根据累积的信息素不断搜索较优路径，并最终找到全局最佳路径。
Dorigo等于1991年提出了第一个蚁群算法的模型(As)[1]，并成功用于求解旅行商问题(TSP)等复杂的组合优化问题。
(一)蚁群算法的数学模型。将m只蚂蚁随机放到n个全连通的城市上，并使各路径上信息素浓度相等。t时刻位于城市i的蚂蚁k倾向于选择那些长度较短且信息素强度较高的路径，并在某一时间更新路径上的信息素浓度。当所有蚂蚁都遍历完n个城市以后，计算出此次遍历的最短路径。此后算法迭代至满足终止条件后结束，找到遍历整个城市的最短路径。
(二)基本蚁群算法的优缺点。AS算法具有天然的随机性，自适应性，分布式计算，无中心控制和个体间异步间接协作的优点，具有良好的并行处理和全局优化能力。但也存在一些缺陷：
1、求解速度慢。算法时间复杂度为O(n3)，当问题规模(n)增大时，算法时间将以三次幂的速度增长。
2、算法执行过程中容易出现停滞。当搜索进行到一定程度后，被信息素更新算法选中的路径和未被选中的路径间的差异会越来越大，会使解趋于一致，不利于发现更好的解。
二、蚊群算法的理论研究与改进
(一)改进的蚁群算法。针对蚁群算法的不足很多学者围绕着改进蚁群算法，提高算法的性能做了大量工作。
Dorigo等随后提出蚁群系统(ACS)[2]。改进了蚂蚁选择城市的状态转移规则；只允许当前找到最优路径的蚂蚁在遍历后释放信息素；在转移过程中，减少路径上的信息素浓度，有效避免过早的收敛到同一路径。
Stutzle[3]等提出MMAS算法，将路径上信息素的浓度限制在[T min。Tmax]范围内；各路径上信息素的初始值设为t max，p取较小值，可在初始阶段搜索到更多可行解。此算法是目前求解TSP等离散优化问题最好的算法模型之一。Gambardella等提出混合蚁群算法，Taillard等提出了快速蚂蚁系统，都尽可能提高蚁群算法在一定空间复杂度下的寻优能力，并拓宽蚁群算法的应用领域。
(二)参数设置研究。在蚁群算法实现过程中。ρ α β等参数的值决定了搜索速度与收敛速度的平衡。Dorigo等通过实验得出当a＝1，β＝5，ρ＝0.5时为AS算法的最佳参数设置，而在ACS算法中α＝0.9，β＝2，ρ＝0.1。蔣玲艳等分析了α β ρ对算法性能的影响，并利用大量数据指出，当α∈[0.1，0.3], β∈[3,6]，ρ∈[0.1，0.3]时算法有较好的性能。
(三)收敛性研究。Gutjahr等首先对基于图的蚁群算法(GBAS)及其后改进的GBAS/tdev和GBAS/tdlb算法的收敛性进行了证明，Stuezle和Dorigo证明了一类蚁群算法当迭代次数趋于无穷时，算法可以保证找到全局最优解。黄翰等结合ACS对蚁群算法的收敛速度进行了分析。孙焘等对一类简单蚁群算法的收敛性做了初步研究。
(四)与遗传算法融合。Abbattista等利用遗传算法寻找最优的α βq参数设置。丁建立等利用遗传算法产生较好的信息素初始分布，再利用蚂蚁算法求精确解。这样可以把蚁群算法的协作效应与遗传算法的进化效应进行优势互补，获得优化和时间上的双赢。
三、蚁群算法的应用研究
蚁群算法应用研究及适用范围主要归结为两大领域：
(一)离散组合优化问题。除TSP问题外，蚁群算法早已应用到其他典型的优化离散组合优化问题中；指派问题，二次规划，job—shop，图着色，通讯网络路由选择，电力系统故障检测，图像处理，参数辨识等。
(二)连续空间优化问题。蚁群算法在连续优化问题中的应用刚刚起步。高玮等提出的免疫连续蚁群算法应用到了岩土工程分析中，并通过简单的算例验证了算法的有效性及卓越的计算效率。Ho等提出的求解连续优化问题的蚁群算法，并运用在电磁装置的优化设计上，取得了良好的效果。
四、蚊群算法的前景展望
蚁群算法在求解优化组合问题中有着明显的优越性和广阔的应用前景，未来还可以在以下几方面深入研究：
1、算法理论分析的完善和改进。对蚁群算法有效性进行严格的数学解释，算法的收敛性分析与证明及算法通用的模型有待进一步研究。
算法的性能也有待进一步提高，如路径选择概率的适应性调整，信息素的动态更新，算法参数的优化，信息素挥发系数优化等方向。
2、与其他优化算法融合。蚁群算法与其他算法融合研究仍处于初级阶段，探讨新的融合策略来进一步改善蚁群算法的性能，并将其应用于实际问题中，都是很有意义的研究方向。
3、实际工程中的应用扩展。现阶段蚁群算法大部分应用仍停留在小规模的仿真阶段，还需要使蚁群算法的求解更接近工程实际，并对更复杂的问题进行深入讨论，对算法的可靠性进行深入分析，其蚁群算法的应用领域也有待进一步扩展。
对于以上问题的研究必将使蚁群算法展现更加广阔的发展前景。
作者简介：
吴诗娟，女，四川成都人，硕士研究生，主要研究方向：计算机网络与信息系统；李旭伟，男，浙江长兴人，副教授，硕士，主要研究方向：计算机网络与信息系统。
[关键词]蚁群算法 模拟进化 组合优化
中图分类号：029 文献标识码：A 文章编号：1671－7597(2009)0210050－01
一、蚊群算法基本原理
蚁群算法的基本思想是模仿蚂蚁间通过在路径上释放信息素进行交流，并根据累积的信息素不断搜索较优路径，并最终找到全局最佳路径。
Dorigo等于1991年提出了第一个蚁群算法的模型(As)[1]，并成功用于求解旅行商问题(TSP)等复杂的组合优化问题。
(一)蚁群算法的数学模型。将m只蚂蚁随机放到n个全连通的城市上，并使各路径上信息素浓度相等。t时刻位于城市i的蚂蚁k倾向于选择那些长度较短且信息素强度较高的路径，并在某一时间更新路径上的信息素浓度。当所有蚂蚁都遍历完n个城市以后，计算出此次遍历的最短路径。此后算法迭代至满足终止条件后结束，找到遍历整个城市的最短路径。
(二)基本蚁群算法的优缺点。AS算法具有天然的随机性，自适应性，分布式计算，无中心控制和个体间异步间接协作的优点，具有良好的并行处理和全局优化能力。但也存在一些缺陷：
1、求解速度慢。算法时间复杂度为O(n3)，当问题规模(n)增大时，算法时间将以三次幂的速度增长。
2、算法执行过程中容易出现停滞。当搜索进行到一定程度后，被信息素更新算法选中的路径和未被选中的路径间的差异会越来越大，会使解趋于一致，不利于发现更好的解。
二、蚊群算法的理论研究与改进
(一)改进的蚁群算法。针对蚁群算法的不足很多学者围绕着改进蚁群算法，提高算法的性能做了大量工作。
Dorigo等随后提出蚁群系统(ACS)[2]。改进了蚂蚁选择城市的状态转移规则；只允许当前找到最优路径的蚂蚁在遍历后释放信息素；在转移过程中，减少路径上的信息素浓度，有效避免过早的收敛到同一路径。
Stutzle[3]等提出MMAS算法，将路径上信息素的浓度限制在[T min。Tmax]范围内；各路径上信息素的初始值设为t max，p取较小值，可在初始阶段搜索到更多可行解。此算法是目前求解TSP等离散优化问题最好的算法模型之一。Gambardella等提出混合蚁群算法，Taillard等提出了快速蚂蚁系统，都尽可能提高蚁群算法在一定空间复杂度下的寻优能力，并拓宽蚁群算法的应用领域。
(二)参数设置研究。在蚁群算法实现过程中。ρ α β等参数的值决定了搜索速度与收敛速度的平衡。Dorigo等通过实验得出当a＝1，β＝5，ρ＝0.5时为AS算法的最佳参数设置，而在ACS算法中α＝0.9，β＝2，ρ＝0.1。蔣玲艳等分析了α β ρ对算法性能的影响，并利用大量数据指出，当α∈[0.1，0.3], β∈[3,6]，ρ∈[0.1，0.3]时算法有较好的性能。
(三)收敛性研究。Gutjahr等首先对基于图的蚁群算法(GBAS)及其后改进的GBAS/tdev和GBAS/tdlb算法的收敛性进行了证明，Stuezle和Dorigo证明了一类蚁群算法当迭代次数趋于无穷时，算法可以保证找到全局最优解。黄翰等结合ACS对蚁群算法的收敛速度进行了分析。孙焘等对一类简单蚁群算法的收敛性做了初步研究。
(四)与遗传算法融合。Abbattista等利用遗传算法寻找最优的α βq参数设置。丁建立等利用遗传算法产生较好的信息素初始分布，再利用蚂蚁算法求精确解。这样可以把蚁群算法的协作效应与遗传算法的进化效应进行优势互补，获得优化和时间上的双赢。
三、蚁群算法的应用研究
蚁群算法应用研究及适用范围主要归结为两大领域：
(一)离散组合优化问题。除TSP问题外，蚁群算法早已应用到其他典型的优化离散组合优化问题中；指派问题，二次规划，job—shop，图着色，通讯网络路由选择，电力系统故障检测，图像处理，参数辨识等。
(二)连续空间优化问题。蚁群算法在连续优化问题中的应用刚刚起步。高玮等提出的免疫连续蚁群算法应用到了岩土工程分析中，并通过简单的算例验证了算法的有效性及卓越的计算效率。Ho等提出的求解连续优化问题的蚁群算法，并运用在电磁装置的优化设计上，取得了良好的效果。
四、蚊群算法的前景展望
蚁群算法在求解优化组合问题中有着明显的优越性和广阔的应用前景，未来还可以在以下几方面深入研究：
1、算法理论分析的完善和改进。对蚁群算法有效性进行严格的数学解释，算法的收敛性分析与证明及算法通用的模型有待进一步研究。
算法的性能也有待进一步提高，如路径选择概率的适应性调整，信息素的动态更新，算法参数的优化，信息素挥发系数优化等方向。
2、与其他优化算法融合。蚁群算法与其他算法融合研究仍处于初级阶段，探讨新的融合策略来进一步改善蚁群算法的性能，并将其应用于实际问题中，都是很有意义的研究方向。
3、实际工程中的应用扩展。现阶段蚁群算法大部分应用仍停留在小规模的仿真阶段，还需要使蚁群算法的求解更接近工程实际，并对更复杂的问题进行深入讨论，对算法的可靠性进行深入分析，其蚁群算法的应用领域也有待进一步扩展。
对于以上问题的研究必将使蚁群算法展现更加广阔的发展前景。
作者简介：
吴诗娟，女，四川成都人，硕士研究生，主要研究方向：计算机网络与信息系统；李旭伟，男，浙江长兴人，副教授，硕士，主要研究方向：计算机网络与信息系统。