当前位置:首页 >> 能源/化工 >>

蚁群算法及其在路由优化中的应用综述


计 算 机 工程 与设 计 C o m p u t e r   E n g i n e e r i n g   a n d   D e s i g n  
?人 工 智 能 ?  

2 0 0 9 , 3 0( 1   9 )

4 4 8 7  

蚁群算法及其在路 由优化中的应用综述 
贾云 富

  ,   秦  勇  ,   段  富  ,   梁本 来 ,   黄  翰  ,   张 美玉 
( 1 .太原 理 工 大学 计算机 与软件 学院 , 山西 太原 0 3 0 0 2 4 ;2 .茂名 学院 信 息 与 网络 中心 ,   广东 茂名 5 2 5 0 0 0 ;3 .华 南理 工 大 学 计 算机 科 学与 工程 学院 ,广 东 广 州 5 1 0 6 4 1 ;  
4 .解放 军信 息 工程 大 学 电子技 术 学 院广 州训 练 大 队 ,广 东 广 州 5 1 0 5 1 0 )  
摘  要: 蚁 群 算法 ( AC O ) 是 一类新 型 的机 器学 习技 术 , 根据 蚁群 算法 的正反 馈原 理和 启发 式原理 的特点 , 针 对 目前 国内国 际  的研 究情 况 ,对 蚁群 算法在 最优 路径 的搜 寻 上从 收敛 性 ,收敛 算 法的 改进 以及 收敛速 度 等方 面 的研 究分别 进行 了分析 综 

述, 并对 蚁群 算 法的一 些应 用 , 如: L E O卫星 网络 和无线传 感 等方 面进行 了阐述。对 蚁群 算法在路 由优 化和 负载 平衡上 的研 
究 进 行 了对 比 分 析 , 发 现 了它 们 存 在 的 不 足 , 指 出 了在 该 领 域 需 要 进 一 步 研 究 的 热 点 问题 。  

关键词 : 蚁群 算法 ;收敛 性; 最优链 路 ;路 由优化 ; 启发 式算 法  中图 法分类号 : T P 3 9 3 . 0 1   文献 标识 码 : A   文章编 号 : 1 0 0 0 . 7 0 2 4( 2 0 0 9 ) 1 9 - 4 4 8 7 . 0 5  

Ov e r v i e w  o f   ACO  a n d   i t ’ S   a p p l i c a t i o n   o n   r o u t i n g   o p t i mi z a t i o n  
J I A  Y u n — f u  ,   QI N  Y o n g   , DU AN  F u   , L I A NG   Be n - l a i  , HUANG  Ha n   , Z HANG   Me i - y u 4  
( 1 .Co l l e g e   o f C o mp u t e r   S c i e n c e ,T a i y u a n   Un i v e r s i t y   o f T e c h n o l o g y ,T a i y u a n   0 3 0 0 2 4 ,C h i n a ;2 .C e n t e r   o f I n f o r ma t i o n  
a n d   Ne t wo r k s ,M a o mi n g   Un i v e r s i y,M a t o mi n g   5 2 5 0 0 0 ,Ch i n a ;3 . Co l l e g e   o f Co mp u t e r   S c i e n c e ,S o u t h   C h i n a   Un i v e r s i y  t
o f   T e c h n o l o g y , Gu a n g z ho u   5   1   0 6 4   1 , Ch i n a ; 4.T r a i ni n g   Ba t t a l i o n   o f   Gu a ng z h o u ,I ns t i t ut e   o f   El e c t r o n i c   T e c h n o l o g y ,  

P L A   I n f o r ma t i o n   E n g i n e e r i n g   U n i v e r s i y t ,G u a n g z h o u   5   1 - 0 5   1   0 ,C h i n a )  
Ab s t r a c t : ACO  i s   a   n e w  t e c h n o l o g y   o f ma c h i n e   l e a r n i n g . Ac c o r d i n g   t o   i t s   p o s i t i v e   f e e d b a c k   p r i n c i p l e   a n d   t h e   h e u r i s t i c   p in r c i p l e ,t h e r e   i s   ma i n l y   d i r e c t e d   a g a i n s t   t h e   c u r r e n t l y   d o me s t i c   a n d   i n t e r n a t i o n a l   r e s e a r c h. T h e   r e s e rc a h   t h a t   ACO  s e rc a h   t h e   o p t i ma l   p a t h   f r o m  he t   c o n -   v e r g e n c e   p r o p e r t y ,t he   i mp r o v e me n t   o f   c o n v e r g e n c e   a l g o it r h m  nd a   he t   r a p i d i t y   o f   c o n v e r g e n c e   i s   na a l y z e d   nd a   s u mma r i z e d .  M o r e o v e r ,   s o me   a p p l i c a t i o n s   s u c h   a s   L EO  s a t e l l i t e   n e t wo r k   a n d   wi r e l e s s   s e n s e / t r ns a d u c e   a r e   e x p o u n d e d . F i n a l l y , he t   r e s e a r c h   o n   r o u t i n g   o p t i mi z a t i o n   nd a   l o a d   b a l a n c e   o f   ACO  i s   na a l y z e d   nd a   c o mp re a d ,t h e   s h o r t c o mi n g   i s   f o u n d   a n d   t h e   h o t   s p o t   o f   r e s e rc a h   o n   t h i s   ie f l d   i s   p o i n t e d .   Ke y   wo r d s : ACO; c o n v e r g e n c e ;o p t i mi z a t i o n   p a h; r t o u t ng i   o p t i mi z a t i o n ;h e u i r s t i c   a l g o r i t m   h

0 引  言 
路 由 算 法 是 网 络 的 重 要 组 成 部 分 , 它 直 接 影 响 着 网 络  性能 , 而含 有 多约束 条件 的 Q o S路 由是 一 个 NP — C 问题 , 传  统 的路 由算法很 难解 决 , 因此 , 一 些 学 者 尝 试 采 用 不 同 的 算  法 相 结 合 或 者 针 对 问 题 对 某 些 算 法 进 行 改 进 来 解 决 路 由 优 
化 问 题 。 其 中蚁 群 算 法 是 一 个 行 之 有 效 的 方 法 ,针 对 不 同  的 网 络 , 它 在 保 证 服 务 质 量 的 前 提 下 能 够 搜 索 到 网 络 中 的  最 优 链 路 , 提 高 了 网 络 的 传 输 效 率 。 而 这 些 研 究 缺 乏 通 用 

1 蚁 群 算 法 的 定义 
1 . 1 蚁 群 算 法基 本 定 义 
定 义 l( 蚁 群算法 ) 蚁群 算法 ( a n t   c o l o n y   o p t i mi z a t i o n ,   A C O ) , 又称 蚂 蚁 算 法 , 是 一 种 用 来在 图 中寻 找 最优 路 径 的 技术 。   它 最 早 出现 在 1 9 9 2年 D o r i g o  的博士论文 里 , 该 方 法 具 

有 正 反 馈 、分 布 式 计 算 和 富 于 建 设 性 的贪 婪 启 发 式 搜 索 的 特 
点, 主要 用于求解 组合优 化问题 。   定 义 2( 启 发 式 算 法 ) 对 于 那 些 受 大 自然 的运 行 规 律 或 

的 标 准 , 如 何 把 不 同 的 问题 归 结 到 一 个 统 一 的 框 架 下 解 决 
路 由优化 问题 , 如何提 高 寻优速 度 , 缩 短 运 行 时 间 是 当前 的 


者 面 向 具 体 问题 的经 验 、 规 则 启 发 出来 的方 法 , 人们 常 常 称 之 
为启发 式算法 。 现 在 的 启 发 式 算 法 也 不 是全 部 来 自然 的规 律 ,   也 有 来 自人 类 积 累 的工 作 经 验 。  

个 研究 热点 。  

收稿 日期 :2 0 0 8 — 1 0 — 1 6 ;修订 日期 :2 0 0 8 — 1 2 — 1 2 。  
基 金 项 目 : 国家 自然 科 学 基 金 项 目 ( 6 0 4 3 3 0 2 0 、1 0 4 7 1 45 0 、6 0 6 7 3 0 2 3 ) ;广 东 省 自然 科 学 基 金 项 目 ( 9 7 0 4 7 2 、0 0 0 4 6 3 ,0 4 0 2 0 0 7 9 、0 5 0 1 l 8 9 6 ) ; 广 

东省教育厅 自然科学研 究基金项 目 ( Z 0 3 0 8 0 ) 。   作者简介 :贾云富 ( 1 9 8 0 -) ,男,河北沧州人,硕 士研究生 ,研 究方向为路 由算法与工程应用;   秦勇 ( 1 9 7 O 一) ,男,湖 南邵阳人,博 士,副教  授 ,研 究方向为网络并行路 由优化 ;   段富 ( 1 9 5 8 一) ,男 ,山西太 原人,博士 ,教授 ,研 究方 向为软件理 论与算法、计算机 图形学 ;   梁本来  ( 1 9 8 4 一) ,男,山东济宁人,硕士研究生,研究方 向为路 由算法与工程应用 ;   黄翰 ( 1 9 8 0 -) ,男,博士,研究方 向为进化计算方法 的理论基础 、   进化计算方法 的优化设计及其应用;   张美 玉 ( 1 9 7 5 一) ,女 ,硕士 ,研究方向为组合优化算法 。E . ma i l :j i a y u n f u 6 @1 6 3 . c o m 

4 4 8 8  

2 0 0 9 , 3 0( 1 9 )  

计 算机 工程与设 计 C o m p u t e r   E n g i n e e r i n g   a n d   De s i g n  
敛 性 进 行 了 深 入 的理 论研 究 。  

定义 3 ( 信息素)   蚂 蚁 释 放 一 种 化 学物 质 , 根 据 环 境 中 的  这 种 物 质 蚂 蚁 可 以找 到 食 物 和 窝 之 间 的 最 短 路 径 ,我 们 称 这  种 物 质 为信 息 素 。   定义 4 ( 信 息 素 更 新 ) 信 息 素 更 新 是 指 路 径 上 信 息 素 量  与 蚂 蚁 数 量 的变 化 和 时 间 的 推 移 之 间存 在 增 加 和 消 失 的 变 
化关系 。  

1 . 2 . 2 对蚁 群 算 法 的改 进 
蚁群系统 由 D o r i g o和 G a mb a r d e l l a于 9 6年 提 出 , 能够 在 


个 合 适 的 时 间 找 出好 的 解 决 方 案 。但 只 限 小 规 模 的 问题 。   由于 此 限 制 ,专 家 学 者 们 针 对 不 同 的 问 题 对 蚁 群 算 法 进 行 了 

改进 , 典型的蚁群 算法的改进有 : 带精英策 略的蚁群系统 ; 基  于优化 排序蚂蚁系统 ; 蚁 群 系统 ; 最 大 一最 小 蚂 蚁 系 统 ; 最 优 


每只蚂蚁走 完一步或对所有 n 个 节 点 的 遍 历 完 成 后 ,要  对 链 路 上 的 信 息 进 行 更 新 。因 此 , 定义 t + n时刻 在 节 点 i 到 节  点J 的 路 径( i , j ) 上 的信 息量 计 算 公 式 为  ( 什  ) =( 1 一 p )  (   + △  (   ( 1 )  

最 差 蚂蚁 系 统 。   带 精 英 策 略 的 蚁 群 系 统 类 似 于 遗 传 算 法 的精 英 策 略 。 在 

此 系 统 中 ,为 了使 得 当 前 找 到 的最 有 解 对 下 一 次 迭 代 循 环 中  更 能 增 加 蚂 蚁 选 择 的概 率 ,在 每 次 循 环 迭 代 完 以后 对 最 有 解  增 加 额 外 的 信 息 素 量 。缺 点 :虽 然 使 用 精 英 策 略 可 以使 蚂 蚁 
系 统 可 以较 早 的找 出最 优 的解 , 但是 , 由 于使 用 的精 英 蚂 蚁 过  多, 搜索容 易集中在最优值 周围 , 从 而 不 能 找 出 更好 的 解 来 。  

△  ( f ) =E A  ( f )  
I= l  

( 2 )  

式 中: p —— 信 息 素 挥 发 系 数 , △  (   — — 本 次 循 环 中节 点 i 到  节 点 J的 路 径 上 信 息 素 的增 量 。 △  (  — — 第 k只 蚂 蚁 在 本  次循 环 中 在 节 点 i 到节 点 j 的 路 径 上 留下 的信 息 量 。   定义 5 ( 链 路 选 择 概 率 ) 信 息 素 踪 迹 越 浓 的路 径 , 被 选 中  的概 率越 大 , 即路径概率选择机制 。   设 网络 G=( 、 ‘ E ) , 这 里 V表 示 图 中 顶 点 的集 合 , 设i / " =l Vl ,   E表 示 边 的 集 合 。 蚁 群 优 化 的 目的 是 寻 找 图 G 中起 始 节 点 Ⅵ  到 目的节 点 V . 的最 短 路径 , 每 条 边 e( i d ) ∈E都 有 一个 信 息 素  变量 T   , T   会随着迭 代次数的增加而变化 。 P   表 示在 节 点 i 选  择 到节 点 J 的概率 。 Q表 示 节 点 i 处 可 选 择 的 下 一 跳 邻 居 节 点  J的集 合 。 则 蚂 蚁 在 选 择 路 径 时 会 根 据 可 选 每 条 链 路 上 的选  择 概 率 进 行 选择 , 并在该节点根据概 率分配蚂蚁 。   概 率 公 式 为 

基 于 优 化 排 序 的蚂 蚁 系 统 借 助 遗 传 算 法 中 排 序 的 概 念 ,  
根 据 每 只 蚂 蚁 走 过 的路 径 的 长 短 进 行 大 小 排 序 ,并根 据 大 小  顺序进行加权 , 在 这 里 只 考 虑 几 只最 好 的 蚂蚁 , 从 而避 免 局 部  极优路径被 很多蚂蚁过 分重视的情况发 生。   最 大 一最 小 蚂 蚁 系 统 是 把 集 中 到 最 优 解 的 附近 与避 免  早熟收敛行 为结合在一起 。 该 方 法 主 要 做 了 3方 面 改 进 : ① 在  每 次 循 环 迭 代 以后 , 只允许一只蚂蚁 进行信息素更新 , 这 只 蚂 

蚁 既有 可 能 是 找 出 此 次 循 环 中 最 优 解 的蚂 蚁 也 可 能 是 从 一 开  始 以来 最 优 解 的 蚂 蚁 。② 为 了避 免 搜 索 的 停 滞 ,把 路 径 上 信  息素轨迹量 的值域范 围限制在 [ T mi n , T ma x ] 区 间 内 。③ 为 使  蚂 蚁 在 开始 阶 段 就 能 够 搜 索 到 新 的解 决方 案 ,设 信 息 素轨 迹 
初始值 为 T ma x 。  

P / j = :   塑 
[  H 
∈口 

( 3 )  

另外, 宋 雪 梅 等 也 提 出 了 一种 改进 的AC O算 法 即 P MAC O   算 法 , P MAC O算 法 主 要 是 基 于 动 态 信 息 素 升 级 和 变 化 策 略 
( 4 )  

式 中: Q—— 节 点 i 可选 的下一跳节点集合 。  
P/ j=l  
,∈口 

等 以提 高 计 算 质 量 。 根据蚁群 算法 , 有的链路有蚂蚁 通过, 而 
有 的链 路 没 有 蚂 蚁 通 过 ,那 么 当短 链 路 上 的 信 息 素 增 长 比 其  它 链 路 上 的 信 息 素 增 长 快 时 ,更 多 的蚂 蚁 会 以更 高 的概 率 选  择 此 链 路 。这 样 就 容 易 出 现 蚂 蚁 在 开始 时 刻 容 易 选 择 局 部 最  优链路 , 提 出 了变 化 概 率 规 则 , 在刚开始采 取大概率 , 其 它 时  刻 采 取 小概 率 。  

式 中: 珊— — 能 见度 因 数 , 它 由某 种 启 发 式算 法 决 定 。 a ,  , p — — 
3 个参数 , 分 别 反 映 了蚂 蚁 在 运 动 过 程 中所 积 累 的信 息 和 启 发 

信 息 在 蚂 蚁 选 择 路 径 中 的相 对 重 要 性 。  

1 . 2 收 敛 性 
定义 6 ( 收敛 性 )  设P , ( t ) = P “ ∈Y ) 表示第 i 条 路径在 t 次 迭  代 时得 到最 优 路 径 时 的概 率 , 如果l i m P   (  =1 则 称 该 条 路 径 具  有 收敛 性( Y 是 路 径 上 所 有 链 路 集 合) 。  

1 - 3 收敛 速 度 
定 义 7( 收敛速度)   链 路 上 信 息 素 随 迭 代 次 数 增 加 而 聚 

1 . 2 . 1 蚁 群 算法 收 敛性 证 明 
蚂 蚁 通 过 环 境 中 的信 息 素 与 其 它 蚂 蚁 进 行 交 互 , 不 断 的 

集 到 最 优 连 路 上 的快 慢 称 为 收 敛 速 度 。   1 . 3 . 1 蚁 群 算 法 收 敛 速 度 的 分 析 
关 于 蚁 群 算 法 的 收 敛 性 问题 有 很 多 学 者 都进 行 了 一 定 的  研 究 ,并且 得 出 了结 论 ,蚁 群 算 法 是 寻 找 最 优 路 径 可 行 的 方  法, 通 过不断的迭代最终找到最优路径 , 但 是 由于 实 际 网络 中  的情况 非常复杂 , 所 以 有 时 要 经 过 大 量 的 迭 代 最 终 找 到 最 优 

迭代循环 , 最终找到最优路径 , 但是 , 由于 迭 代 的 次数 会 受 到 
具 体 链 路 环 境 的 影 响 ,虽 然 能够 得 到 最 优 路 径 但 有 可 能 会 迭  代好多次. 这 就 影 响 了算 法 的 效 率 , 一 些 专 家 学 者 对 算 法 的 收  敛 性 进 行 了研 究 。  

关 于 蚁 群 算 法 的 收敛 性 , 很 多研 究 者 都 进 行 了分 析 证 明 。  
早 期 的有 G u t j a r h W  J 最 先 从 有 向 图 论 的 角 度 对 特 定 的 改 进 蚁  群算法 B G A S的 收 敛 性 进 行 了 证 明 , G u t j a r h   W  J提 出 了两 种  新 的G B AS , 即G B AS / t d e v 和G B AS / t d l b , 通 过 选 择 合 理 的 参 数  来 保 证 蚁 群 算法 的 收 敛 性 并 收 敛 到 全 局 最 优 解 ;S t u e z l e   T和  D o i f g o   M 提 出 了 一类 改 进 蚁 群 算 法 — — A c O 曲 算 法 并 在 理 

路径 , 虽然能找到但效率也 受到了一定的影响 , 由于 蚁 群 算 法  在 国 内外 研 究 的 比较 晚 ,而 对 如 何 提 高 收 敛 速 度 的研 究 更 是 
成为该领 域一个公开 的问题 。   段海滨等 ”   在 对 基 本 蚁 群 算 法 的 Ma r k o v 链 分析过程中 ,   运 用 离 散 鞅 作 为 研 究 工 具 ,把 最 优 解 集 序 列 转 变 为 下 鞅 序 列  来 考 察 信 息 素 轨 迹 向量 的 收 敛 性 。并对 蚁 群 算 法 几 乎 处 处 收  敛 问题 和 停 时 间 问题 进 行 了研 究 , 提 出 了首 达 时 间 的定 义 , 并 

论 上 分 析 了它 的收 敛 性 , 得 出 当迭 代 次 数 无 限增 大 时 , 算 法 收  敛 到全 局 最 优 解 。 Y o o   J H等 对 一 类 分 布 式 蚂 蚁 路 由算 法 的 收 

对 首 次 到 达 时 间 的 期 望 值 进 行 了分 析 。孙 焘 等 对 一 类 简 单 

贾云富,秦 勇,段 富,等:蚁群 算法及 其在路 由优化 中的应用综述 
蚁 群 算 法 的 收 敛 性 进 行 Ma r k o v 理论分 析 , 并 证 明 了 优 化 解 满 
意值 序 列 单 调 不 增 且 收 敛 。   黄 翰 等 根 据 蚁 群 算 法 的求 解 过 程 是 根 据 信 息 素 和 启 发 式 
作者 
Gu t j a r hW  J I   Ma t h u r M. e t   a l  

2 0 0 9 , 3 0( 1 9 )
表 1 部 分代 表性 蚁群算 法 的证 明与 应用 
解 决的问题 
收 敛 性  连 续 函数 优 化 

4 4 8 9  

改进 的算法或方法 

年代 

向 量 进 行 随机 搜 索 的特 点 , 建 立 了基 于 吸 收态 Ma r k o v 过 程 的 
蚁 群 算 法 数 学 建 模  。 通 过 定 义 和 引理 论 证 了蚂 蚁 最 终 找 到 

GB AS / t d e v , GB AS , c d 1 b   2 0 0 0   AC o— CF O   2 o o O  

L i . X u   S t u e z l e   L   Do r i g o   M 
C i n c o t t i  

最大独立集问题  收敛性 
加 权 最 小碰 集 问题  

A C O— MI S P   A C O 曲 
AA . WM HS P  

2 0 0 3   2 o 0 2  
2 0 0 3  

全 局 最 优 解 ,从 而 为蚁 群 算 法 的 收 敛 性 和 收 敛 速 度 的 分 析 提 
供 了 理 论 依 据 。 通 过 在 Ma r k o v 链 数 学 模 型 的理 论 基 础 上 论 

段海滨”  
Hu a . e t   a l   J e n s e n . S h e n  

提高收敛速度 
点 覆 盖 问  粗 糙 数 据 约 简 

离散鞅 
AA - P CP   ACo - RDR 

2 0 O 4  
2 0 O 4   2 0 0 5  

证 了蚁 群 算 法 的收 敛 性 从 而 对 蚁 群 算 法 的 收 敛 速 度 进 行 分 析 。   由 于研 究 问 题 的 不 同 , 所 以 收敛 速 度 各 不 相 同 , 本 身 由 于 
收 敛 速 度 只 是 定 性 的分 析 收 敛 问题 , 所 以 没 有 特 定 的 公 式 化 

J i n g l e i   G u o , Y o n g   Wu   宋雪梅  黄翰“  

提高收敛速度  收敛性改进  收敛速度 

AC O E O   P MA C O   Ma r k o v数学模型 

2 0 0 6   2 0 0 6   2 O O 8  

描述 , 一般 都 是 根 据 蚂 蚁 的 迭 代 次 数 来 判 断 收 敛 速 度 的 大 小 。  
定 义 8 期 望 收 敛 时 间 :蚁 群 算 法 对 应 的 Ma r k o v过 程  {   }  ( V  , ) =   f ) ,   ) ∈功和 最 优 状 态 空 间 F * c 躇 是 一 个 随  机 非负整数变 量满足 : f ≥y 时P{  f ) ∈  } =1 并且 当 O ≤f ≤y 时,   P{  力 ∈Y   ) ≤ 1则 称^ r 称 为蚁 群算法 的收敛 时 间, y 的期 望 研 称  为蚁群算法 的期望收敛 时 间。   期 望 收 敛 时 间表 述 了 蚁 群 算 法 首 次 以概 率 1 达 到 全 局 最  优 解 的 期 望 时 间 。 收 敛 时 间 越 小表 示 蚁 群 算 法 的 收 敛 速 度 越  快, 效率越高 ; 反之, 蚁 群 算 法 的 收 敛 速 度 越 慢 。 通 过 对 收 敛 

1 . 4 时 间 复杂 性 
定 义 9 给 定 自然 数 n 的两个 函数 F ( n ) * l l   G( n ) , 当 且 仅 当  存 在 一 个 正 常 数 和 一 个 n 。 , 使得 当n 兰n o 时, 有F ( n ) 三K G( n ) ,   则称 函数 F ( n ) 以 函 数 G( n ) 为界 , 记 作  F ( n ) =0( G( n ) )   ( 5 )  

文献 [ 2 6 】 分析 了T S P 的复 杂度 , 基于 此复杂度 的分析 , 我 
们 可 以 得 到 本 算 法 的 时 间 复 杂 度 如 下 :有 n个 节 点 , K 只 蚂 

时 间 的定 义 以及 对 收 敛 时 间 的估 算 方 法 的 分 析 , 得 出 了 对 收 敛 
速度 的定性分析 , 理 论 上 实现 了对 蚁 群 算 法 收 敛 速 度 的 衡 量 。  

蚁, 循 环 迭 代 终 止 条 件 变 量 为 Nc , 则 几 个 关 键 的 步 骤 的 时 间  复杂度 为 :  
( 1 ) 初 始化参数 : O ( n   + m) ;   ( 2 ) 信 息 素 更 新 量 的计 算 : O ( n  m) ;  

1 . 3 . 2 蚁 群 算法 收敛 速 度 的提 高 
J i n g l e i G u o 和Y o n g Wu 在 收 敛 速 度 的提 高 上 提 出 了AC O E O   方 法  , 主 要 思 想 是 在 AC O E O方法 中, 应 用 变 换 操 作 和 交 互  操 作进行搜 寻最优路径提 高收敛速 度 。 O Xc r o s s o v e r 方 法“   被  应 用 到 本 论 文 中 。OX   c r o s s o v e r是 通 过 从 父 类 那 里 选 择 一 个 

( 3 ) 根 据Nc 判 断循环迭 代的终止条件 : O ( n   m) 。   当 足 够 大 时 , 该 蚁 群 算 法 的 时 间 复 杂 度 为 
T n ( n ) =O( N c * 1 1  m)   ( 6 )  

游 走 序 列 并 保 存 这 些 城 市 的 相 关 序 列 顺 序 。通 过 颠 倒 父 类 的 
断 点 间 序 列 得 到 自 己 的序 列 。在 A C O 算 法 中通 过 应 用 进 化 

2 路 由优 化 
2 . 1 路 由寻 路 
数 据 在 链 路 上 传 输 时 会 受 到 带 宽 时 延 丢 包 率 等 影 响 网络 

操 作 和 交 叉 操 作 在 实例 中 证 明最 优 链 路 能 更 高概 率 的 获 得 信  息素的提高从 而提高收敛 速度 , 避免 局部最优 现象 。 另外 , 我 
们 采 用 了 一 个 基 于 适 合 每 一 个 蚂 蚁 的 动 态 选 择 方 式 ,最 好 的  蚂蚁具有 优先更新信 息素的机会 , 研 究 显 示 AC OE O具 有 高 效  的在 搜 索 区 域 中 寻 找 路 径 的 能 力 。模 拟 实 验 显 示 它 的 收 敛 速  度 和 优 化 性 能 比 AC O算法要 好 。   Y i Z h a n g 在R OS中 主 要 是 通 过 减 少 寻路 算 法 的执 行 频 率  和 时 间 复 杂 性 。通 过 限制 访 问最 短 城 市 的蚂 蚁 来 降低 时 间 复 

服 务 质 量 的 约 束 条 件 的 限制 ,用 这 些 约 束 条 件 来 描 述 数 据 传 
输 时的代价 , 根据链 路情况 , 选 择 链 路 代 价 最 小 的 最 优 路 径 进 
行 数据传 输。  

每 只 蚂 蚁 都 跟 蚁 群 优 化 算 法 中 描 述 的一 样 , 根 据 它 在 网  络 上 的 掌 握 的 链 路 的 知 识 ,可 以动 态 的 更 新 路 由 表 项 。如 果 


只 蚂 蚁 在 网 络 中 遇 到 堵 塞 路 由而 产 生 较 大 的延 迟 时 , 它 就 

杂度“   。 他 主要是通过 两个方法 实现 , 一 是 设 定 限制 蚂 蚁 在 寻  路 过 程 中 对 下 一 个 最 短 城 市 的 访 问 权 限 ,二 是 通 过 修 改 个 体  变量法n ,  的值 , 文 章 设 定 了每 个 蚂 蚁 的 6 ( ,  的 值 都 不 一 样 , 由 
于 刚 开 始 时蚂 蚁 对 链 路 的 情 况 不 了 解 , 所 以设 定 d= 1 ,  =5 ,   随 着 迭 代 次 数 的增 加 , 链 路 上 的信 息 素 对 蚂 蚁 的 寻 路 影 响 越  发重要 , a ,  的值 相 应 的 改变 , 采用鼓励机制“ “ , 在循环迭代 中,   优 胜 者 同 时 修 改 个 体 变 量 ≤ 的值 , 即d :1 到5 , 而f l =5到 1 。   只 有 优 胜 者 即优 胜 者 的Ⅱ 逐渐 增加 ,  逐 渐 减 小 。到 最 后 6 c = 5 ,   :1 使 优 胜 者 的 选 择 改 链 路 的概 率 越 来 越 大 , 从 而 可 以 得 到 

对 该 表 项 做 相 应 的 修 改 ,以 增 强 路 由 信 息 。 同 时 利 用 蚁 群 算 

法 中 的信 息 素 挥 发 机 制 对 系 统 的 信 息进 行 更 新 ,抛 弃 过 期 的 
路 由信 息 。 选择一条 最优路径 , 从 而 提 高 网络 的 均 衡 性 、 负 荷 
量和利用 率 。  

2 . 2 蚁群 算 法 在 路 由优 化 中的 研 究 与应 用 
学者们 已经证 明当 Q o S路 由 至 少 含 有 两 个 约 束 条 件 时 ,   它 为 一 个 NP — C 问 题 。而 传 统 的路 由 算 法 很 难 解 决 N P . C 问 
题, 鉴于蚁群算法 的特点 , 许 多学 者 把 蚁 群 算 法 应 用 到 路 由优  

化 和负载 平衡“   中 以 解 决 问题 。 其 中, Z i q i a n g Wa n g和 D e x i n  a
Z h a n g “   把 局 部 信 息 素 和 全 局 信 息 素 的更 新 规 律 应 用 到 多路 路  由中 , 局 部 更 新 机 制  r ,   ) 一( 1 一 p )   , ,   )   . p   ( 7 )   式中: P— — 信 息 素 衰 减 系 数 ,   — — 链 路 上 的信 息素 初 始 值 。   全 局 信 息 素 更 新 机 制 

此 链 路 的 收 敛 速 度 越 来 越 快 ,到 最 后 找 到 最 优 路 径 。 实 验 证 
明这种鼓 励机制 能够加快收敛 速度提 高搜寻质 量。   关 于 蚁 群 算 法 的 收敛 性 及 收敛 速 度 问 题 ,不 同 的 学 者 根  据 不 同 的 情 况 提 出 了 不 同 的 方 法 或 证 明 思 路 ,或 应 用 到 了不  同的领域 , 现 把 进 几 年 的具 有 代 表 性 的 方 法 列 表 如 表 1 所示 。  

4 4 9 0  

2 0 0 9 , 3 O( 1 9 )  
玎  ) 一( 1 一a  

计算机工程 与设计 C o m p u t e r   E n g i n e e r i n g   a n d   D e s i g n  
) 十 a   At  , ,   )  


(  

眦   r   ( 8 )   用 星 上 资源 。  
( 9 )  

定 的收 敛 速 度 的 同时 达 到 了 均 衡 网络 负 载 的 目的 , 充 分 利  具 有 代 表 性 的蚁 群 算 法 的研 究 与 应 用 如 表 2 所 示。  
虽 然 一 些 学 者 对 蚁 群 算 法 在 路 由 优 化 和 负 载 平 衡 中 的 



式 中: a ——信息 素衰减系数 ,   — — 从 开 始 节 点 到最 终 节 点  的最 优 路 径 的 长 度 。 仿 真 试 验 证 明都 能够 较 快 的 找 到 路 由 ,  

研 究 和 应 用 中 已 经 取 得 了 一 定 的成 果 , 但 是 由 于 蚁 群 算 法 的  在 该 领 域 的研 究 刚 刚起 步 , 研 究成 果还不 多 , 并 且 在 网 络 路  由优 化 和 负 载 平 衡 方 面 的研 究 还 没 有 实 质 性 的 成 果 , 人 们 只  是 在 简 化 条 件 下 对 算 法 进 行 了 简 单 的 应 用 。 如 何 更 好 的提  高 蚁 群 算 法 的 收 敛 速 度 并 应 用 到 路 由优 化 中 实 现 流 量 负 载 
平衡 , 如 何 改 变 循 环 迭 代 的条 件 加 速 路 由的 优 化 都 是 将 来 的  研 究 热 点 问题 。  

从 而 提 高 了 收敛 速 度 , 优 化 了 网络 效 率 。   现 有 网 络 中 常用 的链 路状 态 路 由 算 法 等 不 具 有 拥 塞 响 应 
机 制 的功 能 , 所 以当 网 络 上 一 条 链 路 发 生 拥 塞 时 , 它 只 能 通 过 

简 单 的 丢 弃 数据 包 来 解 决 。林 国辉 等  提 出 了 一 种 基 于 蚂 蚁  算 法 的拥 塞 规避 路 由算 法 。 该 算 法 能 够 迅 速 的找 到 两 点 间 的 
最 优 路 径 ,并 且 能 够 预 测 到链 路 的拥 塞 状 态 而 做 出 快 速 的 反  映, 分散流量 , 从 而 避 免 链 路 的拥 塞 , 在 很 大 程 度 上 加 速 了蚂  蚁 路 由算 法 探 索 最 优 路 径 的 过 程 。仿 真 实 验 表 明 该 算 法 在 数  据 包 传 输 时 延 和 网络 丢 包 率 性 能上 比链 路状 态 路 由 算 法 具 有  明显 的优 越 性 。 另外 , Y u a n L i 和Z h e n g x i n Ma 等 同 样 针 对 网络 

3 结束 语 
蚁群 算 法 是 学 者 们 根 据 自然 界 中蚂 蚁 的觅 食 行 为得 出 的  优 化 算 法 ,它 作 为 一 种 解 决 优 化 问题 的 方 法 虽 然 研 究 的 时 间 

拥 塞 和 网络 效 率 低 下 等 缺 点 提 出 了 MS — AC O 算 法  , 主 要 解  决 了信 息 系 停 滞 的 问题 , 在丢包率, 平 均 时 延 以 及 负 载 平 衡 方  面 就 有 比 以往 的 算 法 更 好 的 效 果 。很 好 地 解 决 了 多 约 束 Q o s   路 由优 化 的 问 题 。 实 现 了对 网络 的 Q o s 的优 化 。   也有一些学者把蚁群算 法应用到实 际中, L a y u a n   L I , Y a n g  
X I A N G   ” 用 基 于 并行 蚁 群 算 法 思 想 拓 展 了 Ad h o c 网络 上 的 多 

不长 , 但 是 由于 其 自身 的特 性 , 专 家 学 者 们 在 其 收敛 性 以及 收  敛 速 度 方 面 做 了研 究 , 证 明 了算 法 的 收 敛 性 , 并 在 提 高 收敛 速  度 方 面 对 蚁 群 算 法 做 了 一 定 的 改 进 。但 是 这 些 研 究 大 都 是对  改 进 的蚁 群 算 法 的 分 析 或 是 在 对 实 际 问题 的 实验 条 件 或 约束  条 件 进 行 简化 的 前 提 下 进 行 的 ,因此 对 蚁 群 算 法 的在 收 敛 性 
以及 收 敛 速 度 的 理 论 上 的研 究 深 度 不 够 ,这 些 分 析 没 有 统 一  到 一 个 共 同 的 框 架 内 。如 何 建 立 一 个 统 一 的 框 架 标 准 对 收敛  

路 径 路 由协 议 ,即 在 源 节 点和 目的 节 点 之 间建 立 一 个 多 路 径 
的路 由协 议 , 从 而 大大 提 高 了数 据 包 的传 送 速 度 。在 N S 2 . 2 8  

性 进 行 统 一 的分 析 研 究 仍 然 是 学者 们 要 解 决 的 一 个热 点 问题 。   由于 路 由直 接 影 响 着 网络 性 能 , 所 以 Qo S路 由是 当今 网 
络 技 术 领 域 的 一 个 研 究 热 点 问题 。 专 家 学 者 们 把 蚁 群 算 法 应  用 到 路 由优 化 中 寻 找 最 优 路 径 并 通 过 仿 真 实验 证 明 能够 得 到 

实 验 环 境 中仿 真 表 明对 在 提 供 高连 接 性 而 不 需 要 更 多 的 网络 
容 量 的情 况 下 可 以潜 在 反 映时 间和 端 对 端 的 延迟 , 同时, 并 行  A C O 能够 提 高 路 由预 测 概 率 和 收 敛速 度 。   另 外 蚁 群 算 法 在 无 线 传 感 中 的应 用  和 L E O卫 星 网 络 中  的应 用  圳 等 领 域 也 取 得 了一 定 的 成 果 。其 中 , 王平等n   针 对  低 轨 卫 星 网 络 动 态 拓 扑 路 由 的 问题 ,更 改 了蚁 群 优 化 算 法 结 

最优解 。 但是 , 由 于 不 同 的 网络 结构 其 约 束 条 件 不 同 , 如 何统 


约束条件 限制 , 如 何 规 范 约 束 条 件 标 准 以寻 找 最 优 路 径 是 

当前 的一 个 研 究 热 点 。 另 外 , 蚁 群 算 法 虽 然 能 够 找 到最 优 路  

构 以及 信 息 素 更 新 策 略 , 提 出 了 一种 适 合 L E O卫 星 网 络 的具 
有 多 Qo s 约束条件 的 A C O路 由算 法 , 这 种算法能够根据 L E O   网络 中业 务 流 量 分 布 的 变 化 对 网络 最 优 路 径 做 出调 整 ,均 衡  网络 负载 , 避免拥 塞, 实现 多种 Q o s 指 标 的 联 合 最 优 。改 进 算 

径, 但是 , 由于 不 同 的 拓 扑 结 构 和 网络 节 点对 蚁 群算 法 寻 找最 
优 路 径 的 时 间 影 响很 大 , 如 何 提 高蚁 群算 法 的 寻 优 效 率 , 缩 短  寻优 时间, 也 是 当 前 亟 待 解 决 的 重 要 研 究课 题 。  

法 的具体实现为 : ① 根 据 卫 星 网络 流 量 变 化 有 缓 变 和 激 变 两 
种, 当卫星网络流量缓变时采用温和手段 , 在 选 择 下 一 跳 时 采 

参 考 文献 :  
【 1 】 Do r i g o   M, S t i i t z l e   A n t   c o l o n y   o p t i m i z a t i o n 【 M】 . C a m b r i d g e ,  
MA: MI T  P r e s s . 2 0 0 4.  

用 先 验 概 率 与 随 机 搜 索 相 结 合 的 办法 ;对 于 激 变 采 用 一 种 切  换 通 告 蚂 蚁 来 更 新 切 换 点 与 邻 节 点 间 链 路 上 的 信 息 素 。② 为 
反 映 动 态 网络 特 性 , 将 蚁 量 系 统 模 型 和 标 准 AC 0相 结 合 来 对  多种类 型的 Q o s联 合 优 化 。 并 且 作 者 采 用 O P NE T 网 络 仿 真  软件 , 以I r i d i u m卫 星 通 信 系 统 为 例 , 对 所 提 出的 路 由算 法 进 行 

[ 2 】  G u t j a h r   W  J . A   g r a p h - b a s e d   a n t   s y s t e m   a n d   i t s   c o n v e r g e n c e [ J ] .  
F u t u r e   Ge n e r a t i o n   C o m p u t e r   S y s t e m, 2 0 0 0 , 1 6 ( 8 ) : 8 7 3 - 8 8 8 .  
【 3   J   S t u e z l e   T , Do r i g o   M. A  s h o r t   c o n v e 壤e n c e   p r o o f f o r   a   c l a s s   o f nt a  

c o l o n y   o p t i mi z a t i o n   a l g o i r t h ms [ J ] . I E E E   T r a n s a c t i o n s   o n   E v o l u -  

了仿 真 , 结果显示 : 在 网 络 接 近 满 负荷 的情 况 下 , 算 法 在 保 证 
业 务Q o s 需求 的同时, 该 路 由算 法 能 够 及 时调 整 路 由 , 在 保 持 

t i o n a r y   C o mp u t a t i o n , 2 0 0 2 , 6 ( 4 ) : 3 5 8 — 3 6 5 .  
[ 4 】   Yo o   J   H, L a   R   J , Ma k o ws k i   A  M. C o n v e r g e n c e   o f   a n t   r o u t i n g   a l 一  

表 2 具 有代 表性 的蚁群 算 法的研 究与 应用 
作者  Z i q i a n g   Wa n g , D e x i a n   Z h a n g   林 国辉, 马正新等“  
Yu a n   Li . Z h e n g x i n   Ma   。  

应用领域  网络路 由   网络路 由  
网络 路 由 

采用的方法  局部信息素更新、 全局信息素更新  拥塞规避路 由算法 
MS — ACO 算 法 

解 决问题  收敛速度慢  链路拥塞 
链 路拥 塞 , 网 络 效 率 低 

年代  2 0 0 5   2 0 0 3  
2 0 0 5  

G e   C h e r t . S e l c u k   O k d e m  ̄ - ”   王平, 顾学迈等 
L a y u a n   L I , Y ng a   X I AN G  

无线传感器 网络  基于 A C O的无线传感器网络路 由协议  低轨卫星 网络  多Q o s 约束条件的 A C O路 由算法 
A d h o c网络  并行蚁群算法 

网络优化路径建立与维护  网络负载平衡, 资源共享 
数据包传送效率 

2 O o 6   2 O 0 7  
2 o 0 8  

贾云富 ,秦勇 ,段富 ,等:蚁群算法及其在路 由优化 中的应用 综述 
g o r i t h ms - r e s ul t s   f o r   s i mpl e   pa r a l l e l   ne t wo r k  a n d   pe r s pe c t i v e s  

2 0 0 9 , 3 0( 1 9 )

4 4 9 1  

[ 1 5 ] Hu a   Z , F a n   H, Li   J   J , e t   a 1 . S o l v i n g   p o i n t   c o v e r i n g   p r o b l e ms   b y   a n t   a l g o it r h m[ C ] . P r o c e e d i n g   o f he t   nt I e r n a t i o n a l   Co n f e r e n c e   o n   Ma —  
c hi n e   Le a ni r ng   nd a   Cy be ne r t i c s , 20 0 4: 3 5 01 — 3 5 0 4.  

[ R] . T e c h n i c a l   Re p o  ̄CS HCN  2 0 0 3 - 4 4   I n s t i t u t e   or f   S y s t e ms   Re —  

s e a r c h , Un i v e r s i t y   o f Ma r y l a n d , C o l l e g e   P a r k ( MD ) , 2 0 0 3 .  
[ 5   ] S ut t z l e   T , Ho o s   H   H. MAX— M  a n t   s y s t e m  a n d   l o c a l   s e a r c h   or f   t h e   t r a v e l i n g   s a l e s ma n   p r o b l e m[ C] . I E E E   I n t ' l   C o n f o n   E v o l u t i o —  
n a r y  Co mpu t a t i o n. 1 nd i a n a p o l i s : I EEE  Pr e s s , l 9 9 7: 3 09 — 31 4.  

[ 1 6 】J e n s e n&S h e n   Q. F u z z y — r o u g h   d a a  t r e d u c t i o n   wi t h   a n t   c o l o n y  

o p t i mi z a t i o n [ J ] . F zz u y   S e t s   nd a   S y s t e ms , 2 0 0 5 , 1 4 9 ( 1 ) : 5 - 2 0 .  
[ 1 7 】 Yi n g - T u n g   Hs i a o . Co mp u t e r   n e wo t r k   l o a d — b a l a n c i n g   a n d   r o u t ng i  

[ 6 】 Xu e me i   S ONG, Bi n g   L I , Ho n g me i   Y ANG. I mp r o v e d   nt a   c o l o n y  

b y   nt a   c o l o n y   o p t i m i t i o n [ C ] . I E E E , 2 0 0 4 : 3 1 3 - 3 1 8 .   [ 1 8 】 Wa n g   Z i q i ng a , Z h a n g   D e x i n. a A   Q o s   m u l t i c a s t   r o u t i n g   a l g o i r t h m  b a s e d   o n   nt a   c o l o n y   a l g o i r t m [ h C ] . I E E E   1 0 0 7 , 2 0 0 5 .  

a l g o r i t h m   nd a   i t s   a p p l i c a t i o n s   i n   T S P [ C ] . I S D A。 0 6 , 2 0 0 6 .  

【 7 】   段海 滨, 王 道波 . 一 种快 速全 局优 化的 改进蚁 群算 法及仿 真 【 J ]   . 信息 与控 制, 2 0 0 4 , 3 3 ( 2 ) : 2 4 1 . 2 4 4 .   【 8 】   孙焘 , 王秀 坤. 一种 简单 蚂蚁 算法 及其 收敛性 分析 【 J 】 . 小型微 型  计算 机系 统, 2 0 0 3 , 2 4 ( 8 ) : 1 1 6 . 1 1 9 .   【 9 ]   黄翰 , 郝 志峰 , 吴春 国, 等. 蚁 群算 法 的收 敛速 度分 析 【 J 】 . 计 算机  学报 , 2 0 0 7 , 3 0 ( 8 ) : 1 3 4 5 — 1 3 5 3 .  
[ 1 0 】 Gu o   J i n g l e i ,Wu   Y o n g . An   a n t   c o l o n y   o p t i mi z a t i o n   a l g o i r t m   h

【 1 9 ] 林 国辉, 马 正新, 王 勇前, 等. 基于蚂 蚁算 法的拥 塞规避 路 由算 法  [ J 】 _ 清 华大 学学报 , 2 0 0 3 , 4 3 ( 1 ) : 1 4. -  
【 2 0 】Y u a n   Li 。 Z h e n g x i n   Ma . A  mi t i g a t ng i   s ag t n a t i o n - b a s e d   nt a   c o l o n y   o p t i mi z a t i o n   r o u t i n g   a l g o i r t h m[ C] . P r o c e e d i n g s   o f   I S CI T , 2 0 0 5 .   [ 2 l 】L I   La y u a n , XI ANG  Ya ng . R e s e rc a h   o f mu l t i — p a h  t r o u t i n g   p r o t o ?  
c o l   b a s e d   o n   p ra a l l e l   nt a   c ol o n y   a l g or i t h m  o p t i mi za t i o n   n  i mo —  

w i t h   e v o l u t i o n a r y   o p e r a t o r   f o r   r t a v e l i n g   s a l e s ma n   p r o b l e m[ C ] .  
I EEE, SDA’ 0 6, 20 0 6.  

b i l e   a d   h o c   n e wo t r k s [ C ] . F i t f h   I n t e r n a t i o n a l   C o n f e r e n c e   o n   nf I o r .  
ma t i o n   T e c h nol o g y: Ne w  Ge ne r a t i o n s , 2 0 08 .  

[ 1   1 】  Y i   Zh ng a . n  A i mp r o v e d   nt a   c o l o n y   o p t i mi z a t i o n   a l g o r i t h m  b a s e d  
o n   r o u t e   o p t i mi z a t i o n   nd a   i t s   a p pl i c a t i o n s   i n   ra t ve l l i ng   s a l e s ma n  

【 2 2 】G e   C h e n , T i a n — D e   G u o . An   i mp r o v e d   a n t - b a s e d   r o u t i n g   p r o t o c o l   i n   wi r e l e s s   s e n s o r   n e t w o r k s [ C ] . I E E E , 2 0 0 6 .  
[ 2 3 】S e l c u k   Ok d e m, De r v i s   Ka ra b o g a . Ro u t ng i   i n   wi r e l e s s   s e n s o r   n e t -  

p r o b l e m[ C ] . I E E E, B I BE , 2 0 0 7 .   【 1 2 】 Ma t h u r   M, Ka r a l e   S   B, P r i y e   S , e t   a 1 . An t   c o l o n y   a p p r o a c h   t o   c o n —  

w o r k s   u s ng i   nt a   c o l o n y   o p t i m i z a t i o n [ C ] . P r o c e e d i n g s   o f he t   F i r s t  
N ASA/ ES A  Co n f e r e nc e   o n   Ad a p t i ve   Ha rd wa r e   nd a   S ys t e ms ,  
I EEE, 20 0 6.  

t i n u o u s   f u n c t i o n   o p t i mi z a t i o n [ J ] . I n d u s t i r a l   a n d   E n g i n e e r i n g  
C h e mi s t r y   Re rc a h , 2 0 0 0 , 3 9 ( 1 0 ) : 3 8 1 4 — 3 8 2 2 .   【 l 3 】L i   Y  M. Xu   Z   B. An   a n t   c o l o n y   o p t i mi z a t i o n   h e u i r s t i c   or f   s o l v i n g  

【 2 4 】 王平 , 顾 学迈 . 基 于 AC O的L E O卫 星 网络路 由研 究[ J ] . 南京 理 
工 大学 学报 , 2 0 0 7 , 3 1 ( 3 ) : 3 6 4 - 3 6 9 .   [ 2 5 】Z i - H e   G a o , Q ng i   G u o . A n   a d a p t i v e   r o u t i n g   b a s e d   o n   n  a i m p r o v e d  
nt a   c o l o n y   o p t i mi z a t i o n   i n   L E O  s a t e l l i t e   n e wo t r k s【 C】 .Ho n g  
Ko n g: Pr o c e e di n gs   o ft h e   Si xt h   I n t e na r t i o n a l   Co nf e r e n c e   o n   Ma -   c hi n e   Le a ni r ng   a n d   Cyb e ne r t i c s , 20 0 7.  

m a x i m u m  i n d e p e n d e n t   s e t   p r o b l e ms [ C ] . P r o c e e d n i g   o f   he t   5 h t  
I nt e r na t i o na l  Co nf e r e n c e   on  Co m pu t a t i o n a l  I n t el l i ge nc e  a nd  

Mu l t i me d i a   Ap pl i c a t i o ns , 2 00 3 : 2 06 — 21 1 .  

【 1 4 】C i n c o R i   A, Cu t e l l o   P a p p a l rd a o   F  An   nt a - a l g o i r t h m  f o r   he t   we i g h t e d   mi n i mu m  h i t t ng i   s e t   p r o b l e ms [ C] . P r o c e e d i n g s   o f he t  
I EEE  S wa r m  I n t e l l i ge nc e   S y mp os i u m, 20 0 3: 1 — 5 .  

【 2 6 】 段海 滨 . 蚁 群 算法 原理 及其 应用 [ M】 . 北 京: 科 学 出版社 , 2 0 0 5 .  

( 上接第 4 4 7 4页)  
别 的若干 样本 , 从 已知 的 数 据 中 找 出 违 约 ( “ 坏” 客户) 及 不 违 
约者 ( “ 好” 客户 ) 的特 征 , 从而 总结 出分类 的规则 , 并 把 总 结  出 的 分 类 规 则 用 于 测 量 借 款 人 的违 约 风 险 , 为 消 费 信 贷 决 策  提供 依据 。   借助于数 据挖掘技术 手段进行 信用评 分, 和 传 统 的 主 观  教育 出版社 , 2 0 0 4 .   石庆 焱 , 靳云汇 . 个人 信用 评分 的主要 模 型与方法 综述 [ J ] . 统计  研 究, 2 0 0 3 ( 8 ) : 3 6 — 3 9 .   孙大 利 . 个人 信 用评 分模 型综述 与应 用分 析 【 J ] . 中国信用 卡,  
2 0 0 6 ( 1 8 ) : 2 7 . 3 4 .  

判 断 方 法 具 有 很 多 相 似 之 处 ,比如 都 假 设 未 来 的 情 形 与 历 史  状态相似 ; 把 新 的贷 款 申请 与 过 去 的 经 验 相 比较 ; 目标 都 是 在  可 承 受 的 风 险 范 围 内 发 放 贷 款 等 。然 而 , 与 主 观 判 断 方 法 相 
比, 基 于 数 据 挖 掘 技 术 的信 用 评 分 方 法 可 以 增 强 个 人 信 贷 决 

刘 慧婷, 倪 志伟, 李 建洋 肘 间序列 相似模 式 的有效 匹配[ J ] . 计算  机 辅助 设计 与 图形学 学报 , 2 0 0 7 , 1 9 ( 6 ) : 7 2 5 - 7 2 9 .  
Hu a ng   N  E, Sh e n   Z, Lo ng   S   R, e t   a 1 . Th e   e mpi ic r a l   mod e   d e c o m-   p os i t i o n   nd a   t he   Hi l be r t   s p e c t r um  or f   no n l i n e r  a nd a   n o n- - s at t i o ? ?  

策 的科 学 性 与 公 正 性 , 提高个 人信贷决策 的效率 。  

n a r y   t i me   s e i r e s   a n a l y s i s[ J ] . P r o c   R   S o c   L o n d   A ,1 9 9 8 , 4 5 4 :  
9 03 . 9 9 5.  

参 考 文献 :  
[ 1 】   刘 顺挺 . 基于 数据 挖掘 技 术的个 人信 用评 估 模型 [ D 】 . 南京 : 南  京 理工 大 学, 2 0 0 7 .  

张铃 , 张钱 殷 海风 . 多层 前 向网络 的交 叉覆盖 设计算 法[ J 】 . 软件 
学报 , 1 9 9 9 , 1 0 ( 7 ) : 7 3 7 — 7 4 2 .  

刘 慧婷, 倪 志伟, 李建洋 , 等. 基 于交叉 覆盖算 法 的时间序 列模式 
匹配 [ J 】 . 计 算机 应用 , 2 0 0 7 , 2 7 ( 2 ) : 4 2 5 — 4 2 7 .  
Pe ng   Z  K, Ts e   Pe t e r   W  Chu   F   L. An   i mpr o ve d   Hi l b e r t - Hu a n g  

[ 2 】   姜 琳. 美 国F I C O评 分系 统述 评[ J 】 . 商 业研 究 , 2 0 0 6 ( 2 0 ) : 8 1 . 8 4 .   【 3 】   彭 书杰 , 胡 素华 . 信 用风 险模 型综 述 [ J 】 _ 地 质技 术经 济管 理,  
2 0 0 3 , 2 5 ( 2 ) : 3 6 4 - 0 .  

t r a n s f o r m  nd a   i t s   a p p l i c a t i o n   i n   v i b r a t i o n   s i g n a l   na a l y s i s [ J ] . J o u r -   n a l   o f S o nd u   nd a   V i b r a t i o n , 2 0 0 5 , 2 8 6 ( 1 . 2 ) : l 8 7 . 2 0 5 .  

[ 4 】   杨虎 . 数理 统计 非数 学类 专 业研 究生 教学 用书 [ M】 . 北京: 高等 


相关文章:
蚁群算法文献综述
(论文)文献综述 蚁群算法及其在组合优化问题中的应用研究摘要:本次文献综述主要...问题,其典型代表有 TSP, 车间调度问题;另一类是动态组合优化问题,例如网络路由...
蚁群算法综述
笔者综述性地介绍了 ACA 对一些已 有的提出自己的想法,并对其应用及发展前景...蚁群算法及其在路由优化... 5页 免费 喜欢此文档的还喜欢 蚁群算法综述 9页...
蚁群优化算法及编程实现
蚁群优化算法及编程实现_计算机软件及应用_IT/计算机_专业资料。蚁群优化算法及...当前应用最为广泛的几个领域有:车间作业调度问题、网络 路由问题、机器人领域、...
蚁群算法在连续函数优化求解中的应用
蚁群算法在连续函数优化求解中的应用_其它考试_资格考试/认证_教育专区。一种用于...该算法同时采用在最好解蚂蚁领域内进行搜索将本次循环得到的最优解作为起始解...
蚁群算法及其在序列比对中的应用研究综述
为了将这些分散的文献和资料集中起来 , 本文对蚁群算法 及其 在序列比对中 的应用研究进行了 较全面地综述。 2 蚁群算法的原理用于优化领域的人工蚂蚁算法, 其...
蚁群算法路径优化算法
蚁群算法路径优化算法_信息与通信_工程科技_专业资料。蚁群算法路径优化算法 ...(1,m); % 转移概率,基于路径长度及路由表 for j=1:m ifinroute(j,route...
蚁群算法应用
TSP 问题代表一类组合优化问题, 在实际工程中有许多...,对蚁群算法的基本问题及典型的蚁群算法进行了综述。...网络路由问题,图的着色问题以及机器 6 人路径规划等...
优化算法之蚁群算法概述
本文简述了蚁群算 法的生物学机理、发展过程、算法特点及其研究和应用现况,总结...等人在解决工程设计中连续空间的优化问题时, 用 蚁群算法精确化其利用遗传算法...
基于蚁群优化的自组网路由算法的研究与仿真
由于蚁群优化算法是一种通用的分布 式随机优化方法,并广泛应用于网络的路由算法中,因此,该路由协议结合蚁 群算法的原理,首次提出了蚂蚁释放有效信息素的比率,而且...
蚁群算法的改进策略
保证了蚂蚁种群多样性以及生存时 间,改进算法更有效...是对蚁群算法的很 好补充,该算法应用于求解优化问题...网络路由、单机调度、电路分布 线等各个方面,表现出...
更多相关标签:
蚁群算法综述 | 蚁群优化算法 | 蚁群优化算法 matlab | 蚁群算法优化神经网络 | 蚁群优化算法 马良 | 蚁群优化算法的伪代码 | 蚁群优化算法的特点 | 蚁群优化算法 pdf |