[發明專利]基于多智能體強化學習的大規模服務組合優化方法

在審

• 申請號: 201310161238.8
• 申請日: 2013-05-03
• 公開（公告）號: CN103248693A
• 公開（公告）日: 2013-08-14
• 發明（設計）人: 王紅兵;王曉珺
• 申請（專利權）人: 東南大學
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 南京瑞弘專利商標事務所(普通合伙) 32249
• 代理人: 楊曉玲

技術領域

本發明屬于人工智能領域，涉及利用計算機對Web服務組合自適應優化的方法。

背景技術

面對復雜多變的市場環境和激烈的競爭，企業迫切需要應用的集成和電子商務技術的支持，以便提高自身在市場的競爭力和適應性。由于Web服務所具有的特性，使得它非常適合于當今跨企業商務應用的集成，工業界和學術界都希望能夠通過組合現有的Web服務來創造出新的服務功能。為了實現企業間信息系統的應用互操作和應用集成，可以通過對企業應用系統進行Web服務封裝，建立面向服務的框架體系，提供Web訪問的接口，將企業之間的應用系統以Web服務的方式集成起來，實現跨企業的服務組合與協作，并通過跨企業工作流系統實現業務流程的自動化。Web服務組合技術就是實現上述目標的一個重要途徑。它將多個Web服務按照一定的規則，發現并組裝成一個增值的、更大力度的服務，以滿足用戶的復雜需求。但是，由于Internet環境所特有的復雜性與多變性，組成復合服務的服務組件，在復合服務的執行過程中，可能發生動態變化，這使得組成復合服務的服務組件很難在設計階段或編譯階段確定下來。因此，需要進行動態web服務組合，來適應動態變化的復雜業務環境。另外一個問題就是服務的質量問題，即QoS屬性問題。因為網絡有上許多提供相同功能的服務，選擇一個具有最優QoS屬性的服務也是非常重要的。而且，Web服務在運行過程中其QoS屬性也可能發生動態變化。如Web服務經過一段時間的運行后，其QoS無法滿足客戶的需求。所以Web服務組合，也需要適應動態變化的復雜業務環境，以維持在一個良好的運行狀態和具有一定的容錯功能。

目前，靜態服務組合事先就要確定參與流程的Web服務，要求開發者手動去執行服務組裝和服務執行。因此，這個過程是困難，耗時和易出錯的，而且不能適應動態的環境?；隈R爾可夫決策過程（Markov?Decision?Process，MDP）是隨機環境下序列決策問題的定量化表達框架。隨機環境下的序列決策問題，是指決策者在每個觀測點上都要做出決策，并且決策時不知道下一個狀態上的決策信息。一般來講，這種決策問題不僅需要考慮當前決利益，還需要考慮當前決策對未來的影響，使系統的運行達到最優。Doshi提出了MDP在Web服務組合中的應用，用于產生工作流的動態Web服務組合。但是此方法需要知道狀態轉移概率和回報值函數的環境模型。而這在現實環境中通常是不可實現的。

發明內容

技術問題：本發明提供一種在面對不確定和不可預測的環境時，能夠根據當時環境的變化在線制定出相應自適應行為策略的基于多agent強化學習的大規模服務組合優化方法。

技術方案：本發明的基于多智能體強化學習的大規模服務組合優化方法，包括以下步驟：

1）把Web服務組合的環境建模成一個6元組的Web服務組合馬爾可夫決策過程狀態轉移圖，即WSC-MDP=<S,s₀,s_t,A(s),P:[p_iaj],R:[r_iaj]>，其中S為一系列原子動作從某個特定的初始狀態s₀開始執行的可達到的狀態集合，s₀表示初始狀態，表示動作還沒有發生時的狀態，也即工作流的初值，s_t用戶的目標狀態，也即工作流的終態，A(s)表示Web服務組合智能體在某一狀態s∈S是可執行的Web服務集合，P:[p_iaj]：為系統在某一狀態時，調用該狀態下的可用的Web服務，系統進入下一狀態的概率，R:[r_iaj]為某個狀態下調用服務的綜合評價回報值；

2）初始化強化學習中Q學習算法的學習速率、折扣因子、Q值和公共Q值Q_p；

3）把進行Web服務組合優化的軟件實體作為能夠感知環境并能夠自主運行滿足設計目標的Web服務組合智能體，Web服務組合智能體感知環境中的狀態s；

4）Web服務組合智能體根據動作選擇策略選擇并執行動作A(s)，得到新的狀態s′，同時從新的狀態s′中得到回報值r；

5）對Q學習中的Q值進行計算和更新，并將更新后為的Q值作為Web服務組合監督智能體的公共Q值，結束本次強化學習過程，Web服務組合監督智能體為指導與同步每個Web服務組合智能體學習過程的軟件實體；

6）判斷Q值是否收斂，如是，則把本次強化學習的結果作為最優Web服務執行工作流，否則回到步驟3）。