基于多智能體協同的多源信息搜索方法

褚衍杰,徐正國

(信號盲處理國家重點實驗室,成都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種決策使得系統對馬爾科夫對象和非馬爾科夫對象的信息搜索效率有顯著提高?；诙嘀悄荏w的多源信息搜索模型,能夠提高信息搜索系統的智能性、全面性和靈活性,但由于采用在線采集要素、離線循環分析的方法,在時效性上有所欠缺;另外,該模型對智能體群處理能力的差異未進行詳細分析,這些都有待進一步研究。

[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