（计算机软件与理论专业论文）多agent系统排队算法及应用研究.pdf

多a g e n i 系统排队算法及应用研究 多a g e n t 系统排队算法及应用研究 中文摘要 协调与协作是多a g e n t 研究的核心问题之一，排队是实现多a g e n t 协调与协作的关键技术。本文的工作主要包括以下几点： 1 ) 给出了多a g e n t 排队系统的体系结构及构造a g e n t 的基本要素， 如：心智状态形式化描述、感知器算法、知识库、规划模块和通 信模块等。 2 ) 给出了多a g e n t 排队系统的基本算法，包括多a g e n t 同步休假 m m c 排队算法、多a g e n t 异步休假m f m c 排队算法、多a g e n t 部分服务台同步休假m m c 排队算法以及多a g e n t 部分服务台异 步休假m m c 排队算法。 3 ) 实现了范例验证系统，即交通调度模拟系统。 通过以上工作，可以看出，本文研究取得的成果，一方面实现多a g e n t 排队系统的算法，并实现了实际的模拟系统：另一方面丰富了多a g e n t 系统的研究内容，为人们进一步研究多a g e n t 的协调问题提供了一种新 方案。 关键词： a g e n t ，多a g e n t 系统，多a g e n t 系统排队算法 作者：曹凤雪 指导老师：李凡长( 教授) 垒坠! 坠翌垒型型竺型堕竺! ! ! 旦型堕! ! 婴! 塑! ! 竺些筮! 坐坠! ! 竺 a p p l i c a t i o na n dr e s e a r c ho nq u e u i n ga l g o r i t h mo f m u l t i a g e n ts y s t e m a b s t r a c t c o o r d i n a t i o na n dc o o p e r a t i o nt e c h n i q u ei so n eo fc o r ep r o b l e m si n m u l t i a g e n tr e s e a r c h e s ，a n dt h ek e yt e c h n i q u eo fr e a l i z i n gi ti sq u e u i n g o u r m a i nw o r ki n c l u d e st h r e ea s p e c t sa sf o l l o w s ： 1 g i v e st h es t r u c t u r eo fm u l t i a g e n tq u e u i n gs y s t e m ，a n dg i v e st h e f a c t o r so fa na g e n t ，e g m e n t a ls t a t e 、p l a n n i n g 、k n o w l e d g eb a s ea n d c o m m u n i c a t i o n sm o d u l eo fa na g e n t 。 2 w eh a v e d e s i g n e dq u e u i n ga l g o r i t h m so fm u l t i a g e n ts y s t e m i n c l u d i n gq u e u i n ga l g o r i t h mo fs y n c h r o n o u sv a c a t i o no fm u l t i a g e n t s y s t e m ，q u e u i n ga l g o r i t h mo fa s y n c h r o n o u sv a c a t i o no fm u l t i a g e n t s y s t e m ，q u e u i n ga l g o r i t h mo fs y n c h r o n o u sv a c a t i o ni np a r t l ys e r v e r s o fl f l u l t i - a g e n t s y s t e ma n dq u e u i n ga l g o r i t h mo fa s y n c h r o n o u s v a c a t i o ni np a r t l ys e r v e r so f m u l t i a g e n ts y s t e m 3 g i v e na ne x a m p l es y s t e m ：t h et r a f f i cs c h e d u l i n gs i m u l a t i o ns y s t e m t h r o u g ht h ew o r ka b o v e ，o no n eh a n d ，w ed e s i g nq u e u i n ga l g o r i t h m so f m u l t i a g e n ts y s t e m ，a n dw er e a l i z eas i m u l a t i o ns y s t e m o nt h eo t h e rh a n d ； t h ew o r kh e l p sp e o p l ef i n dan e w a p p r o a c ht ot h er e s e a r c ho fm u l t i a g e n t c o o r d i n a t i o n k e yw o r d s ：a g e n t ，m u l t i a g e n ts y s t e m ，m u l t i a g e n tq u e u i n ga l g o r i t h m w r i t t e nb y ：c a of e n g x u e s u p e r v i s e db y ：l if a n z h a n g 苏州大学学位论文独御性声明及使用授权声明 学位论文独剖性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的成巢。除文中已经注明引用的内容外，本论文不含其他个人或集体已经发 表或撰写过的研究戏果，也不含为获得苏州大学或其它教育枧拘的学位证书面使用 过的材料。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人承担本声明的法待责任。 研究生签名：墟避h 期：迎。墨垃 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清牮大学论文合作部、中 国社科院文献信患情报中心有权保留本人所送交学位论文的复印件翻电子文档，霹 以采鼹影印、缩印或其他复制手段保存论文。本人电子文措的内容和纸质论文的内 容相一一致。除在保密期内的保密论文外，允许论文被遣阅和借阅，司1 以公命( 包括 刊登) 论文的垒部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名；噎国宝日期：2 旦厶垒趁 导师签 躲秽矽 多a g e n t 系统排队算法及应用研究 第一章引言 1 1 多a g e n t 排队系统的研究进展 如何建立在一起工作的计算机系统是目前计算机科学、智能科学、 通讯等领域普遍关注的问题。随着计算机系统越来越复杂，将智能a g e n t 集成起来则更具有挑战性。因此，协调与协作是多a g e n t 研究的核心之 - - 1 1 。排队是实现多a g e m 协调与协作的关键技术。 所谓多a g e n t j p 队系统是指由多个申请服务的顾客a g e n t 矛n 多个提供 服务的服务台a g e n t 组成的一个较为松散的组织，由协调a g e n t 通过调度 来协调它们的行为。多a g e n t 排队系统以自主的a g e n t 为中心，使多a g e n t 的知识、愿望、意图、规划、行动协调，以至实现自己的目标。多a g e n t 排队系统是一个动态的，不存在全局控制的系统。并且，每一个a g e n t 具 有有限信息资源和问题求解能力，缺乏实现协作的全局观点。 1 经典排队系统理论源于丹麦工程师爱尔朗( a k e r l a n g ) 关于电话服 务的研究。1 9 0 9 年，他为了提高通信效率，研究了电话系统的排队问题。 2 0 世纪中期以来，随着计算机通讯网络、柔性制造系统、异步转移模式 等高新技术领域的发展，提出了大量的复杂系统设计和控制问题。2 0 世 纪7 0 年代，经典排队模型在处理这类问题时表现出极大的局限性，于是 出现了休假排队的研究。l e v y 与y e c h i a l i 从有效利用系统闲期的观点出 发，首先研究了m g l 型休假排队系统，并引入了“休假”和“休假策略” 等术语。利用闲期对服务设施进行调整维修，或者服务员在闲期中休假， 或者从事辅助性工作的排队系统称为休假服务系统。【2 】 多a g e n t ) 艮务台休假排队系统是在经典排队系统的基础上再添加一 个休假策略，针对不同的应用背景，引人各种各样的休假行为和多a g e n t 群集的思想，而形成的计算机系统。 一般排队系统主要有三部分组成：输入过程、服务机构以及排队规 第一帝 多a g e n l 系统排队算法及应用研究 则组成。 输入过程是描述顾客a g e n t 来源及顾客a g e n t 是按怎样的规律抵达 排队系统。a ) 顾客a g e n t 总体数：顾客a g e n t 的来源可能是有限的，也可 能是无限的。b ) 到达的类型：顾客a g e n t 是单个到达，或是成批到达。c ) 相继顾客a g e n t 到达的间隔时间服从什么样的概率分布，分布的参数是 什么，到达的间隔时间之问是否独立。根据到达间隔时间所服从的分布 输入过程可分为定长输入、( 负) 指数输入( p o i s s o n 输入) 、k 价爱尔朗 输入、超指数输入、几何输入、一般输入等。 刻划服务机构的主要要素有：a ) 服务台a g e n t 的数目。在多个服务台 的情形下，是串联或是并联。b 】顾客a g e n t 所需服务台a g e n t 时间服从什 么样的概率分布，每个顾客a g e n t 所需的服务时间是否相互独立，是成 批服务或是单个服务等。常见顾客a g e n t 的服务时间分布有：定长分布、 负指数分布、超指数分布、k 价爱尔朗分布、几何分布、一般分布等。 排队规则是指允许不允许排队，顾客a g e n t 是否愿意排队。在排队等 待的情形下服务的顺序是什么，分为：a ) 损失制：顾客a g e n t 到达时，若 所有服务台a g e n t 均被占，服务机构又不允许顾客a g e n t 等待，此时该顾 客a g e n t 就自动离去。b ) 等待制：顾客a g e n t 到达时，若所有服务n a g e n t 均被占，他们就排队等待服务。在等待制系统中，服务顺序又分为：先 到先服务( f c f s ) 、后到先服务( l c f s ) 、随机服务( r o s ) 、优先非抢 占服务、优先抢占服务等。c ) 混合制：损失制与等待制的混合，分为队长 ( 容量) 有限的混合制系统，等待时间有限的混合制系统( 等待时间固 定的时间，否则就离去) ，以及逗留时间有限制的混合制系统。 3 】 由于每个人或物都有不同的目标，为了对目标、资源等进行合理安 排，以调整各自行为，最大程度的实现各自的目标，以至产生了排队。 例如：上下班公共汽车，等待公共汽车的排队；顾客到商店购物形成的 排队：病人到医院看病形成的排队；往售票处购票形成的排队等；另一 种排队是物的排队，例如文件等待打印或发送；路口红灯下面的汽车、 自行车通过十字路口。现实世界中的公共汽车、顾客、病人、售票处、 文件、路口红灯等实体，在虚拟的因特网中都可以看成一个自主的a g e n t 。 多a g e n t 系统排队算法及应用研究 这是由于a g e n t 是一个具有感知能力：问题求解能力和与外界进行通讯 能力的一个实体。 1 2 问题的提出 在一个分布开放的多a g e n t 系统中，a g e n t 之间有着不同的目标。每 个a g e n t 在试图实现它的目标时，可能会与其他的a g e n t 发生冲突。其 主要表现就在于对资源的占用冲突。因此为了使a g e n t 能发挥其效率， 就必须解决a g e n t 问对资源的冲突使用。关于多a g e n t 协调方面的研究， 已有不少文献，例如文献 4 1 5 。 文献 4 通过建立多a g e n t 协调机来解决企业中的功能单元。文献【5 ，6 通过定义协商问题、协商协议和协商策略，来实现电子市场中出现矛盾 时的协商。文献 7 9 是在出现矛盾时提出的解决策略。文献 1 1 ，1 2 幂u 用动 态模糊逻辑理论提出了多a g e n t 协调工作机制的研究。文献 1 3 提出了一 种在交通运输方面的协调技术。文献 1 5 通过组合理论来研究多a g e n t 协 调问题。 由于以上的研究大多是在出现冲突以后，提出的解决方案。而为了 避免冲突的发生，李凡长教授首次利用排队理论引发了多a g e n t 系统的 排队模型 1 6 ，1 7 ，该模型的建立帮助人们解决多a g e n t 系统中的协调 问题开拓了新的途径。本文试图在李凡长教授提出的多a g e n t 排队模型 的基础上，主要以算法再度做进一步的研究，给出多a g e n t 系统的排队 算法。 1 3 内容安排 综上所述，本文的研究内容分为六章： 第一章主要对多a g e n t 排队系统的研究进展做了简单的介绍。 第二章介绍了多a g e n t 排队系统的基本理论。 第三章给出多a g e n t 排队系统的体系结构，并构造了单a g e n t 的基本 要素，如a g e n t 的心智状态形式化描述、a g e n t 的感知器算法、a g e n t 的知 第一章 多a g e n t 系统排队算法及应用研究 识库、a g e n t 的规划模块以及通信模块等。 第四章介绍多a g e n t 排队算法思想，详细介绍实现排队算法的四个 过程；在各种休假模型的基础上，实现了四种排队算法。 第五章给出了多a g e n t 排队算法在交通调度模拟系统中的应用。 第六章对本文内容做了总结，并对下一步的工作给予展望。 多a g e n t 系统排队算法鼓j 监用研究 l f 二章 第二章多a g e n t 排队系统的基本理论 为了研究多a g e n t 的排队问题我们给出一些基本概念。 1 6 1 8 】 2 1a g e n t 状态的生灭概念 定义2 1 假定多a g e n t 系统中，顾客a g e n t 状态元素对应一个 非负整数集 o 1 一) 上的m a r k o v 过程陋( r ) ，o ) ，如果其中有下列三对角 形式： q = 一九五。 ，一( 丑+ )丑 鸬一( 以+ 段)五 - ( 以+ 从) 五j ( 2 1 1 ) 则称扭( f ) ，o ) 是一个a g e n t 状态的生灭过程。执，刀o ) 称为a g e n t 状 态的生率， z , ，盯1 称为a g e n t 状态的灭率。引入瞬时状态概率 p ，( f ) = p i x ( t ) = _ ，歹= o ，1 ， a g e n t 状态的生灭过程的最基本特征是：在充分短的时间内，过程几乎只 能转移到相邻的状态上，即当f 寸0 时，有 e ( x ( t + a t ) = 庀l x ( f ) = ) = a j a t + o ( a t ) ，k = j + 1 1 嚣? p - 篙j o j ( a t l ) ，k ：j 注心) 一( 九+) +，= j 、。 o a t ，i k - j i 2 定义2 2由式( 2 1 2 ) 出发，建立a g e n t 状态的瞬时概率p ，( ，) 的微 分方程如下： i 笺p 劣省地嵋p 川 仁，司 lp ：( f ) = 一乃一川( f ) 一( 乃+ ，) p ，( f ) + ，。，。o ) 。7 墨三翌兰垒g ! 坐墨篓篓坠墨堡丝壁旦堕! ； 式( 2 1 3 ) 称为a g e n t 状态的生灭过程的k o l m o g o r o v 方程。如果极 限 p ，= 脚p j ( t ) ， j = o ，l ， ( 2 1 4 ) 存在，并且p 。+ p 。+ = 1 ，则称过程是正常返的a g e n t 状态，并称 p ，0 ) 为a g e n t 状态过程平稳概率分布或稳态分布。a g e n t 生灭过程的 重要问题之一是如何从生成元式( 2 1 1 ) 出发，判断a g e n t 状态过程的正 常返状态特征性并给出它的稳态分布。如果稳态分布存在，由式( 2 1 4 ) 必有! i m p i = o ，歹= o ，l ， 在式( 2 1 3 ) 的两端取极限，给出 等p 。二篙，z 加，p j ，乩脚 c 2 ”， 【- 一。，一一( t + 以) p ，+ 以+ + ，= o ，l 、。 如果把稳态分布写出无穷维向量万= ( p o ，a ，) ，式( 2 1 5 ) 可改写成更 紧凑的矩阵形式 石q = o ，席= l ( 2 1 6 ) 式( 2 1 5 ) 和( 2 1 6 ) 统称为a g e n t 状态过程的平衡方程( 及正规化条件) 。 求解差分方程( 2 1 5 ) 可给出a g e n t 状态过程的平稳概率分布。另一个更 直接的方法有k a r l i n 与m c g r e g o r 给出。 定理2 1 ( k a r l i n m c g r e g o r )a g e n t 状态的生灭过程式( 2 1 1 ) 正 常返当且仅当垒鱼尘 0 ( 2 2 4 ) 现在考虑二次方程 c 2 2 2 一r 旯+ c 2 ) z ：+ 兄= 0 ( 2 2 5 ) 它的两个根是z = p = 3 , ( c 2 ) 1 c ，满足( 2 2 4 ) ，其中k 是 待定常数。在式( 2 2 4 ) 中，取k = c + l ，给出 名石一2 r ( + ( a x 一( 五+ c u ) k p + q 螂2 ) = 2 ( n c k ) = 0 于是k = 7 t 。对k c 时，我们有 曩= 。，* - c ，k c 现在，只要再确定，石i ，7 c 。 ( 2 2 6 ) 由平衡方程( 2 1 6 ) 及( 2 2 3 ) ，并 兰垒! 竺! 墨竺篓坠墨堡丝丝型竺坚 注意到以+ 。= 7 。p ，得到 一h o + p 7 c l = 0 h k l 一( 九+ k ) r e k + ( k + 1 ) p ) k + = o ，l k c i 【h 。一+ 【- ( 九+ c ) + c p k 。= 0 如果引入c + 1 价方阵 b p = 一五 五 ： 卢一( a + ) a ( c 1 ) 一( 五十( c 1 ) ) 旯 c - ( 旯+ c ) + c # p ( 2 2 7 ) 我们并不算出c # p = 五，是为了在后面的讨论中加以比较。，万j ，一，7 。满 o r o ，7 i ，一，以) b 纠= 0 ( 2 2 8 ) 求解方程( 2 2 8 ) 并应用表达式( 2 2 6 ) ，给出多a g e n t 系统的m m c fk 寻1 2 j , ，o c 其中常数因子k 可由正规化条件确定 = 争k ：o 三k ( 丢) + 西1 ( 昙) 。( ，一p 广) 定理2 2 经典生灭过程( 2 2 3 ) 正常返，当且仅当方程( 2 2 5 ) 的 最小非负解p 落入( 0 ，1 ) 区f n q 内，并且线性方程组( 7 l 。，石l ，- ，石。) b p 】- 0 有正解。当过程正常返时，稳态分布可表示为巩= 死，尼2 c 而砜，以有方程组( ，即，万。) 研纠= 。，喜去( 皂) + 石( 1 一p ) = 】 唯一确定。 2 3a g e n t 状态的拟生灭过程 型兰童 墨皇g ! ! ! 叠堕塑! 坠墨垄丝生旦! ! 塑 设 ( f ) ，( f ) 的状态空间是q = ( 尼，办尼o ，1 肌) 并且生成元可 以表示为 p = a oc o b l ac bac bac ( 2 3 1 ) 式( 2 3 1 ) 中所有的子块是m 价方阵。为适应生成元的分快结构，将稳 态分布写成分段向量。 7 ( q = l i m p x ( t ) = k ，j ( ，) = _ ) ，( 七，) q ， 7 r 女= ( j r l ，r h ) ，i | 0 ， 万= ( 7 l o ，石i ，7 l ) 。 定理2 3q b d ( 2 3 1 ) 正常返当且仅当矩阵方程月2 b + r a + c = 0 的最小非负解r 满足卵( r ) 1 ，并且线性方程组 ，r o ( a o + 砧。) = 0 ，n o ( i - r ) 一e = 1 有唯一正确。过程的稳态分布可表示为以= 万。r ，七0 定理2 4 形如( 2 2 2 ) 的复杂边界q b d 过程正常返当且仅当矩阵 方程月2 b + r a + c = 0 的最小非负解r 的谱半径妒似) 0 ，或x 女2 署w ( k ) x k 0 时则判x 国，：若d ( x ) l 。 定义3 2 设 x 。，门= 1 , 2 ，) 是所有领域中一列独立同分布的a g e n t 知 识量，分布函数均为f ( t ) ，假定f ( o ) l 。记 z = 可以】= f x a f ( x ) 0 i t o o ， 瓦= z ；胛l ，瓦：；0 ， ( f ) = s u p n ，s f ) ， 这里，平均( 期望) 更新时i 司i n i n ，瓦是第n 次更新发生的时间， n ( 0 表示a g e n t 在时间【o ，q 中发生的知识更新次数。 其中，m ( f ) = e ( f ) 】称为a g e n t 知识的更新函数，7 卣m ( t ) = e ( f ) 。 m ( f ) 的导数兄( f ) = 兰埘( f ) = e l ( t ) 。a f t ) 是只( ，) 的知识更新强度。 多a g e n t 系统排队算法及碰用研究 3 2 4 a g e n t 的通信模块 在多a g e n t 排队系统中，每个a g e n t 自主的运行，但是由于每个a g e n t 仅拥有不完全的信息和问题求解能力，所以多个a g e n t 必须相互通信、 协同工作。通信是协作的基础。采用消息通信是实现灵活复杂的协调策 略的基础。使用规定的协议、a g e n t 彼此交换的信息可以用来建立通信和 协作机制。 通信模块主要包含如下的部分 1 ： 1 s o c k e t 接口：它的功能是将直接与协议有关的通信部分组合在一 起，并给通信模块的其它部分提高一种通信方式，使通信模块的 其它部分不用再考虑与发送协议有关的部分。s o c k e t 接口包含以 下内容。 服务线程：s o c k e t 接口中有一个服务线程，它使用一个 s e r v e r s o c k e t 不停地监听a g e n t 的端口地址，一旦发现有消息到 来，就启动一个消息线程处理这个消息，然后继续监听。 消息线程：有服务线程启动。它的任务是读入消息，并将消息送 到接受缓冲区。 客户线程：由发送线程启动。它的任务是将消息通过s o c k e t 发出。 2 接受缓冲区：用来缓存从外界发来的消息。 3 发送缓冲区：用来缓存向外界发送的消息。 4 发送进程：是一个常驻线程。它的任务是不断监视发送缓冲区， 一旦有消息进入发送缓冲区就启动s o c k e t 接口中的方法来将消息 发出。 5 接受线程：它的任务是不断查看接受缓冲区，一旦有消息进入接 受缓冲区就启动一个过滤线程来对消息进行解释和处理。 6 过滤线程：有接受线程启动。它调用语法分析将接受到的字符流 的消息转换成符合语法结构的原语，然后调用解释器来对原语解 释。 7 解释器：解释并处理一些简单的且仅与通信模块有关的一些通信 第三章多a g e n t 系统排队算法及应用研究 原语。 8 地址薄：通信模块保留a g e n t 的地址薄信息。 9 消息发送函数：调用转化函数将原语转化成字符流放入发送缓冲 区。 下面介绍几种常用的消息： b i n d ( a g e n t u r l ，s e n d e m a m e ，r e c e i v e r u r l ) 发送注册消息给对方 s h u t d o w n ( c o n t e n t ，s e n d e r n a m e ，r e c e i v e r u r l ) ； 发送注销信息给对方 i n q u i r e ( c o n t e n t ，s e n d e m a m e ，r e c e i v e r u r l ，s e n d e r u r l ) ； 询问接受a g e n t 信息 r e q u e s t ( c o n t e n t ，s e n d e m a m e ，r e c e i v e r r u r l ，s e n d e r u r l ) ； 向接受a g e n t 发送请求信息 3 2 5 a g e n t 的规划模块 在a i 领域，规划是通过模拟人类求解复杂问题的过程而形成的一种 方法。规划的问题求解方法分为两个过程：规划过程和执行过程。其中， 规划过程是针对某一任务，求取完成该任务的动作序列，这动作序列 称为计划。计划是规划过程的输出结果。执行过程是指按照集合实现问 题求解，并监控问题求解的进行，当出现意外情况计划无法执行时，调 整行为集合或再次规划，直至任务完成。 a g e n t 的规划模块负责建立中短期的行动计划。它是一个局部的规 划。每个a g e n t 根据目标集合、自身的状态、对环境和其它a g e n t 的了 解，以及以往的经验规划自身的行为。 a g e n t 规划常用方法之一是将a g e n t 的计划库定义为一个与或图结 构，其中，每一条计划由4 部分组成。 1 ) 计划目标表示该计划能达到的目标； 2 ) 计划的前提表示计划执行需要满足的条件； 多a g e n t 系统排队算法及应用研究 第三市 3 ) 计划体表示计划内容，由计划序列和计划子目标组成： 4 ) 计划执行结果表示执行计划后外部世界的更新结果。 有了这些基本要素以后，我们可以根据需求构造基本的a g e n t 了， 下面给出a g e n t 的工作流程及算法。 园 图3 2a g e n t 的工作过程 3 2 6 a g e n t 工作流程及算法 1 、a g e n t 的工作原理 a g e n t 工作过