基于自适应蚁群算法的分析和延展

1 自适应蚁群算法的概述

蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合,这种算法在构造解的过程中,利用随机选择策略,这种选择策略使得进化速度较慢,正反馈原理旨在强化性能较好的解,却容易出现停滞现象。这是造成蚁群算法的不足之处的根本原因。因而从选择策略方面进行修改,采用确定性选择和随机选择相结合的选择策略,并且在搜索过程中动态地调整作确定性选择的概率,当进化到一定代数后,进化方向已经基本确定,这时对路径上信息量作动态凋整。缩小最好和最差路径上的信息量的差距,并且适当加大随机选择的概率,以小于l对解空间的更完全搜索,从而可有效地克服基本蚁群算法的不足,此算法属于自适应算法。该算法按照下式确定蚂蚁由所在转移到下一个城市S。

其中,q∈(0,1),τ是(0,1)中均匀分布的随机数。当进化方向基本确定后,简单的放大(或缩小)方法调整每一路径上的信息量,该方法不仅能够加快收敛速度,节省搜索时间,而且能够克服停滞行为的过早出现,有利于发现更好的解,这对于求解大规模优化问题是有益的。通过标准蚁群算法的对比,学者就提出了一种自适应蚁群算法。

2 自适应的信息更新策略

蚂蚁在行进过程中常常选择信息量较大的路径,但当许多蚂蚁选中同一条路径时,该路径中的信息量就会陡然增大,从而使得多只蚂蚁集中到某一条路径上,造成一种堵塞和停滞现象,表现在使用蚁群算法解决问题时就容易导致早熟和局部收敛。为了解决这一问题,提高蚁群算法的全局收敛能力和搜索速度,许多文献提出了各种不同的更新信息量的策略,如引言中所谈到的蚁群算法,在更新信息量时:1)只要蚂蚁遍历时选择此路径就更新其路径上的信息量;2)只让最优适应度的路径上的信息量增强,而其余路径上的信息量被削减;3)基于等级变化的算法,让适应度相对较好的蚂蚁固定在若干条路径上,根据其解的优劣程度决定信息量的增加幅度。这些算法虽然各不相同,但主要都采用固定信息量增减的比例来进行信息量的更新,都忽视了解的分布特征,在一定程度上虽对蚁群算法的特性进行了一定的改进,但这一般只适合于处理较小规模的问题,为了解决较大规模的问题,这里从解的分布状态入手,提出了一种新的自适应的信息量更新策略。

当问题规模较大时,由于信息量挥发系数的存在,使那些从未被搜索过的路径上的信息量减小到接近于0,从而降低了算法在这些路径上的搜索能力,反之,当某条路径中信息量较大时,这些路径中的信息量增大,搜索过的路径再次被选择的机会就会变得较大,这也影响了算法的全局搜索能力,此时通过固定地变化挥发系数虽然可以提高全局搜索能力,但却使算法的收敛速度降低,因而提出一种自适应的改变τ值的方法,将信息素更新公式:

这里c为常数,根据解的分布情况自适应地进行信息量的更新,从而动态地调整各路径上的信息量强度,使蚂蚁既不过分集中也不过分分散,从而避免了早熟和局部收敛,提高全局搜索能力。

3 小结

自适应蚁群算法作为一种新的生物进化算法,目前还没有遗传算法、模拟退火等那样形成较系统的分析方法和坚实的数学基础,各种参数的确定也没有一定的理论指导,相信经过进一步研究,自适应蚁群算法在求解人类基因的问题中的应用前景会更广阔,将会同其他生物进化算法一样获得越来越广泛的应用和坚实的理论根据。

摘要：本文首先了解了自适应蚁群算法的产生及原理,接着主要论述了自适应蚁群算法的信息更新策略。

关键词：蚁群算法,自适应调整,路径

参考文献

[1] 忻斌健,吴启迪,等.蚁群算法的研究现状及其应用[A]//中国控制与决策学术年会论文集[C],2001.

[2] 张纪会,徐心和,胡勇,等.带遗忘因子的蚁群算法[J].系统仿真学报,2000(2):22-30.

[3] 张纪会,徐心和,胡勇,等.一种新型的模拟进化算法:蚁群算法[J].系统工程理论与实践,1999(3):84-87.

[4] 唐飞,膝弘飞,等.十进制整数编码遗传算法的模式定理[J].计算机科学,1999,12(6):54-56.

[5] 杨秋贵,张杰,张素贞,等.基于拟牛顿法的前向神经元网络学习算法[J].控制与决策,1997,12(4):357-360.