
蚁群算法在求解
!"#
问题中的改进研究
王宝生!屈宝存
"辽宁石油化工大学 辽宁 抚顺
!!"##!
#
摘要 ! 针对蚁群算法在求解大规模优化问题时存在的
"
个缺点$消耗时间长%蚂蚁在下次搜索时目标导向不强导致搜
索随机性大%寻优路径上的信息素过度增强导致得到假的最优解& 本文提出了基于边缘初始化和自适应全局信息素的
改进蚁群算法& 在相同参数下!其搜索时间大大缩短!并且得到了更好的最优解& 将其应用到旅行商
$%&'(
问题中!和基
本蚁群算法%遗传算法相比较!其具有以下优点$较好的搜索最优解的能力'对新解不会过早 的终 止'探 索新解的能力
进一步增强& 因此!改进的蚁群算法在求解
%&'
等组合优化问题时非常有效&
关键词! 蚁群算法'改进的蚁群算法'边缘初始化'自适应全局信息素 '旅行 商问题
中图分类号!
%'"#)
文献标识码!
*
文章编号
! !+,-!+)"+
!
)#!-
"
)).##!-.#/
!$% &'()*+%'%,- *. /,- 0*1*,2 /13*)&-$' &, 4*1+&,3 !"#
0*12 345.6789:;<= 345.>?9
!
!"#$%"%& '%" ()*+",- ./ 0),*$1)23 4 56)3" 781 9)76%$1$&-:;2+62% !!"##!;<6"%8
"
564-)/0-7%5 >5 @8 ABC7 C78 C 7D88 ED4AF4>G6 5H 49C >5I59J 4I:5 DBC7K B9 65ILB9: I4D:8 .6>4I8 5@CBKBM4CB59 @D5FI8K6N I59: CBK8.
>596?KB9: ;C78 FB: D49E5K9866 5H C78 49C
#
6 684D>7 E?8 C5 C78 A84G9866 5H C78 :54I.5DB89C4CB59;C78 H4I68 5@CBK4I 65I?CB59 E?8 C5
C78 8O>866BL8 89 749>8K89C 5H C78 @78D5K5986 5H C78 5@CBK4I @4C7;C78 BK@D5L8E 49C >5I59J 4I:5 DBC7K A7B>7 B6 F468E 59 C78
8E:8 B9BCB4IBM 4CB59 49E C78 4E4@CBL8 :I5F4 I @78D5K598 B6 @D8689C8E B9 C78 @4@8DP=9E8D C78 64K8 @4D4K8C8D6;BC6 684D>7B9: CBK8
675DC896 :D84 CIJ 49E BC :8C6 4 F8CC8D 5@CB K4I 65I?CB59P*@@IJ BC C5 C78 CD4L8IB9: 64I86K49 @D5FI8K;>5K@4D8 BC ABC7 C78 5C78D CA5
K8C75E6 A7B>7 4D8 F46B> 49C >5I59J 4I:5DBC7K 49E 2*;BC 746 C78 H5II5AB9: 4EL49C4:86NBC 746 4 F8CC8D >4@4FBIBCJ B9 684D>7B9:
5@CBK4I 65I?CB59QBC >49RC F8 @D8K4C?D8IJ C8DKB94C8E C5 C78 98A 65I?CB59QC78 4FBIBCJ 5H 8O@I5DB9: 98A 65 I?CB596 B6 89749>8EP&5;C78
BK@D5L8 E 49C >5I59J 4I:5DBC7K B6 L8DJ 8HH8>C BL8 B9 65ILB9: C78 > 5KFB94C5DB4I 5@CBKBM4CB59 @ D5FI8K6 6 ?>7 46 %&'P
8%2 9*):4749C >5I59J 4I:5DBC7KQBK @D5L8E 49C >5I59J 4I:5DBC7KQC78 8E:8 B9BCB4IBM4CB59QC78 4E4@CBL8 :I5F4I @78D5K598Q%D4L8.
IB9: &4I86K49 'D5FI8K
旅 行 商 问 题
$%D4L8IB9: &4I86K49 'D5FI8K; %&'S
是 一 个 易
于描述 却难以 处理的
1'.T*UV
问题$ 近年来%它引起了许
多学 者 的 广泛 关 注 $ 旅 行 商 问 题 不 仅 具 有 很 重 要 的理 论 价
值%而且还具有广泛 的实际 应 用价 值 %如机器人路径规划&电
路板设计&城 市 管 道 铺 设 优 化 &交 通 运 输 以及 物 流 配送 等 领
域都可视为
%&'
问题的 具体应 用$ 对于 旅行商问 题%目 前常
用的方法有模拟退火算法&遗传算法&神经网络法等$
蚁群 优化算法是模拟自 然界中真实蚁群的 觅 食 行 为 而
形 成 的 一 种 模 拟 进 化 算 法 $ 它 是 一 种 新 兴 的 仿 生 学 优 化 算
法%属于元 启发算 法的一种 $ 它具有 采用分布式并行 计算机
制&易于与 其他方 法结合&具有较 强的鲁棒 性等优 点%但其搜
索时间长&易陷于局部最优解是其最突出的缺点 $ 因 此%既 要
使得 蚁群算法的搜素空间尽 可能的大 %以寻 找那些可能存在
最优解的解 空 间 %同 时 %又 要 充 分 利 用 蚂 蚁 体 内 当 前 所 有 的
有效信 息%使得蚁群算法搜 索的侧重 点放在 那些可 能具有较
高适应值的个 体所在 的 区间 内 %以较大的概率收敛到 全局最
优解 $ 因此%在'探索(和'利用(之间建立一个平 衡 点 是 蚁群
算法研究的关键问题之一$
为了克服蚁群算法的这些缺陷%使它的性能更好
;
研究者们
探索了信息素残留因子
$!.!S
&信息启发式因子&期望启发式因
子&信息素强度&蚂蚁数目等蚁群算法的影响因素%并进行了改
进
W!."X
$ 高尚提出了混沌蚁群算法%采用混沌初始化改善个体质量
和利用混沌扰动避免搜素过程陷入局部极值%实验表明该算法
提高了计算效率
W-X
$ 汤可宗等从参数的动态调整&信息量的更新
规则&局部搜索策略进行相应的改进%引入信息素平滑机制%实
验表明该算法具有较好的收敛性和稳定性%能够克服算法中早
熟和停滞现象的过早出现
W/X
$王峰峰等提出了在蚁群算法中植入
遗传算法%利用遗传算法生成信息素的分布%克服了蚁群算法
中搜索时间长的缺陷%在蚁群算法寻优中%采用交叉和变异的
策略改善了
%&'
解的质量%实验表明该算法是有效的
W+X
$ 蔡荣英
等提出了迭代改进蚁群算法%在构造解的过程中%蚂蚁始终记
忆一个完整的解%并只接受能够改进解的候选城市%使用解的
部分重构策略来保持种群的多样性%避免早熟收敛%实验表明
电子设计工程
YI8>CD59B> V86B:9 Y9:B988D B9:
第
))
卷
Z5IP))
第
))
期
15P))
)#!-
年
!!
月
15LP )#!-
收稿日期!
)#!-.#!.!#
稿件编号!
)#!-#!#[)
作者简介! 王宝生"
!\[\
()!男!山东 临沂人!硕士研究生& 研究方向$系统故障 诊断及优化&
!!-!