#30#

内江师范学院学报

JOURNALOFNEIJIANGNORMALUNIVERSITY第25卷第6期No.6Vol.25

求解最小费用流问题的蚁群算法

夏林林, 叶茂莹, 杨凌云, 牟廉明

*

(内江师范学院数学与信息科学学院, 四川 内江 641100)

摘 要:为了运用蚁群算法解决最小费用流问题,首先结合有向网络描述了最小费用流数学模型,运用从终点向始点反向计算的思想求解在最大可行流约束下的最小费用,然后给出了其具体过程.最后通过仿真实验,调整圈法和标号算法验证表明:该算法是有效可行的.

关键词:蚁群算法;最小费用流;有向网络中图分类号:TP183

文献标志码:A

文章编号:1671-1785(2010)06-0030-03

最小费用流问题是一个经典的组合优化问题,是计算机科学和运筹学的重要内容,有着广泛的实际应用背景,如现实生活中的铁路网、公路网、通信网、运输网等,该问题就是在流值一定的情况下如何将网路中某种量从一个地方流向另一个地方使得费用达到最小[1].因此,研究如何解决最小费用流问题有着重要的实用意义.目前,关于对最小费用流问题的传统算法较多[2 3],而用现代优化算法来求解的研究较少,本文采用启发式蚁群算法求解该问题.

蚁群算法(AntColonyAlgorithm,ACO)是由意大利学者MarcoDorigo,Maniezzo等人[1]于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式仿生进化系统[4 5].蚁群算法最早成功应用于解决经典的优化问题 旅行商问题(TravelingSalesmanProblem,简称TSP),取得了较好的试验结果

[6 8]

素浓度高低有关,路径越短,信息素浓度就越高[4 5].蚁群在寻找最优解的过程中遵循了多样性、信息正反馈机制的特点,多样性保证了蚂蚁在觅食的时候不出现重复反复的路径;而正反馈机制是指在信息素的作用下蚁群倾向于选择信息素浓度高的路径,即最短路径,这样,在相同时间段内选择该路径的蚂蚁会越来越多,从而在路径上又留下了更多的信息素[4].而信息素浓度较低的路径会随着时间的流逝逐渐减弱直至消失.直到最后所有的蚂蚁都会倾向于选择这条最短路径[5].于是,受蚁群算法思想的启发,本文建立了启发式蚁群算法解决最小费用流问题.

2 启发式蚁群算法建立

最小费用流又称最小费用最大流问题,是建立在有向图基础上的组合优化问题:给定一个有n个节点的有向图G=(V,E),其中节点以s为发点,节点t为收点,其余点为中间点,图中任意两节点i与j之间的单位流费用为w(i,j)(i,j=1,2, ,n)且wij=wji,节点i与j构成的弧(i,j)!E,通过其上的容量,可行流[9 10]分别为cij,fij.在每条弧上的流量不超过该弧允许通过的最大流量(容量)的情况下,建立的数学模型如下:

minZ=

可行流f

ij

n

n

.因此,对蚁

群算法思想的研究及应用仍是各领域关注的热点,本文尝试将最小费用流问题建立在有向图的基础上采用蚁群算法来求解.

1 蚁群算法的基本思想

蚁群算法是受自然界中真实蚁群行为启发而模拟产生的一种人工进化算法,是一种用来在图中寻找优化路径的机率型算法.自然界中的蚂蚁在寻找食物过程中,利用在经过的地方留下一种叫信息素(Phenomenon)的化学物质将信息传递给其他蚂蚁,通过这种相互协作并随环境的变化而变化找到一条最短路径.蚂蚁寻找食物所走的路径与路径上信息 收稿日期:2009 12 25

基金项目:内江师范学院大学生科研项目(09NSD-172)

i=1

w

j=1

ij

#fij,

(1)

满足容量限制条件

0 fij cij,

(2)

可行流fij满足发点的输出量=收点的流入量,即平衡条件

作者简介:夏林林(1987 )女,四川广安人,内江师范学院2007级学生.

,.