当前位置:首页 >> 机械/仪表 >>

基于混合蚁群遗传算法的Agent联盟求解


第 3 6卷  第 4 期 
20 9 ‘ 4 月 0    









学 

Vo . 6No 4 13   .  
AD. 0  r 20 9

Co o e  Sc e e m ut r inc  



基 于 混 合 蚁 群 遗 传 算 法 的 Agn 联 盟 求 解  et
梁 军 程显 毅 

( 苏大 学计 算机科 学 与通信 工 程 学院  镇江 2 2 1 ) 江 1 0 3 
摘 要 针对混合蚁群遗传算法容 易融合 时机过早或过 晚、 种群进 化经 历的代数过 多、 效率低等 问题 , 首先改进 了蚁 

群算法 , 并将改进的蚁群 算法和遗传 算法结合 , 应用 于 Agn 联盟 求解。提 出了基于混合蚁群遗传算 法的 Agn 联盟  et et 求解算法( b i An  oo yadG n t   g r h HAGA , Hy r   t ln  n   e ei Aloi m, d C c t ) 算法的核 心是 动 态寻找 两个算法的衔接 点 , 该点 左  在 侧使 用遗 传算法, 右侧使 用蚁群算 法。与其他传统 算法的实验 比较 , 明了该 算法在 求解联 盟的最优解的时间和精度  证
上都 有较 高 的 效 果 。把 HAGA 应 用 于 R bC p2 o o u  D龙 队客 户 端 程 序 中 , 用 比 赛 分 析 工 具 软 件 S ceD c r 比赛  使 ocr ot 对 o

结果进行 了统计 分析 , 结果显示龙 队在诸 多技术参数 方面均 占有明显优 势。  
关键词 Agn 联 盟, et 蚁群算法 , 遗传算法 , 器人足球 比赛  机
T 2 3 2  P 7 . 2 文献标识码 A  中 图法 分 类 号

S l i   e h d o   e tCo lto   o lm   s d o H y r d AntCo o y a   ne i  l o ihm   o v ng M t o   fAg n   a ii n Pr b e Ba e   n  b i     l n   nd Ge tcA g r t L ANG u   CHENG  a - i I Jn Xin y 
( c o l f o ue  ce c S h o    mp tr in e& C mmu i t n E gn eig Ja g u Unv ri , h n i g 2 2 1 , hn ) oC S o nc i   n ie r , i s   ie s y Z e j n   1 0 3 C ia   ao n n t a

Ab ta t Ai n   ts c   r b e   st o e ry o  o  a e f s n o  h   y rd a tc l n , o   n   e e a i n   ft e sr c  mi g a   u h p o lms a  o   a l   r t o lt  u i   ft eh b i  n   o o y t o ma y g n r t s o  h   o o s e is e o u in a d l w  fiin y, h   n   o o y ag rt m , is  fa l g t i r v d An   h   o n c i n o   h  m— p ce   v l t   n  o e f e c t e a tc l n   l o i o c h f to   l o  mp o e . r , d t ec n e t   ft ei   o p o e   n   o o y ag r h a d t e g n tca g rt m s a p id t   h   r b e s l i g o  h   e tc a iir  e a — r v d a tc l n   l o i m  n  h   e e i  l o ih i p l  o t e p o lm- o v n   ft e Ag n - o l o LTh   l t   e t  

g r h   f h  g n o l i   a  u   r a d Th  o e t h   l r h   y a c l   e rh sf rt e on  on  f oi t o  ea e tc aio w s p tf w r . e c r o t eag i m d n mi l s ac e o  h   itp it   m t tn o o t ay j o
t e e t   l o i ms i    y a i wa . e g n tca g rt  s u e  n t e lf  ft i  o n ,h   n   o o y a g rt m  h s  wo ag r h  n a d t n m c   y Th   e e i  lo ih i s d i  h  e to  h sp i t t e a tc ln   l o ih m   i  h   i h . mp r d wi   h   r d t n la g rt m  x e i n s t e e a g rt ms i h g l   fiin   n t e t e a d n t e rg t C o a e   t t e t a i o a  l o ih e p rme t , h s   lo ih  s ih y e f e ti   h   i   n   h i   c m

p e iin o h   lo i m ft ec aio .Th   r cso   ft eag rt o h  o l in h t eHAGA  su e    l n  n  fRo o p 2 Dr g nTe m nJa g S   wa  s di ci te do  b Cu   D  a o   a i in   u n e
Un v r iy Th   th r s l wa   n l z d s a itc l   y t e a ay i t o  o t r  ̄ S c e Do t ri   h n   ie st   i e s t . ema c   e u t s a a y e   t ts i l b  h   n l ss o l fwa e   a y   s o c r co   C i a Un v r i n y o   ce c   n   c n l g . e r s l s o  h tt e Dr g n Te m  a   v d n   d a t g     a y t c n l g   a a — fS in e a d Te h o o y Th   e u t h ws t a  h   a o   a h s e ie ta v n a e i m n  e h oo y p r me     n
tr. e s 

Ke wo d   Ag n   o l in, tc l n   l o ih , n t   l o i m , b   u   y rs e t c ai o An   o o y a g rt m Ge e i a g rt t c h Ro o c p

目前 在 MAS中 , 盟 生 成 的 基 本 理 论 是 N 人 合 作 对 策  联 理论 , S al 如 hpe y值 、 、 心 等 。S n h l 证 明 了有  个 A— 核 核 ad o m   g n 的 MAS系统 的联 盟 结 构 总 数 是 一 个 NP Had问 题 [ 。 et - r 】  ]

解 策 略 , 对 T P问 题 的 应 用 实 验 中 取 得 了 良好 效 果 , 策  在 S 该

略将遗传算 法设置 为运行 固定 的迭代次 数 , 有简单易行 的  具 优点 , 但这样容易造成 融合 时机过早或过晚 。文献[ ] 9将蚁 群  算法 与遗传算 法反复交 叉 , 利用蚁群算 法不断 生成种群个体 
进 行 同 步 时序 电 路 的初 始 化 , 种 优 化 方 法 能 够 尽 可 能 多 地   这

很多学 者根 据实际需 要 , 对这 个 N P问题进 行各 种算 法的探  讨, 研究 了各种实际条件限制下 的求解近似 的最优联盟 结构 。   文献 E] 2 研究在高层模 式下 执行任务 的 Ag n 的合 作行  et 为 , 出了一种基于市场 的传输协议 , 提 用于管理在群体 中各个  A et g n 的行 为以及紧 急情 况处 理 。文 献[ —] 出了一些 具  35 提 有 界限或任意 时间等条件下 的联盟生 成算法 , 根据实 际问题 
需 要 找 出近 似 解 , 率 较 高 。 效   近 年 来 很 多 学 者 不 再 满 足 于 求 得 联 盟 的近 似 解 , 始 研  开

初始化触发 器 , 但每 次种 群进 化都 要 经历 几代运 行 , 率较  效
低。   本 文 在上 述研 究 的 基 础 上 , 出 一 种 新 的基 于 混 合 蚁 群   提

遗传算法 的 Ag n 联盟求 解算法 , et 主要创新 之处为 :1 动态  () 实现蚁群算法 和遗传算 法的衔接 ;2 改进 了蚁群路 径选择规  ()
则和信息素更新规则 。  

究最优联盟 的求解 。郑 金华_ 等运用遗传算 法实现对 Agn  6 ] et 联盟的求解 , 求解精确 解效率较 高 ; 献E 3 出基于蚁群 算  文 7提 法的单任务 Agn 联盟求 解 , et 在时 间效率上 比较有 优势 。文  献E3 出了遗传算法 与蚁群算 法融合 的一般 性优化 问题求  8提
到稿 日期 :0 80 —3 2 0 —51 


1 联 盟 问题 的描 述 
定 义 1 设 一 个 MAS中 有 ,个 Ag n , MAS { , 2 et记 = A   Az … , } 向 量 B 一 (} 6 , , )  ≥ 0 1 ≤ , 1   , A  。 i 6,} …   ( , ≤  2 ≤ ,

本文受国家 自然科 学基金 ( 00 0 6资助 。 6 7 25 )  

 ̄ (9 6 ) 男 , 师 , 要研 究 方 向 为模 式 识 别 、 Ag n 理 论 与应 用 ,- i in jn us e u c ; 显 毅 (9 6 ) 男 , 授 , 士 生  17- , 讲 主 多 et E ma :l gu @ j. d .n 程 l a 15 - , 教 博

导 师 , 要 研 究 为模 式 识别 、 A et 论 与 应 用 。 主 多 gn 理  

≤r 表示 A e t 执行 某一 特定动 作 的能力 。Agn 完 成  ) g n  A  et

程 。G A在 自适应控制 、 组合优化 、 模式识 别 、 器学 习、 机 规划 

任务 t 所具有的能力 需求 表示为 E 一< , ,   ) 完成任        …, ,
务 获 得 的收 益 记 为 P() £。MAS中 的一 个 非 空 子 集 C称 为 一 

策略 、 信息处理等领域 的应用 中展示 了明显的优越性 。  
G A的主要优点是 :a具有领域 无关 的群体性全局搜 索  () 能力 , 可避免陷入局部最优 ;b 搜索使用评价函数启发 , () 过程  简单 ;c使用概率机制进 行迭代 , () 具有 随机性 ;d 可扩展 性  () 强, 易于介入到 已有模型中 , 且易于与其他优化技术结合。   GA 的主要缺点是 : a 没有 充分 利用 系统 反馈信 息 , () 使  搜索具 有盲 目性 ;b 算法求解到一定范 围时往往做大量冗余  ()

个 A et g n 联盟 , MAS的一个 完全划 分 C S称为该 MAS的一 
个联盟结构 。   定 义 2 设 联 盟 结 构 C 一 { 1 C , , } 联 盟 G    C , 2… G ,
k  

MAS UG =MAS G nC — D,, 12 … , ,   。 其  , ,  J i  一 , , k 且 ≠ 

中, 联盟 G 中 A e t g n 个数定义 为联盟 C 的大小 , 为 j j 记 G ,  

联盟结构 C k的大小为该联盟结 构 内含有 的联盟个 数 , 为  S 记
lS 1 是  C k一 。 定 义 3 设 所 有 大 小 为 k的 联 盟 结 构 的 集 合 为 L    一 { & }所 有 的 联 盟 结 构 为 L— U L , 向量   一 ( , , , c ,  k 记     …  
k一 1  

迭代 , 向最优解 收敛 的速度 大大 降低 , 导致 求最 优解效 率 较 
低。  

2 蚁群 算 法 (n oo yo t zt n A O ) ) a t ln pi ai , C   c mi o 意 大利 学 者 M   oio 1 9 首 次 提 出 了蚁 群 算 法 。 D r 在 9 2年 g   研究 表 明, 乎不具备视觉 的蚁群之所 以能够找到蚁巢到食  几

> 联盟 中所 有 Agn 能 力 向量 的 总 和 , 盟 C可 以完 成 任  是 et 联 务 t的必 要 条 件 是 V1   r6 6。   ≤ ,≤ I ≤ {   定 义 4 设 U( ) 联 盟 G 的 一 个 收 益 , 联 盟 结 构  G 为 则
k  

物 之间 的最短路 径 , 是靠其 在走过 的路 上释放一种挥发性分 
泌物 ( 即信息素 ,h rmo e来实现 的。后来的蚁群选 择该路  p eo n) 径 的概率与 当时这条路径上信息素 的强度成正 比。当某路径 

C k 总 收 益 可 以表 示 为  (   ) i∑U(  。 S的 C 一 - i c)   
定 义 5 设 在 A e t 盟 结 构 中 VG , J1 i ≤ ,   gn 联 C ,≤ ,   污

上 通过 的蚁群越 来越多时 , 在此路径 上留下的信息素也越来 
越强 , 使得后来的蚁群选 择此路径 的概率更高 , 而更增加 了  从 此路径上 的信息素强 度 , 吸引更多 的蚁群选 择此路径 。这  可 样就形成 了一种正 反馈 机制 , 使蚁 群最 终可 发现最 短路 径 。  
蚁 群 算 法 在 许 多 组 合 优 化 问 题 上 取 得 了 较 好 的 效 果 。如 

J 如 果 有 U( + C ) U( ) , G j≥ G +U( j , 称 联 盟 收 益 满 足 超  c)则 可 加 性 ; 果 有 U( +c ) U( ) 如 G j≤ G +U( ) 则 称 联 盟 收 益  G , 满足次可加性 。  

定义 6 设有 联盟 结构 C 一 {   C ,   }c     c , 2 …, ,  一 一 
{ 1 … ,   G , , I , J , , ) 每 个 C 可 以生 成  C , G一 , … C一 C  … G 。     k忌 1/ ( 一 )2个 C 1  一 。如 果 { l … , 1G , ,  1 C , c , G一 , … C , 汁1 


TS P问题 、 一次分配 问题和车 间作业调度问题等 。  

AC O的主要优 点是 :a具有 正反馈机制 , () 通过信息素 的 
不断更新 , 高效 收敛 到最 优解 ;b 具有通 用随机优 化特性并  () 在蚁群 中融人人类智 能 ;c是 一种分 布式优化 方法 , () 有利 于  并行计算 ;d 是一种全 局优化方 法 , 目标优化 和多 目标优  () 单
化 问题 均 可 求 解 。  



G } 由 {   C , , } 成 的 , 记 为 C 一 C 一 。 如  是 c , 2…   生 则       一 C z则 C — C  — ,     , 该 联 盟  则

果 有 C k C lC S — S— ,   生成满足传递性 。  

定 义 7 将   个 Agn 组 成 的 联盟 结 构 用 一 个  层 的联  et

AC O主要缺点 是 : 期信息素 缺乏 , 初 导致搜索 初期积 累  信息素 占用 的时 间较长 。  
2 2 算 法 改进  .

盟结构 图表示 , 中第 k层 是 L 其  中所有 的 Ag n 联 盟结构 。 et  

在相邻 的两层 , 一 1之 间, k 如果 c — c   &  , 在 c 与  则  
C   1 画一 条 线 。从 高 层 (   到 低 层 (   可 以看 成 是 联 盟  S一间 L) L)

1改进蚁群路径选择规则和信息素更新 规则  )
AC 的路 径 转 移 概 率 使 用 固定 的公 式 : O  

的合并过程 , 从低层 到高层可 以看成 是联盟 的分 解过程 。联 
盟 的 形 成 与 演 化 正 是 由联 盟 的 合并 与 分解 组 成 。   给 定所 有联 盟 G 的 收 益 , 盟 结 构 优 化 问 题 就 是 找 出 收  联

( 一l 删[ £ ] j U f{ ) ∑  (M    E   ) ,
0 oh r , t e 

f  

: ]    

(  1 )

益最大的 A et g n 结构 , 即最优联盟结 构 C  , C  ) r  S V( S 一ag mac∈ V( S 。联盟 G 的效用 U( 取决 于完 成任务所 获  xs   C) G) 得的利益以及联 盟中各成员完成任 务所 付出的代 价和其他 花 
费 , 表 示 为 : G ) P() 可 U( 一 £ 一F( ) C G ) 其 中 P() 示  G 一 ( , £表 完 成 任 务 t 获 得 的 利 益 , G ) 示 联 盟 G 中各 个 成 员 A_ 所 F( 表  

在算法运行初期 , 如果 问题 的规模较大 , 则蚁群很难在众  多路径 中找 出一条较 好的路径 。为了加快算法 的收敛 , 蚁群 

路 径选择 的概率值 应当取 比较大 的数 , 样较好的路径被选  这
择 的概率就较 高, 较优联盟 中的 Ag n 容易找 到。随着算法  et 的运行 , 正反馈的作用越来越明显 , 一些路径上的信息素 明显 

g n 完成任务 t et 所付 出的总代价 , G) 示联盟 G 求解 任  c( 表 务 t花 费的额 外开 销 , 如联 盟 中各 A e t 间 的通 信 开销 。 gn 之   由此 , et Ag n 联盟求 解 问题就转 换成 了优化 问题 。鉴 于进 化 

高于其 他路径 , 但这些路径 不一定是 最优 的, 因而容 易停滞 。  
为了缓 解正反馈过 程中容易 陷入局 部最优解 , 进化过程 中做 

算法在解决 优化问题 中的 良好表现 , 以本 文考虑使用遗 传  所
算法和蚁群算法 。  

了适 当改进 和调整 。这时 , 应该减少路径选择 的概率 , 使解 的  搜 索更 多样化 , 才有利于找到全局最优解 。因而 , 可设 第 k只 
蚂蚁在 节点 i 选择下一个节点 . ,的规则是 :  

2 I A算 法    t AG
2 1 相关算法简介  . 1 遗传 算法( e ei Aloi m,   ) G n t   g rh GA) c t
美 国 Mi ia 学 J Holn c g n大 h . l d教 授 于 1 7 a 95年 提 出 的 遗 


1gx ([ }i- f { £ 啦),fq a a ) (   o r [ ]   q  m 。  ̄
u U  E ‘  

J,

。h r t e 

其中 , 是 0 1中均匀分布的一个随机数 ,o q 到 q 是预先设 置的 

个阈值 ,o O 1 。J是服从概率 分布  () q ∈( , ) f的一个 随机  而且 , O采用信息素随时间挥发 的方程为 : AC  
矗 (+ 1 一 p ?n () △   ,£ )   £+ , () 3 

传算法 , 以达尔文 生物进化理论“ 适者生存 , 优胜劣汰” 和孟德  尔遗传变异理论“ 生物遗传进化 主要在染 色体上 , 子代是以父 
代遗传基 因在染色体上 的有序排列” 为基础 , 模拟生物进化过 
?

变量 。  

2 28 ?  

其 中信息素挥发 因子 为[ ,] 0 1 固定 常量 , 样在 算法 运 行初  这 期 , 息素 比较 小 , 信 挥发 因子相对 比较 大 , 这样 信息 素浓 度 比  较大 的边消逝得更快 , 易削弱它们的优势 , 成算 法行 进的  容 造

d 以概 率 P 选 择 两 个 个 体 进 行 交 叉 并 将 新 个 体 替  o{  

换原个体插入到种群 P t中;  () )
fri 1t o 一  oM / 变 异  /

速度慢 ; 而在算 法运 行后期 , 息素 比较 大 , 发 因子就 相对  信 挥
比较小 , 息素浓度 比较 大的边更容易保持其信息素 , 信 正反馈  的优势更 明显 , 法容易过早 收敛于非全局最优解 。为此 , 算 在  算法运行初期 , 当尽 量减 小挥 发 因子 , 应 采用 较小 的更 新 系 
数 ; 算 法 运行 后 期 , 当 尽 量 增 大 挥 发 因 子 , 用 较 大 的 更  在 应 采 新系数 。  

d 以概率 P o{  选择某个个体进行变 异并将新个体 替 
换 原 个 体 , 入 到 种 群 P t中 ;  插 () }
f ori 1 t 一   oM  

d   t 1 一 P( )  oP(+ ) t;

t t 1) — + ; 

se   i 是 拐 点 a dt T)生 成 中 间优 化 解 向量 X— P t 1 ; tp2 f ( n  ≤ (+ ) 

se   初始化 蚁群算法 ,—O tp3 t ;N=0  ; fr o 每条边 (,) i   j
() 4 

因此 , 信息 素更新规则 可以采用 :  


(+ 1 一l   , £ +  , f ) D? () △  

d {根据中间优化解向量 X得 到初始信 息素分布 T( ) 0 i t 并  j
△r = O )   ;  

其 中,1 p是挥发 因子 ,-O 9+ ; (- ) p . 1  A是信息素更新 系数 , =  


10 1 N 为蚁群算 法循 环的次数 。 . 0 ;   同时借 鉴 To sSuze提 出 的 MMAS ( xri n  ma  tt l ma- n a t a

se  设置当前尚未访问的 Agn 集合 J ={la , a )随机放  tp4 et k a ,2 …,  ,
置 m 只 蚂 蚁 到 n个 Ag n 上 ; et  
frk一 1t o    om 

sse 算法 的 思想 , 各 路 径 的 信 息素 大小 控 制 在 [ , ytm) 将    
] 之间 , 如式 ( ) 5 所示 , 这样 可以 比较 有效地 避免 算法早 熟 
问题 。  
rm ,  i  Zn ' i () f   ≤  n     () 5 

d 记第 k只 蚂 蚁 所 在 的 Ag n 为 a 并 将 a 从 J o{ et i i k中 删 

除, 计算初始联盟能力向量 B   ) c ; 
se   frk 1t tp5 o  一  om /路 径 选择   /
d   l( k< B【  owhi Bc e )

r (+ 1 一 r () i r ≤  ( ) ‰    £ )   £, f   ,   £ ≤

【 , i'f       fz )  ̄(≥ / l
开始 取 N一0 P . ,1 P 一 0 1 一 1 , 一0 9 ( 一 ) . , 。此 时 I D比较  

{ 据 式 ( ) 择 下一 个 Ag n j并 将 该 蚂 蚁 移 到 Ag n j  根 2选 et, et,

将 a从 J j k中删除 , 计算当前联盟能力向量  se   fr =1t  / 计算 当前最优联盟  tp6 o   om / k

;  )

大, 挥发因子( -p 比较小 , 息素更 新 系数  比较 小 , 1 ) 信 这样  既有利于信息素浓度大 的路径脱颖 而出 , 又能避免过早 收敛 。   随着算法 的运行 , 逐渐变小 , 1 p 逐渐变大 , 渐变  . D (- )  逐
大。  

d o{根据式 u C) () ( ) C C) ( i一P t一F Ci- ( I计算第 k只蚂 蚁所 
形 成 的联 盟 的 效 用 , 出 m 个 联 盟 中 效 用最 大 的联 盟 作  求 为 当前 找 到 的最 优 联 盟 ;  }

se  fr tp7 o 每条边 (,)/ 信息素的更新    i j /
d {根 据 公 式 Ar一  o  
△ . △r ; t和    )  


在算法运行后期 , 比较 小 , D . 挥发 因子 ( -p 比较 大 , 1 ) 信  息素更新 系数 比较大 , 能改善 GA和 A O后期算法 容易停  C 滞等缺点 , 加快算法收敛速度 。  

△  r (k/ :( k 计 算  r和△5 c)k u c )  u S =


fr 条 边 (,   o每 i) j

2 蚁群算法和遗传算法 的动态衔接  )
文献f O 提出的蚁群算法和遗传算法 的动态融合策 略方  -  ̄ l

d 根据式( ) o{ 4 计算 r (+1 ;   .t ) )  
se    t t 1; t p8 — + N— N+ 1;  

法是首先设置最小 遗传 迭代 次数 G nn 和 最大 遗传 迭代 次  ee   ̄
数 G nr ; ee. 然后 统计 遗传 算 法迭 代过 程 中子 代 群体 的进 化  a   率 , 以此设置 子代 群体 最小 进 化率 G no 最 后 , 并 ee ; 如果 在设  定的迭代 次数 范围 内, 连续 子代群 体的进 化率都 小于 C no  - e, e 则遗传算 法过 程结 束进 入蚂 蚁算 法 。这种 方法 的主要 缺点 
是 :) ee , n一 和 G no 容 易 预 先 设 定 或 设 定 不 够 准   aG n    P ee不

fr 条 边 (, r —O  o每 i )A   ; j d i( o{f N< N 并 且 算 法 无 停 滞 )    
( Se  ; 转 tp6 )  

es 出最优联盟及其效用值 , le输 终止程序 ; )  

3 算 法 分析 
3 1 复 杂 性 分 析  .

确, 仅凭经验或实验估计缺乏理论依据 .) b 未真正实现蚁群算  法和遗传算法 的动 态衔接 , 未体 现连接 的 自主性。本文 通过  分析 文献 [O , 1 ] 并在其 基础 上考 虑到遗 传算法 进化到 一定阶  段 以后 , 适应度变化缓慢 , 出采用样 条曲线对遗传算法的进  提 化曲线建模 , 通过发 现曲线 的拐点而 自动搜 索到动 态衔接 的 

HAG 的 运 行 时 间  A 表示 为  一 

G A主 要 由遗 传 算 法 运 行 时 间 

了 、   蚁群算法运行时 间  D和衔 接部 分运行 时 间 丁 J组 成 ,   +  ∞+丁 。HA J GA 中的遗传算法 与蚁 

群算 法过程采 用相 同的适 应值 计算规则 , 因此 可 以使用 一致 
的时 间值 T  表示这 两个算 法中计算 每个划 分方案 适应值 所 
需 的时 间 。下 面分 别 对 了 ,  和 T   了 J的大 小 进 行 分析 。  

最优位置 , 以实现蚁群算法和遗传算法的动态衔接 , 体现 了衔 
接 的 自主性 。由于篇幅原 因 , 这里不作介绍 。  
2 3 H A描 述  .   AG
s p 初始化遗传算法 , t  e0 随机生成初 始种群 P O , ; () t   一0
se   whl t T n tp1 i ≤ a d不是 拐 点 ) e(   d o{{ri  oM / 适 应 度 函 数  o 一1t /

1了 )  包括 遗传 算法初始设置时 间 了  … 、 终止条件判 断  时间 了   和种群进化迭代 时间。假设 遗传算法进化 了 
那 么种群迭代进化时 间就是 JA G ×N×  
一 "4 l TA +  × N× ( r I -t c 'i +   Gn   + 

代, 种群规模 为 ~; 种群 中每 个个 体完 成一 次遗 传操 作 的过 
程所 需的时间为 
( 十了     ) 。这 样 

d 计 算当前群体 P() o{ t每个 个 体 C 的适 应度 函数 f i  
( )} G ; 

fri 1t o =  oM /选 择   /

了  

) 而7 A + 了 ,  _ m  

远 小 于 I ×N× ( r 了 p 。     +  。)  、 止条 件判  终

d 根据 当前种群 P t的每个个体适应度函数 fC)  o( () (  ) 选择生成 中间群体 ;  )
fri 1t 0 =  oM / 交 叉  /

因此  

≈  ×N X( r T a )    + c  。

2  ∞包括蚁 群算 法初始设置 时 间  )

断时 间 了 一 和蚁 群 算 法 迭代 时 间。假设 蚁 群 算 法 迭代   
?

22 ? 9  

仞 次 。每次迭代中使 用 m只蚂蚁 , 每只蚂蚁完成一 次任务 图  着色的时间 为  m  那 么蚁 群算法 的迭代 时 间就是 
x(  丁
mX(  

通过分析 , 我们认 为 主要原 因是 S HA能够 形成 的联盟 比较 

× 
×  

少, 有些任务不 能完 成 , 以系统 总收益也较 少。当然 , 所 我们 
还要考虑到 , 因为没有进行模拟真实 的分布式计算 , 运行时 问  不一定准确 , 以只能作参考 。但 HAG 所 A能够形成更多的联  盟, 能够完成更多的任 务 , 以运行 时间长一些 , 所 系统 总收益  也必然较大 。从表 1可以看出 , 不论 一1 0还是 2 , HA 的  OS
系 统 总 收 益 均 比 HA GA 系 统 总 收 益 小 得 多 。  

+  ) 。这 样 , ∞ 一 了 m + 了 一 +       

+ 丁, , r) 而  m  + 了 一   小 于 I × m ×   远    

( 蝣 砷+  r 。因 此 , ∞≈ ∞ ×m X( n   )     砷+  r 。 ) 

3 丁 包括 构造优 化解 集合 所需 的时 间 T )』  

和计 算信 

息素初始所需 的时 间 T  。 由于采用样 条 曲线拟 合遗 传算  法进 化曲线 , 涉及 大量 的数据 运算 , 以 丁一 的时 间有  不 所 J  

接着对 HA GA, L 和 A 0[ GA 5 ] C  求解 A e t g n 联盟 问题 的 

限。假设任务 图节 点数 为 K, 数为 H, 次计算 一条 边上  边 每 的信 息素值 的时间 为 7_ 那 么 , 息素初 值计算 时 间  却 1 J 砷, 信  
就是 J ×HX  印。这样 7 ≈NxHx p  、 , " 1   。 由上 述分 析 可 知 ,   ≈  ×N× ( ,   +  ) +  ×mX( m。+ T, + N×H× 丁_ 我 们还 发现  r   p f ) 『     的复杂度为 0( K×H)远 大 于  a , m 以及 N ×H× , 却   
T, J 砷。因 此 可 以 简 化 得 丁 A Ⅲ6 ≈  × N × r k D× ×   +    
f (G 一 JA×N+ I0 ^D×m) ×T4。  

比较 。实验参数 :  =3 , 用 3 o采 0个 Agn , 传 编码位 数为  e t遗
3 O位 , 遗传算法 种群规模 取 为 5 , O 遗传 迭代次 数为 3 , 叉  O交 概率 P —O8 变异概率  —O 0 。蚁群算 法  一2口=3  c ., .5 , ,
I 09 D .  一 ,一 1 0 1 li 1 , 一 3 , ra= 60 迭    . 0 ,m = 0  "  0 取 mx 0 ,

代次数为 2 。图 1 O 显示 了这 3 算法 的优化解 进化 曲线 , 种 结  果显示 HAGA在解 的精度和 时间上 , 都明显优 于 G AC A, O  两种算法 。图 2中 X轴对应 每层 Agn 联盟 的结 构 图, et Y轴  是需要搜索的联盟结构数。在 x 从 2 轴 0到 1的变化过程 中 ,   开始时 , gn 联盟 结构 中具有 同构关 系的 A et A et g n 联盟结 构  较少 , 因此 , HAG A算法 与其他两个算 法相差不大 , 是在变  但
化 到 3到 7层 时 , 一 层 的 Agn 联 盟 结 构 中 , 有 同构 关 系  每 et 具 的 Ag n 联 盟 结 构 非 常 多 , 此 , GA 经 过 挥 发 因 子 ( 一  et 因 HA 1

在运行过程 中遗传算法部分所需 的存储空间约为 2 ×NX 
0( , K)蚁群算法部分所 需 的存储 空间约 为 m×O ( K+H)  ,

算法衔接 部 分 构 造 优 化 解 集 合 所 需 的存 储 空 间为 . 0  Nx 
( 。当然不 同的程 序实现对算法运算 时间与存储 空间也有  K)


定 的影 响 。  

32 运 行 效 率 分 析  .

p 抑制 以后 , ) 可以显著减少需要搜索 的 Ag n 联盟结构个数 。 et  
这 说 明 HAG 能 较 高 效 地 找 到 Agn 联 盟 的 优 化 解 , 多  A et 是

上述 复杂性分析 表明 , HAG 的运行 时间 . AA A I G 主要取  、 H 决 于 JA G ×N+ I∞×m与 T 的乘积 。其 中, r ^ r   是对某个划  分解进行评价所需 的时间 , 与所用 的优化算 法无关 。对 于特  定 的组合优化 问题 , ,   本质上是评价问题空间 中一个 解所需  的时 间。因此 HAG A效率改进 的关键在于最小化 J  ×N+ 

Agn 联盟合作求解的一种很有效 方法 。 et  

/ ×m, 中 N, A m 其 m是控制参数 , 分别表示遗传算法 的种群规  模 和蚁群算法 的蚂 蚁数 , 一般是预 先设 定 的固定值 。当遗传  算法迭代次数 I  为 0时 , HAG A就退化为蚁群算法 ; 当蚁群 
算法 迭代次数 蜘 为 0时 , HAG A则退化为遗传算法 。  
图 1 最优进化曲线 比较  图2  Agn 联盟结构 图和需要  et 搜索的结构数 比较 

4 实验结 果及分 析 
实验 中主要采用 的是 集 中式 计算 , 没有模拟 真实 的分布  式计算 , 中在一起计算所有潜在联盟 的联盟值 , 集 并不影响系  统总收益 的值 , 但会对算 法执行 的时间和通信复 杂度造成一 
定 的影 响 。  

最后将 HAG 应用 于 R b C p仿 真 比赛客 户 端程 序  A oo u
中。实验使用 3台机 器 , 台机器 用于 运行 S ce; re 和  一 o crevr S Mo i r另外两 台机 器分别 运行 在 L n x下 , nt , o iu 对应 的球 队分 

首先对 S e oy等人 的算 法口 ( hh r j 简记 为 S HA) HAGA 和   两种算法 的系统 总收益进行 比较 , 以检验这两种算 法的优劣 ,  
结 果 如 表 1 列 , 中 : C ) 示 总 收 益 , SA 示 S 所 其 V( S 表 TH 表 HA 运 

别为江苏大学龙队( HAGA算 法 的程 序 ) 含 和江苏大 学超新  星队 ( 曾获得 2 0 , 0 5年全 国机 器 人足 球赛 二等 奖 , 等  0420 三
奖) 。Ro o u b C p仿真 比赛在 6 0 0 0*1 个 仿真周 期 中进 行 , O 然 

行时间 ,  

表示 HA GA运行时间 。实验部分参 数为 : o N.  

后使用 中 国科 技 大学 比赛 分 析工 具 软 件 S eeD co ( t oer otr h—  
t :/oo u . i SCe L c/i p /rb c p a U t.dL n s .   m/tosS ceD eo.x )  ol/ ocr otre e ,

1n 0 m一4 Agn 个 数 1 ; . : : —l , , et 0 No 2 一2 , 一8 A e t   O  , gn 个

数 2; 0 能力 r 均为 1 ; 0 联盟大小 k ; =3 算法各运行 5 。 次 
表 1 S   HA和 HA GA两种联盟形成机制 的结果对 比 
第一次  
S HA  V( S C )
2  9 9   2  0 1  9 1  3

对 比赛结果进行了统计 分析 , 如表 2 列。结果显示 前者 面  所
对 超 新 星 队 时 , 论 在 S o t ucs 还 是 在 De n i -u  无 h o~ ces S f s eS - e v

ces cs 等重要方面均 占有 明显优势 。  
表 2 实验统计数据 

第二次 
HAGA  S HA  HAGA 

TS A  V( ) TH G   V( ) TS h H CS A A CS H  V( S TH G   C ) A A
0 7  . 1 08  .2 07  .2 0 7  . 1 08  . 9 6  6 17 2  5  7 14 0  9  8 1 1  .7 l 3  _9 l2  _7 1 2  .2 l 2  。9 16 0  8  3 6  9 6  6 8  9 1. 0 6 0  1. 7 6 4  1. 3 4 8  1. 3 5 4  1. 3 6 3 

从 运 行 时 间 上 看 , HA 时 问 很 短 约 为 HAG 的 一 半 。 S A  
?

20 ? 3  

结束语

本 文 的 创 新 之 处 是 提 出 了 HA GA 来 求 解 A—  

Co l i n a i o  Fo ma i t r t on:I v s i a i g n e tg t  M a ke — a e  Co p r tv   n r tB s d o ea ie

g n 联盟 问题 , et 该算法融合并 改进 了遗传算 法 和蚁群算 法两 
种仿生算法 , 实现 了对这两 种算法 的动态衔接 。HAG 在遗  A 传算法运行 过程 中加 入 了子代优 化解改进 效率检测 机制 , 使  得当遗传算法对优化解改进 效率 降低到一 定程度 时 ( 即进 化  拟合曲线拐点处) 自动终 止遗 传过 程 , 而避 免  , 从 无谓 的  增长 。并且 把优 化解 转换 为较为准确的初始信息素开始蚁群  算法 的执行 , 使蚁 群算法大 大降低 了用 于形成 最优解上 信息  素所需的迭代次数 。这样利 用蚁 群算法正 反馈 、 高效 收敛 的  优势 , 以在  可
G 通 过 抑 制  A

P o lm}I E   o ue oit  rbe fE E C mp trS c yAAMAS 0 .uy2 0  5—   e  4 J l 0 4 5 6 
5 3 6 

[ ] S n h l     , asn A dr o   R e a A yi e o l  3 a d om T W L r   n e s n o K, s M  ,t 1 n t   a —  . m c i
t nsrcueg n rt nwi   rtcs  urnes f rce  i  tut r e eai   t wos aeg aa te   o e- o o h   fP
dn so h   5h Na in l o frnc  n AriiilI tli n e ig   ft e 1 t   to a  ne e eo   t ca  n el c f ge c .   M e l  a k, no P r AAAI e s 1 9 4 — 4 Pr s ,  8: 6 5   9

E 3 S e oyO. a s Meh d  rakalct nva e t o l  4  h h r  Kru  S  to so  s l ai  iAg n  ai f t o o   e —
to  o a i n Ar iii lI e l e c , 9 8, 0 (   : 6 — 0   i n f r to . tfca  nt l g n e 1 9 1 1 1 2) 1 5 2 0 m i

[ 3 Jn ig    D n   n  n rt nc aio  tutrs t — 5  e nn s R。 a gV  Ge eai   linsrcue  hf  N o o t wi i nt  o n  rm  pi 1g aa te ∥ P o. fteAAMAS i b u d fo o t   u rnes e ma rc o  h   
2 0 2: 7 — 9 0 4, 5 2 57  

很小的情况下迅速找到最优解 。因此 ,   HA—
与 们 无 谓 的增 长 , 而 最 小 化  从 × N+ 

×m来达到 提高搜 索效 率 的 目的。通 过 对 HAGA复杂 
性 分析 和运 行 效 率分 析 进 一 步 说 明 了 HAG 在 Ag n 联 盟  A et 求 解 问题 上 的 优 势 。 对 比实 验 以 及 HAGA 在 R b C p中 的  oo u

[ ] Z e gJnh a C e  h nzo , a i ig Mut A etC ai 6 h n  i-u , h nZ e —h u C i — n . l— g n  ol  Zx i —
t n Fo ma i n B s d o   ne i  g rt m s o p t r En — i   r to   a e   n Ge tc Al o ih .C m u e   gi o  

n e ig& S i c . 0 4 6   er n ce e 2 0 ( ) n

应 用也都表 明 HAG 在联 盟求 解 问题 上取 得较 满 意效 果 。 A  
值 得 一 提 的是 本 文 得 到 的是 一 种 通 用 的 联 盟 算 法 , 以 通 过  可

[ ] Xi Na J n  i g o we Xig e 1Sac igfr e t a  7 a ,i gJa u , i n ,ta. erhn     n  —   a n   oA g O C
l in f rSn eTa k Usn  m p o e   i o  o   igl  s   ig I r v d AntC o y Alo ih   t   oln   g rtm .

参数变化适应不 同的联盟 对象 ( 比如企业 动态联 盟 中供 应商  选择联盟与零售商选择联盟有很 大的不 同) 从而充分体现 出 ,  
具 体 Ag n 联 盟 的 特 点 ; 二 , 条 逼 近 曲 线 需 要 大 量 的 计 算  et 第 样

J r a  fCo p trRe e r h a   v lp e , 0 5, 2( : ou n lo  m u e  sa c   nd De eo m nt 2 0 4 5) 
7 47 9 3 —3 

[ ] DigJL, h nZQ, a   .  h o iaino e eia— 8 n   C e   Yu nZz Ontecmbn t  f n t  l   o g c  
g r h a d a t a o i m J u n lo  mp tr R s a c   n   o i m  n   n   l r h . o r a  fCo u e  e e r h a d t g t
De e o me t 2 03, ( ): 3 1 1 5   v lp n , 0 40 9 1 5 - 3 6

时间, 将降低遗传算 法的效率 , 必 实验 中我们 改进了样条逼近  曲线方法 , 由于篇 幅原 因不 作介绍 ; 三 , 们多 次实验证 明  第 我 了得 出的曲线拐点 就是最佳 的两种算法 的交接点 , 缺乏理  但
论依据 。  

[ ] L  ,    ,   e a.nt lainfr y c rn u eu n  9 i XuC P MoW,t 1Iiai t     n ho o ssq e— Z   iz o os
t lc c i   a e  n a t ag r h i   i ut b s d o   n  lo t m&g n t   lo i m.Aca a r s i e e i a rt c g h t 
Elcr nc Si c , 0 e to ia nia 2 03, 1 8): 2 6 1 8   3( 1 7—2 0

参 考 文 献 
[ ] 程显毅. g n 计算 E ] 哈尔滨 : 1 A et M- . 黑龙江科学技术出版社 ,0 3 2 0  E ] C rf t  , i e  B s m i   . g n H t o e e ya d 2 o n r D K r yM, os a r A e t ee gn i     oh l o eT   r t n

[ O in  h — u , ii k n C e J— u .Had r / f r  1 ]Xo gZ ih i L S — u g, h n ih a rwae S t e o wa
P r ii n n   s d n a tto i g Ba e  o  Dy a c Co b n to   f Ge e i n mi  m i a i n o   n t  Al o   c g—

r h a d An  g r h J u n lo  f r , 0 5 1 ( )  i m  n   t Alo i m o r a  f S t e 2 0 , 6 4 : t t. o wa
5 3 5]   0 — 2

( 接 第 2 7页) 上 1  

[ ] Xin   LuL P e  r s:u p rigrp tt nb sdtu tn 3 o gL, i . erT u tS p ot  euai - ae rs    n o i
p e -c p e  c m mu ii s I e rt  ̄ e r o n te . EEE Tr n a to s n a s c i n  o  Da a nd t  a   Kn wl d e En i e r n S e ilI s e o   e -o Pe rB s d Da   o e g   g n e i g, p ca  s u   n Pe r t - e   e   — a

lr 0 95 ; a 为 . 0 0 当要 求 服 务 下 载 a c 信 息 时 , er ,类 pe1与 B 的 

内容相似度 Smi r为 0 7 2 ; i l a . 5 5 当要 求服 务下载 d f类 信息  , 时 ,er B 的内容相似度 S mi r为 0 9 2 ; p e1与 i l a . 5 4 同一节 点 B   由于要求服 务 的 内容不 同与节 点 pel的 内容相 似 度也 不  er 同, 内容相似度的大小直接影响到推荐节点推荐值 。  
通 过 以上 关 于 节 点 间 内容 相 似 度 的 分析 , 用 式 () 式  应 5和

t   a g m e , 0 4, 6 ( ): 4 — 7 aM na e nt2 0 1 7 8 385 

[] Ab u — a ma  , l s .A i r ue   ut d l/P o— 4 d l R h nA Hal   eS ds i tdt smoe / r   tb r  
c e i g   ft e Ne Se u t  rdg s W o ks o 9 .Cu — ed n so  h   w  c r y Pa a im   i r h p’ 7 e r  
b i , K , 9 7: 8 6   r a U  1 9 4 — 0

[ ] Ab u— h nA, i s S p o t g t s i vrul O l U  5 d l ma  Hal   u p rn  r t n i a CII — Ra e S  i u     t   Tn nt sf rceig f h 3dHa iItmain   o frn e ie {P oe n so  e3 r  waine t a C neec  i   d t   o
o   s e S inc s M a i H a i, 0 0: -   n Sy t m  e e . C u , wa i 2 0 4 7

() 6计算 pe2的全局 信 任 值 。当需 要 下 载 d, er f类 信 息 时 
p e2 er 全局信任值 为 0 4 1 , . 2 2 如果不考虑部分相似度 p e2的  er

全局信任值仅为 0 3 7 ; 易结束后 pel 改 B, . 3 6交 er 修 c的推 荐  可信值 ( c , P,) 同时根 据文 献 [o pe2对 pel所提 供 的服  1 ] er er 务做出评价 。  
结束语 本 文 在 已 有 P P模 型 的 基 础 上 提 出 了基 于 内  2

[ ] B t  B rh rigM , e l Vau t no  utno e e— 6  ehT,oc edn   Kli   n R  lai  fr s i pnn t o t    

wok/ rc o h  rpa   y   n R sac n S cr y r /P o. fteEuo en S mp o  eerh i e u t    i
( 0RI ES CS). ri S ig rVe lg, 9 4:3 1   Be l n: prn e  ra 1 9 1 — 8

【  Ga et  Trs. fr , l k l,9 0 7f   mb t n  u tOxod Ba wel1 9  a e

容相似度和推 荐反 馈计 算节 点 推荐值 的对等 网络 信用 模 型  IB 。通过计算该节点 问 的 内容 相 似度 来评 价 节点 提供 推  PS
荐 服 务 的 能 力 , 点 问 相 似 度 是 根 据 每 次 交 易 的 内 容 不 同改  节

[ 3 Z n   XigC X, h uLZ Smi r yme sr n   sa c e  8  e gC. n    Z o   . i l i   aueadi tnes— at n l t n frcl b rt eftr g a k n iP。 n sy G, t e i  o  ol oai  ie n ?B o y co a v li   He ce   e 
a., d . o . ft e 1 t n ’  o l  ie W e   n.( w w   1 e s Pr c o h   2h I t lW rd W d   b Co f W 2 3 . w  r ACM   es 2 0 6 26 8 00 ) Ne Yo k: Pr s , 0 3: 5 — 5  

变节点 的相似度值 ;P S通过历史交易 时间权值来调 整相应  IB 的推荐值 , 根据交互的结果对推荐者 的推荐分配不 同的权 重 ,   基于上述 3 方面 的考虑可 以加强模 型的动态适应 能力 和搜索  服务的效率 。  

[ ] 陈颖熙 , 9 李贤有. 基于 内容相似度的对等网络信用模 型研究 []  J.

计算机科学 ,0 7 3 ( ) 2 0 ,4 8  
[ 0 B b aR B Esh n u r Gl o  e 1B osrp igscr y 1- o b    , c ea e  ] L, i r g V,t . o tta pn   u i   a e t ascain  r o t gi  bl a  o ewok  Prc I E   soit sf   ui   mo i dh en t rs} o .E E o or n n e
GL0BEC0^LS n Fr n ic CA , c 2 0 1 1 — 51  , a   a cs o,   e D . 0 3: 5 1 1 5

参 考 文 献 
[ ] S a   . vrd y e ed b i   r vrd y ed ∥ S p l — 1 h w M E e a   p n a i y o  ey a  es y d l f e t n u pe 
me tl o edn so h  3 hItr ain  y o im nS f r  na  c eig  f e1 t n en t a S mp su o   t e Pr t ol o wa Reibly E iern . EE C mp trS cey 2 0 7 1  l it  n n ei I E  o ue  oit , 0 2:-  a i g g 1

[ 1 h n   n XuF n , n   a ,ta. S ma t  n   i   1 ]Z a gLi,   e g Wa gYu n e 1A  e ni ad Tme c
Reae  eo ltd R cmmed t nF eb c  u tMo e ∥ S en  n  n ai —ed ad Trs  d l eo d I— o
t r a i n lC n e e e o   a l b l y e n t a  o o f r nc   n Av i i t .Re i b lt   nd Se u t   a i l i y a   c ry a i

( ARE ’7 E S 0 )IEE 0 07 9—7 520   0 7 —6 52 7 —/ 7

[3 Se h n F r a s   ut s   m uai a cne tP .   2  t e  om li t s a  c p t o l o cp. h n p M  in r   a o g tn 
ds et t n Unv riyo   il g, ota d, 9 4 isra i. o ie st  fStri s ln 1 9   n c

[ 2 石志国 , 1- ] 贺也平 , 张宏. 一种对等计 算安全性 的时间 自衰减信 任  
管理算法[] 计算机研究与发展 ,0 7 11  J. 2 0 :-0
?

2 31 ?  


相关文章:
更多相关标签: