蚁群算法简述及实现

《蚁群算法简述及实现》由会员分享，可在线阅读，更多相关《蚁群算法简述及实现（6页珍藏版）》请在金锄头文库上搜索。

1、蚁群算法简述及实现1 蚁群算法的原理分析蚁群算法是受自然界中真实蚁群算法的集体觅食行为的启发而发展起来的一种基于群 体的模拟进化算法,属于随机搜索算法,所以它更恰当的名字应该叫“人工蚁群算法”,我们一 般简称为蚁群算法。M.Dorigo 等人充分的利用了蚁群搜索食物的过程与著名的 TSP 问题的 相似性,通过人工模拟蚁群搜索食物的行为来求解 TSP 问题。 蚂蚁这种社会性动物,虽然个体行为及其简单,但是由这些简单个体所组成的群体却表现 出及其复杂的行为特征。这是因为蚂蚁在寻找食物时,能在其经过的路径上释放一种叫做信 息素的物质,使得一定范围内的其他蚂蚁能够感觉到这种物质,且倾向于朝着该物质强度

2、高的 方向移动。蚁群的集体行为表现为一种正反馈现象,蚁群这种选择路径的行为过程称之为自 催化行为。由于其原理是一种正反馈机制,因此也可以把蚁群的行为理解成所谓的增强型学 习系统(Reinforcement Learning System)。 引用 M.Dorigo 所举的例子来说明蚁群发现最短路径的原理和机制,见图 1 所示。假设 D 和 H 之间、B 和 H 之间以及 B 和 D 之间(通过 C)的距离为 1,C 位于 D 和 B 的中央(见图 1 (a)。现在我们考虑在等间隔等离散世界时间点(t=0,1,2)的蚁群系统情况。假设每单 位时间有 30 只蚂蚁从 A 到 B,另三十只蚂蚁从 E

3、 到 D,其行走速度都为 1(一个单位时间所走 距离为 1),在行走时,一只蚂蚁可在时刻 t 留下浓度为 1 的信息素。为简单起见,设信息素在 时间区间(t+1，t+2)的中点(t+1.5)时刻瞬时完全挥发。在 t=0 时刻无任何信息素,但分别有 30 只蚂蚁在 B、30 只蚂蚁在 D 等待出发。它们选择走哪一条路径是完全随机的,因此在两 个节点上蚁群可各自一分为二,走两个方向。但在 t=1 时刻,从 A 到 B 的 30 只蚂蚁在通向 H 的路径上(见图 1 (b)发现一条浓度为 15 的信息素,这是由 15 只从 B 走向 H 的先行蚂蚁留 下来的;而在通向 C 的路径上它们可以发现一条浓

4、度为 30 的信息素路径,这是由 15 只走向 BC 的路径的蚂蚁所留下的气息与 15 只从 D 经 C 到达 B 留下的气息之和(图 1 (c)。这时, 选择路径的概率就有了偏差,向 C 走的蚂蚁数将是向 H 走的蚂蚁数的 2 倍。对于从 E 到 D 来的蚂蚁也是如此。（a） （b） （c） 图 1 蚁群路径搜索实例这个过程一直会持续到所有的蚂蚁最终都选择了最短的路径为止。 这样,我们就可以理解蚁群算法的基本思想:如果在给定点,一只蚂蚁要在不同的路径中 选择,那么,那些被先行蚂蚁大量选择的路径(也就是信息素留存较浓的路径)被选中的概率就更大,较多的信息素意味着较短的路径,也就意味着较好的问题

5、回答。2 人工蚁群算法描述蚁群算法可以看作为一种基于解空间参数化概率分布模型(Parameterized Probabilistic Model)的搜索算法框架 (Model-based search algorithms)。在蚁群算法中,解空间参数化概率, 模型的参数就是信息素,因而这种参数化概率分布模型就是信息素模型。在基于模型的搜索 算法框架中,可行解通过在一个解空间参数化概率分布模型上的搜索产生,此模型的参数用以 前产生的解来更新,使得在新模型上的搜索能够集中在高质量的解搜索空间内。这种方法的 有效性建立在高质量的解总是包含好的解构成元素的假设前提下。通过学习这种解构成元 素对解的质量

6、的影响有助于找到一种机制,并通过解构成元素的最佳组合来构造出高质量的 解。一般来说,一个记忆模型的搜索算法通常使用以下两步迭代来解决优化问题: 1)可行解通过在解空间参数化概率分布模型上的搜索产生。 2)用搜索产生的解来更新参数化概率模型,即更新解空间参数化概率分布的参数,使得在 新模型上的参数搜索能够集中在高质量的解搜索空间内。 在蚁群算法中,基于信息素的解空间参数化概率模型(信息素模型)以解构造图的形式给 出。在解构造图上,定义了一种作为随机搜索机制的人工蚁群,蚂蚁通过一种分布在解构造图 上被称为信息素的局部信息的指引,在解构造图上移动,从而逐步的构造出问题的可行。信息 素与解构造图上的节

7、点或弧相关联,作为解空间参数化概率分布模型的参数。 由于 TSP 问题可以直接的映射为解构造图(城市为节点,城市间的路径为弧,信息素分布 在弧上),加之 TSP 问题也是个 NP 难题,所以,蚁群算法的大部分应用都集中在 TSP 问题上。 一般而言,用于求解 TSP 问题、生产调度问题等优化问题的蚁群算法都遵循下面的统一算法 框架。算法 1：求解组合优化问题的蚁群算法设置参数,初始化信息素踪迹 While(不满足条件时)do for 蚁群中的每只蚂蚁 for 每个解构造步(直到构造出完整的可行解) 1)蚂蚁按照信息素及启发式信息的指引构造一步问题的解; 2)进行信息素局部更新。(可选) end

8、for endfor 1)以某些已获得的解为起点进行邻域(局部)搜索;(可选) 2)根据某些已获得的解的质量进行全局信息素更新。 endwhile end在算法 1 中,蚂蚁逐步的构造问题的可行解,在一步解的构造过程中,蚂蚁以概率方式选 择信息素强且启发式因子高的弧到达下一个节点,直到不能继续移动为止。此时蚂蚁所走过 的路径对应求解问题的一个可行解。局部信息素更新针对蚂蚁当前走过的一步路径上的信 息素进行,全局信息素更新是在所有蚂蚁找到可行解之后,根据发现解的质量或当前算法找到 的最好解对路径上的信息素进行更新。3 蚁群算法与其他搜索算法比较3.1 蚁群算法与进化算法比较近年来,遗传算法(GA

9、)、进化规划(Evolutionary Planning)、进化策略(Evolutionary Strategies)在理论和应用上发展迅速、效果显著并逐渐走向了融合,形成了一种新颖的模拟进 化的计算理论,统称为进化计算(Evolutionary Computation)。因此我们可以用进化计算作为 代表与蚁群算法进行比较,从另一个角度来认识蚁群算法,加深对蚁群算法的理解。 蚁群算法与进化计算的相似之处有两点：首先,两种算法均采用群体表示问题的解;其次,新 群体通过包含在群体中与问题相关的知识来生成。两者的主要区别在于进化计算中所有问 题的的知识都包含在当前群体中,而蚁群算法中代表过去所学的知

10、识保存在信息素的踪迹中。3.2 蚁群算法与模拟退火算法比较从模拟退火算法的搜索策略可以看出蚁群算法和模拟退火算法(SA)从本质上来讲是一 致的。 SA 对某个“固体的”一个微观状态 i 计算其能量 Ei的过程与蚂蚁的一次“周游”一样,都是 对解空间的一次采样;“退火”与“分泌信息素”都是利用积累信息来增强对子空间的搜索;而 “Metropolis 准则”和“随机状态转移规则”类似,都是使算法能够跳出局部最优,在一定范围内 接受恶化解,搜索新的子空间。 因此,SA 已经非常成熟的收敛性研究对分析设置蚂蚁规模参数和信息素分布策略对最 终解质量的影响有很大的借鉴意义。对于 SA 的收敛性分析一般分两

11、种情况,齐次 Markov 链和非齐次 Markov 链。齐次 Markov 链的分析结果告诉我们,在任意温度 t,SA 都达到平衡 分布的情况下,当 t0 时,SA 将收敛于全局最优。也就是说,在任意温度 t,SA 都要遍历整个 解空间。那么,如果我们保留 sA 采样后的当前全局最优解,则即使在任何温度 t,SA 都会收敛 于全局最优。换句话说,对于蚁群算法,如果蚂蚁数量(规模)足够多,能够保证对解空间的遍历,那 么即使不用信息素,也能保证全局收敛。不过这种方法显然就是一种盲目随机搜索,没有任何 实际的应用价值。 对于非其次 Markov 链的 SA,即在某个固定温度 t,采样次数有限,而

12、t 将无限趋近于 0 的 情况下,结论告诉我们当控制参数序列满足一定条件时,SA 才收敛于整体最优解集。其更直 接的表述方式是:控制参数 t 的衰减量与在温度 t 下的采样数之间存在一种均衡:t 的衰减量 越大,则在温度艺下的采样数就必须越多;反之,若 t 的衰减量缓慢,则在每个温度下 SA 只需 进行少量采样。 那么。从蚁群算法的角度可以看到:因为蚂蚁的规模实际上影响的只是信息素更新的频 率,所以当规模设置较大时,每次更新信息素时,可以以较快的速度拉大不同状态上的信息素 差距;当规模较小时,每次只对信息素进行少量更新,以免算法早熟。 由此可见,对蚁群算法的参数设置可以直接利用 SA 中对“冷

13、却进度表”的研究成果。 此外,既然两者在本质上一致,那么 SA 的一些改进和变异可以直接用在蚁群算法上以改 进其性能。 3.3 蚁群算法与神经网络比较由许多并发、局部交互的单元(人工蚂蚁)组成的蚁群,可以看成是一种“连接”系统。 “连 接”系统最具代表性的例子是神经网络(Neural Network,简称 NN)。从结构上看,蚁群算法与 通常的神经网络具有类似的并行机制。蚂蚁访问过的每一个状态 i 对应于神经网络中的神 经元 i,与问题相关的状态 i 的邻域结构与神经元 i 中的突触连接相对应。蚂蚁本身可以看成 是通过神经网络的并发输入信号,以修改突触与神经元之间的连接强度。信号经过随机转换

14、函数的局部反传,使用的突触越多,两个神经元之间的连接越强。蚁群算法中的学习规则可以 解释为一种后天性的规则,即质量较好的解包含连接信号的强度高于质量较差的解。4 基本蚁群算法及其实现4.1 引言蚁群在觅食过程中总能找到蚁巢和食物源之间的最短路径。受蚂蚁的这种行为启发,意 大利学者 M.Dorigo、V.Maniezzo 以及 A.Colorni 首先提出了一种新型的随机搜索模拟进化 算法蚂蚁系统(Ant System,简称 As)。AS 算法是第一个蚁群算法的模型,被称为基本蚁群 算法。AS 算法首先被用来求解 TSP 问题,并取得了巨大成功。实验结果显示 AS 算法具有 很强的发现较好解的能

15、力,但同时也存在一些缺点,如收敛速度较慢、易出现停滞现象等等。 针对 AS 算法的不足之处,许多学者对其进行了深入的研究,提出了一些改进的蚁群算法,如带 精英策略的蚂蚁系统(Ant System With elitist strategy,简称 ASelitist、蚁群系统(Ant Colorni System,简称 ACS)、基于优化排序的蚂蚁系统(Rank-Based Version of Ant System,简称 ASrank)、 最大-最小蚂蚁系统(Max-Min Ant System,简称 MMAS)以及最优-最差蚂蚁系统(Best-Worst Ant System,简称 BWAS

16、)等等。 4.2 蚂蚁系统的模型描述为了说明蚂蚁系统的模型,首先引入 TSP 问题。 一般地来说,旅行商问题(Traveling Salesman Problem,简称 TSP 问题)可以描述如下: 设 C=cl,c2,cn为 n 个城市的集合,L= Lij|ci、cjC 是 c 中元素两两连接的集合, G=(C,L)是一个图,已知各城市之间的距离,TSP 问题的求解目的是从 G 中找出长度最短的 Hamiltonian 圈,即找出对 C=cl,c2,cn中 n 个城市访问且只访问一次的最短的一条封闭曲 线。TSP 问题分为对称型和非对称型。在对称型 TSP 问题中,有 dij=dji, ci，cjC1,2，n，dij是 lij的长度;在非对称型 TSP 问题中,至少存在一对ci，cjC，使dijdji。 为了模拟实际蚂蚁的行为,我们首先引入如下记号: m蚁群中蚂蚁的数量;bi（t）t 时刻位于城市 i 的蚂蚁数,m=； = 1（）dij