基于HMM的自适应软件决策模型

2018-11-06王平凡刘淑芬

吉林大学学报（理学版） 2018年3期

王平凡, 刘淑芬

(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.