|
- UID
- 1029342
- 性别
- 男
|
蚁群算法是一种新型的模拟自然界蚁群行为的进化算法，由意大利学者Dorigo M等人于20世纪90年代初首先提出。该算法采用了分布式并行计算机制，易于与其他优化算法相结合，而且具有鲁棒性较强、正反馈等许多优点，具有无中心控制和分布式个体之间间接通信的特征，被广泛的应用于求解复杂的优化问题。但该算法也存在如搜索时间长、易陷于局部最优解、收敛速度慢等不足。针对这些不足，国内外学者提出了许多改进的蚁群算法。本文介绍了蚁群算法的基本原理及其研究进展情况，并且介绍了蚁群算法的几个应用领域，对其几个研究方向作了展望。 1、蚁群算法的基本原理
蚁群算法（ant colony algorithm，ACA），又称蚂蚁算法，是一种用来寻找最优解决方案的机率型技术。蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物选择其要走的路径，其选择一条路径的概率与该路径上分泌物的强度成正比，即信息素强度越高的路径，选择它的蚂蚁会越多。反之，路径上经过的蚂蚁越多，则在该路径上留下的信息素的其强度就更大，如图1所示：
.jpg)
设A是蚂蚁的巢穴，B是食物源，CD为一障碍物。现今蚂蚁要从A到B，由于中间有障碍物CD，可知蚂蚁有A-C-B或A-D-B两条路径，同理可知从B到A存在相似的情况。假设单位时间有8只蚂蚁从A到B，有8只蚂蚁从B到A, 蚂蚁过后留下的信息素为1，ACB距离是ADB距离的一半。刚开始蚂蚁经过C和D都是以相同概率选择的如图1（a）。一个时间单位后，ACB上的信息素为ADB上的信息素的2倍。再经过一段时间, 就会有6只蚂蚁经过ACB, 如图2（b）。随着时间发展, 蚂蚁会以越来越大的概率选择路径ACB，最终会完全选择路径ACB，从而找到巢穴到食物源的最短路径。
因此，由大量蚂蚁组成的群体的集体行为，实际上构成一种学习信息的正反馈现象：某一条路径走过的蚂蚁越多，后面的蚂蚁选择该路径的可能性就越大。蚂蚁的个体间通过这种信息的交流，寻求通向食物的最短路径。蚁群算法就是根据这一特点，通过模仿蚂蚁的行为, 从而实现寻优。
2、蚁群算法的研究
20世纪90年代初，蚁群算法首先成功应用与求解TSP问题，引起了许多学者的关注，成为研究热点之一，并不断提出新的改进算法，使蚁群算法得到了广泛的应用。算法的改进主要是从局部搜索策略、蚂蚁内部状态、信息素更新策略及选择策略四个方面进行，都取得了较好的效果。如自适应蚁群算法、基于信息素扩散的蚁群算法、多态蚁群算法、基于信息熵的改进蚁群算法、基于网格划分策略的连续域蚁群算法、基于交叉变异操作的连续域蚁群算法等。
蚁群算法还能与其他优化算法相融合，从而相互取长补短，改善算法的性能。目前这方面的研究有蚁群算法与遗传算法、人工神经网络、粒子群算法及人工免疫算法等算法之间的融合。这些融合了的算法在解决某些特定问题时，表现出了比较优异的性能，因此，设计新的融合策略结合其他优化算法进一步改善蚁群算法的性能是非常有意义的研究方向。
蚁群算法的参数设置对算法的性能也有重要的影响。Solno提出了在蚁群算法运行前加入一个预处理阶段，这个阶段先不使用信息素找到一定数量的路径，再从中选择部分路径在算法开始前初始化信息素，获得了较好的效果。然而对这方面的研究相对较少，因此参数的设置原则也值得深入的研究。
3、蚁群算法的应用
蚁群算法最初被应用到经典的组合优化问题，随着研究的深入，应用范围扩大到更多的组合优化问题，如在作业调度、网络路由、电力系统、生命科学、空战决策、聚类分析等领域都得到了广泛的应用，体现了蚁群算法的实用性和通用性。以下是几个蚁群算法应用的例子。
3.1网络路由问题
将蚁群算法应用于解决受限路由问题，目前可以解决包括带宽、延时、丢包率和最小花费等约束条件在内的QoS组播路由问题，比现有的链路状态路由算法有明显的优越性。王卫亚等人将蚁群算法和遗传算法相结合的融合算法用于对带宽、时延和差率等多项QoS参数有要求的最优路由选择，在优化性能和时间性能上都取得了很好的效果。李俊等人提出了一种基于改进蚁群算法的分布式动态RWA方法，用于解决波分复用光网络中动态选路和波长分配问题，与现有最短路径相比，该算法有效降低了光路阻塞率，促进波长资源的合理分配，也降低了大型网络的通信开销。
3.2电力系统领域
电力系统的许多优化问题本质上是属于组合优化问题。Gomez等人将蚁群算法应用于配电网络的规划。王林川等人将一种改进蚁群算法应用于配电网故障的定位。王海燕等人将蚁群算法应用于电力系统暂态稳定评估特征选择，减少了特征维数，提高了分类正确率。电力系统的这些组合优化问题的有效解决将为电力企业节省大量的资金，因此在电力系统的应用具有很大的实际价值。
3.3航迹规划问题
航迹规划是指在特定的约束条件下，寻找运动体从初始点到目标点满足某种性能指标最优的运动轨迹。在空防技术日益先进、防空体系日益完善的现代战争中，航迹规划是提高飞行器作战效能、实施远程精确打击的有效手段。因此对航迹规划方法的研究将有重要的现实意义。田伟等人提出了一种改进蚁群算法用于无人作战飞机的航路寻优过程，提高了无人作战飞机的航路寻优能力。孟祥恒等人将蚁群算法用于多无人机航迹规划。曹晋等人提出了一种基于蚁群算法的最小代价航迹规划方法，解决了航迹维数解算问题，为飞行器提供最优航迹规划路径。
4、存在的问题及解决方法的进展
蚁群算法以其分布式并发性、正反馈、鲁棒性强、收敛速度快、易获得全局最优解等特点，成为目前国内启发式算法研究的热点，但是蚁群算法也存在如下缺点：容易出现停滞现象（stagnation behaviour），算法运算时间过长。针对这些缺陷，近年来众多国内外的学者在蚁群的改进方面做了大量的研究工作, 其目的是在合理时间复杂度的限制条件下，尽可能提高蚁群算法在一定的空间复杂度下的寻优能力，从而改善蚁群算法的全局收敛性，扩宽蚁群算法的应用领域。
M.Dorigo等人提出一种修正的蚁群算法为Ant-Q System，该算法和基本蚁群算法有如下不同：
（1）状态转移规则不同：仅让信息量最大的路径以较大的概率选中。
（2）全局更新规则不同：仅对一次循环中的最优的蚂蚁使用。
（3）增加更新规则：在所有蚂蚁完成一次转移后执行。
德国学者Thomastuzle和Holerhoos提出了一种改进的算法即最大最小系统（MAX-MINant system，MMAS）。为了防止算法过早的停滞，MMAS限定了信息量允许的上下限，并且采用了平滑机制对蚂蚁系统的解进行了改进。1999年，M.Dorigo把先前的各种蚁群算法归结为ACO元启发式算法（ant colony optimization metar-heuristic）的概念，把各种基于蚁群系统的算法归结到一个统一的框架中。作为一种新型的启发式算法，ACO元启发式算法近年来受到广泛的关注。
一些学者把蚁群算法和其它的一些仿生优化算法进行融合，并且取得了较好的应用效果。Abbattista F等人最早提出将遗传算法（GA）和蚁群算法相融合的策略，并且在Oliver30TSP和Eilon50TSP的仿真实验中得到了较好的结果。候云鹤等人将微粒群（PSO）引入蚁群算法（GACA）的局部搜索中，采用GACA进行全局搜索，确定最优解存在的领域。Lee Z J提出一种新的融合算法即免疫-蚁群算法，并将其成功应用在求解WTAP。蒋加伏等提出了一种基于免疫-蚁群算法的多约束QoS路由选择算法，也取得了很好的应用效果。
5、结束语
蚁群算法自20世纪90年代出问世以来，其理论和应用都有了很大的进步，从最初求解TSP问题开始，逐渐发展为一个优化工具，并成功地应用到科学和工程中的多个领域。蚁群算法具有分布式计算、无中心控制、个体之间异步间接通信等特点，并且易于与其他优化算法相结合。同时其也存在一些缺点，因此蚁群算法还有很大尚待解决的问题，其应用也有待进一步挖掘。蚁群算法仍有很多方面值得深入研究：
（1）目前大部分改进蚁群算法的普适性不强，同时其模型也不能直接应用于实际优化问题。因此，对通用的蚁群算法普适性模型的研究值得深入下去。
（2）同其他几种仿生优化算法相比较，蚁群算法没有坚实的数学基础。具备坚实的数学理论基础，将使蚁群算法得到更加广泛的应用。因此，这方面也值得深入研究。
（3）蚁群算法以其他算法之间的比较研究还处于起步阶段，与其他算法之间融合机制和策略仍有待进一步的探讨。
（4）仿生硬件是并行计算环境下的产物，蚁群算法的硬件实现是仿生硬件研究领域中的一个新分支，还存在许多问题需要解决。
（5）目前蚁群算法的应用领域大多是静态组合优化问题，如何使其应用于动态组合优化问题和连续优化问题也是一个研究方向。
总之，蚁群算法是一种很有前途的一种算法，也是一个很值得研究的领域。随着对其研究的不断深入，其应用也将更加广泛，其理论将更加成熟。 |
|
