蚁群算法在路径优化中的应用3改

蚁群算法在路径优化中的应用

作者：孙阳阳 指导老师：刘冲

摘要 针对蚁群算法在路径中的优化问题，本文首先介绍了蚁群算法的概念及其原理，利用数学

形式建立算法模型.根据蚁群算法计算的基本步骤来分析蚁群算法在交通路径优化、TSP问题等3个方面的应用，由实验结果可知蚁群算法在路径优化中具有很好的可行性和优越性，能起到很好的效果.

关键词 蚁群算法 算法模型 算法步骤 分析应用

1 引言

路径规划是指在具有障碍物的环境下，在符合某种评价条件中，寻找到一条从起始地

点到目标地点最优的路径.蚁群算法是近几年优化领域中新出现的一种启发式仿生类并行智能进化系统,计算法采用分布式并行计算和正反馈机制，且易于其它算法结合，目前已有许多关于其在路径规划方面的文献.

建立蚁群算法模型

[1][2]，解决城市交通路径优化问题，实验结果表面在搜索效率和搜索

最优解的能力两方面都有很大的提高.但是传统蚁群算法易陷入局部最优解和收敛速度较慢，为此在机器人路径规划的应用中

[4?7]，将传统蚁群算法进行改进，例如与栅格法相结合、

在几何模型下建立模型等.提高了算法的有效性和鲁棒性，解决了蚁群过早陷入局部最优解的问题，扩大了蚂蚁的搜索空间，增强了蚁群算法在机器人路径规划中的适应能力.

本文通过对蚁群算法的研究以及解决几实际路径规划问题，得出了蚁群算法是有其可行性和优越性的，说明了该算法可以在众多优化领域中得到广泛的应用.

2 蚁群算法

蚁群算法(ant colony optimization),又称蚂蚁算法，简称ACO.是由Dorigom、Maniezzov、Colorni等人在1992年所发表的论文提出的，其灵感来源于蚂蚁在寻找食物中发现路径的行为.它是一种模拟进化算法，通过人工模拟蚂蚁觅食过程，即个体间的信息交流与合作不断排除不适合的路途，最终寻找到从蚁穴到食物源的最短路径.

2.1 蚁群算法的基本原理

蚂蚁在搜寻食物过程中总能找到一条从蚁穴到到食物的最优路径，这是因为蚂蚁在搜寻路径上释放一种特殊的信息素.当它们遇到一个还没有被走过的路口时，会随机的选择一条路径，而选择的路径与信息素的浓度有关，同时在该路径上它们也会释放自己的信息素.路径越短，信息素浓度越大；反正路径越长信息素堆积的越少.则过一段时间蚂蚁选择信息素浓度高的路径的概率越来越大，而其它路径随着蚂蚁越来越少的选择信息素浓度逐渐减小，这一就形成了一个正反馈现象，最终指导整个蚁群找到从蚁穴到食物源的最短路径.

2.2 蚁群算法的数学模型 2.2.1 问题的描述

求解两地间最优路径，即为求某两地间用时最少的行进路线.如在一个城市中，有A、B

两个地点，从A到B有多条路径线路可选，即求一条从A到B用时最少的路线.又比如在当今热门研究项目机器人路径规划问题中，其本质为在规划空间内依据环境信息，在某些评价标准下，找出从出发点到目标点最优的路线，比较有代表的问题是喷涂机器人，即在一个复杂曲面上如何规划喷涂机器人的路径，使其喷涂效率最高.

这些问题都符合蚁群算法的思想，因此可以用蚁群算法来求解.

2.2.2 模型的建立

首先将蚂蚁觅食与路径优化问题进行对照如表1所示

表1 蚂蚁觅食和路径优化对照表

蚂蚁觅食 蚂蚁要遍历的各个路径 整个蚁群经过的一条完整的路径

最短路径 信息素的浓度 信息素的更新 路径的长度

路径优化问题 各个状态 解 最优解 各状态的吸引度 状态更新 目标函数

以旅行商问题（TSP）为例来构建模型，定义路与路段的交叉口为节点，路段为边.即TSP问题可描述为给定n个节点和每两个节点之间的距离，要寻找到一条路径，从某个节点出发周游到其它节点一次且仅一次，最终回到出发节点的封闭环路径长度最短.设节点数为n，蚂蚁的数目为m，蚂蚁从一个节点到另一个节点逐步完成搜索的过程.蚂蚁k(k=1,2,3...m)，根据概率转换的规则选择下一个节点.由此可以生成一个由n个节点组成的行动路线，并伴有信息素的不断更新.bi(t)表示位于t时刻节点i的蚂蚁数目.则有：

m?b1(t)?b2(t)?...?bn(t);dij(i,j?1,2,3....,n)

d 表示两个节点 i 和 j 之间的距离

在基本蚁群算法模型中，人工智能蚂蚁有以下特点：

(1) 人工智能蚂蚁具有记忆功能.每一个蚂蚁k(k=1,2,3,....m)都有一个禁忌表(tubek)，即蚂蚁经过节点i(i?n)后，不能再经过节点i.

(2) 两个节点的距离越近，能见度则越大，被选择的期望也就越高，由此来指引人工智能蚂蚁的搜索.定义?ij?的概率可表示为：

1，被称为期望因子，所以蚂蚁k在t时刻从节点i转移到节点jdij???(t)????(t)????ij??ij?,j?Jk(i)???k （1） pij(t)?????is(t)???is(t)??s?Jk(i)?0,j?Jk(i)?其中tubek(s)表示禁忌例表中第s个元素，即蚂蚁所走过的第s个节点；Jk(i)为蚂蚁所允许到达的节点的集合，期望因子?ij表示对边i,j上的期望程度；Jk(i)??1,2...,n??tabuk；

?表示信息素的相对重要程度；?表示启发式因子的相对重要程度.这里需要重点说明一下：

当?取较大值时，蚂蚁在选择路径的过程中路上的信息素非常重要；当?取较小值时蚁群算法变成随机的贪婪算法.?取较大值时会使整个蚁群陷入随机搜索，这样的话收敛速度 较慢，很难找到最优的结果，?取较小值时虽然加快了收敛速度，这样会很快得到一个最优解但是容易陷入局部最优的状况.

(3) 在蚁群算法中有一个非常重要的参数指标，就是信息素浓度.蚁群在节点i到节点j时，算法会在路径ij上遗留信息素，而信息素是时时刻刻动态变化的，它的多少决定蚁群选择该路径的概率大小.下面我们给出信息素浓度公式，设?ij(t)表示t时刻i,j上的信息数浓度，则在t+n时刻此路径上的信息素浓度为 ?ij(t?n)?(1??)?ij(t)????k?1mkij(t) （2）

1)它表示信息物质的保留率；??ij(t)表示时刻t在蚂蚁k在路径ij上信息式中，?(0＜?＜素的增量.

k?Q若蚂蚁k在本次周游中经过ij ?，k??ij(t)??Lk （3）

?0，否则 ?式中，Q表示蚂蚁释放的信息素量；L表示蚂蚁k在本次周游遍历中所经过边的总和长度,Lk表示本次遍历中蚂蚁所用的时间总和.

以上4个因素即禁忌列表、期望因子、概率转换规则、信息素浓度蚁群系统路径选择的实现和信息素更新策略，两者互相配合，实现模型的正反馈机制，促进人工智能蚂蚁收敛于最优解.

根据信息素更新策略的不同，又出现了3种不同的模型：蚁量模型、蚁密模型、蚁周模型.

① 蚁量模型

?Q?d,蚂蚁k在时刻t和t?1经过ij k??ij(t,t?1)??ij （4）

?0,否则 ?在式中，Q为常量，信息素的增加量与边ij的长度有关. ② 蚁密模型

?Q，蚂蚁k在时刻t和t+1经过ij k??ij(t,t?1)?? （5）

?0，否则

在式中，Q为常量，也就是说信息素增加量只是个固定值，与边ij的距离无关. ③ 蚁周模型

?Q?,蚂蚁k在本次周游中经过边ij k ??ij(t,t?1?)?Lk （6）

?0,否则 ?在式中，Q是常量表示k只蚂蚁的周游路线，即如果蚂蚁经过边ij信息素的增加量为一个常量除以蚂蚁k循环路线长度.这里信息素的增加量只与蚂蚁的循环路线和Q有关，与dij没有关系.在该模型中采用了全局信息的更新，较前两种模型性能更优.原因是蚁周模型利用整体

信息，即蚂蚁在历经一个循环路径所释放的信息素量与所得解的质量成正比.周游路径长度越短的蚂蚁，释放在该路径上的信息素量越多，而前两种模型在搜索解时，只使用了局部更新信息，没有用到任何解的信息.

2.2.3 选参原则

讨论的参数包括?,?,?,m,Q.上文已经提到信息素的相对重要程度?和启发式因子的

重要程度?对算法模型的影响，这里主要说下信息素蒸发系数?，蚂蚁数目m以及蚂蚁释放的信息数量Q对搜索过程的影响.?增大，残留信息素1??减少，负反馈机制增强，随机性增强，利与发现更多最优解，但是收敛性降低.反之?增大，残留信息素增加，正反馈加强，虽然收敛性加快，但是随机性减弱容易陷入一个范围狭小的搜索圈，所以搜索质量并不高.蚂蚁数m较小时，会使为走过路径上的信息素减小为0，即搜索的随机性能会降低，虽然加快了收敛性，但是搜索的全局性能降低，算法稳定性差，容易陷入过早的停滞.m较大时，会使搜索路径上的信息素浓度过于平均，收敛速度变慢.对于蚂蚁释放的信息素量Q来说是一个常量，Q越大，路径信息素积累越多，收敛速度越快.显然可见，参数的选择对于搜索的准确性是很重要的，这里选参原则如下：

(1) 确定蚂蚁数目m,可参照“问题规模数约为蚂蚁数目的1.5倍”; (2) 参数?,?的粗调，常用的几种组合有(??1,??1),(??1,??2),

??5)(?,?0.5?,? (??1,5 )(3) 参数?细调，?通常设定在0.5以下.

2.3 蚁群算法的基本步骤（流程）

这里主要是以蚁周算法为例，总结蚁群算法的基本步骤.

流程框图如下所示：

注: (1) 在流程图中整个算法的迭代过程是以N为刻度，1?N?Nmax（Nmax为最大迭代次数）.在迭代过程中以时间t为刻度(1?t?n),蚂蚁k根据概率转换公式选择下一个节点.

(2) 禁忌表(tube):禁忌表是为了避免蚂蚁走进同一个节点的数据结构.设tubek为蚂蚁k