系统工程理论与实践.pdf

《系统工程理论与实践.pdf》由会员分享，可在线阅读，更多相关《系统工程理论与实践.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、?2008年 1 月系统工程理论与实践第 1 期?文章编号:1000?6788(2008)01?0118?06基于维数划分策略和免疫的多任务联盟并行生成算法苏兆品1,2,蒋建国1,2,夏?娜1,2,张国富1,2(1?合肥工业大学 计算机与信息学院;2?安全关键工业测控技术教育部工程研究中心,合肥 230009)摘要:?设计了一种基于维数的 Agent 能力划分策略,提出?子 Agent 概念;在此基础上设计了一种基于三维二进制编码的免疫算法求解多任务联盟并行生成问题,并对疫苗采取了自适应提取的策略.实验结果证明了该算法的有效性.关键词:?并行生成;维数划分策略;子 Agent;免疫算法;三维二

2、进制编码中图分类号:?TP18?文献标志码:?A?Multi?task coalition parallel generation algorithm basedon dimension partition strategy and immunitySU Zhao?pin1,2,JIANG Jian?guo1,2,XIA Na1,2,ZHANG Guo?fu1,2(1?Department of Computer and Information Science,Hefei University of Technology,Hefei 230009,China;2?Engineering Res

3、earchCenter of Safety Critical Industrial Measurement and ControlTechnology,Ministry of Education,Hefei 230009,China)Abstract:?Coalition generation,especially multi?task coalition parallel generation,is a key topic in Multi?AgentSystem.It mainly researches how to generate several optimal task?orient

4、ed coalitions parallel in dynamic manner.Butexisting researches are restricted in the condition that multi?task coalitions are generated serially and each Agent canonly take part in a coalition.To solve the problem,an ability partition strategy based on dimension and a novel ChildAgent are proposed

5、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

6、 of the Immune Algorithm.The experimental results show that the proposed algorithm is effective and can obtain a reasonable solution in anacceptable time.Key words:?parallel generation;dimension partition strategy;child Agent;immune algorithm;three?dimensionalbinary encoding收稿日期:2006?10?12资助项目:国家自然科

7、学基金(60474035);国家教育部博士点基金(20060359004);安徽省自然科学基金(070412035)?作者简介:苏兆品(1983-),女,博士研究生,主要研究方向为智能控制、进化计算、Agent 理论;蒋建国(1955-),男,教授,博士生导师,主要研究领域为分布式智能控制系统,数字图像分析与处理,DSP 技术与应用;夏娜(1979-),男,副教授,博士,主要研究领域为分布式人工智能、智能控制、计算智能;张国富(1979-),男,博士研究生,主要研究方向为分布式人工智能、不确定系统、进化计算.1?引言Agent 间通过组成联盟可以提高求解问题的能力,获得更多的效益,因此联盟是多

8、Agent 系统(MAS)的重要合作方式.自 1993 年提出联盟方法以来,联盟生成已成为多Agent 系统研究的一个重要方面并取得了一定的进展 1.国外学者 Shehory 2、Zlotkin3、Sandholm 4以及国内学者徐晋晖 5、罗翊 6、夏娜 7的工作具有代表性,主要解决了单任务联盟的生成.蒋建国 8提出基于改进型蚁群算法求解多任务联盟的串行生成,可按任务优先级依次为每个任务生成求解联盟;骆正虎 9提出了一种基于遗传算法的多任务联盟的并行生成算法,并设计了相应的交叉和变异算子.但上述研究都只允许一个 Agent 参加一个联盟,在许多场合不能满足实际应用系统的需要,可能造成Agen

9、t 能力的极大浪费,从而在一定程度上降低了系统总收益,本文在参考已有文献的基础上,设计了一种基于维数划分策略和免疫的多任务联盟并行生成算法,试图在最小的约束条件和计算代价下实现一个Agent 可以同时加入多个联盟,以减小 Agent 能力的浪费,增加系统总收益.2?问题描述与分析当多Agent 系统同时存在多个待求解的任务时,需要针对每个任务同时生成相应的联盟予以求解,这类问题称为多任务联盟的并行生成问题.在 Agent 资源和能力非常强的环境中,如果一个 Agent 只能加入一个联盟,势必造成很大的浪费,这就迫切需要一个Agent 能加入到多个联盟中,并同时参与多项任务的求解,从而获得更高的

10、系统总收益.设在MAS 中,存在备选Agent 集N=A1,A2,!,An,任意 Ai(i=1,2,!,n)都具有一个 r 维的能力向量,Bi=b1i,b2i,!,bri#,bji0(j=1,2,!,r),用于定量描述 Ai执行某种特定动作的能力大小.设待求解任务集 T=t1,t2,!,tm,每个任务 tk(k=1,2,!,m)具有一定的能力需求 Btk=b1tk,b2tk,!,brtk#,任务 tk在系统中的权重用Wtk表示,且 Wtk%0,1,Wtk越大说明任务 tk越紧急,越优先给予完成;Agent 完成任务 tk可获得相应的收益P(tk).定义一个联盟 Ck(k=1,2,!,m)是 N

11、 的一个非空子集.联盟 Ck有一个能力向量BCk=b1Ck,b2Ck,!,brCk#,BCk是联盟中所有Agent 能力向量的总和,即 BCk=&Ai%CkBi.联盟 Ck可以完成任务tk的必要条件是:i=1,2,!,r,bitk biCk.我们作以下假设:(1)和惯例一样 1 4,在特征函数对策(CFGs)中研究联盟形成.每个联盟 Ck的值用一个特征函数V(Ck)给出.我们假定 V(Ck)0,V(Ck)=P(tk)-F(Ck)-C(Ck).式中 P(tk)指完成任务tk所获得的利益,F(Ck)指联盟成员总能力折合的成本,C(Ck)指联盟协作求解 tk过程中的额外开销,主要指通信开销.如果联盟

12、 Ck不满足上述必要条件,则 V(Ck)为 0,否则 V(Ck)为正数.(2)在非超加性环境中研究联盟生成 4(超加性是指 C1,C2!N,C1(C2=?,有 V(C1)C2)V(C1)+V(C2),在这样的环境中,最大的联盟将是最有益的.定义系统联盟集 C=C1,C2,!,Cm,且 C1)C2)!)Cm!N,系统总收益定义为:V(C)=&kV(Ck)=&k P(tk)-F(Ck)-C(Ck).图 1?多任务联盟并行生成问题A1A2A3!Ant1t2t3!tm101!1010!0001!1!111!0多任务联盟并行生成问题就是面向任务集合 T=t1,t2,!,tm,在 Agent 集合 N 中

13、为每个任务 tk生成最优求解联盟Ck,使系统总收益 V(C)最大;且允许一个Agent 参加多个联盟而参与多项任务的求解(如图 1所示),比如对于 Agent A2可以同时参与任务 t2与 tm的求解.3?基于维数的 Agent 能力划分策略在MAS 中,每个Agent 之间都存在彼此合作形成联盟的可能,可能的联盟总数同 Agent 数目成指数关系;而且每个Agent 都有加入多个任务的可能,如果能力无限可分,则其可能的联盟将是无穷多个,多任务联盟的并行生成问题将是一个无法求解的组合优化问题.因此,国内外的学者都是以一个Agent 只能加入一个联盟为前提,对任务联盟进行求解.为了使多任务联盟的

14、并行生成问题可以求解,而又能实现一个Agent 加入到多个任务联盟中的目标,本文设计了一种基于维数的Agent 能力划分策略,并提出?子Agent 的概念来求解多任务联盟的并行生成问题.由第 2 节可知,对具有 r 维能力的Agent Ai,其能力可以用向量 Bi表示为:Bi=b1i,b2i,!,bri#;由线性代数知识可知,向量 Bi可以表示为r 个正交向量的和,即:Bi=&jBji,其中 B1i=b1i,0,!,0#,B2i=119第 1 期基于维数划分策略和免疫的多任务联盟并行生成算法0,b2i,0,!,0#,!,Bri=0,0,!,0,bri#.我们把能力 Bji=0,!,0,bji,

15、0,!,0#赋给虚拟 Agent Aji,这时称Aji为Ai的子Agent,Ai为Aji的父Agent.因此,具有 r 维能力的 Agent 可以包含 r 个子Agent.在求解多任务联盟的并行生成问题时,子 Agent 将代替父 Agent 参加联盟.对于 Ai,每个子 Agent 最多可以参加一个联盟,则 Ai最多将能加入到r 个任务联盟中.可能的系统联盟总数与 Agent 数目、维数 r 以及待求解任务的数目m 成指数关系.为了得到一个满意的结果,必须考虑大部分的联盟组合,因而多任务联盟并行生成问题是一个复杂的组合优化问题.4?基于免疫算法的多任务联盟并行生成算法免疫算法 10 13(I

16、mmune Algorithm,IA)是借鉴生物免疫系统的基本原理,模仿生物免疫学和基因进化机理通过人工方式构造一类优化搜索算法.由于免疫系统通过从许多抗体中选择匹配抗原的一种类型来消灭或排除抗原,因此可以把要求解的问题当作抗原(antigen),把问题的解作为抗体(antibody).对待解问题(抗原)首先进行具体分析,由先验知识得到对最佳个体基因的估计(疫苗,vaccine);然后根据疫苗修正某个个体的基因得到新个体(抗体),最后根据目标函数选择最佳个体.多任务联盟并行生成问题就是在含有 n 个 Agent 的 MAS 中,针对任务 t1,t2,!,tm并行地求解最优联盟,其最优联盟集能使

17、系统总收益 V(C)最大.我们借助于自适应提取疫苗的免疫算法,把待求解的任务集 T=t1,t2,!,tm作为抗原,多任务的多组联盟组成方案作为抗体,系统收益 V(C)作为抗体的目标函数值,以进化的方式逐渐形成系统联盟值最大或近似最大的系统联盟集 C*.4?1?编码方式与适应度函数本文基于维数划分策略设计了三维二进制编码方式来表示抗体.抗体的每个基因位由三维坐标值 C(i,j,k)表示(如图 2所示),这样就得到一个三维基因位的排列.其中 C(i,j,k)的值由公式(1)确定.C(i,j,k)=1,子Agent Aji参与tk0,否则(1)?这样,多任务联盟的并行生成问题就转换为利用免疫算法求解

18、最优抗体的三维二进制编码,而且保证一个Agent 最多能加入 r 个联盟,参与 r 个任务的求解.图 2?编码方式设种群 A=C1,C2,C3,!,CN,N 为种群规模,抗体 h 的适应度函数fh定义为公式(2).fh=f(Ch)=Vmax-VhVmax-Vmin(2)其中 h=1,2,!,N,fh表示抗体与抗原之间的结合程度,其中 Vh为抗体h的目标函数值,Vmax和 Vmin分别为同一代群体中抗体目标函数值的最大值和最小值.4?2?记忆库和记忆库更新对于种群 A=C1,C2,C3,!,CN,若f1(C1)f2(C2)!fp(Cp)!fN(CN),则称集合 M=C1,C2,C3,!,Cp为抗

19、体记忆库,p 称为抗体记忆库规模.记忆库更新:新的种群中最优的 p 个不同抗体组成新的记忆库.记忆库中的 p 个不同抗体作为每一代的精华不仅对本次搜索的性能产生积极影响,保证了解的质量,而且能为下一次求解同类问题提供较好的经验信息.4?3?自适应提取疫苗疫苗是根据进化环境或待解问题的先验知识得到的对最佳个体基因的估计.疫苗的信息量及其准确性对算法的性能起着重要的作用.在 MAS 中,一方面对待求解的任务难以形成较为成熟的先验知识,而无法从分析任务的过程中提取合适的特征信息,得不到有效的免疫疫苗 14;另一方面,为寻求疫苗而使算法的计算成本大幅度增加、效率降低,就失去了提取疫苗的意义.为了解决这

20、两方面的问题,在免疫算法中应对疫苗采取自适应的提取策略.120系统工程理论与实践2008 年 1 月如果对 Cl%M(l=1,2,!,p),Cl(i,j,k)=e,则称 M 的第(i,j,k)位为优良基因位,记为 M(i,j,k).如果模式 w 满足(3)式,则称 w 为疫苗.需要注意的是,疫苗只是一种模式,而不是一个抗体.w(i,j,k)=M(i,j,k)第(i,j,k)位为优良基因位*否则(3)*为通配符,这里的通配符集为0,1.通过对疫苗的自适应提取,可以得到每代种群里最优的抗体模式,用来引导下一代种群的进化,可以提高收敛的速度.4?4?交叉和变异按交叉概率 Pc对抗体u 与抗体v 进行

21、交叉操作,交叉的过程为:随机选中某一 Agent Ai,对所有的 j与k,Cu(i,j,k)Cv(i,j,k).例如抗体 u 与抗体v 如图 3 所示,选中 A5,当 j=1,2,!,r 与k=1,2,!,m时,Cu(5,j,k)Cv(5,j,k),得到如图4 所示的新抗体.图 3?抗体 u 与抗体v图 4?抗体 u 与抗体v 交叉后生成的新抗体uv与vu按变异概率 Pm对抗体u 进行变异,其操作为:随机选中Agent Ai和Aq,对所有的 j 与k,Cu(i,j,k)Cu(q,j,k).例如对抗体 u 进行变异操作,选中 A2与 A5,当 j=1,2,!,r 与k=1,2,!,m 时,Cu(

22、2,j,k)Cu(5,j,k),得到如图 5 所示的新抗体.4?5?接种疫苗按概率 Pv对种群A=C1,C2,C3,!,CN接种疫苗,抗体 C 接种疫苗w 操作定义如(4)所示,记 C 表示接种后的抗体.C (i,j,k)=w(i,j,k)若 w(i,j,k)+*C(i,j,k)若 w(i,j,k)=*(4)4?6?免疫选择对第 t 代种群体At=C1t,C2t,!,CNt,接种疫苗后,按照(5)式进行免疫检测:设 Cht是第t 代种群的第h 个体,对其接种后得到第 t+1 代种群 At+1.Cht+1=C ht若f(C ht)f(Cht)Cht否则(5)121第 1 期基于维数划分策略和免疫

23、的多任务联盟并行生成算法图 5?抗体 u 变异后生成的新抗体4?7?算法描述多任务Agent 联盟并行生成算法描述如下:Step1?初始化群体 A0 N 和抗体记忆库 M0 p,把疫苗w 的各基因位置为*,令迭代代数 t=1;Step2?如果 t 已经达到最大迭代代数,则转到 Step 9,否则转到Step 3;Step3?计算第 t 代群体At N 中的每个个体的目标函数值 Vh,并根据 Vh进行排序,得到 Vmax和 Vmin,然后由式(2)计算每个个体的适应度值fh;Step4?对 At N 按概率 Pc进行交叉操作,按概率 Pm进行变异操作;按概率 Pv进行接种疫苗,并进行免疫选择,生

24、成新的群体 At N;Step5?对 At N 的抗体按适应度由高到低进行排序,群体中较优的 N-p 个抗体和抗体记忆库中的p 个抗体组成新的种群,得到第 t+1代群体 At+1 N;Step6?抗体记忆库更新:用 At+1 N 中最优的 p 个不同的抗体组成新的抗体记忆库Mt+1 p ;Step7?从抗体记忆库 Mt+1 p 提取疫苗,置 w 的相应位为优良基因;Step8?令 t=t+1,转到 Step 2;Step9?将 At+1 N 中具有最大适应度的个体作为最优解 C*.5?实验图 6?系统最优解的进化曲线为了检验算法的性能进行了实验.假设MAS 系统中Agent 数 n=20、每个

25、Agent 的能力向量 Bi、Agent 之间的通信开销 dij(由于篇幅限制,不再列出);种群规模为 N=100,最大迭代次数 t=200.Pc的合适取值范围为 0?4,0?9,本例中取定 Pc=0?65;Pm的合适取值范围为 0?01,0?2,且取定 Pm=0?20;Pv的合适取值范围为 0?5,0?9,且取定 Pv=0?71.系统中待求解的任务集 T=t1,t2,t3,t4,t5,每个任务的能力需求如表 1 所示.现对五个任务进行最优联盟的并行求解,其系统收益最优解的进化曲线如图6 所示,表 2给出了本文算法为每个任务生成的最优联盟.由图 6 可以看出,采用本文算法对 5 个任务并行生成

26、最优联盟时,最优解经过多次进化,其目标函数值在 86 代时从 29934 进 化到 30030,最后稳定在30030;由表 2 可以看出,一个 Agent 可以加入到多个任务联盟中,如:Agent A1参加了任务 t2,t5,Agent A11参加了任务 t1,t3,t5.可见,本文算法从根本上解决了一个Agent 加入多个任务联盟的问题,突破了已有算法的局限,提高了Agent 能力的利用率.6?总结在MAS 系统中,联盟是主要的合作方式.当系统中存在多个待求解任务而 Agent 能力很强时,完全可能一个 Agent 加入到多个联盟中,参与多项任务的求解,从而获得更大得系统收益.为此,本文设计

27、了一种基于维数的Agent 能力划分策略,并提出了?子 Agent 的概念;在此基础上,设计了一种基于三维二进制编122系统工程理论与实践2008 年 1 月码的免疫算法求解多任务联盟并行生成问题,并在求解过程中对疫苗进行自适应地提取.实验结果表明该算法可以为多个任务并行生成最优联盟,实现了一个Agent 加入多个联盟的目标.表 1?任务的能力向量任务b1tb2tb3tb4tb5tb6tt15000415640512541634589t21234234532452356783800t3456454452959293076754t45006004500550054002600t513002300

28、32503007003700表2?本文算法为 5个任务并行生成的最优联盟任务最优联盟t1 A2,A3,A7,A11,A12,A18t2A1,A6,A8,A9,A10,A12,A14,A16,A19t3A6,A7,A8,A10,A11,A14,A17,A20t4 A3,A4,A9,A13,A16,A17t5 A1,A2,A4,A5,A6,A11,A16,A18,A19,A20?如何提高算法的收敛速度是下一步工作的重点.参考文献:1?Talluri S,Baker R C.A quantitative framework for designing efficient business proce

29、ss alliances C?Proc of IEMC?96,IEEEPress,Vancouver,BC,Canada,1996,656-661.2?Shehory O,Kraus S.A kernel?oriented model for coalition formation in general environments:Implementation and results C?ProcAAAI?96,Portland,1996,134-140.3?Zlotkin G,Rosenschein J S.Coalition,Cryptography and stability:Mechan

30、isms for coalition formation in task orientedC?ProcAAAI?94.Seattle,1994,432-437.4?Sandholm T W,Lesser V R.Coalition among computationally bounded agents J.Artificial Intelligence,1997,94(1):99-137.5?徐晋晖,石纯一.一种基于等价的联盟演化机制J.计算机研究与发展,1999,36(5):513-517.?Xu Jinhui,Shi Chunyi.A mechanism of coalition evo

31、lvement based on equivalence J.Journal of Computer Research&Development,1999,36(5):513-517.6?罗翊,石纯一.Agent 协作求解中形成联盟的行为策略 J.计算机学报,1997,20(11):961-965.?Luo Yi,ShiChunyi.The behavior strategy to form coalition in agent cooperative problem?solvingJ.Chinese Computer,1997,20(11):961-965.7?夏娜,蒋建国,魏星,等.改进型蚁

32、群算法求解单任务 Agent 联盟J.计算机研究与发展,2005,42(5):734-739.?Xia Na,Jiang Jianguo,Wei Xing,et al.Searching for agent coalition for single task using improved ant colony algorithm J.Journal of Computer Research and Development,2005,42(5):734-739.8?蒋建国,夏娜,齐美彬,等.一种基于蚁群算法的多任务联盟串行生成算法 J.电子学报,2005,33(12):2178-2182.?Ji

33、ang Jianguo,Xia Na,QiMeibin,et al.An ant colony algorithm based multi?task coalition serial generation algorithm J.ActaElectronica Sinica,2005,33(12):2178-2182.9?骆正虎.移动 Agent 系统若干关键技术问题研究D.合肥:合肥工业大学研究生院,2002,81-98.?Luo Zhenghu.Research on several key problems in mobile agent systemsD.Hefei:Institute

34、 of Postgraduate,HefeiUniversity ofTechnology,2002,81-98.10?Wang Lei,Pan Jin,Jiao Licheng.The immune algorithmJ.Acta Electronica Sinica,2000,28(7):74-78.11?Zhao Fuqing,Hong Yi,Yu Dongmei,et al.A novel genetic algorithm for partner selection problem in virtual enterprise C?Procof the 2004 Inter.Conf.

35、on Intelligent Mechatronics and Automation,IEEE Press,2004,477-482.12?Liu Kesheng,Cao Xianbin,Zhen Haorang,et al.Solbing TSP based on immune algorithm J.Computer Engineering,2000,26(1):1-2.13?武晓今,朱仲英.基于模式记忆的免疫遗传算法J.计算机仿真,2005,22(8):98-114.?Wu Xiaojin,Zhu Zhongyin.Schema control for immune genetic al

36、gorithmJ.Computer Simulation,2005,22(8):98-114.14?韩学东,洪炳,孟伟.基于疫苗自动获取与更新的免疫遗传算法J.计算机研究与发展,2005,42(5):740-745.?Han Xuedong,Hong Bingrong,Meng Wei.An immune genetic algorithm basedon vaccine autonomous obtaining and updating J.Journal of Computer Research and Development,2005,42(5):740-745.123第 1 期基于维数划分策略和免疫的多任务联盟并行生成算法