蚁群算法研究现状及发展

蚁群算法研究现状及发展

作者：戴宏发 张源原 孙国强 刘成亮 来源：《科技创新导报》2011年第21期

摘 要:蚁群算法是一类模拟生物群体突现聚集行为的新型机器学习技术。本文回顾了蚁群算法的主要概念,总结了蚁群算法与其他智能方法的融合,介绍了一种基于群体蚁群算法的硬件实现方法,最后对蚁群算法的发展方向提出了预测。 关键词:蚁群算法智能方法优化硬件实现

中图分类号:O224 文献标识码:A 文章编号:1674-098X(2011)07(c)-0132-02

在社会科学和工程技术的发展中,需要解决问题的复杂性、约束性、非线性,建模困难等问题日渐突出。多年来,人们一直致力于寻找一种有效处理此类问题的方法。蚁群算法最初是由意大利学者Macro Dorigo等人在蚂蚁觅食行为的启发下而提出的一种新型的元启发式算法,随着研究的逐步深入,Macro Dorigo与其合作者于1991年设计出了第一个蚁群优化算法——蚁群系统[1]。经过十几年的发展,蚁群算法在理论和实际应用上取得了长足的发展。近几年来,由于它在知识发现、数据挖掘、故障检测、路径规划等领域的广泛应用,研究逐渐趋热。 蚁群算法通过模拟蚂蚁在寻找食物过程当中,通过个体行为影响的累积,最后形成群体行为,从而找到适合问题的最优解。本文介绍了蚁群算法的基本理论,总结了国内外的研究现状,最后对蚁群算法未来的研究方向提出了预测。 1 蚁群算法简介[2] 1.1 信息素

单个蚂蚁在行为过程中释放一种化学物质,群体中的其他个体根据环境中的这种物质可以找到食物和窝之间的最短路径,我们称这种物质为信息素。 1.2 信息素更新

路径上的信息素量随着蚂蚁的选择以及随时间的推移而产生的增加和消失的现象称为信息素更新。

蚂蚁完成一步或对所有路径上的节点遍历之后,要对路径上的信息进行更新。因此,定义信息量的计算公式为: (1)

龙源期刊网 http://www.qikan.com.cn

(2)

式中:Tij(t+n)表示t+n时刻在节点i到节点j的路径上的信息素更新;ρ表示信息素挥发系数;△Tij(t)表示循环中节点i到节点j的路径上信息素的增量;表示第k只蚂蚁在循环中的节点i到节点j的路径上留下的信息素。 1.3 路径选择概率

蚂蚁根据路径上信息素的浓郁程度,按概率选择路径。

设网格G=(v,A,d)其中,d是A的权函数,目标是找到访问每个节点一次的最短回路。每条路径都有信息素变量Tij,Tij会随着迭代次数的增加而变化。表示在t时刻蚂蚁k从城市i转移到城市j的概率: (3)

allowdk表示蚂蚁k下一步可走节点的集合,а表示信息量对蚂蚁选择路径的作用大小,ηij表示蚂蚁从节点转移到城市的期望,β表示ηij的作用。 2 蚁群算法与其它智能算法的融合 2.1 蚁群算法与遗传算法

遗传算法作为仿生态进化算法的一种,具有天生隐含并行性和强大的全局搜索能力,最初是由密歇根大学Holland教授创建的。它通过模拟自然界中,生物竞争产生出适者生存的进化原理来得到解空间的全局最优解。遗传算法的特点很多,通过将遗传算法与蚁群算法融合,可以更有效解决蚁群算法中的很多问题。文献[3]通过利用遗传算法首先对工程设计中的连续空间问题进行优化,然后采用蚁群算法再对所得结果进行精确化,从而解决了蚁群算法不能很好应对连续空间求解的问题。文献[4]通过利用遗传算法的快速的全局搜索能力结合蚁群算法的优秀正反馈能力提出了一种改进的蚁群算法,并应用于TSP问题中,取得了很好的效果。文献[5]通过引入遗传算法中的杂交算子,提出了一种带杂交算子的蚁群算法,从而有效的解决了进化过程中收敛速度慢且精度不高的问题。 2.2 蚁群算法与神经网络

神经网络通过模拟人的直觉思维方式进行工作,通过网络的参数设置,达到不同的效果[6]。但是,神经网络在有冗余属性时,存在训练时间长,收敛速度慢等问题。且在处理经典的旅行商问题中,容易陷入局部极小点等问题。文献[7]通过利用蚁群算法对特征参数进行属性约简,从而删除非必要属性,然后再将结果输入到神经网络中训练。通过这样的组合,达到了简化神经网络处理数据的维数,提高了网络的训练效率,并将方法运用到柴油机的故障诊断中,取得了良好的训练效果,最终提高了故障分类的准确性。文献[8]提出了一种基于蚁群算法的Hopfiled神经网络,通

龙源期刊网 http://www.qikan.com.cn

过引入蚁群算法,提高了神经网络的收敛速度,且比原方法易于跳出局部最优,最后应用于多空间站的路径规划中。BP神经网络作为人工神经网络中一种应用最广泛的多层前馈神经网络,在实际应用中同样存在学习效率低,易于陷入局部极小的问题。文献[9]在分析了蚁群算法的优点之后,将蚁群算法融合入BP网络的网络权值训练中,从而使蚁群神经网络既能满足广泛的映射能力,又能达到快速及全局收敛的要求。 2.3 蚁群算法与粗糙集理论

粗糙集理论[10]是由波兰数学家Pawlak Z于1982年提出的,通过引入数学中的等价关系,对特定空间进行划分,采用这样的方法达到利用已知的知识库描述模糊不确定信息的目的。粗糙集理论中,属性约简是其核心内容,目的是导出相关决策表中的决策规则。但由于属性组合的爆炸,找出决策表的最小约简就成为了NP-hard问题,所以单纯依赖粗糙集理论解决实际问题存在很多困难。蚁群算法作为进化算法的一种,在组合优化,路径选择等问题上有较强的适应性,但同时存在搜索时间长、易于停滞等问题。通过将蚁群算法与粗糙集理论结合,可以很好的解决两种问题中各自的不足。文献[11]在回顾了粗糙集属性约简方法以及蚁群算法的基础上,提出了一种基于量子蚁群算法的粗糙集属性约简方法,该方法利用量子旋转门实现蚂蚁的移动,从而在蚂蚁数目相同时,使搜索空间加倍。同时,充分利用了蚁群算法搜索效率高又能满足得到最小属性集的要求。文献[12]在分析了蚁群算法的仿真实验之后,发现存在多种不确定因素影响信息素的更新,为了找出各因素对算法影响的重要性,引入粗糙集理论,最后发现:蚂蚁数量和信息素初始浓度的设置对蚁群算法的影响是全局性的,会影响所有节点间查找最短路径的正确性和执行时间;而信息素的衰减与增长对蚁群算法的影响则是局部性的。文献在得到这些结论之后,确定了蚁群算法的改进原则:当算法路径搜索准确度不高且收敛速度慢,则应调整全局性参数,包括蚂蚁数量和初始信息素浓度;当算法需要提高实时性要求,应先调整初始信息素浓度然后再调整蚂蚁数量;当需要提高搜索的准确度时,应同时调整信息素更新的速度。 3 蚁群算法的硬件实现

FPGA(Field Programmable GateArrays)是一种可编程使用的信号处理器件,用户可通过改变配置信息对其功能进行定义,以满足设计需求。作为专用集成电路(ASIC)领域中的一种半定制电路,它与传统数字电路系统相比,FPGA具有可编程、高集成度、高速和高可靠性等优点,通过配置器件内部的逻辑功能和输入/输出端口,将原来电路板级的设计放在芯片中进行,提高了电路性能,降低了印刷电路板设计的工作量和难度,有效提高了设计的灵活性和效率[13]。

文献[14]详细的介绍了如何利用FPGA实现蚁群算法,它采用易于FPGA实现的群体蚁群算法,设计了其中的群体生成模块、群体更新模块、行为模块、评价模块以及算法进程的控制模块(图1)。

其中群体模块包括一个群矩阵Q=[qij]n×k,矩阵是由j=0列的精英蚂蚁和列中的FIFO序列构成。其中每一个qij都对应了一个工作数目。行为模块中接收群体模块中的个体,并模仿蚂蚁

龙源期刊网 http://www.qikan.com.cn

行为过程,当迭代结束时,评价模块即得到本次迭代的最优解,并送入群体模块中。行为模块可以同时让m个蚂蚁同时工作,实现了硬件上的并行性。

由于FPGA资源的限制,在蚁群算法的选择中,文献没有采取其他性能更优的算法。与用软件实现群体蚁群算法相比,利用FPGA硬件的高速性,以及软件的灵活性,很好的解决了传统设计方法在高速及灵活两者不能兼得的局面。 4 蚁群算法存在的问题和发展趋势 4.1 存在的问题

蚁群算法的研究成果令人瞩目,但作为一种较新的理论,它依然存在一些问题。

(1)对于大规模组合优化问题,算法的计算时间而且复杂。由于蚁群算法的时间复杂度是,因此在处理较大规模的组合优化问题时,运算量较大,时间较长。

(2)算法容易在某个或某些局部最优解的邻域附近发生停滞现象,造成早熟收敛,即搜索进行到一定程度后,所有蚂蚁发现的解完全一致,不能继续对解空间进一步搜索,不利于发现全局最优解。

(3)不能较好的解决连续域问题。

(4)由于蚁群算法中蚂蚁个体的运动过程的随机性,当群体规模设置较大时,很难在较短时间内从杂乱无章的路径中找出一条较好的路径。

(5)信息素更新策略,路径搜索策略和最优解保留策略都带有经验性,没有经过严格的理论论证。因此基本蚁群算法的求解效率不高、收敛性较差、求解结果具有较大的分散性。 4.2 发展趋势

随着蚁群算法在工程实践中应用的深入和系统复杂性的增加,需要处理的数据量也越来越大,这些问题的影响日益突出,使得单纯一到两种智能方法往往不能很好的解决问题。由于蚁群算法易与其他进化算法或者局部搜索算法结合。所以如何根据实际情况融合多种智能方法必将成为今后蚁群算法新的研究热点。

目前,蚁群算法的研究大多集中在算法、模型的更新,以及软件的开发上,所处理的数据也都是静态的。硬件的运行速度要高于软件,如何利用硬件的优势,利用DSP,FPGA和PLC等硬件实现蚁群算法,并使它能够应用于实时系统将是以后研究的一个方向。 参考文献

龙源期刊网 http://www.qikan.com.cn

[1] Colorni A,Dorigo M,Maniezzo V,et al.Distributed optimization by ant colonies

[A].Proceedings of ECAL91(European Conference on Artificial Life) [C].Paris,France:1991:134～142.

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

[3] Bilchev G and Parmee I C.Searching heavily constrained design spaces[C].In Proc.of 22nd Int.Conf,Computer Aided Design 95.Yelta:Ukraine,1995:230～235.

[4] Marcin L P,Tony W.Using genetic algorithms to optimize ACS-TSP[C].Proc of 3rd Int workshop ANTS.Brussels, 2002:282～287.

[5] 陈烨.带杂交算子的蚁群算法[J].计算机工程,2001,27(12):74～76.

[6] Zurada J M.Introduction to Artificial Neural System[M]. West Publishing Company,1992. [7] 张扬,曲延滨.基于蚁群算法与神经网络的机械故障诊断方法[J].机床与液压,2007,35(7):241～244.

[8] 金飞虎,郭琦.基于蚁群算法的Hopfield神经网络在多空间站路径规划的应用研究[J].计算机应用研究,2010,27(1):51～53.

[9] 汪怔江,张洪伟,雷彬.基于蚁群算法的神经网络在企业资信评估中的应用[J].计算机应用,2007,27(12):3142～3144.

[10] Pawlak Z. Rough sets[J].International J of Computer and Information Sciences,1982,11(5):341～356.

[11] 袁浩.基于量子蚁群算法的粗糙集属性约简方法[J].计算机工程与科学,2010,32(5):82～84.

[12] 王天擎.基于粗糙集的蚁群算法不确定性分析[J].计算机工程与设计,2008,29(24):6337～6339.

[13] Slimane-Kadi, M,Brasen,D.and Saucier G.A fast-FPGA prototyping system that uses

inexpensive high-performance FPIC.Proc.2nd Annual Workshop on FPGAs,Berkeley,1994:147～156. [14] B.Scheuermann,K.So,M.Guntsch,M.Middendorf.FPGA implementation of population-based ant colony optimization[J].Applied Soft Computing,2004,4:303～322.