维普资讯 http://www.cqvip.com 计算机科学２００７Ｖｏ１．３４Ｎｏ．５ 基于面向自治计算的Ａｇｅｎｔ系统动态重构模型 ） 陶丽 张自力 （西南大学智能软件与软件工程实验室 重庆４００７１５） （迪肯大学工程与信息技术系 澳大利亚ⅥＣ３２１７） 摘要动态重构问题是支持Ａｇｅｎｔ系统对环境自适应的关键挑战之一，亦是Ａｇｅｎｔ领域亟待解决的关键问题。面 向自治的计算是一种全新的自底向上解决问题的计算范型，擅于提取并刻画复杂、自组织系统的行为规则，特别适合 于对复杂问题和复杂Ａｇｅｎｔ系统进行建模。因此，本文采用面向自治的计算ＡＯＣ（Ａｕｔｏｎｏｍｙ Ｏｒｉｅｎｔｅｄ Ｃｏｍｐｕｔｉｎｇ）， 提取出了基于多Ａｇｅｎｔ的动态重构模型ＡＤＲＭ，重点讨论了模型中自治实体、环境、自治实体行为等关键要素的定 义，分析了该模型如何能够实现动态重构，并提供了ＡＤＲＭ有效工作的动态重构算法ＡＳＤＲ（Ａｇｅｎｔ Ｓｙｓｔｅｎｒ Ｄｙｎａｍｉｃ Ｒｅｃ０ｎｆｉｇｕｒａｔｉ０ｎ）。经实验验证，在任务和环境动态变化的情况下，模型ＡＤＲＭ能够较好地解决Ａｇｅｎｔ系统的动态重 构问题。 关键词 多Ａｇｅｎｔ系统，动态重构，面向自治的计算ＡＯＣ，模型 Ｄｙｎａｍｉｃ Ｒｅｃｏｎｆｉｇｕｒａｔｉｏｎ Ｍｏｄｅｌ ｏｆ Ｍｕｌｔｉ－ａｇｅｎｔ Ｓｙｓｔｅｍｓ Ｂａｓｅｄ ｏｎ Ａｕｔｏｎｏｍｙ Ｏｒｉｅｎｔｅｄ Ｃｏｍｐｕｔｉｎｇ ＴＡ０ Ｌｉ ＺＨＡＮＧ Ｚｉ—Ｌｉ ， （Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｏｆｔｗａｒｅ ａｎｄ ｏＳｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｏｕｔｈｗｅｓｔ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｏｎｇｑｉｎｇ ４００７１５） （Ｓｃｈｏｏｌ ｏｆ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ，Ｄｅａｋｉｎ，Ｇｅｅｌｏｎｇ，Ａｕｓｔｒａｌｉａ，ＶＩＣ ３２１７） Ａｂｓｔｒａｃｔ Ｄｙｎａｍｉｃ ｒｅｃｏｎｆｉｇｕｒａｔｉｏｎ ｈａｓ ｂｅｅｎ ｌｉｓｔｅｄ ａｓ ｏｎｅ ｏｆ ｔｈｅ ｋｅｙ ｃｈａｌｌｅｎｇｅｓ ｉｎ ｓｕｐｐｏｒｔ ｏｆ ｇＡｅｎｔ ａｄａｐｔａｔｉｏｎ ｔＯ ｅｎｖｉ— ｒｏｎｍｅｎｔｓ，ｗｈｉｃｈ ｈａｓ ａｔｔｒａｃｔｅｄ ｍｕｃｈ ａｔｔｅｎｔｉｏｎ ｏｆ ｒｅｓｅａｒｃｈｅｒｓ ｗｏｒｌｄ ｗｉｄｅ．Ｔｏ ｔａｃｋｌｅ ｔｈｉｓ ｔｏｕｇｈ ｐｒｏｂｌｅｍ，ａｎ Ａｇｅｎｔ－ Ｂａｓｅｄ Ｄｙｎａｍｉｃ Ｒｅｃｏｎｆｉｇｕｒａｔｉｏｎ Ｍｏｄｅｌ（ＡＤＲＭ）ｉｓ ｐｒｏｐｏｓｅｄ ｆｒｏｍ ｔｈｅ ａｕｔｏｎｏｍｙ－ｏｒｉｅｎｔｅｄ ｃｏｍｐｕｔｉｎｇ（ＡＯＣ）ｐｏｉｎｔ ｏｆ ｖｉｅｗ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｓ ａｎ ａｕｔｏｎｏｍｙ－ｏｒｉｅｎｔｄｅ－ｃｏｍｐｕｔｉｇｎ ｍｏｄｅｌ ＡＤＲＭ，ｆｏｒ ｓｏｌｉｖｎｇ ｇＡｅｎｔ ｓｙｓｔｅｍ ｄｙｎａｍｉｃ ｒｅｃｏｎｆｉｇ— ｕｒａｔｉｏｎ．Ａｎｄ ａｎ ａｌｇｏｒｉｔｈｍ ＡＳＤＲ（Ａｇｅｎｔ Ｓｙｓｔｅｍ Ｄｙｎａｍｉｃ Ｒｅｃｏｎｆｉｇｕｒａｔｉｏｎ）ｈａｓ ｂｅｅｎ ｄｅｖｅｌｏｐｅｄ ｆｏｒ ｉｍｐｌｅｍｅｎｔｉｎｇ ｒｅｃｏｎｆｉｇｕｒｉｎｇ．Ｉｎ ｏｒｄｅｒ ｔＯ ｔｅｓｔ ｔｈｅ ｅｆｆｉｃｉｅｎｔ ｏｆ ｔｈｉｓ ｍｏｄｅｌ，ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔｈｉｓ ｍｏｄｅｌ ｗａｓ ｉｎｖｅｓｔｉｇａｔｅｄ． Ｋｅｙｗｏｒｄｓ Ｍｕｌｔｂａｇｅｎｔ ｓｙｓｔｅｍ，Ｄｎａｍｉｃ ｒｅｃｏｎｆｉｇｕｒａｔｉｏｎ，Ａｔｏｎｏｍｙ ｏｒｉｅｎｔｅｄ ｃｏｍｐｕｔｉｎｇ，Ｍｏｄｅｌ １ 引言 者借鉴博弈论和社会学的方法，对在动态网络中构建健壮、敏 捷的Ａｇｅｎｔ动态联盟进行了探索［８］。目前，中科院的诸葛海 多Ａｇｅｎｔ系统和混合多Ａｇｅｎｔ系统在探索大规模分布式 研究员领导的小组也在与该问题类似的方面展开研究，称为 开放系统和理解、刻画现实世界中的许多复杂问题都有非常 “网络资源的智能聚融”（ｈｔｔｐ：／／、＾ｒ、ｖｗ．ｓｅｒｎｇｒｉ．ｄｎｅｔ／）。 广泛的应用［１０］。但在基于多Ａｇｅｎｔ的应用中，有一个亟待 ｇＡｅｎｔ系统的动态重构与Ａｇｅｎｔ联合关系密切，它实际 解决的困难问题，即在用户需求、Ａｇｅｎｔ所处环境、甚至Ａ— 上是对某种Ａｇｅｎｔ联盟联合成功后的动态管理过程。联合是 ｇｅｎｔ本身均可动态变化的情况下，如何根据任务或者环境的 多Ａｇｅｎｔ系统和电子商务领域的研究热点。Ｓｈｅｈｏｒｙ等提出 变化来动态重构基于多Ａｇｅｎｔ的系统，以避免因静态的组织 了一个在大规模电子市场中的多Ａｇｅｎｔ联盟形成模型，描述 结构造成不恰当的甚至是错误的配置，造成错误的解决方案 了Ａｇｅｎｔ加入、离开直至达到联盟稳定状态的宏观行为［９ ； 或者产生不可接受的严重质量问题。 Ｎａｔｈａｎ Ｇｒｆｆｉｔｈｓ和Ｍｉｃｈａｅｌ Ｌｕｃｋ给出了基于动机和信任的联 事实上，这一问题称为“运行时重构与重设计”，被列为 盟形成机制，阐述了自利的Ａｇｅｎｔ如何建立、维持、解体一个 支持Ａｇｅｎｔ对环境自适应能力的关键挑战之一Ｌ３］。针对这一 部落（Ｃｌａｎ）的过程Ｌ１ ；Ｗｏｏｌｄｒｉｄｇｅ和Ｊｅｎｎｉｇｎｓ提出了完整的 问题，国内外学者探索了多种解决途径。Ｓｙｃａｒａ等提出了利 包含联合意图、全局规划等协商各阶段的多Ａｇｅｎｔ协作问题 用不同种类的中间Ａｇｅｎｔ，以实现系统中Ａｇｅｎｔ的动态增加 求解方案Ｌ１ ；Ｋｒａｕｓ等人提出了一种协议，某个Ａｇｅｎｔ可以 或删除［４ ；Ｈａｎｎｅｂａｕｅｒ提出了侧重于个体Ａｇｅｎｔ（微观）而不 用边际启发和专家启发的方法来选择联盟的伙伴，而不需要 是社会（宏观）级别的两种重配置操作——“Ａｇｅｎｔ合并”与 确切地知道其他Ａｇｅｎｔ完成子任务的耗费，从而使Ａｇｅｎｔ面 “Ａｇｅｎｔ分解，，［ ；Ｐａｌｍａ等研究者探索了修改系统中Ａｇｅｎｔ 对不完全信息可以更好地形成联盟［１ ；Ｌｅｒｍａｎ等人提出了 地理分布的重构技术［６ ；ｖａｎ ｄｅｒ Ｈｏｅｋ和Ｗｏｏｌｄｒｉｄｇｅ提出了 一种基于动态物理微分方程的Ａｇｅｎｔ进出联盟管理方法，通 授权和协作的动态逻辑（Ｄｙｎａｍｉｃ Ｌｏｇｉｃ ｏｆ Ｄｅｌｅｇａｔｉｏｎ ａｎｄ ｏＣ— 过增大模型的普遍性和复杂性允许Ａｇｅｎｔ在一定条件下离 ｏｐｅｒａｔ￣ｎ，ＤＣＩ，ＰＣ），变量可以在Ａｇｅｎｔ联盟中动态分配，使 开联盟，并能计算联盟的总体效用［１引。 得联盟的能量结构（Ｐｏｗｅｒ Ｓｔｒｕｃｔｕｒｅ）发生变化Ｌ７ ；一些研究 但是在以上的研究中，都没能提出一个在任务个数、要 ＊）本课题得到国家教育部重点项目基金（１０４１６０）资助。陶丽硕士研究生，研究方向为人工智能，面向自治的计算。张自力教授，研究生 导师，目前从事人工智能、基于代理的计算、混合智能系统等方面的研究。 ・１４７・ 维普资讯 http://www.cqvip.com 求，Ａｇｅｎｔ的个数、能力均动态变化情形下，使完成任务的多 Ａｇｅｎｔ系统本身自适应变化的有效解决途径。 为此，本文采用一种新的计算范型——面向自治的计算 （Ａｕｔｏｎｏｍｉｃ Ｏｒｉｅｎｔｅｄ Ｃｏｍｐｕｔｉｎｇ，简称ＡＯＣ）＿１ ，提取出了 Ａｓ［ＩＲ来实现问题４的解决。 在本文中，我们将重点对模型的系统结构、动态重构实现 机制进行详细的阐述。 Ａｇｅｎｔ系统动态重构的抽象模型ＡＤＲＭ，设计了完成动态重 构的算法ＡＳＤＲ（Ａｇｅｎｔ Ｓｙｓｔｅｍ Ｄｙｎａｍｉｃ Ｒｅｃｏｎｆｉｇｕｒａｔｉｏｎ）。 ３为什么采用面向自治的计算ＡＯＣ 面向自治的计算ＡＯＣ，是一种非常适用于提取并刻画复 由于系统的动态重构可能涉及到Ａｇｅｎｔ系统的重新形成，因 此，我们改进了面向多Ａｇｅｎｔ解决ＣＳＰ问题的算法ＥＲＡ （Ｅｎｖｉｒｏｎｍｅｎｔ，Ｒｅａｃｔｉｖｅ ｒｕｌｅｓ，ａｎｄ Ａｇｅｎｔｓ）Ｄ６］用于支持重构 问题，该算法另文讨论ｌ＿】 。 本文第２节将首先描述动态重构问题在现实世界中的一 个真实场景；第３节将重点阐述为什么面向自治的计算ＡＯＣ 适用于动态重构问题的解决；第４节将介绍基于ＡＯＣ的动态 杂、自组织系统的行为规则的计算范型＿１ ，已经被广泛应 用到约束满足问题求解ｌ＿ｌ６］、图像特征提取ｌ＿】川、优化ｌ＿】 等众多 领域当中。 一个Ａ０Ｃ的形式框架是一个三元组（｛ｅ１，ｅ２，…，ｅＮ｝， Ｅ， ＞。其中｛ｅ ，ｅ “，ｅ ）是自治实体，Ｅ是环境， 是整个 系统的目标函数。一个自治实体包括感受器（一个或多个）、 效应器（一个或多个）和一个本地行为规则库。自治实体被定 重构系统ＡＤＲＭ模型和ＡＳＤＲ算法；第５节给出实验结果以 及讨论；最后对全文进行总结，并对未来工作进行展望。 ２ Ａｇｅｎｔ系统动态重构例示 动态重构问题普遍存在于基于Ａｇｅｎｔ的系统中。为了更 好地阐述本文将解决的动态重构问题，本文选择国际贸易Ａ— ｇｅｎｔ竞赛中的供应链管理单元作为研究背景（ｈｔｔｐ：／／ｗｗｗ． ｓｉｃｓ．ｓｅ／ｔａｃ）（ＴＡＣ ＳＣＭ）。在ＴＡＣ ＳＣＭ中，Ａｇｅｎｔ将模拟一 家小型计算机装备工厂的管理人员，它需要对从原料获取、产 品生产到完成客户订单的整条供应链进行良好的管理，以获 取最大的利润。为更好地阐明何种情况需要动态重构，在原 有的应用背景基础上，依据对现实世界需求的分析，本文引入 了３种动态变化的情况。 ・每一种原料的供应商是不稳定的。除了ＴＡＣ ＳｃＭ原 本规定的两家外，还有无数家供应商愿意提供他们的原料。 原料供应商的总数目和各自的报价可能每天都在改变。 ・每个原料供应商的状态是变化的。比如某个供应商可 能会一夜破产或者阕为一些其他不可抗力导致无法按时到 货。 ・在订货后的某个时间范围内，客户的需求是可以改变 的。比如，某个客货的订单表明他只需要由ＣＰＵ、主板、内存 和硬盘组装的电脑，但在订货的第２天，他又希望每台电脑都 能拥有ＤＶＤ光驱。 由于现有的经典供应链管理模型和ＴＡＣ ＳＣＭ参赛选手 的解决方案都忽略了这样的动态情形，因此现有的策略不能 满足这样的动态变化要求。 为了实现如场景中描述的动态重构情况，我们构建的动 态重构模型ＡＤＲＭ需要能够满足：（１）一种信息服务的机制， 以便系统能够检测、收集、定位需要的供应商Ａｇｅｎｔ；（２）一种 表述供应商Ａｇｅｎｔ特征的方法，以便能够较为方便地比较不 同供应商间的优劣；（３）一种能够在众多供应商Ａｇｅｎｔ中找到 最优解的算法，该算法即使在有限时间内不能找到最优，至少 也能够提供一个可以接受的次优解；（４）一种用来维持和动态 重构Ａｇｅｎｔ系统的机制。 对于问题１，本文采用一个中间Ａｇｅｎｔ——黄页Ａｇｅｎｔ， 来实现供应商Ａｇｅｎｔ的发现和注册；对于问题２，采用约束求 解和ＲｅｄｌｉｎｅＥ ］相结合的方法进行解决，把用户的每一项要 求都作为一个约束，然后采用Ｒｅｄｌｉｎｅ的方法进行匹配，从而 将每一个供应商Ａｇｅｎｔ的能力都通过一个约束值和来表示； 改进面向多Ａｇｅｎｔ解决ＣＳＰ问题的算法ＥＲＡ用以解决问题 ３；通过一个ＡＤＲＭ系统的动态重构控制器和动态重构算法 ・ 】４８・ 义为五元组＜ｓ，Ｆ，Ｇ，Ｂ，Ｒ）。其中ｓ是实体ｅ当前的状态， Ｆ是评价函数，Ｇ是系统的目标函数，Ｂ和Ｒ分别是实体的原 始行为和原始行为规则。 采用ＡＯＣ的方法提取Ａｇｅｎｔ系统动态重构的抽象模 型，就是要把系统中的元素映射到ＡＯＣ的形式框架，即抽取 并定义环境、自治实体、自治实体的本地行为规则库。 动态重构问题还可归纳为约束满足问题ＣＳＰ（Ｃｏｎｓｔｒａｉｎｔ Ｓａｔｉｓｆａｃｔｉｏｎ Ｐｒｏｂｌｅｍ）。ＣＳＰ问题的基本组成元素为变量 、 变量的域Ｄ以及约束Ｃ＿＿２ 。变量的域Ｄ是变量可能取值的 集合，变量 只能在它的域Ｄ 中进行取值；约束Ｃ描述了 变量 之间必须满足的关系。 据此，我们可以对基于多Ａｇｅｎｔ的动态重构问题进行建 模： ・网络中愿意提供服务的Ａｇｅｎｔ可以对应于ＣＳＰ中的 变量 ； ・Ａｇｅｎｔ所处的网络环境就是变量的域Ｄ； ・任务对Ａｇｅｎｔ的各种要求自然的表示为约束条件Ｃ。 本文将采用 Ｃ的方法来解决动态重构这一ＣＳＰ问 题。 ４基于ＡＯＣ的动态重构系统模型ＡＤＲＭ 基于ＡＯＣ的动态重构模型ＡＤＲＭ实际匕包含了多种 不同的Ａｇｅｎｔ：提供资源的成员Ａｇｅｎｔ（Ｍａｇ（ Ｉ），承担资源搜 寻工作的建组Ａｇｅｎｔ（Ｃａｇｅｎｔ），在联盟中执行用户任务的雇 员Ａｇｅｎｔ（Ｅａｇｅｎｔ），提供资源发现、注册、归类的黄页Ａｇｅｎｔ （ＹＰ），以及动态重构行为的控制Ａｇｅｎｔ（Ｒｅｃｏｎｆｉｇｕｒａｔｉｏｎ Ｃｏｎ— ｔｒｏｌｌｅｒ，ＲＣ）。 ＡＤＲＭ模型的体系结构如图１所示。 图１ ＡＤＲＭ模型体系结构 ４．１ Ａｇｅｎｔ系统动态重构问题形式化描述 动态重构模型 ＩＲＭ在某个时刻可形式化描述如下： 维普资讯 http://www.cqvip.com ・网络中存在 个位于不同地理位置、具备不同行为能 一个Ｍａｇｅｎｔ可表示为一个４元组： 力的成员Ａｇｅｎｔ： Ｍａｇｅｎｔ＝｛Ｍａｇｅｎｈ，Ｍａｇｅｎｈ，…，Ｍａｇｅｎｔ ｝ ・Ｍａｇｅｎｔ＝（ＭｊＤ，ＲＴ，ＣＶ，ＭＬ） 其中，ＭＩＤ：Ｍａｇｅｎｔ的唯一标识号；ＲＴ：Ｍａｇｅｎｔ提供的某种 资源类型；ＣＶ：Ｍａｇｅｎｔ所提供的某种资源约束值，采用约束 求解和匹配算法计算得出，本文不进行详细阐述；ＭＬ：Ｍａ— ｇｅｎｔ在真实网络中的所在位置。 ４．３．２建组Ａｇｅｎｔ（Ｃａｇｅｎｔ） 需要ｉ个建组Ｃａｇｅｎｔ承担资源搜索角色： 约束条件ｍ，即任务需要成员Ａｇｅｎｔ具备的ｍ种能 Ｃａｇｅｎｔ＝｛Ｃａｇｅｎｔ１，Ｃａｇｅｎｔ２，…，Ｃａｇｅｎｔ ｝ ・力： Ｃ一｛Ｃ１，Ｃ２，…， ｝ Ｃａｇｅｎｔ是形成和维持ＡＤＲＭ系统最重要的自治实体。 它由控制Ａｇｅｎｔ ＲＣ根据任务的要求或者环境的变化指派产 生相应的Ｃａｇｅｎｔ种群。Ｃａｇｅｎｔ有两个主要的功能：一是在环 ４．２ ＡＤＲＭ模型中的动态重构流程 Ａｇｅｎｔ系统的动态重构行为发生在联盟形成后、任务执 行过程中，有如下几个原因导致重构行为的发生： ・境中通过本地搜索行为，选择出最适合任务需求的Ｍａｇｅｎｔ， 组成完成任务的组织。二是组织形成，对自己挑选出来的 网络中成员Ａｇｅｎｔ执行任务的愿望是动态变化的； ・成员Ａｇｅｎｔ执行任务的能力，或者叫做可提供的资源 Ｍａｇｅｎｔ进行侦听，一旦发现该Ｍａｇｅｎｔ出现不能继续完成任 是动态变化的； ・执行任务的组员Ａｇｅｎｔ的愿望是动态变化的； ・执行任务的组员Ａｇｅｎｔ的个体能力是动态变化的； ・用户或者任务对于组员Ａｇｅｎｔ的要求是动态变化的， 这个要求包括组员Ａｇｅｎｔ的个数和个体能力等。 在ＡＤＲＭ模型中，Ｃａｇｅｎｔ、任务、Ｅａｇｅｎｔ的状态改变信息 主要是通过黄页Ａｇｅｎｔ和控制Ａｇｅｎｔ来搜集的。黄页Ａｇｅｎｔ ＹＰ将根据任务的不同要求和网络真实环境的变化，动态地 组织和管理成员Ａｇｅｎｔ，接受Ｍａｇｅｎｔ加入和退出的申请。而 控制Ａｇｅｎｔ将根据任务的不同分配相应的建组Ａｇｅｎｔ，同时 接受组员Ａｇｅｎｔ的退出申请，并指派相应的Ｃａｇｅｎｔ重新开始 建组行为。控制Ａｇｅｎｔ将会尽可能地重用以前的Ｃａｇｅｎｔ种 群，以缩短建组时间。但是，ＹＰ和ＲＣ仅仅是一个信息搜集 者、咨询者和指令发出者的角色，ＡＤＲＭ模型中最核心的部 分一组织形成和动态维护则主要是通过Ｃａｇｅｎｔ在逻辑环 境中的行为来实现的。 ＡＤＲＭ模型的动态重构流程图如图２所示。 图２ ＡＤＲＭ模型的动态重构流程图 ４．３ ＡＤＲＭ模型中的Ａｇｅｎｔ类别及原始行为 ＡＤＲＭ模型中的Ａｇｅｎｔ类别及原始行为分别定义如下： ４．３．１成员Ａｇｅｎｔ（Ｍａｇｅｎｔ） Ｍａｇｅｎｔ种群是ＡＤＲＭ模型中最基本的组成部分，是真 实网络中的一些具有任务要求的能力，并愿意提供这些能力 的自治实体。在系统的运行过程中，Ｍａｇｅｎｔ将把自己的能力 与任务的要求相匹配，并将匹配后的约束值和自己在网络中 的位置等相关信息注册到黄页Ａｇｅｎｔ当中。在系统的运行过 程中，Ｍａｇｅｎｔ整个种群的大小、个体能力、个体位置等都是动 态变化的。 务执行的状况，将向ＲＣ发起重构申请。 ４．３．３雇员Ａｇｅｎｔ（Ｅａｇｅｎｔ） 当Ｃａｇｅｎｔ搜索行为结束之后，由Ｃａｇｅｎｔ寻找到的那些 Ｍａｇｅｎｔ就构成了当前执行任务的一个组织，从而执行任务的 这些Ｍａｇｅｎｔ就转变为了Ｅａｇｅｎｔ的角色。因此，Ｅａｇｅｎｔ种群 实际上是任务的最后执行者。在任务的执行过程中，每个 Ｅａｇｅｎｔ可以根据自己的能力、愿望等变化状况，可以向控制 Ａｇｅｎｔ提出停止自己承担的任务，退出当前的组织。 ４．３．４黄页Ａｇｅｎｔ（ＹＰ） 黄页Ａｇｅｎｔ ＹＰ是Ｍａｇｅｎｔ种群的管理者。它的主要功 能是提供网络中的Ｍａｇｅｎｔ将自己的能力和相关信息注册并 存储，然后通过随机选择划分，形成逻辑环境表，以提供给 Ｍａｇｅｎｔ搜索和查询。如果某Ｍａｇｅｎｔ不愿意提供自己的能 力，那么它需要向ＹＰ申请，ＹＰ将注销这个Ｍａｇｅｎｔ的相关信 息。 黄页Ａｇｅｎｔ ＹＰ要求的注册信息是一个３元组： ＲＰｇ ５￡Ｐｒ一（ＲＴ，ＣＶ，ＭＬ）， 其中，ＲＴ：Ｍａｇｅｎｔ提供的某种资源类型；ＣＶ：Ｍａｇｅｎｔ所提供 的某种资源约束值；ＭＥ：Ｍａｇｅｎｔ在网络中的所在位置。 ４．３．５ 控制Ａｇｅｎｔ（Ｒｅｃ０ｎｆｉｇｕｒａｔｉ０ｎ Ｃｏｎｔｒｏｌｌｅｒ，ＲＣ） 控制Ａｇｅｎｔ——Ｒｅｃ０ｎｆｉｇｕｒａｔｉ０ｎ ｏＣｎｔｒｏｌｌｅｒ（ＲＣ），是建组 Ａｇｅｎｔ的分配者和协调者。根据任务的要求，ＲＣ将分配满足 用户要求个数的Ｃａｇｅｎｔ，并指派各自的搜索类型。同时，它 还能够根据Ｃａｇｅｎｔ提出的重构申请，判断到底是对Ａｇｅｎｔ系 统进行重构还是解散整个系统重新组织。本文采用要求重构 的Ｅａｇｅｎｔ占整个Ｅａｇｅｎｔ种群的比例作为判断的标志，一旦 该比例超过给定的阈值（比如０．４），控制Ａｇｅｎｔ就决定不再 实施重构，而是解散整个Ａｇｅｎｔ系统。值得注意的是，ＲＣ不 会对每个Ｃａｇｅｎｔ的本地搜索行为进行控制，只是在宏观上对 整个Ｃａｇｅｎｔ种群进行协调。 ４．４环境描述 环境是成员Ａｇｅｎｔ的所在地，也是建组Ａｇｅｎｔ行为的发 生地。这里的环境包括两个层面，一是物理环境：由 个成员 Ａｇｅｎｔ构成的实际网络环境；二是逻辑环境：即 个成员Ａ— ｇｅｎｔ注册后，经过ＹＰ的映射、划分，由各自的限制值和一些 相关信息构成的一张二维表。在后面的描述中，环境就特指 逻辑环境，它是我们动态重构行为的发生地，用于传递Ｃａ— ｇｅｎｔ感兴趣的特征，以及Ｃａｇｅｎｔ间可共享的本地知识，比如 当前的Ｍａｇｅｎｔ是否已经被其他Ｃａｇｅｎｔ挑选。 物理环境与逻辑环境的关系如图３所示。 ・】４９・ 维普资讯 http://www.cqvip.com ｆ ＋ｓ当Ｙ＋ｓ＜ｌＤ ｌ ｔｏｐ＝ｌ 当 ＋ｓ≥ｌＤ ｌ 其中，ｅ（ｘ， ）为当前建组Ａｇｅｎｔ所在位置，ｚ表行号，Ｙ表列 号ｉｓ代表搜索的步长；ｌｏｗ是当前搜索范围的下限，ｔｏｐ为上 限。 ４．５。３交叉移动（ａｃｒｏｓｓ－ｍｏｖｅ） 建组Ａｇｅｎｔ以概率ａｃｒｏｓｓ－ｐ，或者在已经无法找到更好 （ａ】 成员Ａｇｅｎｔ情况下，移动到一个新行，重新开始搜索。在选择 图３（ａ）真实网络中的Ａｇｅｎｔ构成的物理环境 （ｂ）经映射和划分后形成了逻辑环境 定义１环境的数据结构： （１）表大小 新行的时候，它可以随机选择或者选择所有成员Ａｇｅｎｔ的均 值最高的那一行，同时，还应当避免选择已经有多个建组Ａ— ｇｅｎｔ存在的行数。 定义４找到本次搜索范围内最好的成员Ａｇｅｎｔ所在位 置ｅ（ｘ， ）的函数 ａｃｒｏｓｓ为： ＩＩ ＩＩ ・ｎ行甘 个建组Ａｇｅｎｔ．Ｅ一（ｆＯＷｌ，ｒｏｗ２，…，ｒＯＷｎ＞； ・Ｖｉ∈Ｖａ， ］，ｒｏｗ 甘建组Ａｇｅｎｔ Ｃａｇｅｎｔ ｉ的行为域甘 ａｃｒｏｓｓ（ｘ， ）一 ｆｉ Ｖｔ［１， ］ ｅ（ｉ， ）＞ ｅ（ｔ， ） ． ，因此第ｉ行便有ｆ ｆ列； ｒｏｗｉ一（１ａｔｔｉｃｅ￣ｌ，ｌａｔｔｉｃｅ￣ｚ，…，ｌａｔｔｉｃｅ￣ｌ ｌ＞； ・【Ｒａｎｄｏｍ（ｎ） 建组Ａｇｅｎｔ的三种本地行为如图４所示。 Ｅ是一个大小为∑ｌ ｌ的数组。ｅ（ｉ， ）就等于ｌａｔｔｉ— ｃｑ 的位置。 （２）表值，这里的表值由两个数据项组成： ・ｅ（ｉ， ）．ｖａｌｕｅ记录了位于第ｉ行、第Ｊ列的成员Ａｇｅｎｔ ｎ 略ｎ ｎ Ｈ ｒｌ ｒ２ ｒ３ ｒ４ Ｍａｇｅｎ￣的值，即该成员Ａｇｅｎｔ满足约束值的个数，如果ｅ（ｉ， ）．ｖａｌｕｅ：ｍ，那么说明这个Ａｇｅｍ完全满足任务要求的 个 约束条件，是一个非常适合完成任务的Ａｇｅｎｔ； ・ｅ（ｉ， ）．ｖｉｏｌａｔｅ记录了位于第ｉ行、第Ｊ列的成员Ａ— ｇｅｎｔ Ｍａｇｅｎ￣是否已被挑选成为雇员Ａｇｅｎｔ的候选者。ｅ（ｉ， ）．ｖｉｏｌａｔｅ＝Ｏ，表示未被挑选，而ｅ（ｉ， ）。ｖｉｏｌａｔｅ＝ｌ，则表示已 （ａ）１６个物理环境中的真实Ａｇｅｎｔ经映射和划分后构成的逻辑 环境。（ｂ）由成员Ａｇｅｎｔ的约束值构成的４×４的表格——建组 ｇｅｎｔ存在的环境。（ｃ）某时刻，４个建组ＡＡｇｅｎｔ在环境中的位置 示意。（ｄ）下一时刻，原ｒ１行的建组Ａｇｅｎｔ采取ｂｅｔｔｅｒ－ｍｏｖｅ移 被挑选，其他的Ｃａｇｅｎｔ将不能再把这个Ｍａｇｅｎｔ作为候选者。 ４．５建组Ａｇｅｎｔ本地行为规则库 建组Ａｇｅｎｔ在环境中的行为需要遵循本地行为规则库的 规定。行为规则是自治实体Ｃａｇｅｎｔ的核心，它用来指导每个 Ｃａｇｅｎｔ如何动作，如何对从环境、黄页Ａｇｅｎｔ和控制Ａｇｅｎｔ 收集到的信息进行反应。建组Ａｇｅｎｔ的本地行为规则库定义 如下： ４．５．１较好移动（ｂｅｔｔｅｒ－ｍｏｖｅ） 动到位置（１，２）；原ｒ２行的建组Ａｇｅｎｔ采取ａｃｒｏｓｓ－ｍｏｖｅ移动到 位置（３，１）；原ｒ３行的建组Ａｇｅｎｔ已经找到最优解，不移动；原ｒ４ 行的建组Ａｇｅｎｔ采取ｂｅｓｔ－ｍｏｖｅ移动到位置（４，１）。 图４建组Ａｇｅｎｔ的本地行为示意 ４。６动态重构算法ＡＳＤＲ 建组Ａｇｅｎｔ以概率ｂｅｔｔｅｒ－ｐ移动到一个比目前所在位置 的成员Ａｇｅｎｔ更好的某个成员Ａｇｅｎｔ所在位置。 定义２找到一个更好的成员Ａｇｅｎｔ所在位置ｅ（ｘ，Ｊ） 的函数 ｂｅｔｔｅｒ为： ｂｅｔｔｅｒ（ｘ， ）一 ｌ ∈Ｅｌｏｗ，ｌＤｘ１］，ｅ（ｘ， ）．ｖａｌｕｅ￣ｅ （ｘ，ｙ）．ｖａｌｕｅ ， 动态重构算法ＡＳＤＲ（Ａｇｅｎｔ Ｓｙｓｔｅｍ Ｄｙｎａｍｉｃ Ｒｅｃｏｒｆｉｇｕ— ｒａｔｉｏｎ）用于提供Ａｇｅｎｔ系统实现动态重构。它包括对模型中 的各种Ａｇｅｎｔ初始化、侦听系统状态、俘获重构请求、发起重 构行为等工作。函数Ｒｅｆｒｅｓｈ用于在动态情况下，对Ｃａｇｅｎｔ 种群的大小、搜索任务、逻辑环境、雇员Ａｇｅｎｔ和成员Ａｇｅｎｔ 状态进行更新。函数ＯｒｇａｎｉｚａｔｉｏｎＦｏｒｍａｔｉｏｎ是在动态重构情 形下进行建组的算法，在文Ｅ１６．］中有详细阐述。 Ｆｕｎｃｔｉｏｎ ＡＳＤＲ １． Ｗｈｉｌｅ ｏｒｇａｎｉｚａｔｉｏｎ ｆｏｒｍａｔｉｏｎ ｃｏｍｐｌｅｔｅｄ ａｎｄ ｔａｓｋ ｈａｓ ｎｏｔ ａｃｃｏｍ— ｐｌｉｓｈｅｄ ２．ｄｏ ｔａｓｋ ｍｏｎｉｔｏｒｉｎｇ； ３． ｉｆ ｄｙｎａｍｉｃ ｒｅｃｏｎｆｉｇｕｒａｔｉｏｎ ａｃｔｉｏｎ ｐｕｔ ｆｏｒｗａｒｄ ４． Ｒｅｆｒｅｓｈ（Ｃａｇｅｎｔｓ，Ｅａｇｅｎｔｓ，ｅｎｖｉｒｏｎｍｅｎｔ）； ５． ｃａｌｌ ＯｒｇａｎｉｚａｔｉｏｎＦｏｒｍａｔｉｏｎ； ６． Ｅｎｄｉｆ； ７． Ｅｎｄ ｗｈｉｌｅ． ｆ１ 当ｙ－－ｓ￣ｌ ０７．１３一ＩＹ—ｓ当 —ｓ＞１ 其中，ｅ（ｘ， ）为当前建组Ａｇｅｎｔ所在位置，ｚ表行号，Ｙ表列 号；ｓ代表搜索的步长；ｌｏｗ是当前搜索范围的下限。 ４．５．２最好移动（ｂｅｓｔ－ｍｏｖｅ） 建组Ａｇｅｎｔ以概率ｂｅｓｔ－ｐ移动到一个在本次搜索范围内 约束值最高的位置。 定义３找到本次搜索范围内最好的成员Ａｇｅｎｔ所在位 置ｅ（ｘ， ）的函数 ｂｅｓｔ为： ｂｅｓｔ（ｘ， ）一 ｌ Ｊ∈Ｅｌｏｗ，ｔｏｐ］，（Ｖｔ∈Ｅｌｏｗ，￡０户］）ｅ （ｚ， ）．ｖａｌｕｅ￣ｅ（ｘ，￡）．ｖａｌｕｅ ， ５实验结果及讨论 在假设成员Ａｇｅｎｔ的个数分别为５Ｏ、１００、１０００、１００００， 建组Ａｇｅｎｔ的个数分别为４、１０、５０、１００，三种行为选择概率 （概率在０．０～１．０范围内）共６６种不同组合的情况下，我们 对ＡＤＲＭ模型的收敛和运行情况进行了实验。 ｆ１ 当ｙ－－ｓ￣ｌ 【 —ｓ当Ｙ－－Ｓ＞１ ・ １５Ｏ・ 维普资讯 http://www.cqvip.com 实验表明，只要概率选取在合理的范围内，模型都能够收 态变化的情况下，采用模型 ）ＲＭ和算法ＡＳＤＲ能够较好 敛到比较好的解。这里比较好的解指的是最优解，或者是位 地解决Ａｇｅｎｔ系统的动态重构问题。在模拟试验中，黄页Ａ— 于最优解附近一个很小范围内的解集范围内。找到较好解的 ｇｅｎｔ不断地接收未加入供货联盟的供应商Ａｇｅｎｔ的各种申 概率ｓｏｌｕｔｉｏｎ－ｐ￣９５ 。 请，动态维持建组Ａｇｅｎｔ的行为环境，并通过重构发起后的刷 图５和图６是在Ｍａｇｅｎｔｓ＝５０，Ｃａｇｅｎｔｓ一４，ｍａｘ－ｔｉｍｅ－ 新保证了环境的一致性；建组Ａｇｅｎｔ通过Ｍｏｎｉｔｏｒ模块的监 ｓｔｅｐ＝１００，ｂｅｔｔｅ￣ｐ一０．６，ｂｅｓｔ￣ｐ：０．２，ａｃｒｏｓｓ－ｐ一０．２， 控，能够及时发现联盟中的供货商供货优劣情况，比如某个供 ｛ｏｏｔ＝２，Ｍａｘ－ｅａｇｅｎｔ－ｖａｌｕｅ＝１２时的一次运行情况。在某 货商的货物迟迟不到，那么它将申请ＲＣ发起重构行为，替换 个时刻，５０个Ｍａｇｅｎｔｓ中愿意提供服务的只有３２个，这３２ 该不合格的供应商；ＲＣ还能在货物供应过程中接受客户的 个Ｍａｇｅｎｔ及它们的约束值经黄页Ａｇｅｎｔ划分后的二维表如 要求，通过对供货商联盟（Ａｇｅｎｔ系统）进行重构，使得在很短 表１所示。需要重构的成员Ａｇｅｎｔ有４个，所以分派了４个 的时间内，组建起一个新的满足用户需求的联盟。 建组Ａｇｅｎｔ来寻找合适的解。 ／ 表１ ３２个Ｍａｇｅｎｔ形成的逻辑环境， ，一 — 一 — 表中的数值为某Ｍａｇｅｎｔ的约束值 ／ １ ３ ５ ７ ９ １１ １２ １０ ／ ／ ２ ３ ４ ５ １２ １１ ７ ９ ４ ３ ５ ５ ９ １２ １２ １２ ／ ／ ／ １１ ２ ３ ５ ７ ８ １ ９ ２ ３ ４ ５ ６ ７ ８ ｘａｒ＆：ｔｈｅｔｉｍｅｂａｒ 图５表示在该次运行中Ｃａｇｅｎｔ找到的候选Ｅａｇｅｎｔ的约 束值总和随时间步变化的情况。可以看到，在第８步的时候 ∞ ｑｏ警Ｕ尝 ０ ｄ异ｎｓ ｏｑｌ｜ｓ州 蝠 图５ Ｃａｇｅｎｔ种群找到的候选Ｅａｇｅｎｔ的 就收敛到了最优解——每个Ｃａｇｅｎｔ都找到了最满足要求的 约束值总和随时间步变化的情况 Ｍａｇｅｎｔ，即约束值为１２的Ｍａｇｅｎｔ。 图６是４个Ｃａｇｅｎｔ随时间步的变化，在逻辑环境中的搜 结束语动态重构不仅是Ａｇｅｎｔ领域中一个关键问题， 寻位置变化的情况。 类似问题亦是网格领域中一个亟待解决的难问题，被称为“虚 同时，结合第２节例示的模拟实验表明，在任务和环境动 拟组织的形成和管理 。 １０ 量５ 专 ０ ８ ４ ｙａｘｉｓ：ｔｈｅ 图６ Ｃａｇｅｎｔｓ在逻辑环境中的位置变化情况 本文结合供应链管理的背景，利用最新的可计算范型 理能力，实现在不同情况下更理智、更恰当的行为选择；可以 ＡＯＣ，提取并设计出了基于多Ａｇｅｎｔ系统的动态重构模型 在模型中增加信任和信誉，防止某些成员Ａｇｅｎｔ的欺骗和雇 ＡＤＲＭ￣提出了动态重构算法ＡＳＤＲ；对模型和算法的有效性 员Ａｇｅｎｔ不负责任的随意退出行为；可以放松约束值的计算 和收敛性进行了实验型研究，证明在参数设定恰当时，能够保 方法，通过约束条件和约束值的模糊，使约束值更恰当地体现 证在可接受的时间范围内收敛。 不同资源间的差异。 ＡＤＲＭ模型从宏观上实现了在任务不同和环境变化的 情况下动态重构基于Ａｇｅｎｔ的系统；配套的ＡＳＤＲ为ＡＤＲＭ 参考文献 模型的有效工作提供了技术和方法。在Ａｇｅｎｔ领域，有了动 ｌ Ｗｏｏｌｄｒｉｄｇｅ Ｍ Ａｎ Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ｍｕｌｔｉ－Ａｇｅｎｔ Ｓｙｓｔｅｍ．Ｊｏｈｎ 态重构技术，Ａｇｅｎｔ系统可以适用于不同的任务和不断改变 Ｗｉｌｅｙ ａｎｄ Ｓｏｎｓ Ｌｔｄ，２００２ 的环境。在某种意义，Ａｇｅｎｔ系统就具有了按需而变的学习 ２ Ｚｈａｎｇ Ｚ。Ｚｈａｎｇ １２．Ａｎ Ａｇｅｎｔ—Ｂａｓｅｄ Ｈｙｂｒｉｄ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍ 和适应能力。在网格领域，动态重构技术可以对虚拟组织的 ｆｏｒ Ｆｉｎａｎｃｉａｌ Ｉｎｖｅｓｔｍｅｎｔ Ｐｌａｎｎｉｎｇ．Ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＰＲＩｃＡＩ 形成和管理提供参考和有力支持。 ２００２，ＬＮＡ１－２４７１，Ｓｐｆｉｎｇｅｒ，Ａｕｇｕｓｔ ２００２．２５５～３６４ 尽管我们提出了基于多Ａｇｅｎｔ系统动态重构的模型和算 ３ Ｌｕｃｋ Ｍ．Ｍｃｂｕｍｅｙ Ｐ．Ｐｒｅｉｓｔ Ｃ Ａ Ｍａｎｉｆｅｓｔｏ ｏｆｒ ｇＡｅｎｔ Ｔｅｃｈｎｏｌ— 法，并得到了一些初步结果，模型中还有不少问题留待进一步 ｏｇｙ：Ｔｏｗａｒｄｓ Ｎｅｘｔ Ｇｅｎｅｒａｔｉｏｎ Ｃｏｍｐｕｔｉｎｇ．Ａｕｔｏｎｏｍｏｕｓ Ａｇｅｎｔｓ 解决。比如在模型中添加启发式机制，或者给Ｃａｇｅｎｔ增加推 ａｎｄ Ｍｕｌｔｉ—Ａｇｅｎｔ Ｓｙｓｔｅｍｓ，２００４，９：２Ｏ３～２５２ （下转第１５８页） ・ １５１ ・ 维普资讯 http://www.cqvip.com