蚁群算法中的信息素更新方法探讨(2)
时间:2018-05-05 21:31 来源:毕业论文 作者:毕业论文 点击:次
统一的指挥， 但它们却可以相互帮助相互引导寻找食物。 据此意大利学者 Dorigo M 等 人提出了蚁群算法（Ant Colony Algorithm，ACA） 。该算法采用正反馈并行机制，带 有很强的鲁棒性，并且包括优良的分布式计算机制、易于与其他方法结合等优点 ] 4 [ 。 当时，Dorigo M 等人于法国巴黎召开的第一届欧洲人工生命会议（European Conference on Artificial Life，ECAL）上首次提出了蚁群算法，但在之后的 5 年 中没受到国际学术界的广泛关注。1996 年 Dorigo M 等人在《IEEE Transactions onSystems，Man，and Cybernetics-Part B 》上发表了“Ant System：optimization by a colony of cooperating agents”一文，这才奠定了蚁群算法的基础 ] 13 [ 。在这之后 的几年里，蚁群算法慢慢发展起来，成为了国际学术界的广泛关注的对象。1998 年， Dorigo M 组织的第一届蚁群算法国际研讨会于比利时布鲁塞尔召开。 两年后， Gutjahr W J 发表了题为“A graph-based ant system and its convergence”的学术论文， 他在文中首次证明了蚁群算法的收敛性 ] 14 [ 。同一年中，Dorigo M 和 Bonabeau E等人 在国际顶级学术杂志《Nature》上发表了蚁群算法研究综述，这使得蚁群算法成为了 国际学术界的前沿课题。 目前蚁群算法整个体系的发展不是很完整，在研究中其经验性太强，没有完善普 适性强的理论，且搜索时间过长，易于停滞等问题也逐渐暴露出来。为了使蚁群算法 更高效更适用于实际应用，学者们竞相研究并提出各自的改进算法。例如，蚁群系统 (Ant Colony System．ACS)算法，此算法使用伪随机比例状态转移规则选择下一个城 市,在每一次迭代中只让最好个体所走过的路径上的信息素进行调整。Dorigo 和 Gambardella提出的 ACS 算法虽然加快了收敛速度，由于强化了最优信息的反馈，可 能会导致早熟、 停滞现象 ] 17 [ 。 又例如 Stutzle 和 Hoos 提出的最大一最小蚂蚁系统(Max —Min Ant System，MMAS)对路径上的信息素进行限制，有效避免了算法的早熟、停 滞现象 ] 16 [。2 蚁群算法原理 2.1蚁群觅食的特性 单个的蚂蚁功能简单、相对弱小，为什么蚂蚁总是能避开障碍物找到食物源，并 最终找到蚁穴到食物源的最短路径距离？他们具有智能么？其实，这是简单规则的涌 现。每只蚂蚁都遵循简单的规则，他们只能察觉周围很小范围内的东西，然后根据有 限的信息进行决策，然后在大量的蚂蚁共同行动，完成复杂的问题。这就是人工生命 科学。下面，我们来看看这些简单的规则： 1、环境规则： 蚂蚁存在于一个有障碍物、蚂蚁和信息素的虚拟世界。信息素也有不同的种类，食 物信息素能够引导蚂蚁寻找食物，而巢穴信息素则指引蚂蚁回巢。在一定范围内，蚂蚁能 从环境中得到许多信息（如信息素浓度） 。在环境中，信息素会随着时间流逝以一定 的速度挥发。 2、范围规则： 蚂蚁能观察到的范围是其周围的一个方格世界，蚂蚁的速率有限，假设为1的话， 那么它能观察到的范围就是它周围的8个方格，并且其下一步的位置只能是这8个方格 中的一个。 3、移动规则： 当它在周围没有感知到信息素的时候，蚂蚁会保持自己原来的运动方向，并且，在运动 的过程中，蚂蚁以很小的概率使其前进方向与原来的方向发生偏差；若环境存在信息素，则蚂 蚁将优先朝信息素浓度高的的方向走。 4、觅食规则： 在蚂蚁的可观察范围内，蚂蚁首先会观察是否有食物，有则直接去搬运；否则蚂 (责任编辑：qin) |