蚁群算法的改进及其应用

收稿日期:$%%#;##;#!

基金项目:上海市高等学校科学技术发展基金资助项目<==&0%

>%@作者简介:张宗永<#=A ";@B

男B 湖南武冈人B 硕士B 研究方向为船舶与海洋结构物设计制造和航道规划8

文章编号:#%%";$?"A <$%%$@##;#>"?;%?

蚁群算法的改进及其应用

张宗永#B 孙

静$B 谭家华#

<#8上海交通大学船舶与海洋工程学院B 上海$%%%!%C$8上海交通大学贝尔联合实验室@摘

要:为对上海市的内河航道提供科学合理的规划B 解决集装箱集散问题B 同时B 也为推广蚁群

算法的应用B 在介绍蚁群算法解决旅行商<2.D @问题的模型上B 对蚁群算法做了相应的改进8配合随机分布技术B 以上海市整个内河航道和集装箱运输为研究对象B 对内河航道进行规划B 得出上海市内河集装箱集散系统合理的分配方案B 并提出为满足该合理系统所须进行的相应的河道改造8关键词:蚁群算法C 航运规划C 最优化中图分类号:("=A 8!

文献标识码:+

E F F G H I J K H L ML N K O PQ R F S L T P UE M K V L G L M WE G X L S H K O R

Y Z[\\]Y ^_‘;a ^_‘#

B b c \\d e _‘$

B f [\\d e g ;h i g

#

<#8.j k 6676l *m 9m 7+n j k o p q j p r n q s ’j q m t4t u 8B .k m t u k m o &o m 6p 6t u(t o 98B .k m t u k m o $%%%!%B v k o t m

C $8w q 77;&6o t p ,m x 8B .k m t u k m o &o m 6p 6t u(t o 9

8@E y z K S J I K :+t p j 676t {m 7u 6n o p k |o }m t q ~m 7u 6n o p k |m t !k m }|m t {"n 6|o }o t u j k m n m j p q n }o tn q }679o t u p k q 2.D

m t !6p k q n "n 6x 7q |}82k qu m p k q n o t um t !!o }x m t !o t u6l j 6t p m o t q n }o }m #q {l m j p 6n p 6.k m t u k m o $q q "%m p q n

D 6n p &}j 6t }p n r j p o t u 81t6n !q n p 6"n 69o !q m n q m }6t m x 7q 7m {6r p l 6n .k m t u k m o &}o t 7m t !n o 9q n t q p m t !"6"r 7m n o ’q

p k q m t p j 676t {m 7u 6n o p k |B p k o }"m "q n m t m 7{’q !.k m t u k m o &}o t 7m t !n o 9q n t q p m t !j 6t p m o t q n }k o ""o t u 8+to |;

"n 69q !m t p j 676t {m 7u 6n o p k |~m }r }q !~o p kp k qn m t !6|!o }p n o x r p o 6tp q j k t 676u {8+}mn q }r 7p 6l p k q "7m t ;t o t u B p k q }{}p q |6l .k m t u k m o o t 7m t !n o 9q n t q p o }}r o p m x 7q l 6n p k q j 6t p m o t q n }k o ""o t u 8.6|q n q m }6t m x 7q m !9o j q

6l n q j 6t }p n r j p o t up k q o t 7m t !n o 9q n }~q n q 6l l q n q !

8(P W )L S U z :m t p j 676t {m 7u 6n o p k |C }k o ""o t u "7m t t o t u C 6"p o |o ’m p o 6t

从$%世纪>%年代中期开始B 仿生学日益得到人们的重视8受仿生学中生物进化机理的启发B 人们提出了一系列新的算法B

解决了许多比较复杂的优化问题8遗传算法*进化规划*进化策略*神经网络等算法从那时起得到长足的发展B 并逐渐成为比较成熟的算法8而蚁群算法<+t p v 676t {.{}p q |B +.

@是最近几年才由$6n o u 6等+#,首先提出来的一种新型的模拟优化算法8

蚁群算法是模拟蚁群寻找最短路径时的交互过程的一种算法8在解决离散优化问题时B 该算法显示出了很大的优越性B 能够获得较好的实验结果8本文把蚁群算法经过一定的改造B 应用于上海市内河航运网的规划优化中B 通过解决实际问题B 来推进这一算法的实际应用8

-蚁群算法概述

蚂蚁觅食时B 对于从蚁窝到食物源的诸多途径B

开始时不同的蚂蚁会选择不同的路径B 但最后B 几乎所有的蚂蚁都会找到同一条最短的路径8这是因为蚂蚁寻找最短路径的过程是一个交互式的过程B 它们会在经过的路上留下一定量的外激素B .

..................................................................而且能感

万方数据

知这种激素的存在及强度并朝该物质强度高的方向运动!这些激素既会随通过的蚂蚁数量增加而增加"也会随时间的流逝而按一定的函数关系消逝!因为最短路径通过的蚂蚁数量较多"所以其上激素的积累速度将比其他路径快!蚁群通过外激素这种物质来不断地交流反馈信息"最终找到一条从蚁窝到食物源的最佳路径!

从自然蚂蚁系统可引出人工蚂蚁#$$%&人工蚁群系统#$’(%以及蚁群算法#$(%"人工蚂蚁类似于真实蚂蚁"在运动中会释放出一定的信息"能感知

该信息的存在及强度并以此为行动指南)*+,-!

.!.原理及解法

在/个相互连通的城市中"要找出一条连接所有城市的最短通路称为旅行商#0(1%问题!如果考虑到不同路径之间的不同费用"

则问题转化为求花费最小的通路#234567回路%!假设:;"<

#*=;=/"*=<=/";><%表示从第;个城市到第<个城市单位路程所需费用"即边;<上的权!当:;"<>:<";

时"称为非对称的0(1问题!非对称0(1问题的实质是在具有/个结点的完全带权图上找一条花费的

234567回路)?-!.!.!.初始化及说明把/座城市抽象为/个结

点"每?个结点间有边相连@选定有A 只蚂蚁组成的蚁群@每只蚂蚁随机选取一结点作为起始点@每条边初始信息量设为B ;"#;"%为;结点到<结点的距离@在H 时刻"位于;城市的蚂蚁数为I ;#H %"残留在边;<上的信息量为J H

#;"<%!于是有J K #;"<%C D E F ;"<

#*%L /

;C *

I ;

#

H %C A #?%

.!.!M 转移及更新过程在蚁群系统中"

人工蚂蚁N 在O

结点根据以下公式来选择下一个结点P Q R N #;"S %C J

#;"S %)B #;"S %-T

L S U E V N

J #;"S %)B #;"S %-T

S U E V N K

W X Y 其他

#,%P C 3Z [43\\R N

#;"S %#]%式中Q J #;"S %为边;S 上的信息总量@T 为权重因子"表示残留信息和距离的相对重要性@V N 为蚂蚁N 已经访问过的结点的集合@S U E V N 为所有没有经过的结点@R N

#;"S %为蚂蚁N 从结点;以结点S 的概率!人工蚂蚁每次转移到新的结点时"所经过边的信息量就得到修正"称为局部修正!蚂蚁N 经过的边上会留下信息量

^J N #;"<%C _E F ;"<

#‘%式中"_为事先选定的常数!在一次循环中"边;<所增加的信息总量

^J #;"<%C

L A

N C *

^J N

#

;"<%#a %

在这个过程中"^J N

#;"<%和该路径的长度成反比!所有蚂蚁都完成了旅程后"每个环路上的信息量都会得到修正"称为全局修正!在A 只蚂蚁各自

的巡游回路中"找出最短的一条"根据

J #;"<%C #*b c %J #;"<%d c ^J #;"<%#e %进行全局更新!式中Q c 为事先拟定的K

+*的常数@^J #;"<%C _E f "f 为该蚂蚁巡游回路总长度)]-!

通过上面的过程"可以找到一条比较合理的花费234567回路"也可以在已有信息分布的完全带权图上进一步寻找"以期找到更优的回路!寻找完毕后"比较这两条最优回路"如果两者差别在预期的范围内"则可终止程序"否则"进一步寻找最佳回路"直到与前一次的差别在规定的范围内"或者已到了预定的最大循环数!一般而言"因为有了预先的信息分布"后面的循环中"蚂蚁可以更迅速地找到最佳回路"计算所需时间将比前面的循环少!

.!M 适用范围与局限性

蚁群算法适应面较广"稍加改造便可以解决很多实际问题@且因具有本质并行性"容易并行实现!

蚁群算法本身是一种模拟启发式算法"可与其他启发算法结合"改善算法的性能"搜索到较好的结果!由于充分利用了正反馈原理"加快了运算速度"

尤其是求解小型的0(1问题"效果十分明显!但随着计算规模的增大"算法效率下降得很快"而且易出现停滞现象"

陷入局部最优的陷阱!针对这些问题"一些学者提出相应的解决方案"如$g &hh$(及

新蚂蚁算法#i $$%

等)‘"a -!M 蚁群算法的应用

以上海市航运网随机优化问题为例"运算网络包含,,个结点

每结点有相应的运输任务"每河段有相应的运输能力!运输任务与运输能力都是对未来的一个预期"有一定的随机性!分析对象为?K K ‘年的运输任务及该航运网!在完成运输任务的同时"要求得出最优航道的选择情况和航道满载的概率"以期求得各河段相应的改造概率"保证运输网的畅通!网络模型由上海市现有内河航运系统抽

象而成"如图*所示)e -!M !.算法的改进

上海市内河航运网中所考虑的因素与0(1问

‘

a ‘*第**期

张宗永"等Q 蚁群算法的改进及其应用

万方数据

万方数据!"#$%&

对整个网络进行统计’得出每条河的利用率结束()(实例应用

计算结果如表*所示’表中+为计算次数)

表,河段满载率及满载概率表-只截取有代表性的河段.

/01),/234561017879:6;;<88860=6;>6?39:47@0857A35>

河段代号

满载率B C

D E*D EF D EG D EH D EI D EJ D EK D EL D EM D E*N

满载概率B C *G K)N L G K)H*G K)N J G L)J I G K)H J G I)M J G L)*K G H)I I G I)**G J)F F N F*)L H*)I I N)M I*)F K*)I G*)H G*)I**)I F*)J G N)M M N *J*M)H H*M)F M*L)*I*M)*K*M)I K*L)H K*L)L M*L)*M*L)L K*M)F H N *K G*)F*G*)K L G*)I L G*)N M G*)H J G*)K F G*)J H G N)K L G N)H I G*)*F N *L G M)J H G K)M M G K)M L G L)**G L)H K G L)G H G L)J K G M)*K G M)F*G L)J M N *M*N N*N N*N N*N N*N N*N N*N N*N N*N N*N N*N N

F N

G I)L F G H)*F G I)*J G J)N K G L)N K G H)M L G H)M M G K)N M G I)L F G H)I J N

F*N)N N N)N N N)N N N)N N N)N N N)N N N)N N N)N N N)N N N)N N N

F F M L)*N*N N M K)J L M M)N*M M)L N*N N M K)M L M L)I H M L)J K*N N

G N

F J

G M)L*G L)M L G L)M M G M)

H K G M)*L G M)K H G L)L H G M)**G M)*K G M)**N

F K

G F)N G G F)N

H G F)N*G N)G L G F)L

I G*)N L G N)L F G N)L M G*)

J I G F)G I N

F L*F)L M*H)N H*G)I L*G)J H*G)L M*F)M L*H)N**H)*L*F)L M*H)*L N

G L K N)H K K N)I H K N)L L K N)K N K N)J K K*)N N K N)L I K N)G*K N)**K N)N G N

由表*可见’河段*与F虽然运输任务差不多’但由于能力相差悬殊’所以利用率相差较大)相对而言’河段*J O*L运输任务较重’承担着许多节点的运输任务’而且运输能力有限’虽然F N N I年在P P P 港分配的任务不多’但这些河段利用率已经比较高)随着P P P深水港的建设’这些河段将很快满载而需要改造)河段*M比较特殊’其运输能力较小’东面是外高桥’考虑到以后河段的部分运输能力将为外高桥所占用’而且其周边地域广阔’对运输量要求较大’所以自然最先达到饱和状态)目前’上海市对这一河段正在进行必要的改造)由于河段*M的满载’剩余的运输量自然转移到与其相邻的比较合理的河段F N)对于河段F*’因为不管从哪点到港口’都不是最佳的路径’而且’周围河段的运输能力都没有完全利用’所以’其运输量暂时为N)等到相邻河段*J Q *L Q F N等的运输量增加而不能满足时’方才选择河段F*)河段F J Q F K在运输网中的位置关键’鉴于目前的改造情况’运算时预先设定其运输能力为*N N R)和河段*J O*L等一样’在以后的日子里’河段F J Q F K的运输量也将大幅度上升)河段G L是P P P深水港与各点的唯一通道’随着深水港的建成’应该将其建设成一条运输量很大的河段方能满足需要)参考文献S

T*U V%&D W%X’P Y&%Z V)[\\!Y"R]%^%"_%‘R D a D b Y R D%"

a!R Y c\\!d&D e R D]T f U)g3h8=30>7ij497?7k0976i T P U)

l%"#%"S X]Z&Y m c n D^^’*M M M)*oF K)

T F U V%&D W%X’Z Y a p Y&#!^^Yl X)f"R]%^%"D!e$%&R\\!

R&Y q!^^D"We Y^!e a Y"‘&%p^!a T r U)s76t:>93?>’*M M K’

H G S K G oL*)

T G U r Y_Y&Y a Y"u v’v d^w Y&"D xV’v Y&Y^!y’z{|})f"R ]%^%"_$&Y a!m%&w$%&%‘R D a Y^#!e D W"Y"#e]\\!#d^D"W

%$p Y R]\\‘^Y"R e T r U)~6?4<935>0i=~23?7@08!i"7c

i3357i"’F N N N’K-F H.S*M N*o*M*F)

T HU V%&D W%X’x%"Y p!Y d#’[\\!&Y d^Y bZ)f"RY^W%c &D R\\a eY"#e R D W a!&W_T r U)$<9<53%3i350976i~6?&

4<935t:>93?>’F N N N’J-*J.S L I*oL K*)

T I U张徐亮’张晋斌)基于协同学习的蚁群电缆敷设系统T r U)计算机工程与应用’F N N N’I S*L*o*L F)

’n f(Z)d c^D Y"W’’n f(Z r D"c p D")f"R]%^%"_]Y c

p^!^Y_D"We_e R!a p Y e!#%"]%%‘!&Y R D q!^!Y&"D"W T r U)

~6?4<935!i"7i3357i"0i=*4487@0976i>’F N N N’I S

*L*o*L F

T J U张纪会’高齐圣’徐心和)自适应蚁群算法T r U)控制理论与应用’F N N N’F-*K.S*oG)

’n f(Z r D c\\d D’Z f+,D c e\\!"W’)-)D"c\\!)f e!^$

Y#Y‘R D q!Y"R]%^%"_Y^W%&D R\\a T r U)~6i9568/2365:

0i=*4487@0976i>’F N N N’F-*K.S*oG)

T K U上海市统计局)上海统计年鉴T X U)北京S中国统计出版社’*M M M)F N oF F’F H N oF H G)

K

J

I

*

第**期张宗永’等S蚁群算法的改进及其应用万方数据