第29卷第6期控制与决策2014年6月文章编号:1001-0920(2014)06-1027-08DOI: ),男,博士生,从事任务规划与优化算法的研究；王瑛(1967 ),女,教授,博士生导师,从事任务规划与优化算法等研究.
1028控制与决策第29卷率的目的,围绕招标策略[7-8]、协议机制[9-10]、合同类合同网协议状态转移随机矩阵型[11-12]、控制方式[13-14]等方面,对合同网协议的收敛假设条件的设定性与收敛速率进行了一定程度的探索.作为分布式环境下的问题求解方法,合同网协议目前,对于合同网协议收敛性与收敛速率的研只提供协作主体之间协商的协议框架,具体的任务分究,尽管在提升收敛效率方面取得了一定的成果,也配策略需要根据应用背景进行设定.鉴于合同网协议已经认识到影响收敛质量的关键因素,但是,由于采扩展形式众多,为了简化分析且不失共性,本文以文用的是仿真实验与数量统计方法,而没有从数学解析献[2-6]的研究成果为基础,对扩展形式进行有针对的视角进行分析,无法形成揭示客观规律的共性准则.性的取舍,假设如下.面对纷繁复杂的合同网协议拓展研究,Sandholm指1)招标策略:招标者采用广播方式发布任务,全出,对传统合同网协议的改进和扩展工作都存在一定体协作主体都可以参与投标,不考虑扩展形式对于招的局限性,需要根据具体应用环境设定合适的协议内标范围的影响.容、类型和机制.2)协议机制:允许协作主体在任务执行过程中对本文以马尔可夫链为分析工具,通过构造任务分任务进行再分配,并进行多次协商以避免分配陷入局配状态空间与建立状态转移随机矩阵的方式,分别对部最优.合同网协议的收敛性和收敛速率进行分析,从数学解3)合同类型:协作主体可以采用买卖合同、交换析的视角为协商机制的完善提供依据.合同、聚类合同和多主体合同.鉴于计算复杂性的要1合同网协议协商机制收敛性分析求摒弃了融合合同,将条件合同纳入适应度函数的范全局收敛性是求解质量的保证,合同网协议协商畴而合理规避.机制收敛性研究的现状,源于控制逻辑分析能力以及4)控制方式:多主体合同的采用使得分布式控系统动态行为预见能力研究的缺乏.制也具有集中式控制的能力,控制方式归结为集中式任务分配问题的状态空间控制.作为典型的最优化问题,任务分配问题的形式化状态转移随机矩阵的构建表述与状态空间的构建都与问题求解算法密切相关.在模型假设的基础上,构建状态转移随机矩阵,合同网协议协商机制没有涉及群体智能的内容,与还需要理解合同网协议的工作机理.合同网协议是以TA、SA等迭代智能算法类似,问题求解的可行域构招标策略与合同类型决定搜索范围,以中标策略明确成了状态空间的规模.搜索方向的问题求解方法.其中,招标策略可以显著为应用合同网协议进行求解,需要对任务分配问降低通信频率,中标策略基本是在招标策略已经有效题的状态进行编码,为此,可以分别建立协作主体集缩减搜索范围的前提下进行解析计算而得出的.但是,合Agent:fagentig与任务集合Task:ftaskjg.考虑本文所假设的广播式任务发布方式破坏了搜索范围agenti的任务分配情况,可以建立长度为#Task的有效缩减的前提条件,而采用解析计算的中标策略又二进制代码表示agenti的任务分配,#表示集合中无法同时满足时效性要求.考虑到本文所进行的收敛元素的个数.若taskj分配至agenti,则对应j位置的性分析主要是针对协商机制的探讨,并不涉及应用背代码为1,否则取0.将此推广到Agent集合,则可以景,为满足收敛性分析的共性原则,假设中标策略为生成#Agent #Task的二进制代码矩阵,用以表示随机遍历搜索方式,即通过合同类型所确定的搜索范状态空间的一种状态.注意到,同一任务不可能同围中的状态与当前状态之间都存在正概率直接连通.时分配至多个协作主体,规模为#Agent #Task的本文确立如下步骤建立状态转移随机矩阵:二进制代码矩阵可以表示#Agen#Taskt种情况,由1)根据随机遍历搜索方式,对于任意状态i,j,设此也构成了任务分配问题的状态空间I,设#I=pij>0;#Agen#)根据状态序列,对于任X意状态i,j,当i<j时,将适应度函数f引入状态空间,可以对构成状设pij=0,并且sequencei=pij,i<j;态空间的状态进行排序与分类.为便于描述且不失3)根据设定的合同类型,对于任意状态i,j,在一般性,假设存在单一最优点,以序号表示状态且按i>j范围内,综合运用多种合同验证是否可以将状照适应度从小到大的顺序构成状态序列I=fi0;i1;态i,j直接X连通,若无法直接连通,则设pij=0,并且 ;i#I 1g,于是合同网协议求解任务分配问题的实vacanti=pij,i9j;质便转化为从任意状态is出发搜索状态i0的过程.4)令pii=pii+sequencei+vacanti.
第6期刘刚等:合同网协议协商机制收敛性与收敛速率分析1029观察状态转移随机矩阵的建立步骤可以发现,关类型是通过限定投标者数量与任务转化数量来影响键在于步骤3)中状态i,j直接连通性的验证.为此,需搜索范围,任务的转换只限定于招标者与中标者之间,要进一步理解合同类型对于搜索范围的决定方式,可而控制方式则关注于招标者是否具有在投标者之间以在任务的传播方向与传播数量两个层面进行分析.进行任务转换的能力.在任务的传播方向层面,买卖合同提供任务的单在集中式控制方式中,招标者具有对系统绝对的向传播能力,交换合同提供任务的双向传播能力,在控制权力,可以在系统内任意协作主体间进行任务的集中式控制方式下,多主体合同提供在任意协作主体转换.在分布式控制方式中,包括招标者在内的协作间任务的多向传播能力.在集中式控制方式下,3种合主体之间没有必然的权力义务关系,任务转换只能在同的运用使得传播方向可以覆盖全部状态空间.于是招标者与中标者之间进行.以agenti为招标者,控制问题转化为在任意主体间迁移的合同数量是否具有方式对于任务转换的限制如图1所示.连通状态空间的能力.然而,聚类合同中任务的组合agentagentagentiik及其数量是由协作主体依据自身信息得出的,存在与全局最优相矛盾的可能taskijtaskiktasktaskijkl,因此无法保证在任务的传播数量上对于全部状态空间的连通.agentagentjktaskagentagentjkjl需要说明的是,采用上述步骤建立的状态转移矩agentiagentagentik阵满足随机矩阵的定义,但由于在问题求解过程中不可能掌握适应度函数在状态空间的分布情况以及状tasktaskijiktasktaskijkl态之间的连通关系,只能得出pij>0的结论agent,而无法jagentktaskagentagentj得到ljkpij=0的数量与位置.合同网协议收敛性分析图1控制方式对于任务转换的限制为便于分析的需要,引入状态分布概率 n因合同类型与招标策略对于收敛性的作用机理,构建X长度为#Agent #Task的向量,满足( n)相似,故由合同类型所导致的收敛性分析结论经过转i>0且( n)i=1,用以表示在时刻状态空间的概率分化后同样适用于招标策略,但是控制方式对于收敛性布情况的影响还有待于证实.为此,本文引入变邻域搜索算.吸收态i0对应的概率分布为 =(1;0; ;0),于是收敛性分析转化为验证limPfj nj=法的相关思想[15-16],借鉴邻域结构的定义,提出了变0g=邻域合同系的概念,探讨了控制方式对收敛性的影响.limPfj 0Pnj=0g=1是否成立.按照本文确立的步骤建立合"同网协议#状态转移变邻域合同系的提出随机矩阵O与现有的合同类型限定协作主体数量相区别,变,可以得到类似于P=E的分块矩HT邻域合同是以协作主体之间任务转换数量为约束条阵.其中:E为1 1规模的单位矩阵块,表示吸收态;件而不考虑参与协商协作主体数量的合同类型.以任H为(#I 1) 1规模的矩阵块,表示非吸收态向吸收务转换数量为划分标准,按照转换数量由小到大进行态转移的概率;T为(#I 1) (#I 1)规模的矩阵块,排序,全体变邻域合同组成了变邻域合同系.表示非吸收态之间的状态转移概率;O为1 (#I 1)定义1变邻域合同可描述为三元组hchange;规模的矩阵块且oij=0.鉴于步骤3)关于pij>0的hagenti;agentj;taskiji;bene ti.其中:change表示任结论,可以推导出hij>0,tij>0.由此,对于任意的i,务转换数量;hagenti;agentj;taskiji表示任务在协作Pfpii=1g>0)Pfpnii=1g>0,意味着存在局部主体间的转换情况,为change组三维向量,每组向量最优解的可能,故limPfj njg61.由此可得出结中agenti代表任务发送方,agentj代表任务接收方,论:采用目前存在的合同类型的合同网协议不能保证task协商机制的全局收敛性ij代表单一任务,不同向量中的agenti、agentj代.表的协作主体可以不同;bene t表示任务转换后系2变邻域合同网协议协商机制收敛性分析统效能的变化.变邻域合同系可以描述为change从1导致合同网协议协商机制无法保证收敛的原因s#Task的全体变邻域合同组成的合同体系.在于,目前存在的合同类型是以应用背景或算法效率按照变邻域搜索算法的设计思想,一种变邻域提升为出发点而提出的,并没有考虑连通状态空间的合同代表相应的邻域结构,以变邻域合同系为工具问题.的计算方法,为寻找到最优的分配方式,必须在全部对收敛性结论的进一步分析可以发现,关键环节邻域结构中进行搜索,但是限于运算时间和消耗资对于收敛性的影响机理也是不同的.招标策略与合同源的制约,存在求解质量与效率的矛盾.为此,仍然沿
1030控制与决策第29卷用节除控制方式以外的假设条件.作用以便于状态连通数量的统计.集中式控制方式收敛性分析1)建立规模为#Agent的向量sCl,用以表示任根据节设定的步骤,按照随机搜索方式建务分配情况,sCli元素的取值表示对应agenti承载的立状态转移随机矩阵任务数量,令sCl.在步骤3)中,为计算vacanti=0,i=1;2; ;#的值,需要检验状态空间的直接连通性.采用集中式控2)构建函数sCl=sClI(lA;lT;i),其中lA表示制方式使得招标者可以任意转换协作主体间的任务,待分配协作主体数,lT表示待分配任务数,i表示正因此从任意状态is出发,采用任务转换数量为change在赋值的agenti.函数sClI运行机制的伪代码表述如的变邻域合同连通的状态数量为Cchange#T表1所示.ask(#Agent 1)changeX,采用变邻域合同系连通的状态数量为#T表1函数sClI运行机制的伪代码askCchange#Task(#Agent 1)change.注意到状态functionsClI(lA;lT;i)is也fortA=lTto[lA=lT];=[lA=lT]为lA=lT的整数部分change=1表示一种状态,因此sCli=tA;=变量tA表示agenti的任务赋值数量,状态is与采用变邻域合同系所能连通的X状态数量为ifi<#Agent=说明任务分配未完成sClI(lA 1;lT tA;i+1);=计算agent#Ti+1的任务分配askendCchange#Task(#Agent 1)change=#I:endchange=0可以看出,采用集中式控制方式能够实现状态3)令sCl=sClI(#Agent;#Task;1)并进行计算.空间的全连通,因此vacanti=0,所构建的状态转移类型包含方案数量计算随机矩阵为下三角元素均为pc=1/#I,对角线元素设分配方案类型的划分数量为sA,类型划分的p结果为sA组sCl组成的矩阵.为便于分析,设sCli为ii=1 (i 1)pc的矩阵形式.对于任意的初始分布 序号i对应的分配方案类型,sCl0,limij为分配类型i中出结论n!1Pfj 0j=0g=1.由此可得:在集中式控制方式下,采用变邻agentj对应的任务分配数量,i=1;2; ;sA,j=1;域合同系2可以保证协商机制的收敛性2; ;#Agent.,即311)建立规模为sA的向量sCa,用以表示对应分667p7配类型包含状态的数量情况,sCai元素的取值表示c1 (i 1)pcP=6676..)...对应分配类型包含状态的数量,令sCai=0,i=1;2;...5 ; 1 (#I 1)pc232)构建函数sCa=sCaI(lA;lT;sCl).其中:lA表16示待分配协作主体数,lT表示待分配任务数,sCl表示67107分配类型分类矩阵.函数sCal运行机制的伪代码表述=67lim67n!1P6...4...7:...5如表2所示.10 0表2函数sCaI运行机制的伪代码分布式控制方式收敛性分析functionsCaI(lA;lT;sCl)招标者在系统中的地位与作用的差异,使得分fori=1tosA;=采用循环赋值方法,依次对sCai进行计算布式控制方式不具备在协作主体间任意转换任务的sCai=cI(lA;lT;sCli;j)/rI(sCli);end能力.结合集中式控制方式变邻域合同连通状态数量3)构建函数cI(lA;lT;sCli;j),用以表示按照组的分析,可以得出分布式控制方式实际上不能保证协合数计算的状态数量.其中:lA表示待分配协作主体商机制全局收敛性的结论.但是,分布式控制方式遵数,lT表示待分配任务数,sCli表示序号为i的分配类循任务转换仅在招标者与中标者之间进行的客观规型.函数cI运行机制的伪代码表述如表3所示.律,据此仍然可以得到协商机制收敛性的相关结论.面对纷繁复杂的分配方案,本文采用分配方案类型表3函数cI运行机制的伪代码划分、类型包含方案数量计算、类型连通方案数量计functioncI(lA;lT;sCli;j)算、状态连通数量计算、收敛概率计算的思路,对分cbij=C1lA CsClijlT;iflA<#Agent=说明任务分配未完成布式控制方式变邻域合同条件下的收敛性进行分析.cb=cbij cI(lA 1;lT sClij;sCli;j+1);else=说明任务分配完成分配方案类型划分cb=cbij;=迭代终止对分配方案类型进行划分,可以起到化繁为简的end
第6期刘刚等:合同网协议协商机制收敛性与收敛速率分析10314)构建函数rI(sCli),用以表示按照组合数计算4)构建函数rI(sCli),用以表示按照组合数计算的状态重复比例,其中sCli表示序号为i的分配类的状态重复数量,其中sCli表示序号为i的分配类型.函数rI运行机制的伪代码表述如表4所示.型.函数rI运行机制的伪代码表述如表7所示.表4函数rI运行机制的伪代码表7函数rI运行机制的伪代码functionrI(sCli)functionrI(sCli)dpj=numberoftasksequaltosClij;=相同次数只记录一次rtij=0;rt=Qdpj!;=变量rt表示累计重复比例fork=1to#Agent=建立招标者循环forl=1to#Agentl6=k=建立投标者循环5)令sCa=sCaI(#Agent;#Task;sCl)并进行计ifsClik+sClil>j=说明可能引起重复计数算.ifsClik>j=说明agentk只发送任务也能满足转换数量count=0;=变量count表示agentk,agentl接收任务数量类型连通方案数量计算whilesClik>j count&sClil>count&j>count设分配方案类型的划分数量为sA,类型划分结rtij+=Cj countntsCl CcouiksCl;il果为count+=1;=接收任务数量依次递增sA组sCl组成的矩阵.为便于分析,设sClij代表序号i对应的任务分配方案类型,sClij为分配类型endielse=说明agentk需要接收任务才能满足转换数量中agentj对应的任务分配数量,i=1;2; ;sA,j=count=sClik;=变量count表示agentk发送任务数量whilecount>0&sClil>j count&j>count1;2; ;#+=CcountsClik Cj countsCl;il1)建立规模为sA #Task的矩阵cCa,用以表count =1;=发送任务数量依次递减示各分配类型在应用变邻域合同网协议类型系中end对应的状态连通数量end,令cCaij=0,i=1;2; ;sA,endj=1;2; ;#=投标者循环终止2)构建函数cCa=cCaI(sCl),其中sCl表示分配end=招标者循环终止类型分类矩阵.函数cCaI运行机制的伪代码表述如状态连通数量计算表5所示.设分配方案类型矩阵sCl的规模为sA #Agent,表对应类型包含状态向量sCa的规模为sA,类型在变邻5函数cCaI运行机制的伪代码functioncCaI(sCl)域合同系中连通状态数量矩阵cCa的规模为sA fori=1tosA=依次选取sCli#=1to#Task=依次选取任务转换数量为j的合同1)建立规模为sA的向量tC,用以表示对应分配cCaij=cI(sCli;j) rI(sCli)=2;end类型应用变邻域合同系连通状态的数量统计,按照公#end式XTasktCi=sCai cCaij进行计算.3)构建函数cI(sCli;j),用以表示按照组合数计j=1算的状态连通数量.其中:sCli表示序号为i的分配类型,j表示任务转换数量.函数cI运行机制的伪代码X2)设分布式变邻域合同系状态连通数量和为tS#sA=tCi,数量统计完成.表述如表6所示.t=收敛概率计算表6函数cI运行机制的伪代码通过tS的计算虽然无法获得状态分布的位置信functioncI(sCli;j)cb息,但是根据得到的状态连通的数量信息,可以采用ij=0;fork=1to#Agent=依次以agentk为招标者计算状态连通数量概率计算的方式对收敛性进行分析.设ps=tS=(#I ifsClik>j=说明agentk只发送任务也能满足转换数量(#I 1)),表示状态空间内任意状态连通的概率,即count=0;=变量count表示agentk接收任务数量whilesClik>j count&#Task sClik>count&j>countPfpij=pcg=ps,i6=j.考虑到局部最优点在状态转cbij+=CsClikj count (#Agent 1)j count C#Task sClikcount;移随机矩阵的表现形式为pii=1,i6=1,即pij=0,count+=1;=接收任务数量依次递增i>j,因此状态i不是局部最优点的概率为1 (1 endelse=说明agentk需要接收任务才能满足转换数量ps)i 1,i6=1,分布式控制应用变邻域合同系可以收敛count=sCl#Iik;=变量count表示agentk发送任务数量whilecount>0&#Task sClik>j count&j>count到全局最优点的概率为YP=1 (1 pi 1s).cbij+=CsClikcount (#Agent 1)count C#Task sClikj count;i=2count =1;=发送任务数量依次递减案例分析end为便于理解,本文列举#Agent=3,#Task=3endend时各步骤对应的计算结果,如表8所示.
1032控制与决策第29卷表8分布式变邻域合同系状态连通数量计算各步骤结果为此,合同网协议协商机制收敛速率的研究变得十分sClsCacCatCtS必要.3003612878收敛速率通常采用收敛速度[17]、迭代次数[18]和210186126432654时间复杂性[19]等概念进行描述.采用马尔可夫链理论11166126144sCl表明存在3种分配方案类型划分.类型对收敛速率进行分析,根据对状态转移随机矩阵处理1将3个任务分配至同一协作主体;类型2将2个任务分配方式的不同,可以分为特征值分析[20]和Doeblin理论分析[21]至同一协作主体,1个任务分配至另一协作主体.其中,Doeblin理论作为研究马尔可夫链长时;类型分布的数学工具,具有相对自然的表达方式,为此本3将3个任务分别分配至各协作主体.文采用Doeblin理论对合同网协议协商机制的收敛速sCa表明类型1包含的方案数量为3,类型2包含率进行分析.的方案数量为18,类型3包含的方案数量为的行代表分配类型集中式控制方式收敛速率分析,列代表任务转换数量.第1行表明类型1在任务转换数量分别为根据节的结论,集中式控制方式构建的状1、2、3时,可以连通的方案数量为态转移随机矩阵为下三角元素均为pc,对角线元素6、12、8.类型2和类型3的情况以此类推pii=1 (i 1)pc的矩阵形式,并保证可以收敛到.全局最优解.应用Doeblin收敛定理[22],可以确定吸tC是sCa与cCa的乘积之和,表明类型1连通的方案累计数量为收态i0为惟一满足Doeblin条件的特定状态,也可以78,类型2连通的方案累计数量为确定出"=pc,为此对于任意的初始分布 0,存在惟432,类型3连通的方案累计数量为表明变邻域合同系连通的方案累计数量为一的吸收态概率向量 =(1;0; ;0),使得( )i0=1>",k 0Pn kv62(1 pc)n成立.654.根据ps与收敛概率P的计算公式,分布式控制分布式控制方式收敛速率分析应用变邻域合同系的全局收敛概率为根据节的结论,分布式控制方式以概率P=#I#Agent与#Task的不同取值对全局收敛性的1 (1 pi 1s)收敛到全局最优解.在存在全局收概率及变化情况如表i=29所示.敛性的情况下,状态转移随机矩阵事实上也存在多种表可能形式.对于分布式控制方式收敛速率的分析,需9#Agent与#Task的不同取值对全局收敛性的影响#T要根据马尔可夫链的运算法则,寻找极端情况下随机ask#Agent矩阵的表现形式,从而给出明确的上下界估计.概率pij>0表示状态i经一步转换可以直接连通状态j,当状态i与状态j之间不存在直接连通的可能性时,状态i可以通过若干中间状态连通状态j,即>0,n2Z+.在不考虑pnij取值的情况下,n的取值是影响收敛速率的重要因素.为尽快连通吸收态,任意状态is所经历的中间状态数量应尽可能少.沿此分析思路,设极端情况下最优收敛速率矩阵为由表9可以看出,#Agent与#Task对于全局收Ph,最劣收敛速率敛概率变化的影响略有差别,但是随着#Agent或2矩阵为Pl,则有31#Task的增大,收敛概率都表现出急剧减小的趋势 pc当#Agent或#Task取值大于5时,分布式控制变邻Ph=..7;域合同系几乎不能保证协商机制的收敛.. pc3变邻域合同网协议协商机制收敛速率23分析16受问题规模、信息传输、设备性能等众多主客观677P7l=6pc1 pc6因素的限制67..4..7:..,利用有限时间探索问题的最优解决方案5存在相当的难度.鉴于算法需求变化的影响,评价优pc1 pc化算法质量的准则正逐渐转变为在可以接受的时间最优收敛速率矩阵Ph是表示任意状态is与吸及消耗范围内,寻找到一个足够满足需求的优化解,收态i0之间存在一步转移概率的矩阵形式.应用
第6期刘刚等:合同网协议协商机制收敛性与收敛速率分析1033Doeblin收敛定理,其收敛速率与集中式控制方式收及其扩展理论分析的基础上,通过在招标策略、协议敛速率相同,即k 0Pn kv62(1 ")n=2(1 pc)n.机制、合同类型与控制方式等方面设定假设条件,构事实上,由于事先无法获取状态空间分布的具体建了合同网协议的马尔可夫链模型,并借鉴相对成熟信息,最优收敛速率矩阵Ph作为一种状态转移随机的群体智能算法收敛性分析方法,得出了利用目前存矩阵类型,并不具备指导实践的作用.但是其与集中在的合同类型无法保证全局收敛的结论.式控制方式收敛速率相同的结论却说明,具有系统局2)为检验控制方式对于收敛性的影响,借鉴变邻部控制能力的分布式控制方式在收敛速率方面至多域算法的设计思想,提出了变邻域合同系的概念,并与具备全局控制能力的集中式控制方式相同.最优收分别在集中式控制方式与分布式控制方式中进行了敛速率矩阵Ph收敛速率的结论符合实践经验,构成验证.由于无法事先获取状态空间的分布信息,在对了分布式控制收敛速率的上界状态空间进行分类的基础上,设计了分布式控制方式.最劣收敛速率矩阵Pl是表示适应度排序为条件下状态连通数量的详细计算步骤与方法,并得出了收敛概率的计算公式.i#I 1的状态需要遍历全部状态空间才能连通吸收态i0的矩阵类型.显然Pl的概率分布不满足Doeblin3)采用Doebin理论,分别对集中式控制方式与条件分布式控制方式条件下,应用变邻域合同系的协商机,为此本文采用Doeblin收敛定理推论进行收敛速率分析制收敛速率进行分析,得到了相应控制方式收敛速率.应用Doeblin收敛定理推论[22],需要分别计算M与收敛速率上下界的估计表述,所得结论符合全局控与制能力优于局部控制能力的实践经验."的取值.最劣收敛速率矩阵遵循对角线元素pn11=应该清楚地看到,合同网协议只是各协作主体之1,pnii=(1 pc)n,i>1,且在i>j范围内,当j=1时间进行协商的协作协议框架,并没有根据问题具体情,pnij=pn 1ij(1+pc),当j6=1时,pnij=pnijpc的运算规律.结合Pl的矩阵形式,可以得出在范围i>1,j>况设计任务分配优化策略.为了拓展收敛性与收敛速率分析的适用范围,本文对合同网协议的局部搜索方2且i>j+1内,pnij=pni+1;j+1的结论.分析运算规律可以发现,当n=#I 1时式采用随机搜索方式进行替代.在此基础上,为简化,pn#I;1首次转变为正值分析,在处理任务之间的关联关系时,只是将其纳入,pn#nI;1=pc,可得出M的分析结果.在此基础上,对"的取值进行分析适应度函数的范畴进行规避而未作详细的讨论.同时,.令由于需要传送协作主体的私人信息,本文设计的变邻k=1,pM11=1;pMii=(1 pc)M,i>1)pM11>域合同系对应的任务分配步骤,是建立在合作型协作pMi1,i>k.主体假设基础上的,对于非合作型协作主体任务分配令XlXl+1k=l>2,pMlj=pMl+1;j=1,pMij=问题的收敛性与收敛速率的分析还有待于研究.j=1j=1pMi+1;j+1)pMl1=pMl+1;1+pMl+1;2且pMl+1;2>0)pMl1>参考文献(References)pMl+1;1.[1]:Highlevel综合以上分析可得出infipMi1=p#Ic的结论.令communicationandcontrolinadistributedproblemM=#I 1,"=p#Ic,则最劣收敛速率矩阵Pl的收solver[J].IEEETransonComputers,1980,29(12):357-敛速率为 0Pn kv6[2](1 "[n=M])=2(1 p#I[n=(#I 1)]protocolbasedonmarginalcostcalculations[C].Procofc):最劣收敛速率矩阵Pl分析的实质是计算收敛步长为DC:AAAIPress,1993:且初值选择最劣解时的收敛情况,构成了分布[3]式控制收敛速率的下界.allocation,I:Theoreticalresults[C].ProcoftheAAAI4结论:AAAIPress,1998:合同网协议作为协商机制的典型代表,以其简洁68-75.实用、能够成功模拟利益关系等特点,正逐步发展成[4]MartinRAndersson,为解决任务分配问题的有效途径.为理解合同网协议forsatisficingtaskallocation,II:Experimentalresults[C].的工作原理:,本文在协商机制收敛性与收敛速率分析中进行了3个方面的探索AAAIPress,1998:1-7.:[5]龙涛,陈岩,沈林成.基于合同机制的多UCAV分布式协1)为分析收敛性与收敛速率,在传统合同网协议同任务控制[J].航空学报,2007,28(2):352-358.
1034控制与决策第29卷(LongT,ChenY,[13]高黎,沙基昌.基于合同网的分布式卫星系统任务优化missioncontrolbasedoncontractmechanismformultiple分配研究[J].宇航学报,2009,30(2):[J].ActaAeronauticaet(GaoL,,2007,28(2):352-358.)fordistributedsatellitessystembasedoncontractnet[6]龙涛,陈岩,霍霄华,等.战场环境中多无人机动态任务protocol[J].JofAstronautics,2009,30(2):815-820.)调度[J].计算机工程,2007,33(10):36-38.[14]刘跃峰,张安.有人机/无人机编队协同任务分配方法[J].(LongT,ChenY,HuoXH,系统工程与电子技术,2010,32(3):(LiuYF,[J].ComputerEngineering,2007,ofmanned/unmannedaerialvehicleformation[J].Systems33(10):36-38.)EngineeringandElectronics,2010,32(3):584-588.)[7]ZhaoX,HuangHK,[15]NenadMladenovi’c,DraganUrosevi’c,-agentsystem[C].[J].JofOperationsResearch,2012,Beijing:2009:(1):58-73.[8]于振华,刘宇,蔡远利.基于扩展合同网协议的无线传[16]SandroPirkwieser,感器网络协作方法研究[J].控制与决策,2009,24(1):periodicroutingproblems[C].:Springer,2010:(YuZH,LiuY,[17]RabinovichY,[J].ControlandDecision,2009,24(1):61-65.)geneticalgorithm[C].Procofthe4thIntConfonGenetic[9]龙涛,朱华勇,沈成林.UCAV协同中基于协商的分布式:MorganKaufmann,1991:215-任务分配研究[J].宇航学报,2006,27(3):.(LongT,ZhuHY,-baseddistributed[18][J].JofAstronautics,2006,27(3):457-463.)optimization[C].The11thIntConfonParallelProblem[10]唐苏妍,梅珊,朱一凡,等.基于扩展合同网协议的分布:Springer,2010:697-706.式武器目标分配方法[J].系统工程与电子技术,2011,[19]AsohH,Mü(3):[C].(TangSY,MeiS,ZhuYF,:Springer-targetassignmentalgorithmbasedonextendedcontractnetVerlag,1994:[J].SystemsEngineeringandElectronics,2011,[20]FlorianSchmitt,(3):568-574.)ofthesecondlargesteigenvalueontheconvergence[11]LesserV,DeckerK,[C].ProcoftheGeneticandGPGP/:Morganframework[J].PlenaryLecture,2002,12(1):,2001:559-564.[12]龙涛,沈林成,朱华勇,等.面向协同任务的多分布式[21]任务分配与协调技术[J].自动化学报,2007,33(7):731-chains:Asimpleaccount[J].,2002,7(13):123-128.(LongT,ShenLC,ZhuHY,[22]&coordinationtechniqueofmultipleNCAVsforprocesses[M].Berlin:Springer,2007:[J].ActaAutomaticaSinica,2007,33(7):731-737.)(责任编辑：李君玲)
