基于多智能体协同的多源信息搜索方法

褚衍杰,徐正国

(信号盲处理国家重点实验室,成都610041)

基于多智能体协同的多源信息搜索方法

褚衍杰,徐正国

(信号盲处理国家重点实验室,成都610041)

针对实时、多源、海量数据条件下用户所需信息的获取问题,提出一种面向对象的、基于多智能体协同的多源信息搜索模型,以对象为中心,在反馈循环搜索的过程中,完善对象描述模型并实现多源数据中关联对象信息的获取,提高多源信息获取的全面性和准确性。设计基于Q学习的协同控制算法,针对马尔科夫对象与非马尔科夫对象给出相应的决策方法。实验结果表明,该协同控制算法比概率转移矩阵及概率统计算法具有更好的信息获取能力。

多智能体;信息搜索;多源信息;面向对象;Q学习;协同机制

1 概述

随着网络技术的飞速发展,尤其是移动互联网日益深入人们的日常生活,各种数字化信息呈爆炸式增长,据IDC(International Data Corporation)公司统计, 2011年全球被创建和被复制的数据总量为1.8 ZB (1021),其中75%来自个人(图像、视频、音乐等)[1];大数据、云计算等技术提供了海量数据处理的基本技术,但是如何从繁杂多样的多源数据中有效获取用户需要的信息仍是一个有待深入研究的课题。

多智能体技术是一项利用多个智能体组成有机整体,并相互协同、服务以共同完成一个任务的人工智能技术,能够有效地实时解决动态复杂问题。文献[2]提出一种利用移动智能体在多个网站搜索特定信息的系统及相应算法,但未解决多种数据类型(如文本、图片、视频等)的协同搜索问题。文献[3]构建一个基于多智能体系统的知识管理模型;文献[4]建立基于多智能体系统的多级库存智能管理系统;文献[5]设计了以智能车为载体的区域监控系统;文献[6]利用多智能体建模与仿真的方法分析了大众生产系统在不同情况下的稳定性;文献[7]将多智能体系统应用到城市管理领域,设计城市自动应急联动系统;文献[8]提出利用分布值函数的多智能体协同算法;文献[9]提出利用多智能体交通滤波效应的分布式协同控制算法;文献[10]分析了复杂网络特性对大规模多智能体协同算法的影响。本文借鉴上述模型、方法,将多智能体系统应用到多源信息的协同搜索问题中,提出多智能体协同模型及协同算法。

2 基于多智能体协同的多源信息搜索模型

用户关心的信息一般可以概括为2种:面向对象的信息和面向过程的信息。面向对象的信息是指用户关心某个对象,例如人、组织、物品、文章等的相关信息;面向过程的信息是指用户关心某个事件的发展进程。由于对事件过程描述的复杂性,在信息搜索的过程中,一般也以事件过程中相关对象的特征为搜索要素,因此可以用一种对象描述模型来表示信息模型。根据用户关心内容的不同,对象模型具有不同的形式,且可以在信息搜索过程中进行更新。一般而言,对象的基本模型包含以下因素:[对象名,对象身份特征,对象行为特征],例如,某人可以描述为[姓名,籍贯,年龄,民族,电话号码,联系人,联系时间],在信息搜索过程中可以根据需要逐渐更新学历、微博账号、微博内容等要素。

2.1 模型介绍

多智能体协同的多源信息搜索模型利用不同的智能体处理不同类型的数据,并融合多种结果作为最终的对象信息,结构如图1所示。

图1 多智能体协同的多源信息搜索模型

多智能体协同的多源信息搜索模型结构具体如下:

(1)协同控制智能体:负责根据用户的搜索要求、对象知识库和对象描述模型,制定下达搜索任务,协调不同的智能体完成不同的子任务。

(2)智能体群:即图1中的智能体A、智能体B等,具体完成数据分析的子任务;这些智能体可以具有相同的功能,并行处理数据,也可以具有不同的功能,处理不同类型的数据。

(3)素材数据采集智能体:由多个素材数据采集智能体组成,负责从不同的数据源采集素材数据。在数据源众多、数据采集设备有限的条件下,需要利用原始素材库及对象知识库的统计信息制定合理的数据采集策略。

2.2 信息搜索流程

信息搜索流程如下:

(1)用户下达信息搜索任务。

(2)协同控制智能体根据任务内容,初始化对象模型。

(3)协同控制智能体根据对象模型和对象知识库中已有的知识制定搜索子任务,分发给智能体群中的各智能体;协同控制智能体根据各子任务内容,将素材数据的筛选条件下达到素材数据采集智能体。

(4)素材数据采集智能体实时进行数据采集,将原始数据存入原始素材库。

(5)智能体群中的各智能体从原始素材库中采集要素信息,完成分析处理任务,通知协同控制智能体,将结果存入对象知识库,并更新对象描述模型。

(6)协同控制智能体判断任务完成情况,若达到用户的要求,则结束任务,否则转步骤(3),直至达到要求。

在图1中,素材数据采集智能体面临从多源数据中提高获取有效素材效率的问题,该问题已在文献[11]中详细论述;协同控制智能体面临协调智能体群处理多源、多类型数据的问题,下面将针对该问题提出协同控制算法。

3 多源信息搜索协同控制方法

用户关心的对象数据经常会在多个数据源、多种类型数据之间跳转,其跳转规律通常蕴含了该对象的行为特性,基于Q学习的协同控制算法利用Q学习思想训练对象的出现记录,从而解决控制多智能体群在何时处理哪个数据源中哪类数据的问题。

3.1 Q学习

Q学习是一种传统的多智能体强化学习方法,通过智能体与环境交互得到外部环境的回报,从而决定下一步的动作。Q学习把智能体的学习过程看作一个Markov决策过程(Markov Decision Proccss, MDP),即智能体根据当前内部状态、外部状态、固定的状态转移概率,以最大化将来的总体回报为目标,决定下一步采取的动作并得到一个即时回报。

Q学习中定义Q值为按照某一个策略执行一系列动作得到的回报的总和,其一步更新算法如下[12]:其中,st∈S表示t时刻的状态;at∈A表示t时刻采取的动作;P(st,at,st+1)表示在状态st下执行动作at,转化到状态st+1的概率;r(st,at)表示在状态st下执行动作at得到的回报;γ表示折扣因子,描述时间远近对回报的影响;α表示学习率。

在Q学习中,累计回报函数表示为Vπ(s)=Qπ(s,a),按照策略与状态动作对的映射寻找最优策略,即π:s→a,可以得到最优策略如下:

通过反复迭代执行动作-更新Q值,Q值将逐步逼近最优策略Q∗(s,a)。

通过对Q学习算法的介绍可以发现,Q学习算法通过学习训练过程中动作与环境回报之间的对应关系,实现寻找最优策略的目的,与多源信息搜索问题中希望通过对象数据的出现规律预测下一步动作的问题类似,因此下面提出基于Q学习的协同控制方法。

3.2 基于Q学习的协同控制方法

在多源信息搜索的协同控制问题中,利用Q表训练对象的出现记录,其中有以下问题需要关注:

(1)系统状态与动作:系统状态S表征系统发现对象信息的情况,可以直接使用发现对象的数据源和数据类型(s,d)表示,即共有M×N种状态,且可以变换为S=s+(d-1)×M,状态间可以任意跳转;系统执行的动作a表示处理某数据源的某类数据,同样有M×N种动作。

(2)环境回报函数:Q学习算法的环境回报函数r(st,at)表征在状态st下执行动作at,将得到的回报应用在多源信息搜索问题中,表示在相应数据源、数据类型中发现对象信息的价值,该价值可以由用户通过历史经验对数据源、数据类型的重要程度评价得到,也可以统计单位时间内在数据源、数据类型内获取的对象信息数量确定,环境回报函数示例如图2所示。

图2 环境回报函数示例

(3)对象特性:传统的Q学习算法采用二维Q表存储Q值,相当于默认对象下一状态仅由其当前状态确定,符合马尔科夫过程的特点;在多源信息搜索问题中,对象的特性未知,有可能不符合马尔科夫过程的特点,因此对Q表进行改进,采用多维Q表,则Q表的维度表示了对象前后相关状态的数量;从经验上看,对象的相关状态数量不会太多,基于Q学习的协同控制算法(图3)采用三维Q表。下面根据对象是否符合马尔科夫过程特点将对象称为马尔科夫对象和非马尔科夫对象。

图3 基于Q学习的协同控制算法流程

基于Q学习的协同控制算法具体步骤如下:

(1)初始化系统内部状态,系统内部状态为(s-,s0,s+),其中,s0表示对象最近一次出现的状态;s-表示s0的前一个状态;s+表示s0的后一个状态。

(2)初始化Q表,Q(i,j,k)=0(1≤i,j,k≤M×N),初始化环境回报函数,为便于仿真,此处假设环境回报函数由人工设定,实际使用时可以统计获取。

(3)当有新的对象出现记录g={gs,gd}时,更新s+=gs+(gd-1)×M;更新Q值表,一步更新公式为Q(s-,s0,s+)=Q(s-,s0,s+)+r(s+)。

(5)对象属性判断:系统初始时,无历史信息,无法确定对象属性,同时执行步骤(6)、步骤(7);系统运行一段时间后,统计马尔科夫决策和非马尔科夫决策对下一步动作的预测与对象下一步实际状态相同的次数,选择预测正确次数大的决策属性作为对象属性。

(8)执行下一步动作,处理状态s+对应的{s,d}数据,对应公式为:

其中,表示向下取整,等待新的对象出现记录,转步骤(3)。

分析算法步骤可以看出,算法计算量主要集中在预测下一步动作时求Q值矩阵的最大值,马尔科夫决策的复杂度为O(M2N2),非马尔科夫决策的复杂度为O(MN),因此算法总的复杂度为O(M2N2),能够满足实时处理的需求。

4 实验验证与结果分析

为验证算法性能,在Matlab 2012上对算法进行仿真验证。验证系统结构如图4所示,其中,对象记录生成模块负责生成马尔科夫对象和非马尔科夫对象的出现记录;对象信息价值统计模块负责按照环境回报函数统计不同算法获取的对象信息价值,作为比较算法性能的依据。为了说明算法性能,下面对比了本文算法、转移概率矩阵算法以及概率统计算法的性能(“Q学习2”表示本文算法的马尔科夫决策,“Q学习3”表示本文算法的非马尔科夫决策),其中转移概率矩阵算法是指利用对象出现记录,统计对象在各状态间的转移概率矩阵,并根据当前状态的最大转移概率值确定下一步动作;概率统计算法是指统计对象在各状态的历史出现记录作为对象在该状态出现的概率,下一步动作为向出现概率最大的状态对应的数据源、业务派遣处理智能体。

图4 验证系统结构

在下面实验中,如无特殊说明,实验数据条件为:M=5,N=5,对象在各数据源、数据类型的出现符合正态分布;每次实验初始时对象出现记录数为0,然后生成对象出现位置并预测下一步动作,每种方法生成并预测1000次,统计获取的对象信息价值;每种实验给出10次实验的结果。

实验结果中的2个性能指标定义如下:(1)信息价值是指历次预测正确时的环境回报函数累计求和;(2)信息获取率是指算法获取的信息价值与搜索次数的比值。

4.1 环境回报函数对算法性能的影响

环境回报函数是本文算法与转移概率矩阵算法的主要区别之一,为了说明环境回报函数的影响,按照图5给出的2种回报函数设置进行实验,结果如图6所示。

图5 2种环境回报函数设置

图6 环境回报函数对算法性能影响的对比

在图6(a)中,本文算法的马尔科夫决策和转移概率矩阵算法的实验结果基本一致,都比概率统计算法有显著提高,这是由于所有的回报函数值都设为1时,本文算法退化为和转移概率矩阵算法相同,从本质上讲,两者对下一步动作的预测都是基于马尔科夫模型的概率转移矩阵;图6(a)中有个别实验结果有微小区别,是由于两者第一次训练需要的数据量不同造成的,本文算法需要3次记录生成第一个Q值,而转移概率矩阵算法只需要2次记录;在图6(b)中,由于环境回报函数分为5级,本文算法的优势得以体现,比转移概率矩阵算法性能提升在40%～50%左右,说明了环境回报函数的有效性。

4.2 算法综合性能分析

图7(a)和图7(b)分别给出了对于马尔科夫对象与非马尔科夫对象,4种方法的整体性能对比。图7(a)的学习次数为1000次,图7(b)的学习次数为10 000次,本文算法采用图5的第2种环境回报函数。

图7 算法整体性能对比

由图7(a)可以看出,对于马尔科夫对象,在训练次数为1000的条件下,本文算法的马尔科夫决策效果最好,转移概率矩阵算法效果次之;由图7(b)可以看出,对于非马尔科夫对象,在训练次数为10 000的条件下,本文算法的非马尔科夫决策效果最好,马尔科夫决策次之,转移概率矩阵算法和概率统计算法的性能较差。上述结果说明当算法假定的对象特性与实际相符时,算法效果最好,实际使用时需要根据情况选择适当算法。

图8(a)和图8(b)分别给出了对于马尔科夫对象和非马尔科夫对象,4种算法的性能收敛趋势。图8(a)针对马尔科夫对象,进行了1次实验,预测10 000次;图8(b)针对非马尔科夫对象,进行了1次实验,预测100 000次。

图8 算法收敛性对比

由图8(a)可以看出,对于马尔科夫对象,本文算法的马尔科夫决策的信息获取率最高,且收敛速度较快。在学习次数为500左右时,算法信息获取率达到20%左右,此后持续增长,在学习次数为3 000左右之后增速放缓,趋于平稳;另外,3种算法收敛后的性能按照转移概率矩阵算法、本文算法的非马尔科夫决策、概率统计算法的顺序性能依次降低。

由图8(b)可以看出,对于非马尔科夫对象,本文算法的非马尔科夫决策的信息获取率最高,且收敛速度较快。在学习次数为5 000左右时,算法信息获取率达到20%左右,此后持续增长,在学习次数为20 000左右后增速放缓,趋于平稳;另外,3种算法收敛后的性能按照本文算法的马尔科夫决策方法、转移概率矩阵算法、概率统计算法的顺序性能依次降低。在学习次数小于3 000次左右的情况下,本文算法的马尔科夫决策的性能比其他3种算法好。

另外,上述实验是对象在各数据源、数据类型正态分布的情况下进行的,在现实中根据对象分布特性的不同,算法性能提升效果有所不同。一般来说,对象分布越不均匀,算法效果越好。

通过上述实验验证,发现本文算法的特性如下:

(1)基于Q学习的协同控制算法中分别针对2种类型的对象设计了马尔科夫决策和非马尔科夫决策。马尔科夫适用于马尔科夫对象或者非马尔科夫对象但学习次数较少的情况;非马尔科夫决策适用于非马尔科夫对象且学习次数较多的情况。

(2)由于马尔科夫决策的收敛速度较快,因此在实际使用中,建议学习次数小于M2N2的情况下使用马尔科夫决策;学习次数大于M2N2后,2种决策方法分别预测,根据预测正确率确定对象属性,从而选择预测方法。

5 结束语

本文研究海量实时数据条件下有效获取多源信息的方法,在多智能体技术的基础上,设计面向对象的多智能体协同多源信息搜索模型,并提出基于Q学习的多源信息搜索协同控制方法。与传统搜索引擎相比,利用该模型能够以对象为中心,在反馈循环搜索的过程中,完善对象描述模型并能从多源数据中关联获取对象信息,在信息搜索的全面性、有效性上有较大提高,模型的可扩充性也较强。针对基于Q学习的多源信息搜索协同控制方法的实验证明,该方法设计的2种决策使得系统对马尔科夫对象和非马尔科夫对象的信息搜索效率有显著提高。基于多智能体的多源信息搜索模型,能够提高信息搜索系统的智能性、全面性和灵活性,但由于采用在线采集要素、离线循环分析的方法,在时效性上有所欠缺;另外,该模型对智能体群处理能力的差异未进行详细分析,这些都有待进一步研究。

[1] Gantz J,Reinsel D.IDC IVIEW:Extracting Value from Chaos[J].IDC IVIEW,2011,(12):1-12.

[2] Chu Yanjie,Wei Qiang.A Network Specific Information SearchSystemBasedonMobileAgent[C]// Proceedings of the 3rd Global Congress on Intelligent Systems.Wuhan,China:[s.n.],2012:302-304.

[3] 蒋翠清,幸龙潮,丁 勇.基于Agent的知识管理系统模型研究[J].情报杂志,2007,(2):56-61.

[4] 薛 红,赵 川.基于多智能体的连锁零售多级库存集成与优化[J].计算机工程,2012,38(14):167-170.

[5] 陈 栋,关新平,龙承念,等.基于多智能体的区域监控系统[J].计算机工程,2010,36(21):72-74.

[6] 姚灿中,杨建梅.基于多智能体的大众生产系统稳定性研究[J].计算机工程,2011,37(3):13-15.

[7] 熊立春,陈建宏,石东平,等.基于Multi-Agent协同模式的城市应急联动系统[J].科技导报,2012,(5): 33-38.

[8] Ferreira E D,Khosla P K.Multi Agent Collaboration Using Distributed Value Functions[C]//Proceedings of IEEE Intelligent Vehicles Symposium.Dearborn,USA: IEEE Press,2000:404-409.

[9] 徐 杨,张玉林,孙婷婷,等.基于多智能体交通滤波效应分布式协同控制算法[J].软件学报,2012, 23(11):2937-2945.

[10] 徐 杨,李 响,常 洪,等.复杂网络特性对大规模多智能体协同控制的影响[J].软件学报,2012, 23(11):2971-2986.

[11] 褚衍杰,徐正国.基于行为规律的搜索资源分配新算法[J].电讯技术,2014,54(2):195-200.

[12] 赵增荣,韩提文.基于Q-Learning的智能体训练[J].石家庄铁道学院学报,2007,20(2):37-39.

编辑 陆燕菲

Multi-source Information Search Method Based on Multi-Agent Collaboration

CHU Yanjie,XU Zhengguo
(National Key Laboratory of Blind Signal Processing,Chengdu 610041,China)

A new multi-source information search model based on multi-Agent collaboration is put forward to deal with the problem that under the real time,multi-source and huge information condition.Multi-Agent information search model centers around objects,builds the whole object model by cycling search,and gets the information that users care for.This model has higher intelligent and open-ended features,and it can make multi-source information searing more comprehensive and accurate.Q-learning-based collaborative control algorithm is proposed.The algorithm designs different decision-making methods for Markov objects and non-Markov objects.Experimental results show that the algorithm has better information search ability than probability transfer matrix and probability statistics algorithms.

multi-Agent;information search;multi-source information;object-oriented;Q learning;collaborative mechanism

褚衍杰,徐正国.基于多智能体协同的多源信息搜索方法[J].计算机工程,2015,41(2):193-198.

英文引用格式:Chu Yanjie,Xu Zhengguo.Multi-source Information Search Method Based on Multi-Agent Collaboration[J].Computer Engineering,2015,41(2):193-198.

1000-3428(2015)02-0193-06

:A

:TP393

10.3969/j.issn.1000-3428.2015.02.037

褚衍杰(1982-),男,博士研究生,主研方向:信息处理;徐正国,博士研究生。

2014-02-28

:2014-04-07E-mail:chuyanjie@tsinghua.org.cn