王平凡, 劉淑芬

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

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

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

1 算法框架

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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

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

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

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

1) 訓(xùn)練集采用數(shù)據(jù)集{(x1,y1),…,(xm,ym)}, 處理集為新的環(huán)境向量(x′,y′). 對(duì)于本文已知的環(huán)境數(shù)據(jù)輸入集x, 假設(shè)環(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ù);表示對(duì)概率分布進(jìn)行歸一化, 使得所有概率之和為1.

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

(9)

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

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

3 自適應(yīng)決策

3.1 隱Markov模型

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

3.2 軟件決策依據(jù)

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

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

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

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

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

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

2) 計(jì)算t=1時(shí)刻的概率變量

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

(10)

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

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

(11)

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

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

4 決策驗(yàn)證

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

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

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

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

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

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

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