王平凡, 劉淑芬

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

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

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

1 算法框架

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

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

2 環(huán)境分類處理

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

2.1 初始環(huán)境分類

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

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

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

(1)

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

(2)

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

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

2.2 感知環(huán)境劃分

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

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

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

(8)

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

2) Softmax的代價函數(shù)為

(9)

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

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

3 自適應決策

3.1 隱Markov模型

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

3.2 軟件決策依據(jù)

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

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

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

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

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

用于記錄系統(tǒng)狀態(tài)的轉(zhuǎn)移過程;

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

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

(10)

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

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

(11)

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

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

4 決策驗證

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

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

表1 狀態(tài)轉(zhuǎn)換概率(%)

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

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

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

表3 自適應決策結(jié)果