阅读量：

404

作者：

杨学峰

展开

摘要：

近年来,人们将自然界的许多有益特性应用于工程实际。蚁群算法就是借鉴自然界中群居性昆虫通过自组织的合作能力所产生的群集智能解决组合优化问题的典型例子。蚁群算法是由意大利学者Dorigo M等人于20世纪90年代初期,通过模拟自然界中蚂蚁群体寻优行为而提出的一种新兴的启发式仿生进化算法,它在解决旅行商问题中取得了较好的结果。在求解旅行商问题(TSP)时,首先引入交叉策略进行预处理,将具体的地图抽象为常见的无向完全图,即把TSP抽象为求无向完全图的一条Hamilton回路,然后用蚁群算法与人工神经网络相结合的方法来求解。实验结果表明了该方法的可行性和高效性。在介绍蚁群算法的原理和特点后,着重分析了当前一些有代表性的蚁群算法的改进机制和应用成果,并采用比较的方式指出了这些方法的特点和主要应用范围等,最后总结了好的蚁群算法应具有的特点以及将来的研究策略与发展趋势。 蚁群算法的应用领域很多,如应用于TSP、Job shop调度问题、大规模集成电路综合布线问题、电信网络路由问题等。针对蚁群算法的缺陷提出了许多改进算法,并且把改进的蚁群算法应用到不同的新领域。由于基本蚁群算法利用随机选择策略,使得进化速度较慢;同时,蚁群算法旨在利用正反馈原理和分布式计算的模式,却未能较好地加快进化过程及避免过早收敛,反而容易出现停滞现象。针对蚁群算法加速收敛与早熟、停滞现象等的矛盾和寻找最优解的时间过长等缺点,可以从以下方向改进蚁群算法。 (1)算法的自适应性。①从选择概率来看,可以采用不同的阶段使用不同的选择概率,在寻路的过程中动态地调整选择概率,并且可以使用选择概率的不同方法。②信息素更新策略的自适应,应该能对信息素进行动态更新和自适应调节。③如果把寻路过程优化为几个不同的阶段,并且在不同阶段采用不同的方法,则应该自适应地分析蚁群个体进行的程度已经到哪个阶段了,选择应该执行什么样的策略等。④蚁群算法的公式中各个参数的自适应选择。 (2)初始解的优化。由于各个路径上的初始信息素是相同的,初始解即第一次选择的路径很可能对整个蚁群的进化过程产生误导,必须提高初始解的质量,尽量扩大在初始阶段可以选择路径的数目,以增加解的多样性。 (3)信息素动态更新策略。信息素的浓度强弱直接关系到蚂蚁个体的寻优过程。如何让信息素动态、自适应地更新,如何通过信息素作用的扩散和信息素种类的增加等方法来达到蚂蚁间的协作,以及如何调整信息素的更新公式,都是非常重要的。 (4)路径选择概率的适应性调整。①应该实现选择概率的自适应;②按照不同的应用、不同的实际环境等合理设计和调整选择概率公式等。 (5)门槛值的设计。信息权重、感觉阈限,对于设计这种门槛值,能够定义信息素、选择概率等发挥作用的区间或临界点,把蚁群算法分为不同的阶段、不同的策略来实施等,也辅助了自适应的实现。 (6)蚂蚁的协作。已经有较多研究提到了蚂蚁间的协作,并且有研究者提出要把蚂蚁分成多类,不同的类别实现不同的策略、完成不同的工作,然后再通过蚂蚁间的协作达到更优的策略。正如在真实的蚁群世界中,蚂蚁也是被分了类的,不同类别的蚂蚁完成不同的工作。蚂蚁的协作在一定程度上优化了算法,但也增加了算法的复杂性。 论文还延伸到了以下几种基于蚁群算法的相关研究 (1)基于蚁群算法的地图矢量化算法研究 (2)动态自适应蚁群算法在二次分配问题中的应用采用一种新算法动态自适应蚁群算法解决二次分配问题,并引入3-opt方法对问题求解进行局部优化,通过对二次分配问题的不同实例进行实验,结果表明,该算法在求解二次分配问题上具有较好的能力,可以很好地解决较大规模的二次分配问题,而以往的算法只适合于处理较小规模的二次分配问题。 (3)基于蚁群算法的实质性应用蚁群算法最初被应用到经典的组合优化问题,随着研究的深入,应用范围逐渐扩大到更多的组合优化问题,而且目前已有将蚁群算法应用到连续优化问题的研究。 (1)静态组合优化问题中的应用 蚁群算法目前已经在诸多领域得到应用,如水资源规划、电力系统的优化、物流领域等等。典型的组合优化问题。从最初用蚁群算法解决旅行商问题开始,研究者们陆续将其应用到其它典型的组合优化问题:二次规划问题、图着色问题。这些问题具有很强的工程代表性,蚁群算法在典型的组合优化问题上的出色表现加速了它在工程应用领域的发展。 (2)动态组合优化问题中的应用 在动态组合优化问题中,问题的解随时间而变。蚁群算法在动态组合优化问题的中的应用研究集中在通信领域。Schoonderwoerd等一副人率先将蚁群算法用于通信网络的路由问题,提出了基于蚁群算法的路由算法。Dic Caro等人基于蚁群算法设计了自适应路由算法AntNet,每个节点根据网络的状况动态更新路由表项。Hussein等提出了改进的蚁群算法应用于移动自组织网络的路由问题。通信网络的一些特征,如分布式的信息存储结构、网络的动态特性等与蚁群算法的本质特性非常类似,因此蚁群算法在通信领域中有广泛的应用前景。 (3)连续优化问题中的应用 目前蚁群算法在连续优化问题中的应用相对较少。BiIchev等最先尝试用蚁群算法解决连续优化问题。Ho等通过改进信息素更新策略提出了求解连续优化问题的蚁群算法,算法应用在电磁装置的优化设计上获得了良好的效果。目前将蚁群算法应用于连续优化问题的研究才刚刚起步,连续优化问题与组合优化问题相比,它们的最终优化目标不同,因此需要在信息素更新策略、蚂蚁的状态转移策略上进行改进以适应连续的连续优化问题的求解。 以上是蚁群算法中最重要的改进和优化的主要方向,当然还有蚁群算法中参数的优化,如信息素挥发系数的优化等。 对于蚁群算法的研究一直都未停止,研究者尝试各种策略来解决蚁群算法问题以及探索其能够适合的各种应用场合。通过阐述蚁群算法的最新进展和应用前景,可以展示蚁群算法的发展、需要解决的问题以及为使用蚁群算法提供思考。

展开

关键词：

蚁群算法 TSP问题 并行蚁群算法 信息素 ant colony algorithm TSP problem parallel pheromone

DOI：

CNKI:CDMD:2.2011.014305

被引量：

36