-1-
中国科技论文在线
最大最小蚁群算法在最大流问题中的应用
宋华珠，夏天扬，肖建立
武汉理工大学计算机科学与技术学院，武汉（430070）
摘 要：最大流问题是一个经典的组合优化问题。传统的最大流问题大多都是基于“增广链
定理”。而根据蚁群算法的特点，将最大流问题进行相应地转化，然后利用蚁群算法进行求
解。本文利用最大-最小蚁群算法及其改进解决算法最大流问题的方法进行对比，仿真结果
表明，该算法能够解决最大流问题，给最大流问题的研究提供了新的思路。
关键词：最大流问题，增光链，蚁群算法，最大-最小蚁群算法
中图分类号：
1. 引言
最大流问题是网络流理论的重要组成部分，是一个经典的组合优化问题，在许多工程以
及管理科学和应用数学等科学领域有着广泛的应用。目前,解决最大流问题的算法大多是基
于“增广链理论”，如 Ford-Fulkerson 等算法，这些经典算法及相关技术对网络最大流问题的
研究起到了非常重要的推动作用。
在二十世纪九十年代初期，意大利学者 等人从蚂蚁觅食的自然现象中受到启
发，经过大量的观察和实验发现,蚂蚁在觅食过程中留下了一种外激素，指导蚁群在觅食的
过程中选择最短的路径。由此， 等人首先提出了一种新的启发式优化算法--蚁群系
统，这种算法在求解复杂优化问题方面具有很大的优越性，为求解复杂的组合优化问题提供
了一种新思路。
本文运用最大-最小蚁群算法（MMAS）及其改进后的 MMAS 算法来解决最大流问题，
为今后最大流问题的研究提供新的思路和途径。
2 最大流问题描述
最大流问题的模型
最大流问题[1]是指在一定的条件下，要求流过网络的物流、能量流、信息流等流量为最
大的问题。
在实际的网络中，网络的结点和边都是有容量限制的、很多情况下需要知道在一个有容
量限制的网络中，当传输流量时，如何充分利用整个网络拓扑从源点 s 到汇点 t 传输流量，
而不是只使用某个单一链路，实现从 s 到 t 的最大传输流量。
可以建立相应的最大流问题的一般数学模型如下：
一个有向流网络 N=(G,s,t,C)是一个四元组，其中：G =(V,E)是一个具有 n个顶点、m条
弧的有向图，V是 n个顶点的非空有限集合，E是m条弧的非空有限集合，s和 t是 G的两
个特殊顶点，分别称为源点和汇点，s∈V，t∈V，C是一个 E→R+的函数，R+是正实数集合，
即每条弧 e (e∈E)都赋有一个非负的容量 C(e)。
一个可行流{ ( )ijf e }使其流量 ( )Q f 达到最大,必须以下两个条件满足：
1. 容量规则
其弧流量f(e)不超过其弧容量C(e),即
0≤f(e)≤C(e) （1）
-2-
中国科技论文在线
2. 平衡条件：
网络中，对于除起点和终点之外的任何顶点，流入量的总和须等于流出量的总和。
( , ) ( , )
( )
0
( )i j k i
ij ki
v v A v v A
Q f i s
f f i s
Q f i t∈ ∈
=⎧⎪− = ≠⎨⎪− =⎩
∑ ∑ （2）
3. 基于最大-最小蚁群算法的最大流问题
蚂蚁系统
蚁群在觅食过程中总能找到蚁巢和食物源之间的最短路径。受蚂蚁的这种行为启发，意
大利学者等首先提出了一种新型的随机搜索模拟进化算法--蚂蚁系统( Ant-System,
简称 AS）。AS 算法[2]首先被用来求解 TSP 问题[3]，并取得了巨大成功。
那么首先有必要以 TSP 问题为例简单介绍蚂蚁系统。
TSP 问 题 可 以 如 下 描 述 ： 设 1 2{ , ,..., }nC c c c= 为 n 个 城 市 的 集 合 ，
{ | , }ij i jL l c c C= ∈ 是C中元素两两连接的集合， ( , )G C L= 是一个图，已知各城市之
间的距离，TSP 问题的求解目的是从G 中找出长度最短的 Hamiltonian 圈，即找出对
1 2{ , ,..., }nC c c c= 中 n个城市访问且只访问一次的最短的一条封闭曲线。
为了模拟实际蚂蚁的行为，我们首先引入如下记号：
m ---蚁群的规模，即蚁群中蚂蚁的数量
( )ib t -- t时刻位于城市 i的蚂蚁数：即
1
( )
n
i
i
m b t
=
= ∑
ijd --城市 i与城市 j之间的距离
ijη --反映由城市 i 转移到城市 j的启发程度，与城市间的距离成反比
( )ij tτ -- t时刻边 ( , )i j 上的信息素量
ijτΔ --信息素的增量
( )kijP t -- t时刻蚂蚁 k 从城市 i 转移到城市 j的概率
AS 算法可以如下表述：在算法的初始时刻，将m只蚂蚁随机的放到n座城市，同时，
将每只蚂蚁的禁忌表的第一个元素设置为当前它所在的城市。初始时刻，各条路径上的信息
素量相等，设 (0)ij Cτ = 。然后每只蚂蚁按照各条路径上的信息素量和启发式信息(两城市
间的距离)按照概率 ( )kijP t 独立的选择下一座城市，转移概率公式如下：
( ) ( )
( ) ( )( ) ,
0,
k
ij ij
k is isij ks allowed
t t
t tP t j allowed
otherwise
α β
α β
τ η
τ η
∈
⎧⎪⎪ ∈⎨⎪⎪⎩
∑ （3）
当所有蚂蚁完成一次周游以后，各路径上的信息素根据下面的公式更新:
-3-
中国科技论文在线
( ) ( )ij ij ijt n tτ ρτ τ+ = + Δ （4）
1
m
k
ij ij
k
τ τ
=
Δ = Δ∑ （5）
如此循环往复，蚁群会在信息素的指引下，不断的接近最优解。
最大-最小蚁群算法
算法描述
从上面的过程看，AS 是基于全局优化的组合优化算法，有较强的鲁棒性，易于与别的
算法结合解决问题，并且蚁群算法是基于群体的优化算法，其本性就具有分布性。但是蚁群
算法也有其天然的缺陷，最主要的有以下两点:
1） 与其他方法相比，该算法一般需要较长的搜索时间，AS 算法的复杂度可以反映这
一点。
2） 该方法容易出现停滞现象，即搜索进行到一定程度后，所有个体所发现的解完全一
致，不能对解空间进一步进行搜索，不利于发现更好的解。
而最大-最小蚁群算法（Max-Min Ant System,简称 MMAS）很好的弥补了 AS 的缺陷，
使得到最终解更优，下面就来介绍 MMAS 算法
MMAS 算法[4]与 AS 算法有三个不同方面：
1） 信息素更新方式不同。每次循环后只对本次循环最优解或到目前为止找出最优解的
一只蚂蚁进行信息素的更新，而在 AS 算法中，对所有蚂蚁走过路径都进行信息素的更新。
MMAS 的信息素更新更新方式为
( ) ( ) bestij ij ijt n tτ ρτ τ+ = + Δ （6）
1/ ( )best bestij f SτΔ = （7）
其中 ( )bestf s 表示迭代最优解。
2） 为避免搜索的停滞，在每个解的元素上的信息素轨迹量的值域范围被限制在
min max[ , ]τ τ 区间内。
3） 为使蚂蚁在算法的初始阶段能够更多地搜索新的解决方案 ,将信息素轨迹初始化
为 maxτ 。
MMAS 算法在最大流问题上的应用
在求解最大流问题时，可以模仿蚂蚁的行为，将m只蚂蚁定位于源点 s，每只蚂蚁根据
转移概率选择公式选择自己的路径，转移概率公式如下：
(0, )
[ ( )]
( )
[ ( )]
ij
ijlk
ijl
ijs
s C
t
P t
t
α
α
τ
τ
∈
= ∑ （8）
其中 ( )kijlP t 表示 t时刻蚂蚁 k 选择流量为 l的路径 ( , )i jv v 的概率， ( )ijl tτ 表示 t时
-4-
中国科技论文在线
刻蚂蚁 k在流量为 l的路径 ( , )i jv v 上所残留的信息素的量。
在完成一次循环之前，不允许蚂蚁选择己经访问过的城市，该过程由蚂蚁的禁忌表来控
制。设 ktabu 为蚂蚁 k 的禁忌表，则蚂蚁在经过城市 j以后，就将城市 j加入到自己的禁
忌表 ktabu 中，表示下次不能再选择城市 J。完成一次迭代后只对本次迭代最优解或到目
前为止找出最优解的一只蚂蚁进行信息素的更新，信息素更新方式如公式（6）、（7）。
下面利用蚁群算法中性能较好的 MMAS 算法来解决最大流问题。算法流程如下:
开始
参数初始化：设置最大迭代次数为NC，将m只蚂蚁置于源点s，令每条
边的初始信息量为τmax,且初始的Δτ（0）=0
对每只蚂蚁按概率转移公式（10）确定所选择的路径，
将已经遍历的路径置于禁忌表中
更新禁忌表，保证已经遍历的路径不会重复
0≦fij≦Cij
将当前最好解的各边全局信息素更新公式更新，nc=nc+1
nc<NC?
结束
图1：算法流程图
MMAS 是目前为止性能比较好的蚁群算法，但其本身也存在一些不足的地方：
1） 由于各路径上的初始信息量都相同为 maxτ ，并且每次循环只对本次循环最优解或到目
前为止找出最优解的一只蚂蚁进行信息素更新，使得长时间多数路径上信息素量相同，
从而影响最优解的搜索速度。
2） 蚂蚁创建第一条路径的引导信息主要是城市间的距离信息，这样蚂蚁在所经过的路径上
留下的信息就不一定能反映出最优路径的方向，不能保证蚂蚁创建的第一条路径能引导
蚁群走向全局最优解。因此,在第一次循环，蚂蚁创建的本次循环最优解可能离全局最
优解较远，但这条路径的信息素会因正反馈而得到增强，随着算法的重复执行，信息素
会积累在这条不是最优的路径上，从而影响全局最优解的搜索速度。
下面就介绍一种 MMAS 的改进方法，将随机扰动引入到 MMAS 的信息素更新过程中
-5-
中国科技论文在线
来，有效的避免了算法陷入局部最优。
基于随机扰动的 MMAS 在最大流问题上的应用
由于各路径上的初始信息量都相同为 maxτ ，并且每次循环只对本次迭代的最优解或到
目前为止找出最优解的一只蚂蚁进行信息素更新，这样有可能会造成寻优的过程过分围绕首
次迭代得到的最优解，容易陷入局部最优。因此，在信息素更新的过程中，可以增加随机扰
动，每次迭代完成之后，不仅仅只对本次迭代的最优解或到目前为止找到的最优解蚂蚁进行
更新，也对随机产生的次优解蚂蚁进行更新，这样就有效的防止 MMAS 算法陷入局部最优。
在每次迭代之后给予最优解以额外的信息素，信息素量按照下面公式进行更新：
*( ) ( ) bestij ij ij ijt n tτ ρτ τ τ+ = + Δ +Δ （9）
* ( )
0
best
ij
Q
f S
θτ
⎧⎪Δ = ⎨⎪⎩
若边（i,j）是最优解的一部分
其他 （10）
其中， *ijτΔ 表示次优解蚂蚁引起的路径上的信息素量的增加， ( )bestf S 为所找出的
最优解的路径流量，Q 为一个常量。
两种算法仿真结果对比
为了验证本文提出的两种蚁群算法的有效性，仿真选取某公路的布局图，求其最多能通
过多少辆车。利用 MATLAB 软件进行模拟仿真。
A
B
C
D
E
F
G
I
H
(70,70)
(70,70)
(15,0) (15,0)
(35,0) (40,0)
(70,70)
(10,0) (20,20)
(50,50)
(50,20)
(30,30)
(65,50)
图 2：车辆调度仿真实验
参数选择如下表：
α ρ C Q m NC
1 1 20 30 500
表 1：蚁群算法各参数选择表
各个参数选择[5]的不同，对蚁群算法效率的影响是很大的，在这里就不在赘述了。
仿真结果：MMAS 算法和改进的 MMAS 算法得到的最大总流量相同， ( )bestV f =120，
即可最多可通过 120 辆车，70 辆车沿路线 A->B->D->I 行进，50 辆车从 A->F，在站点 F 分
流：20 辆车沿 F->G->H->I 行进，另外 30 辆车沿 F->H->I 行进。
两种蚁群算法求解该问题是，基于随机扰动的 MMAS 算法具有较好的性能，收敛情况
如下：
-6-
中国科技论文在线
图 3：两种算法结果比较
4. 结论
本文将MMAS算法及其改进算法应用到最大流问题中, 利用蚁群算法的特点求解最大
流问题。仿真实验表明蚁群算法能够有效地解决最大流问题。对于容量较大的情况,蚁群算
法更有自身的优势，可以采取并行蚁群算法,加快算法的收敛速度，但算法的精确度会有所
下降，如何平衡算法收敛速度和精确度的问题将是今后研究蚁群算法的主要内容了。
参考文献
[1] Wu Haiyan. A new maximum-flow method of urban road network
[2] 段海滨. 蚁群算法原理及其应用[M]. 科学出版社, 2006. 1
[3] MAX-MIN ant system[J]. Future Gener Comput Syst, 2000,16(8), P889-914(Ch)
[4] 陈峻, 沈洁, 秦玲. 蚁群算法进行连续参数优化的新途径[J]. 系统工程理论与实践. 2003(3):48-53.
[5] 王玥, 陶洪久. 蚁群优化在 TSP 中的应用. 武汉理工大学学报信息与管理工程版, 2006, 28(11)
The application of Max-Min ant colony algorithm on the
maximum flow problem
Song Huazhu, Xia Tianyang, Xiao Jianli
(School of Computer and Technology, Wuhan University of Technology, WuHan, HuBei,
, 430070)
Abstract
The maximum flow problem is one of the classical combinatorial optimization problems. Most of the
traditional maximum flow problems are based on “Augmented chain theorem”. According to the
characteristics of ant colony algorithm, we transform the maximum flow problem correspondingly, and
then we utilize the ant colony algorithm to resolve the problem. In this paper we use the ant colony
algorithm to solve the maximum flow problem, and the simulation results show that the ant colony
algorithm can be used to resolve the maximum flow problem, and this also provided a new approach to
the study on the maximum flow problem.
Keywords: The maximum flow problem, Augmented chain,Ant colony algorithm, Max-Min ant
colony algorithm
