基于HMM的自適應軟件決策模型

王平凡, 劉淑芬

(1. 河南理工大學 計算機科學與技術學院, 河南 焦作 454000； 2. 吉林大學 計算機科學與技術學院, 長春 130012)

隨著Internet的飛速發展, 單一的軟件模式已不能滿足復雜多變的運行環境, 軟件自適應要求軟件針對運行環境的改變做出持續地、 適應性地改變, 以滿足用戶需求.

目前, 大多數的軟件系統面臨復雜的外部環境, 有限的調整策略遠不能滿足要求. 此外, 軟件本身由于版本更替變得越來越復雜, 軟件的維護、 管理和運行難度也越來越大. 所以軟件的自我調整能力非常重要. 軟件自適應過程主要分為3步： 感知—決策—調整, 其中決策模塊是自適應的關鍵. 早期采用計算反射方式進行決策; 中期的Rainbow框架采用體系結構模型支持軟件的自適應[1-2]; 后期采用了動態規劃、 模糊自適應、 基于角色等自適應方法[3-4]. 本文采用高斯混合模型和softmax回歸算法[5]對自適應軟件環境進行處理, 利用隱Markov模型(hidden Markov model, HMM)的預見性代替人工選擇進行軟件自主決策[6], 并在實際軟件環境下進行檢驗.

1 算法框架

將環境數據向量化處理, 并采用高斯混合模型(GMM)對環境進行分類[7], 在環境感知完成后, 使用softmax函數對環境進行歸類處理, 決策方式使用HMM的維特比進行決策[8], 最后形成一個能自動感知環境變化, 并作出適應性改變的自適應軟件決策模型, 模型的基本流程如圖1所示.

圖1 自適應軟件決策模型基本流程Fig.1 Basic flow chart of adaptive software decision model

2 環境分類處理

本文把每個環境映射為一個向量E=(e1,e2,…,en),n表示環境中的特征數量, 每個維度在0～1間, 表示每個特征的程度值. 采用高斯混合模型對已知的環境素材進行分類.

2.1 初始環境分類

1) 環境特征提?。?提取所處軟件環境的重要特征, 包括(但不限于)CPU性能、 硬盤存儲量、 內存存儲量、 顯示器分辨率、 網絡帶寬值、 操作系統版本.

2) 將每組特征進行向量化處理： CPU性能、 顯示器分辨率及操作系統版本不能直接量化, 需要進行間接量化, 間接量化采用調研并排名的策略, 把排名次序作為量化結果.

3) 使用GMM對環境數據分類： GMM適合在無人監督的情況下進行數據分類, 并能得到數據的概率密度函數, 為軟件系統提供了更高的容錯率. GMM的概率密度函數如下：

(1)

其中：K需要根據軟件所處實際情況事先確定, 通常設為3～5, 表示有3～5種環境分類;πk為權值因子;N(x;uk,Σk)為高斯分布概率密度函數,x表示樣本向量,u表示期望,Σ表示協方差矩陣. GMM的對數似然函數公式為

(2)

為使期望值達到最大, 通常采用EM(expectation maximum)算法對GMM參數進行估計. EM算法的概率函數為γ(i,k), 其中包含4個參數Nk,uk,Σk,πk, 將參數進行迭代計算, 直到函數γ(i,k)收斂, 參數的計算公式如下：

其中模型計算結果形式為{(x1,y1),…,(xm,ym)},x表示環境數據,y表示環境分類.

2.2 感知環境劃分

當軟件所處環境發生變化時, 軟件需要進行自適應調整, 首先需要對新感知到的環境進行向量化處理并歸類. 向量化處理同上, 本文使用softmax回歸模型進行歸類處理. 由于本文的分類數量大于2, 所以采用針對多分類問題的softmax回歸模型. softmax模型的處理步驟如下：

由于Elman網絡存在上述問題，而且隧道位移的預測屬于帶有模糊性質的預測，故本文采用模糊控制系統與Elman網絡相結合，對預測模型誤差進行修正。模糊控制視隧道位移系統是一個帶有模糊性質的系統，通過控制預測位移誤差和誤差變化率，達到控制位移序列的輸出。

1) 訓練集采用數據集{(x1,y1),…,(xm,ym)}, 處理集為新的環境向量(x′,y′). 對于本文已知的環境數據輸入集x, 假設環境數據x屬于環境分類y的概率值為P(y=j|x)(j>1).x為z維向量(2

(8)

其中：θ1,θ2,…,θk∈n+1是函數的參數;表示對概率分布進行歸一化, 使得所有概率之和為1.

2) Softmax的代價函數為

(9)

3) 使用梯度下降法進行迭代更新θj∶=θj-αθjJ(θ), 使J(θ)最小化, 直至代價函數實現收斂.

4) 將新加入的環境數據進行歸類處理. 如果概率函數max{P(y|x)}<50%, 則表示新的環境數據不屬于已有知識庫中的環境分類, 需將新加入的環境數據添加為環境分類, 將新的環境分類進行存儲, 環境數據集變為{(x1,y1),…,(xm,ym),(xm+1,ym+1)}.

3 自適應決策

3.1 隱Markov模型

定義1標準的HMM為一個五元組λ=(S,O,Π,A,B), 其中:S={S1,S2,…,Si}(i>0)表示自適應軟件運行狀態的有限非空集合；O={O1,O2,…,Oj}(j>0)表示自適應軟件運行環境中環境類別的有限非空集合；Π=(Π1,Π2,…,Πk)表示自適應軟件運行狀態在時刻t(t>0)的概率矩陣；A表示自適應軟件狀態間的概率轉移矩陣,A=(aji)=P(Si|Sj)表示自適應軟件在處于狀態Sj的前提下, 轉移到狀態Si的概率；B表示自適應軟件運行環境中環境因素間的狀態轉移矩陣,B=(bnm)=P(Om|Sn)表示自適應軟件在處于狀態Sn的前提下, 環境因素Om發生的概率.

3.2 軟件決策依據

在已知(Π,A,B)中3個參數的前提下, 若軟件系統觀測到的環境變化序列為O={O1,O2,…,On}, 可使用維特比算法[11-12]進行t+1時刻系統狀態的預測, 算法步驟如下：

1) 首先定義維特比概率變量

δt+1(i)=max{δt(j)aji}bi(Ot+1),

表示系統在t時刻處于狀態j,t+1時刻轉移到狀態i, 且觀測到環境分類Ot+1的最大概率； 維特比輔助變量

φt(i)=arg max{δt-1(j)aji},

用于記錄系統狀態的轉移過程;

2) 計算t=1時刻的概率變量

δ1(i)=πibn1(O1);

(10)

3) 計算t=2時刻的概率變量δ2(i)和φ2(i), 根據定義可知

δ2(i)=max{δ1(j)aj1}bi(O2);

(11)

4) 遞推求解δt和φt, 直至終止時刻T；

5)φt(t∈[1,T])為所求的系統狀態序列.

4 決策驗證

上述求解出的系統狀態序列, 可作為軟件自適應[13]的依據, 當軟件感知到環境變化到Ot, 軟件系統狀態做出調整到φt狀態的行為, 使軟件做出自適應改變. 為驗證本文方法的可行性, 對一個在線視頻軟件進行模擬實驗.

首先確定軟件狀態有3種: 低分辨率模式、 通用模式和高分辨率模式, 分別用LM(low model), NM(normal model)和HM(high model)表示, 初始概率分布分別為30%,40%和50%. 可觀測的環境數據使用GMM和softmax函數進行分類, 共分為4類, 用E1,E2,E3,E4表示. 狀態轉換概率分布列于表1, 環境概率分布列于表2.

表1 狀態轉換概率(%)

表2 環境因素概率分布(%)

隨機生成一組環境序列, 本文隨機生成的序列為(E2,E4,E4,E1,E1), 根據表1、 表2和可觀測因素序列, 使用維特比算法進行求解, 求解結果列于表3. 由表3可見, 在隨機環境序列的條件下, 自適應軟件決策計算結果與使用者的期望決策相符.

綜上所述, 本文建立了自適應軟件決策模型. 該模型在感知到環境發生變化的條件下, 軟件可應用高斯混合模型和softmax回歸函數對環境進行處理, 并使用隱Markov模型對其進行決策處理. 實驗結果表明, 該方法可較好地實現軟件的自適應決策.

表3 自適應決策結果