736 Proceedings of the 26th Chinese Control Conference July 26- 31, 2007, Zhangjiajie, Hunan, China 基于协进化方法的多智能体系统及其符号演绎理论模型基于协进化方法的多智能体系统及其符号演绎理论模型* 薛宏涛 , 沈林成 国防科技大学机电工程与自动化学院，长沙 10073 E- mail:xue_hongtao163.com 摘 要：协进化方法是解决多智能体协作问题的一种新途径。本文首先介绍了基于协进化机制的多智能体系统体系结 构以及协作机制，然后基于 Wooldridge 关于多智能体系统的符号模型定义了协进化智能体的符号演绎模型，包括协 进化智能体的信念、通信、动作、外部动作的评估、整合模型以及协进化决策器模型等各个方面，并将协进化智能体 模型与实际世界模型形成一个统一的闭环系统。最后，建立了基于协进化方法的多智能体系统的符号演绎理论模型。 关键词：协进化，协进化智能体，基于协进化的多智能体系统，协进化决策器，符号演绎模型 Multi- Agent System Based on Co- evolution Method and Its Symbol Deduction Theory Model Xue Hongtao, Shen Lincheng Institute of Electromechanical Engineering and Automatization, National University of Defence Technology, Changsha 410073, P. R. China E- mail: xue_hongtao163.com Abstract: Co- evolution Method is a kind of new approach for solving multi- agent collaboration problem. In this paper, we firstly introduce the multi- agent system based on co- evolution and its collaboration mechanism, then we make a series of hypotheses about co- evolutionary agent. Basing on Wooldridges symbol model of multi- agent systems, we define the symbol deduction model of co- evolutionary agent, including its belief, communication, action, evaluation and integration model of external action, and the co- evolutionary decision model . Thus, the model of co- evolutionary agent and the world can form a uniform closed loop system. At last, the symbol deduction theory model of multi- agent system based on co- evolution is estab- lished by system modeling method. Key Words: Co- evolution , Co- evolutionary Agent, Multi- Agent System Based on Co- evolution Method, Co- evolutionary Decision, Symbol Deduction Theory Model 1 引言( (Introduction) )1 1 多智能体协作是多智能体理论中的核心问题， 目 前的各种理论流派在系统构造复杂性、 系统效率方面 都没有很好的方法1,2,3,7,8。协进化作为一种模仿自然 界中物种之间协同进化而提出的计算方法， 为解决多 智能体协作问题提供了一条新的、卓有成效的途径 4,5,9,10。用协进化的方法对智能体的信念集和行为规则库进行维护更新以及通过协进化机制进行决策， 能 够极大地提高智能体适应环境的灵活性和动态适应 性。 在 Wooldridge 的博士论文中，针对智能体内部 自身信念集的维护机制， 定义了一个比较系统的多智 能体系统符号化理论模型6。但是，对于智能体与实 际世界进行交互至关重要的外部动作， 智能体如何基 于自身信念库和问题领域来有效地组织动作规则库， 以及智能体的决策机制等问题， 却没有给出更进一步 的定义和描述。我们基于 Wooldridge 关于多智能体 系统的符号模型，结合智能体之间协作的协进化机 制，对智能体的基本特性做出了符号化描述，定义了 一个协进化智能体的符号化演绎理论模型。 协进化智 能体的决策器是模型的核心部分， 我们给出了一个结 合智能体的信念库、 动作规则库等智能体自身内部特* 此项工作得到国家自然科学基金资助, 项目批准号: 60085005。 性、基于协进化机制的决策器模型，从而将协进化机 制的符号化模型有机融入了协进化智能体的符号化 描述模型中，形成了一个统一的符号演绎理论模型， 将协进化智能体模型与实际世界模型形成一个统一 的闭环系统。最后，通过建立系统模型确立了基于协 进化的多智能体系统的符号演绎理论模型。 2 基于协进化方法的多智能体系统(Multi-Agent System Based on Co-evolution Method) 2.1 协进化方法(Co-evolution Method) 为了克服传统进化算法的不足， 解决一类更为广 泛的机器学习、共同适应以及多智能体间的协作问 题，人们模仿自然界中多个物种之间协同进化的机 制，提出了协进化计算的思想 4,5,9- 16。在协进化计算 中，通常存在多个物种群体，每个群体都采用进化算 法进行各自的进化过程， 并且进化过程会因其他群体 的进化而产生正面或负面的影响， 各个群体会向着有 利于相互协调适应的方向进化，从而产生协作行为。 2.2 基于协进化方法的多智能体系统(Multi-Agent System Based on Co-evolution Method) 在基于协进化的多智能体系统中， 多个协进化智 能体通过协进化机制有机联系在一起， 基于协进化机 制进行合作或竞争， 并形成一种基于协进化的多智能737 体体系结构9- 16。首先，每个协进化智能体都拥有自 身独立的计算资源和一个信念集， 并拥有一套机制保 证自身的内部动作、 通信等能够维护一个内部一致的 信念集。 此外， 每个智能体还拥有一个协进化决策器， 能够根据自身信念集和动作规则库通过协进化机制 对智能体的外部动作进行评估、整合，通过协进化决 策能够得到智能体要执行的外部动作作用于实际世 界。 2.3 基本假定(Basic Hypothesis) 协进化智能体拥有一定的计算资源和一个能 够用智能体逻辑语言(不妨记为 L)明确表达的信念 集， 并且能够基于自身信念集与自身资源进行演绎式 推理。 进化智能体能够执行 3 种类型的动作：认知 动作、通信动作和外部动作。 其中： ? 认知动作操作智能体自身的计算资源， 可以 视为从智能体的信念集到一个“认知输入” 的函数， “认知输入”是一个可以整合到智 能体的信念集中的新的知识； ? 每个智能体都有一个消息解释器， 消息被消 息解释器解释为接收智能体的认知状态， 产 生一个“认知输入”。 ? 外部动作作用于实际世界(或环境)，并产生 一定的效用。 根据所产生的效用给出一个对 于外部动作的评价，并由此产生一个“认知 输入”整合到智能体的信念集中去。在协进 化智能体的外部动作模型中， 智能体的外部 动作是根据协进化机制来评价的。 每个协进化智能体都有一个外部动作整合函 数， 按照协进化机制对外部动作进行适应度评估并根 据评估结果产生一个“认知输入”。 协进化智能体能够根据来自内部或外部的 “认知输入”对自身的信念集进行修正。修正的方法 是为每个智能体引入一个信念修正函数， 信念修正函 数可以视为一个从信念集和“认知输入”集到新信念 集的函数。 协进化智能体能够基于协进化机制进行决策 并处理智能体之间的关系。 智能体根据自身的规则库 以及规则适应度建立协进化决策器， 决策器按照协进 化机制进行决策，兼顾自身和其他智能体的协作要 求，给出一个问题求解策略，并给出可以影响实际世 界的外部动作。 2.4 协进化智能体的基本操作流程(Basic Operation Flow for Co-evolutionary Agent) 根据基于协进化的多智能体系统体系结构以及 上述关于协进化智能体的基本假定， 可以得到一个协 进化智能体的基本操作流程如下所示： 接收来自其他智能体的消息并解释消息； 如果智能体不是当前活动智能体，产生一个 “外部动作代表”。否则： 通过自身的协进化决策器进行决策， 产生一个外 部动作。 对外部动作进行评估、整合； 如果外部动作评估得知已经能够解决问题， 则返回。否则： 通过信念修正函数处理“认知输入”来更新智能 体的信念集，“认知输入”来自于： ? 前面执行的认知动作； ? 消息解释器； ? 外部动作整合结果。 智能体信念集的封闭性维护； 智能体的动作规则集更新，并选择一个动作 (包括认知动作、消息动作)来执行或发送。 3 协进化智能体的符号化模型(Symbol Model for Co-evolutionary Agent) 基于上述的各项假定， 我们可以建立协进化智能 体的符号演绎理论模型。为了便于理解，我们尽量采 用与国外相关文献一致的符号描述。 3.1 信念(Belief) (1) 信念集 假定智能体的信念可以用智能体逻辑语言(不妨 记为 L)表达， 那么智能体的信念集就是智能体逻辑语 言 L 的一个公式集： Belset = powerset Form(L) 常用符号(0，1，)来表示信念集。 假定演绎规则(Deduction Rules)的类型为 Drule， 常用符号来表示演绎规则的集合。 假定是智能体的信念集，是一个信念，是 一个演绎规则集，以上均符合智能体的逻辑语言 L， 那么，成立当且仅当：存在的一个证据， 它来自于，并且仅使用演绎规则集。 在演绎规则集下， 智能体信念集的封闭性定 义： close: Belset powerset Drule Belset close(, ) | (2) 认知输入 一个智能体信念的改变是由 “认知输入” 引起的， “认知输入”定义为智能体逻辑语言 L 的一个公式 集： Epin = powerset Form(L) 根据前面关于协进化智能体的基本假定， “认知 输入”来自于：前面执行的认知动作；消息解释器； 外部动作整合结果。 (3) 信念修正函数 为了接受新知识， 智能体能够通过信念修正函数 接受“认知输入”并修正自身信念集，智能体的信念 修正函数具有以下形式： Brf = Belset powerset Epin Belset 常用符号来表示信念修正函数。 如果一个信念 修正函数从不会产生一个逻辑上不一致的信念集， 则 称其为一致的。为了方便起见，我们假定所有智能体738 的信念修正函数都是一致的。 3.2 通信(Commu