[ 4]
( 超加性是指
C 1 , C 2 !N , C 1 ( C 2 =
, 有 V( C 1 ) C 2 ) ∃V ( C 1 ) + V( C 2 ) ) , 在这样的环
境中 , 最大的联盟将是最有益的. 定义系统联盟 集 C = { C 1 , C 2 , !, C m } , 且 C 1 ) C 2 ) ! ) C m ! N , 系 统总 收益 定义为 : V( C ) =
一个特征函数 V ( Ck ) 给出 . 我们假定 V ( C k ) ∃0, V( C k ) = P ( tk ) - F ( C k ) - C ( C k ) . 式中 P ( tk ) 指完成任务 t k 所获得的利益, F ( Ck ) 指联盟成员总能力折合的成本, C ( C k ) 指联盟协作求解 t k 过程中的额外开销, 主 要指通信开销. 如果联盟 C k 不满足上述必要条件 , 则 V ( C k ) 为 0, 否则 V ( C k ) 为正数. ( 2) 在非超加性环境 中研究联盟生成
第1期
基于维数划分策略和免 疫的多任务联盟并行生成算法
119
已有文献的基础上, 设计了一种基于维数划分策略和免疫的多任务联盟并行生成算法, 试图在最小的约束 条件和计算代价下实现一个 Agent 可以同时加入多个联盟, 以减小 Agent 能力的浪费, 增加系统总收益 .
2
问题描述与分析
当多 Agent 系统同时存在多个待求解的任务时 , 需要针对每个任务同时生成相应的联盟予以求解, 这 类问题称为多任务联盟的并行生成问题 . 在 Agent 资源和能力非常强的环境中, 如果一个 Agent 只能加入 一个联盟, 势必造成很大的浪费 , 这就迫切需要一个 Agent 能加入到多个联盟中, 并同时参与多项任务的 求解 , 从而获得更高的系统总收益 . 设在 MAS 中, 存在备选 Agent 集 N = { A 1 , A 2 , !, A n } , 任意 A i ( i = 1, 2, !, n ) 都具有一个 r 维的能力 向量, B i = ∀b i , b i , !, bi #, bi ∃0( j = 1, 2, !, r ) , 用于定量描述 A i 执行某种特定动作的能力大小 . 设待求
1 2 r
&B
j
j i
, 其中 B i = ∀b i , 0, !, 0#, B i =
1 1 2
120
2 r r
系统工程理论与实践
j j
2008 年 1 月
j
∀0, b i , 0, !, 0#, !, Bi = ∀0, 0, !, 0, b i #. 我们把能力 B i = ∀0, !, 0, b i , 0, !, 0#赋给虚拟 Agent A i , 这时称 Ai 为 Ai 的子 Agent, Ai 为 Ai 的父 Agent. 因此, 具有 r 维能力的 Agent 可以包含 r 个子 Agent . 在求解多任务联盟的并行生成问题时, 子 Agent 将代替父 Agent 参加联盟 . 对于 A i , 每个子 Agent 最多 可以参加一个联盟, 则 A i 最多将能加入到 r 个任务联盟中. 可能的系统联盟总数与 Agent 数目、 维数 r 以 及待求解任务的数目 m 成指数关系 . 为了得到一个满意的结果, 必须考虑大部分的联盟组合, 因而多任务 联盟并行生成问题是一个复杂的组合优化问题.
收稿日期 : 2006 10 12 资助项目 : 国家自然科学基金 ( 60474035) ; 国家教育部 博士点基金 ( 20060359004) ; 安徽省自然科学基金 ( 070412035) 作者简介 : 苏兆品 ( 1983- ) , 女 , 博士研究生 , 主要研究 方向为 智能控 制、 进 化计算、 Agent 理论 ; 蒋 建国 ( 1955- ) , 男 , 教 授 , 博士生导师 , 主要研究领域为分布式智能控制系统 , 数字图像分 析与处理 , DSP 技术 与应用 ; 夏娜 ( 1979- ) , 男 , 副教 授 , 博士 , 主要研究领域为分布式人工智能、 智能控制、 计算 智能 ; 张国富 ( 1979- ) , 男 , 博士研究生 , 主要研究方向为分布式人工 智能、 不确定系统、 进化计算 .
2008 年 1 月
系统工程理论与实践
第1期
文章编号 : 1000 6788( 2008) 01 0118 06
基于维数划分策略和免疫的多任务联盟并行生成算法
苏兆品
1, 2, ຫໍສະໝຸດ 建国1, 2,夏娜
1, 2
, 张国富
1, 2
( 1 合肥工业大学 计算机与信息学院 ; 2 安全关键工业测控技术教育部工程研究中心 , 合肥 230009) 摘要 : 设计了一种基于维数的 Agent 能力划 分策略 , 提出 子 Agent 概 念 ; 在此基 础上设计 了一种 基于 三维二进制编码的免疫算法求解多任务联盟并行生成问题 , 并对疫苗采取了自 适应提取 的策略 . 实验结 果证明了该算法的有效性 . 关键词 : 并行生成 ; 维数划分策略 ; 子 Agent; 免疫算 法 ; 三维二进制编码 中图分类号 : TP18 文献标志码 : A
[ 8] [ 9] [ 2] [3] [ 4] [ 5] [ 6] [ 7] [ 1]
的工作具有代表性 ,
主要解决了单任务联盟的生成 . 蒋建国 提出基于改进型蚁群算法求解多任务联盟的串行生成, 可按任务 优先级依次为每个任务生成求解联盟; 骆正虎 提出了一种基于遗传算法的多任务联盟的并行生成算法 , 并设计了相应的交叉和变异算子. 但上述研究都只允许一个 Agent 参加一个联盟, 在许多场合不能满足实 际应用系统的需要, 可能造成 Agent 能力的极大浪费 , 从而在一定程度上降低了系统总收益 , 本文在参考
1 2
bC k #, B C k 是联盟中所有 Agent 能力向量的总和 , 即 B C k =
r
A % C
i
&B
k
i
. 联盟 C k 可以完成任务 tk 的必要条件是 :
i = 1, 2, !, r , b tk ∋ b C k .
i i
我们作以下假设 : ( 1) 和惯例一样
[ 1~ 4]
, 在特征函数对策 ( CFGs) 中研究联盟形成. 每个联盟 C k 的值用
图 1 多任务 联盟并行生成问题
3
基于维数的 Agent 能力划分策略
在 MAS 中 , 每个 Agent 之间都存在彼此合作形成联盟的可能, 可能的联盟总数同 Agent 数目成指数关 系; 而且每个 Agent 都有加入多个任务的可能, 如果能力无限可分 , 则其可能的联盟将是无穷多个 , 多任务 联盟的并行生成问题将是一个无法求解的组合优化问题. 因此, 国内外的学者都是以一个 Agent 只能加入 一个联盟为前提 , 对任务联盟进行求解. 为了使多任务联盟的并行生成问题可以求解, 而又能实现一个 Agent 加入到多个任务联盟中的目标, 本文设计了一种基于维数的 Agent 能力划分策略, 并提出 子 Agent 的概念来求解多任务联盟的并行生成问题. 由第 2 节可知 , 对具有 r 维能力的 Agent A i , 其能力可以用向量 B i 表示为 : B i = ∀b i , b i , !, bi #; 由线 性代数知识可知 , 向量 B i 可以表示为 r 个正交向量的和 , 即 : B i =
&V( C )
k k
=
& [P( t ) k k
F ( Ck ) - C ( C k ) ] .
A1 t1 t2 t3 ! tm 1 0 0 ! 1 A2 0 1 0 ! 1 A3 1 0 1 ! 1 ! ! ! ! ! ! An 1 0 1 ! 0
多任务联盟并行生成问题就是面向任务集合 T = { t 1 , t 2 , !, tm } , 在 Agent 集合 N 中为每个任务 tk 生成 最优求解联盟 C k , 使系统总收益 V( C ) 最大 ; 且允许一 个 Agent 参加多个联盟而参与多项任务的求解( 如图 1 所示) , 比如对于 Agent A 2 可以同时参与任务 t 2 与 tm 的求解.
Multi task coalition parallel generation algorithm based on dimension partition strategy and immunity
SU Zhao pin , JIANG Jian guo , XIA Na , ZHANG Guo fu
1, 2 1, 2 1, 2 1, 2
( 1 Department of Computer and Information Science, Hefei University of Technology, Hefei 230009, China; 2 Engineering Research Center of Safety Critical Industrial Measurement and Control T echnology, Ministry of Education, Hefei 230009, China) Abstract: Coalition generation, especially multi task coalition parallel generation, is a key topic in Multi Agent System. It mainly researches how to generate several optimal task oriented coalitions parallel in dynamic manner. But existing researches are restricted in the condition that multi task coalitions are generated serially and each Agent can only take part in a coalition. To solve the problem, an ability partition strategy based on dimension and a novel Child Agent are proposed to ensure that an agent can take part in several different coalitions synchronously. A novel three dimensional binary encoding approach is designed to solve coalition parallel generation based on Immune Algorithm. And a novel method of vaccine adaptive obtaining is used to improve the searching effect of the Immune Algorithm. The experimental results show that the proposed algorithm is effective and can obtain a reasonable solution in an acceptable time. Key words : parallel generation; dimension partition strategy; child Agent; immune algorithm; three dimensional binary encoding