软件学报  2018, Vol. 29 Issue (9): 2632-2648   PDF    
基于混合智能优化算法的复杂软件可靠性分配
徐悦, 皮德常     
南京航空航天大学 计算机科学与技术学院, 江苏 南京 211106
摘要: 软件可靠性是系统设计、研究和运行过程中必须考虑的关键因素之一.与目前大多数软件可靠性分配的研究主要局限于简单的串并联模型不同,是将最优化算法应用于大型复杂软件系统的可靠性分配.针对分布估计算法收敛速度快、全局搜索能力强但易于陷入局部最优,且差分进化算法局部搜索能力强,但搜索速度略慢的问题,提出一种元启发式算法——基于罚函数的混合分布估计和自适应交叉差分进化的优化算法(PHEDA-SCDE),该算法收敛速度快、全局搜索能力强且不易陷入局部最优.基于4种特定的体系结构风格——顺序、并发、循环、容错,对复杂软件可靠性进行评估.为不失算法通用性,采用3个仿真算例进行实验,分别为单输入单输出系统、单输入多输出系统和多输入多输出系统.实验结果表明,PHEDA-SCDE算法在软件可靠性分配方面与同类算法相比,具有明显的可行性和有效性.
关键词: 软件可靠性分配     软件可靠性评估     分布估计算法     差分进化算法     可靠性优化    
Complex Software Reliability Allocation Based on Hybrid Intelligent Optimization Algorithm
XU Yue, PI De-Chang     
School of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China
Foundation item: National Natural Science Foundation of China (U1433116); Fundamental Research Funds for the Central Universities (NP2017208)
Abstract: Software reliability problem is one of the key factors in the process of system design, research and running. Different from most current researches on software reliability allocation limited to series parallel models, an effective optimization algorithm is applied to large complex software reliability allocation in this paper. Estimation of distribution algorithm (EDA) has fast convergence rate and strong global search capability, but is easily trapped in local optimization. Differential evolution (DE) has good local search capability with slower convergence speed. To address the issue, a new penalty guided hybrid estimation of distribution and self-adaptive crossover differential evolution algorithm (PHEDA-SCDE) is proposed in this paper. PHEDA-SCDE has fast convergence rate and strong global search capability. Also, it is not easily trapped in local optimization. In addition, software reliability is estimated based on four specific architecture styles-sequential, parallel, circulation and fault tolerant. To demonstrate the generality of the algorithm, experiments are carried out on three numerical examples including single-input/single-output system, single-input/multiple-output system and multiple-input/multiple-output system. The experimental results show that the PHEDA-SCDE is significantly feasible and efficient in reliability allocation compared with similar algorithms.
Key words: software reliability allocation     software reliability evaluation     estimation of distribution     differential evolution     reliability optimization    

多年开展软件可靠性的研究表明, 可靠性设计对软件系统可靠性有重要影响.要提高软件系统的可靠性, 关键在于系统可靠性设计.软件系统可靠性的预计和分配是大型复杂软件系统可靠性设计的主要内容之一, 也是可靠性设计的基础[1].可靠性预计和分配处于软件可靠性设计的前期, 并贯穿软件设计的始终.显然, 软件可靠性预计和分配对整个软件系统可靠性的重要性是不言而喻的.

软件可靠性分配是将系统可靠度指标合理地分配给组成该系统的各个构件, 确定构件可靠性定量要求, 从而保证整个系统的可靠性指标.可靠性分配是软件可靠性设计中必不可少的一个环节.软件可靠性分配技术主要分为两类:无约束的可靠性分配和有约束的可靠性分配.前者是不考虑成本等非可靠性因素, 将可靠性按照权重大小分配给各个构件.后者是指采用优化技术进行可靠性分配, 主要分为3类:可靠性分配、冗余分配和可靠性-冗余分配[1-3].本文侧重研究有约束的可靠性分配, 主要内容是以系统可靠性为约束, 使系统成本达到最小.一般来说, 软件可靠性分配优化问题由公式(1)表示:

$ \begin{array}{*{20}{l}} {\rm{Min}}&{cost}\\ {{\rm{s}}{\rm{.t}}{\rm{.}}}&{RE \ge R{E_0}, }\\ {}&{{l_i} < {r_i} < {u_i}.} \end{array} $ (1)

其中, cost为软件系统总成本, ri是第i个构件的可靠性, liui是第i个构件可靠性的下限和上限, RE是软件系统的可靠性, RE0是系统要达到的预定可靠性值.ri为可靠性分配的自变量, 是本文需要求解优化的参数.

软件可靠性分配问题一直是当今软件工程领域的热门研究话题, 许多学者在此领域进行了大量研究.Kuo和Prasad[1]总结了自从1977年以来应用于可靠性最优化的方法, 主要研究了4类系统结构.Rocco[4]提出了一种新的进化算法, 用来解决多状态双端网络的多目标优化问题.2012年, Hsieh和Yeh[5]提出一种基于罚函数的人工蜂群算法, 用以解决冗余分配问题(RAP).Khalili-Damghani等人[6]对二状态多目标可靠性冗余分配问题提出一种动态自适应的粒子群优化算法, 同时, 他们用罚函数和修改策略来处理限制条件.为了解决时间-成本-质量的权衡问题, Tran等人[7]提出了一种基于混合人工蜂群算法和进化计算的多目标进化算法.Zhang和Lei[8]根据遗传算法和粒子群的优势, 提出了一种用来解决网构软件可靠性的动态混合分布算法.由于大多数现有的可靠性冗余分配模型都基于构件固定可靠性的假设, 2016年, Zhang和Chen[9]提出了一种新的基于粒子群优化算法.

软件可靠性评估主要有3种方式:基于状态的模型、基于路径的模型和附加模型[10].文献[11]根据不同的体系结构风格, 评估软件可靠性.本文拟在此基础上新增一类体系结构风格——循环.Cheung[12]基于每个构件的可靠性和构件间的转移概率提出了一个马尔可夫模型用来评估软件可靠性, 同时对构件进行敏感度分析. Zhang和Lei[8]基于马尔可夫链研究了关于网构软件可靠性计算模型.本文拟给出4种特定的体系结构风格, 并对各自的可靠性在第3节进行具体分析.

本文第1节主要阐述软件可靠性分配问题的最优化目标模型, 介绍两种子优化算法——分布估计算法和差分进化算法.在此基础上, 本文提出一种新的基于罚函数的混合分布估计和自适应交叉差分进化算法, 用来解决软件可靠性分配问题.第2节详细介绍4种特定的体系结构风格, 并对各自的可靠性进行分析.第3节主要介绍算例分析, 从收敛速度以及精度两个方面, 采用5种算法进行比较和分析.最后总结全文, 并对未来值得关注的研究方向进行初步探讨.

1 软件可靠性分配算法 1.1 最优化目标模型

软件可靠性分配是将系统可靠度指标合理分配给组成该系统的各个构件, 确定各构件的可靠性定量要求, 从而保证整个系统的可靠性指标.Henlander等人[13]提出了两种设计可靠性和成本的方法:限制可靠性最小化成本(RCCM)和限制预算最大化可靠性(BCRM).本文利用进化计算的方法, 以系统可靠性为约束, 在系统成本最小化的条件下计算各个构件可靠性, 从而帮助系统决策者合理分配资源给各个构件.在此基础上, 软件可靠性分配问题简化为基于费用函数的最优化目标模型, 目标函数可以写成各个构件可靠性的函数:

$ \begin{array}{*{20}{l}} {{\rm{Min}}}&{cost = \sum\limits_{i = 1}^n {cost({r_i})} }\\ {{\rm{s}}{\rm{.t}}{\rm{.}}}&{RE \ge R{E_0}, }\\ {}&{0.5 < {r_i} < 1, }\\ {}&{R{E_0} = 0.9.} \end{array} $ (2)

其中, cost为软件系统总成本, ri是第i个构件的可靠性, RE是软件系统的可靠性, RE0是系统要达到的预定可靠性值.公式(2)使得系统预计可靠性达到0.9, 每个构件可靠性在0.5到1之间的前提下满足成本最小.将约束方程作为罚函数项[14]加入到目标函数中, 变成无约束的优化问题, 即:

$ \begin{array}{*{20}{c}} {{\rm{Min}}}&{cost + penalty = \sum\limits_{i = 1}^n {cost({r_i})} } \end{array} + k \cdot \min \{ 0, RE-R{E_0}\} $ (3)

其中, k为一充分大的负数.综上可知:如果不满足系统最低达到的可靠性值, 罚函数反比例于RE-RE0.

一般在成本最小为优化目标的模型中, 成本与各个构件可靠性之间的函数关系是非常重要的.Henlander等人[13]提出了基于对失效率和成本之间关系现实假设的3种成本函数:线性形式、对数指数形式、逆幂形式. Mettas等人[15]提出了基于经验和(或者)数据的可靠性成本关系函数如公式(4)所示:

$ {c_i}({R_i};{f_i}, {R_{i, \min }}, {R_{i, \max }}) = {{\rm{e}}^{^{(1-{f_i}) \cdot \frac{{{R_i}-{R_{i, \min }}}}{{{R_{i, \max }}-{R_i}}}}}} $ (4)

其中, ci表示构件i的成本; fi表示增加一个构件可靠性的可靠性, 值在0到1之间; Ri为构件i初始(当前)的可靠性值; Ri, min为构件i初始(当前)的最小可靠性值; Ri, max为构件i初始(当前)的最大可靠性值.本文采用Mettsa提出的指数形式函数, 因为其函数满足如下几点可靠性与成本之间关系的需求.

(1) 函数值是正数;

(2) 成本是关于构件可靠性的单调增函数;

(3) 可靠性越高, 成本越高; 反之亦然.

1.2 子优化算法 1.2.1 分布估计算法

分布估计算法(estimation of distribution algorithm, 简称EDA)是一种新型的启发式算法[16], EDA算法是遗传算法的改进, 但与传统遗传算法不同的是, 该算法没有交叉、变异等遗传操作.分布估计算法构建描述解空间的概率模型, 根据目标函数选取优秀的个体集合, 采用统计学习方法构造一个描述当前优秀个体解集的概率模型.对概率模型随机采样, 从而得到新的种群.在此过程中, 概率模型会被不断朝最优解的方向进化.

EDA算法基本步骤如下.

步骤1.初始化群体.

步骤2.适应度值评价.

步骤3.适应度值按照从高到低排序, 用截断选取的策略选取k个优秀个体.

步骤4.分别计算当前种群的均值和方差.

步骤5.构建概率分布模型.

步骤6.根据概率模型采样产生下一代.

步骤7.若终止条件满足, 则算法终止; 否则转向步骤2继续执行.

分布估计算法的优势在于全局搜索能力强、收敛速度快, 可以很快缩小搜索空间.但局部搜索能力相对较弱, 容易陷入局部最优.

1.2.2 自适应交叉差分进化算法

差分进化算法(differential evolution, 简称DE)是一种基于向量的适者生存、优胜劣汰算法[17], 该算法将种群中的个体看成当前向量, 随机产生自适应变异.差分进化算法根据公式(5)初始化种群为NPD维向量, xi={xi, 1, xi, 2, …, xi, D}, i=1, 2, …, NP.个体采用实数编码, 公式中, u为个体上限值, l为个体下限值:

$ x = rand\left( {NP, D} \right)'(u-l) + l $ (5)

DE随机选取两个不同的向量相减产生差分向量, 然后将差分向量赋予权值后与另一随机向量相加, 从而生成变异个体, 如公式(6)所示:

$ {v_i} = {x_{{r_1}}} + F \cdot ({x_{{r_2}}}-{x_{{r_3}}}) $ (6)

其中, xi为当前目标向量, vi为变异产生的种群个体向量, r1, r2, r3互不相等.F是自适应变异算子, 由公式(7)生成:

$ F = {F_0} \cdot {2^\lambda }, \lambda = {{\rm{e}}^{1-\frac{{\max gen}}{{\max gen + 1-gen}}}} $ (7)

其中, F0是初始变异算子, maxgen表示最大进化代数, gen表示当前进化代数.然后, 将变异向量与当前目标向量随机交叉产生实验个体向量ui.最后, 根据公式(8)比较目标向量和实验向量的适应度值, 选择适应度值较优的群体向量:

$ {x_i} = \left\{ {\begin{array}{*{20}{l}} {{u_i}, {\rm{ if }}\;\;f({u_i}) < f({x_i})}\\ {{x_i}, {\rm{ otherwise}}} \end{array}} \right. $ (8)

传统DE算法全局搜索能力较差, 收敛速度较慢.为了改进算法的性能, 自适应策略已普遍应用于差分进化算法.Qin等人[18]提出一种自适应差分进化算法(SaDE), 对实验向量和相应控制参数自适应改进.Wang等人[19]提出一种带有改进变异策略的自适应差分进化算法(IMSaDE), 包括精英备选策略(elite archive strategy)和控制参数适应策略(control parameters adaptation strategy).为解决多文档文摘(multi-document summarization)优化问题, Alguliev等人[20]提出一种新的基于自适应变异和交叉的算法(DESAME).本文采取自适应交叉策略改进算法, 旨在加强全局搜索能力, 迅速得到最优解空间, 如图 1所示.

Fig. 1 The self-adapative crossover of differential evolution 图 1 差分进化算法自适应交叉示意图

在交叉部分, 目标向量不仅与变异向量进行交叉, 而且与当代最优向量best进行交叉, 如公式(9)所示.此交叉过程是一个自适应的过程, 同时, 其变异和选择都具有自适应的性质.本文将改进后的差分进化算法称为自适应交叉差分进化算法(self-adaptive crossover differential evolution, 简称SCDE):

$ {u_{i, j}} = \left\{ {\begin{array}{*{20}{l}} {{x_{i, j}}, {\rm{ }}0 \le rand < C{R_0}}\\ {{v_{i, j}}, {\rm{ }}C{R_0} \le rand < C{R_1}}\\ {bes{t_j}, {\rm{ }}C{R_1} \le rand \le 1} \end{array}} \right. $ (9)

其中, CR0CR1是用户定义的交叉常量, 值在0和1之间.

SCDE详细步骤如下所示.

步骤1.初始化群体.

步骤2.适应度值评价.

步骤3.自适应变异.

步骤4.自适应交叉.

步骤5.选择更优向量产生下一代.

步骤6.若终止条件满足, 则算法终止; 否则, 转向步骤2继续执行.

差分进化算法具有很强的局部搜索能力, 根据差分向量对种群中几个个体向量随机自适应变异.但与分布估计算法相比, DE算法收敛速度较慢.所以在交叉阶段, 当前向量不仅与变异向量交叉, 还有一定概率和当前最优向量交叉, 从而加快收敛速度.

1.3 混合优化算法

EDA算法全局搜索能力强, 收敛速度快.在种群进化初期, 需要将解空间缩小到一定范围, 进一步缩短算法在后期寻优时间.SCDE算法局部搜索能力强, 结构简单.在种群进化中后期, 需要加强局部搜索能力, 避免陷入局部最优.在此基础上, 本文提出一种基于罚函数的混合分布估计和自适应交叉差分进化的优化算法(PHEDA- SCDE).PHEDA-SCDE算法前期具有较强的全局搜索能力, 收敛速度快, 能迅速找到全局最优所在的解空间.该算法在其中后期不仅具有较强的局部搜索能力, 而且避免对复杂优化问题陷入局部最优的困境.

1.3.1 决策因子和轮盘赌选择

在实践中, 最常见的选择方法是轮盘赌选择方法和精英方法.本文通过决策因子n和轮盘赌选择将EDA和SCDE算法有效融合.轮盘赌选择[21]是一种基于适应度函数值的回放式随机采样方法, 每个个体被选中的概率与适应度值大小成正比.适应度值越大, 被选中的概率越高; 反之亦然.其特点是优秀个体具有较大被选中的概率, 且每个个体都有被选择的概率.在PHEDA-SCDE算法中, EDA和SCDE各自对每一代种群进行优化, 产生候选实验个体.本文对EDA产生的候选种群进行轮盘赌选择, 选择出n个候选实验个体; 同时也采用轮盘赌选择方式, 在SCDE产生的候选种群中选择NP-n个候选实验个体.两部分候选解组合成新一代种群, 增加种群的多样性.当前个体既继承了上一代的种群信息, 又产生了不同的机制特征信息.

固定两个算法种群比例或者随机设置比例是不可行的:固定种群比例, 前期算法收敛速度慢, 中后期算法局部搜索能力弱; 随机设置算法比例, 算法很有可能陷入局部最优, 算法稳定性不高.本文采用公式(10)为混合算法决策因子n的计算公式:

$ n(gen + 1) = {n_{\min }} + \left( {1-\frac{{gen}}{{\max gen}}} \right) \cdot (n(gen)-{n_{\min }}) $ (10)

其中, gen为当前迭代次数, maxgen为最大迭代次数, nminnmax分别为决策因子n的下限和上限.

图 2为决策因子变化曲线, 其中, nmin=0.2, nmax=0.9.

Fig. 2 The variation curve of the decisive factor n 图 2 决策因子n变化曲线图

显然, 从图 2可以发现, 决策因子随着迭代次数的增加而减少.在进化初期, 选择较大数值的决策因子, EDA算法占主导作用, 这样可以将解空间快速缩小到一定范围.与此同时, 一小部分个体由SCDE算法产生, 保证了种群多样性, 为算法后期寻优提供了优质解空间.随着迭代次数的增加, 决策因子n逐渐递减, SCDE算法在进化中后期占主导地位.EDA算法虽然全局搜索能力强, 收敛速度快, 但在算法中后期很容易陷入局部最优, 所以PHEDA-SCDE算法在其中后期通过决策因子, 增大了SCDE算法生成个体的比例, 提高算法局部搜索能力.同样的, 算法仍保留部分由EDA算法产生的个体来提供算法的求解质量和效率.

1.3.2 PHEDA-SCDE算法流程

PHEDA-SCDE算法是根据父代种群的差分向量信息和概率模型分布选择适应度较高的子代, 初期维持了种群的全局信息, 中后期维持了种群的局部信息.PHEDA-SCDE算法伪代码见算法1, 具体流程如图 3所示.

Fig. 3 The procedure of PHEDA-SCDE 图 3 PHEDA-SCDE算法流程图

算法1. PHEDA-SCDE算法的伪代码.

输入:种群规模NP, 种群维数D, 个体上限值u和个体下限值l, 决策因子最大值nmax和决策因子最小值nmin,

最大迭代代数maxgen, 交叉算子CR0CR1, 初始变异算子F0, 阈值truncation;

输出:种群中的最优个体及其适应度值.

开始

1 x:=rand(NP*D)*(u-l)+l           //初始化种群

2 f:=fitness(x)          //计算适应度值

3 for gen=1 to maxgen do          //主循环

4   [EDAx, EDAf]:=EDA(x, f, truncation)          //通过EDA算法对当前种群进行优化

5   [EDAu, EDAf]:=roulette(EDAx, EDAf, n)          //轮盘赌选择出n个候选实验个体

6   [SCDEx, SCDEf]:=SCDE(x, f, CR0, CR1, F0) //通过SCDE算法对当前种群进行优化

7   [SCDEu, SCDEf]:=roulette(SCDEx, SCDEf, NP-n)           //轮盘赌选择出NP-n个候选实验个体

8   new:=(EDAu, SCDEu)          //种群合并

9   newf:=(EDAf, SCDEf)          //适应度值合并

10   if newf > f do          //选择个体进入下一代

11     x:=new

12     f:=newf

13   endif

14   n:=nmin+(1-gen/maxgen)*(n-nmin)          //更新决策因子

15 endfor

结束

本文通过一个简单算例介绍PHEDA-SCDE算法的进化操作, 详见附录A.

1.3.3 PHEDA-SCDE算法收敛性分析

定理1. PHEDA-SCDE算法中种群进化方向是单调不增的, 即f(X(gen+1))≤f(X(gen)).

证明:由公式(8)所示, PHEDA-SCDE算法的选择算子是贪婪选择操作, 总会保留更优个体, 因此种群最优适应度单调不增, 命题得证.

定理2. PHEDA-SCDE算法的种群序列{X(gen), genN+}为齐次Markov链.

证明:由于PHEDA-SCDE算法的种群序列:

$ \begin{array}{l} X\left( {gen + 1} \right) = T\left( {X\left( {gen} \right)} \right) = (({T_{crossover}} \circ {T_{mutation}}\left( {X\left( {gen} \right)} \right)) \circ {T_{roulette}}, \\ ({T_{sample}} \circ {T_{truncation}}\left( {X\left( {gen} \right)} \right)) \circ {T_{roulette}}) \circ {T_{selection}} \end{array} $ (11)

其中, Tcrossover, Tmutation, Troulette, Tsample, Ttruncation, Tselection均与n无关.

因此, X(gen+1)仅与X(gen)有关, 即{X(gen), genN+}是Markov链.显然, 其转移概率大于0, 命题得证.

定理3. PHEDA-SCDE算法的Markov链种群序列{X(n), nN+}以概率1收敛于全局最优解集M*, 其中, 全局最优解集M*={X*; ∀X*S, 有f(X*)≤f(X)}:

$ \mathop {\lim }\limits_{gen \to \infty } P(X(gen) \in {M^*}) = 1 $ (12)

证明:由定理1、定理2知, PHEDA-SCDE算法为单调不增的齐次Markov链, 则X(gen-1)到X(gen)的转移概率有:

$ P\{ X(gen-1), X(gen)\} = \left\{ {\begin{array}{*{20}{l}} {P\{ X(gen) \in {M^*}|X(gen-1) \in {M^*}\} = 1}\\ {P\{ X(gen) \notin {M^*}|X(gen-1) \in {M^*}\} = 0}\\ {P\{ X(gen) \in {M^*}|X(gen - 1) \notin {M^*}\} > 0}\\ {P\{ X(gen) \notin {M^*}|X(gen - 1) \notin {M^*}\} > 0} \end{array}} \right. $ (13)

根据全概率公式P(B)=P(A)P(B|A)+P(Ā)P(B|Ā), P{X(gen)∈M*}可以表示为公式(14):

$ \begin{array}{l} P\{ X(gen) \in {M^*}\} = (1-P\{ X(gen-1) \in {M^*}\} ) \cdot P\{ X(gen) \in {M^*}|X(gen-1) \notin {M^*}\} + \\ {\rm{ }}P\{ X(gen - 1) \in {M^*}\} \cdot P\{ X(gen) \in {M^*}|X(gen - 1) \in {M^*}\} \end{array} $ (14)

θ(t)=X(gen)∈M*, ω(t)=P{X(gen)∈M*|X(gen-1)∈M*}, 公式(14)改写为

$ \theta \left( t \right) = (1 - \theta (t - 1))w\left( t \right) + \theta (t - 1) $ (15)

则:

$ \begin{array}{l} 1-\theta (t) = (1-\theta (t-1)) \cdot (1 - \omega (t)) \Rightarrow 1 - \theta (t) = (1 - \theta (t - 2)) \cdot (1 - \omega (t)) \cdot (1 - \omega (t - 1))\\ {\rm{ }} \Rightarrow ...\\ {\rm{ }} \Rightarrow 1 - \theta (t) = (1 - \theta (0)) \cdot \prod\limits_{k = 1}^t {(1 - \omega (k))} \end{array} $ (16)

两边取极限为

$ \mathop {\lim }\limits_{t \to \infty } \theta (t) = 1-\mathop {\lim }\limits_{t \to \infty } \left( {(1-\theta (0)) \cdot \prod\limits_{k = 1}^t {(1-\omega (k))} } \right) \Rightarrow \mathop {\lim }\limits_{t \to \infty } \theta (t) = 1 - (1 - \theta (0)) \cdot \mathop {\lim }\limits_{t \to \infty } \left( {\prod\limits_{k = 1}^t {(1 - \omega (k))} } \right) $ (17)

根据转移概率0 < ω(t)≤1, 可得$\mathop {\lim }\limits_{t \to \infty } \left({\prod\limits_{k = 1}^t {(1-\omega (k))} } \right) = 0$.

因此, $\; \mathop {\lim }\limits_{t \to \infty } \theta (t) = 1$, 即$\mathop {\lim }\limits_{gen \to \infty } P(X(gen) \in {M^*}) = 1$.证毕.

2 软件可靠性评估方法

本节给出顺序、并发等4种特定的体系结构风格, 并对各自的可靠性进行具体分析.任何复杂的大型软件系统都可以由顺序、并发、循环、容错及其扩展情况表示.

2.1 顺序

C1;C2表示构件C1和C2是顺序执行, 即:先执行C1, 再执行C2.假设转移概率为pi, j, 第i个状态可靠性为r(Si), 那么C1;C2可靠性为

$ RE = r\left( {{S_1}} \right) \cdot {p_{1, 2}} \cdot r\left( {{S_2}} \right) $ (18)

假设某顺序执行的体系结构如图 4(a)所示, 其中, C1, C2, …, C5是系统结构的构件, 构件数量为5.顺序风格的状态图 4(b)是体系结构图的一一映射, 其中, S1, S2, …, S5是马尔可夫链的状态, 状态数量为5.则此系统可靠性为

Fig. 4 Sequential style 图 4 顺序执行风格

$ RE = r\left( {{S_1}} \right) \cdot {p_{1, 2}} \cdot r\left( {{S_2}} \right) \cdot {p_{2, 5}} \cdot r\left( {{S_5}} \right) + \\r\left( {{S_1}} \right) \cdot {p_{1, 3}} \cdot r\left( {{S_3}} \right) \cdot {p_{3, 4}} \cdot r\left( {{S_4}} \right) \cdot {p_{4, 5}} \cdot r\left( {{S_5}} \right) $ (19)
2.2 并发

C1||C2表示构件C1C2是并发操作.与顺序风格一次只执行一个构件不同的是:在并发风格中, 两个或者多个构件可以同时执行.假设转移概率为pi, j, 第i个状态的可靠性为r(Si), 其中, p1, p=p1, 2=p1, 3, r(Sp)=r(S2)=r(S3), 那么C1; (C2||C3)的可靠性为

$ RE = r\left( {{S_1}} \right) \cdot {p_{1, p}} \cdot r\left( {{S_p}} \right) $ (20)

假设某并发执行的体系结构如图 5(a)所示, 其中, C1, C2, …, C5是系统结构的构件, 构件数量为5.特别地, 构件C2, C3, C4可以同时发生.在并发风格的状态图 5(b)中, 构件C2, C3, C4合并为并发状态Sp, 其中, S1, Sp, Sn是马尔可夫链的状态, 状态数量为3.假定p1, 2=p1, 3=p1, 4=p1, p, p2, 5=p3, 5=p4, 5=1, 可以得出从状态SpS5的转移概率pp, 5和该系统的可靠性RE

Fig. 5 Parallel style 图 5 并发执行风格

$ {p_{p, 5}} = \prod\limits_{i = 2}^4 {{p_{i, 5}}} = 1 $ (21)
$ RE = r\left( {{S_1}} \right) \cdot {p_{1, p}} \cdot r\left( {{S_p}} \right) \cdot r\left( {{S_5}} \right) $ (22)
2.3 容错

C1|C2表示C1是主要构件, C2是备份构件.如果构件C1故障失效, C2作为备份构件仍可执行相应功能, 系统可正常运行.假设转移概率为pi, j, 第i个状态的可靠性为r(Si), 其中, p1, b=p1, 2=p1, 3, r(Sb)=r(S2)=r(S3), 那么C1; (C2|C3)的可靠性为

$ RE = r\left( {{S_1}} \right) \cdot {p_{1, b}} \cdot r\left( {{S_b}} \right) $ (23)

假设某容错执行的体系结构如图 6(a)所示, 其中, C1, C2, …, C5是系统结构的构件, 构件数量为5.特别地, 构件C3, C4是容错关系, C3是主要构件, C4是备份构件.在容错风格的状态图 6(b)中, 构件C3, C4合并为容错状态Sb, 其中, S1, Sb, Sn是马尔可夫链的状态, 状态数量为3.假定p1, 3=p1, 4=p1, b, p2, 3=p2, 4=p2, b, p3, 5=p4, 5=pb, 5=1, 那么该系统的可靠性RE

Fig. 6 Fault tolerance style 图 6 容错执行风格

$ RE = r\left( {{S_1}} \right) \cdot {p_{1, b}} \cdot r\left( {{S_b}} \right) \cdot r\left( {{S_5}} \right) + r\left( {{S_2}} \right) \cdot {p_{2, b}} \cdot r\left( {{S_b}} \right) \cdot r\left( {{S_5}} \right) $ (24)
2.4 循环

μC1表示循环执行构件C1的相关功能, 可以执行一次也可以执行多次.假设转移概率为pi, j, 第i个状态的可靠性为r(Si), 其中, p1, b=p1, 2=p1, 3, r(Sb)=r(S2)=r(S3), 那么C1; (μC2); C3的可靠性为

$ RE = r\left( {{S_1}} \right) \cdot {p_{1, b}} \cdot r\left( {{S_b}} \right) $ (25)

C1; (μC2); C3循环执行的体系结构如图 7(a)所示, 其中, C1, C2, C3是系统结构的构件, 构件数量为3.特别地, 构件C2自身循环零次或者多次.顺序风格的状态图 7(b)也是体系结构图的一一映射, 其中, S1, S2, S3是马尔可夫链的状态, 状态数量为3.

Fig. 7 Cycle style 图 7 循环执行风格

●  若系统没有执行循环操作, 则系统可靠性

$ RE\left( 0 \right) = r\left( {{S_1}} \right) \cdot {p_{1, 2}} \cdot r\left( {{S_2}} \right) \cdot {p_{2, 3}} \cdot r\left( {{S_3}} \right) $ (26)

●  若系统执行循环操作一次, 则系统可靠性

$ RE\left( 1 \right) = r\left( {{S_1}} \right) \cdot {p_{1, 2}} \cdot r\left( {{S_2}} \right) \cdot {p_{2, 2}} \cdot r\left( {{S_2}} \right) \cdot {p_{2, 3}} \cdot r\left( {{S_3}} \right) $ (27)

●   直至系统执行循环操作μ次, 则系统可靠性

$ RE(\mu ) = r\left( {{S_1}} \right) \cdot {p_{1,2}} \cdot r\left( {{S_2}} \right) \cdot {({p_{2,2}} \cdot r\left( {{S_2}} \right))^\mu }^{ - 1} \cdot {p_{2,3}} \cdot r\left( {{S_3}} \right) $ (28)

所以, 系统可靠性可以表示为

$ RE = \sum\limits_{i = 0}^\mu {RE(i) = \frac{{r({S_1}) \cdot {p_{1, 2}} \cdot r({S_2}) \cdot {p_{2, 3}} \cdot r({S_3})}}{{1-{p_{2, 2}} \cdot r({S_2})}}} $ (29)
3 仿真实验结果与分析 3.1 参数设置

参数设置对随机性算法的性能和效率有显著的影响[22], 因此, 本节通过设置参数对比分析实验, 找出求解软件可靠性分配问题的较优参数.本文提出的PHEDA-SCDE算法包含了几个关键参数:交叉算子CR0CR1、初始变异算子F0、阈值truncation、决策因子上限nmax和下限nmin.本文采用实验设计法(design of experiments, 简称DOE)[23], 每个参数选择合理取值, 将其构成算法的参数集.参数取值如下:CR0∈{0.1, 0.2, 0.3, 0.4}, CR1∈{0.6, 0.7, 0.8, 0.9}, F0∈{0.2, 0.4, 0.6, 0.8}, truncation∈{0.2, 0.3, 0.4}, nmax∈{0, 0.1, 0.2}, nmin∈{0.8, 0.9, 1}.这些参数对于本文提出的算法, 共有4×4×4×3×3×3=1728种不同配置.为了保证实验结果更可靠, 每一种配置都独立运行5次.

本节按照文献[12, 24]的方法生成受控数据集进行参数设置实验, 然后在测试实例集上进行验证.受控数据集详细信息见表 1.

Table 1 The control data set 表 1 受控数据集详细信息

为探寻参数对算法的影响, 本文采用方差分析(analysis of variance, 简称ANOVA)方法来设计实验.主效应图(见图 8)是显示单个参数对结果影响的显示图, 根据图例可以分析得到达到哪个值的时候这个参数的影响力最大, 从而找出最主要因素.从图 8中可以明显看出:初始变异算子F0对目标函数的影响最大, 这主要是因为子算法SCDE中有60%进行自适应交叉, 当其值为0.6时, 目标函数达到最优化; 交叉算子CR0与决策因子下限nmin对目标函数影响相对最小.根据图 8分析可知, 选择表 2中所列出的参数配置较为合理.

Fig. 8 Main effect plot of parameters 图 8 PHEDA-SCDE算法主效应图

Table 2 Parameter tuning of PHEDA-SCDE 表 2 PHEDA-SCDE算法运行参数设置

3.2 仿真算例实验与分析 3.2.1 软件可靠性分配算例

为不失算法的通用性, 本文采用3个仿真算例, 分别为单输入单输出系统、单输入多输出系统和多输入多输出系统.以某复杂软件系统可靠性优化仿真算例进行说明[8], 如图 9.1所示.算例1是由12个构件组成的单输入单输出系统, 其中, C1代表输入构件, C12代表输出构件.特别地, 构件C7C8是并发关系, C10C12的容错构件, 构件C4自身循环.系统状态如图 9.1(b)所示, 是由图 9.1(a)的体系结构图转变过来.本文按照文献[24]的方法, 算例2(见图 9.2)删除算例1中C11C12之间的连接、C11C6之间的连接, 使得C11C12均为输出构件.算例3(见图 9.3)中系统开始于输入组件C1C2, 结束于输出组件C11C12.

Fig. 9.1 A single-input/single-output type (example 1) 图 9.1 单输入单输出系统体系结构图和状态图(算例1)

Fig. 9.2 A single-input/multiple-output type (example 2) 图 9.2 单输入多输出系统体系结构图和状态图(算例2)

Fig. 9.3 A multiple-input/multiple-output type (example 3) 图 9.3 多输入多输出系统体系结构图和状态图(算例3)

为了简化模型, 本文认为, 转移概率pi, j已经考虑了连接件的可靠性.算例1的转移概率如下所示, 算例2和算例3相应的转移概率与算例1相似.

$ \begin{array}{*{20}{l}} {{P_{1, 2}} = 0.6}&{{P_{1, 3}} = 0.1}&{{P_{1, 4}} = 0.3} \\{{P_{2, 3}} = 0.3}&{{P_{2, 5}} = 0.7}&{{P_{3, 6}} = 1}&{{P_{4, 4}} = 0.2}\\ {{P_{4, p}} = 0.8}&{{P_{5, b}} = 1}&{{P_{6, b}} = 1}\\{{P_{p, 11}} = 1}&{{P_{b, 12}} = 1}&{{P_{11, 6}} = 0.1}&{{P_{11, 12}} = 0.9} \end{array} $

如下对算例1进行详细分析, 首先依据公式(3)将可靠性优化模型转变为无约束求目标函数最小化:

$ \begin{array}{*{20}{c}} {{\rm{Min}}}&{cost + penalty = {a_i} \cdot \sum\limits_{i = 1}^n {{e^{(1-{c_i}) \cdot \frac{{{r_i}-{r_{i, \min }}}}{{{r_{i, \max }}-{r_i}}}}}} } \end{array} + k \cdot \min \{ 0, RE - {r_0}\} $ (30)

其中, a=[0.88 0.9 0.86 0.76 0.89 0.93 0.94 0.75 0.95], c=[0.23 0.28 0.37 0.45 0.05 0.25 0.5 0.2 0.41], ri, min=0.5, ri, max=1, r0=0.9.

根据第3节中不同体系风格可靠性的分析, 算例1软件系统可靠性表示为公式(31):

$ \left. \begin{array}{l} RE = 0.42 \cdot r({c_1}) \cdot r({c_2}) \cdot r({c_5}) \cdot r({c_b}) \cdot r({c_{12}}) + \\ 0.18 \cdot r({c_1}) \cdot r({c_2}) \cdot r({c_3}) \cdot r({c_6}) \cdot r({c_b}) \cdot r({c_{12}}) + \\ 0.1 \cdot r({c_1}) \cdot r({c_3}) \cdot r({c_6}) \cdot r({c_b}) \cdot r({c_{12}}) + \frac{{0.216 \cdot r({c_1}) \cdot r({c_4}) \cdot r({c_p}) \cdot r({c_{11}}) \cdot r({c_{12}})}}{{1 - 0.2 \cdot r({c_4})}} + \\ \frac{{0.24 \cdot r({c_1}) \cdot r({c_4}) \cdot r({c_p}) \cdot r({c_{11}}) \cdot r({c_6}) \cdot r({c_b}) \cdot r({c_{12}})}}{{1 - 0.2 \cdot r({c_4})}} \end{array} \right\} $ (31)

其中, 各个构件可靠性r为可靠性分配的自变量, 系统决策者根据最终求得的构件可靠性值分配资源, 从而达到复杂软件整体可靠性最大化和代价最小化.

3.2.2 实验结果和分析

本文主要在收敛速度以及精度方面对PHEDA-SCDE, DE, SCDE, EDA以及DHOACP算法进行比较, 每次目标函数独立运行20次.实验经过200次迭代, 分别得到各种算法最优解的平均值、标准差、最优值、最差值(见表 3)作为目标函数精度的评价结果.同时, 根据一次独立运行的CPU时间作为算法效率的评价结果, 运行时间是一个关键的理论问题[25].从表 3中可以看出:对于单输入单输出软件系统分配问题(算例1), PHEDA-SCDE在求解质量上明显优于其余算法, 在求解效率上明显优于DHOACP, 对于单输入多输出系统(算例2)和多输入多输出系统(算例3)的软件可靠性分配问题, 该算法无论在求解效率还是在求解精度上都具有良好的效果; 其次, 本文对传统的差分进化算法进行自适应交叉改进, 改进结果表明, SCDE算法在求解质量上明显优于DE算法, 进一步验证了SCDE算法相较于DE算法全局搜索能力强, 能迅速得到解空间.

Table 3 The solutions of objective functions 表 3 目标函数实验结果

收敛曲线图主要描绘随着进化次数的增加目标函数适应度值的变化趋势, 算法收敛曲线图如图 10所示.图 10(a)为算例1的算法收敛曲线图, 图 10(b)为算例2的算法收敛曲线图, 图 10(c)为算例3的算法收敛曲线图.为了保证系统可靠性, 软件代价不会是一个无穷小的值, 一定收敛于某个值.为了直观地描述软件代价的收敛曲线, 算法收敛曲线图纵坐标表示适应度值的对数变换, 值为log10(f(x)).横坐标表示进化代数.从3幅图中可以看出, DHOACP算法虽然在其初期收敛速度最快, 但很快陷入局部最优.在算法收敛性上, PHEDA-SCDE明显优于其他3种算法, 说明算法在初期快速搜索解空间, 有很强的全局搜索能力.因此, PHEDA-SCDE算法结合分布估计算法和自适应交叉差分进化算法的优点, 无论在求解精度还是收敛速度方面, 对于复杂软件系统可靠性的分配均具有优秀的效果.算法详细参数设置见表 4.

Fig. 10 The convergence curve of all compared algorithms 图 10 算法收敛曲线图

Table 4 Parameter tuning of all compared algorithms 表 4 算法运行参数设置

4 总结

可靠性问题一直是软件可靠性领域的重中之重的研究难题, 合理分配构件可靠性有利于增强系统可靠性、提高资源利用率、减少开发维护成本.对于大型复杂软件系统, 本文提出一种新型的元启发式算法——基于罚函数的混合分布估计和自适应交叉差分进化的优化算法(PHEDA-SCDE), 该方法结合分布估计算法和差分进化算法的优点.在算法初期, PHEDA-SCDE具有全局搜索能力强、收敛速度快; 在算法中后期, 该算法具有较强的局部搜索能力, 避免对复杂优化问题陷入局部最优.实验结果证明, 算法以更少的成本、较短的计算时间优于其他现有算法.

未来的研究方向主要是云计算环境下的软件可靠性评估和分配问题, 提高算法的精度和收敛速度, 改进目标函数的准确性, 研究构件可靠性对系统可靠性的影响.

附录A

通过一个简单的算例来介绍PHEDA-SCDE算法的进化操作, 对其有一个直观的认识.假设用分布估计算法求解f(x1, x2, x3)=x1+x2+x3的最大值, 其中, xj∈[0, 1](j=1, 2, 3).

第1步, 依据公式(5)初始化种群x, xi={xi, 1, xi, 2, …, xi, D}, i=1, 2, …, NP.种群大小NP为5, 种群维度D为3, 通过适应度函数f(x1, x2, x3)=x1+x2+x3计算各个个体适应度值, 此时, 最优个体为个体1.初始种群及适应度值见表 5.

Table 5 The initial population and its fitness 表 5 初始种群及适应度值

第2步, 通过EDA算法对初始种群进行优化.对种群按照适应度值从高到低排序, 假设阈值truncation=0.6, 选择较优的truncation×NP=3个个体, 分别为个体1、个体3和个体5.

a) 根据均值表达式(32)和方差表达式(33), 得到较优种群的均值和方差:

$ {u_j} = \frac{{\sum\nolimits_{i = 1}^{NP} {{x_{ij}}} }}{{NP}} $ (32)
$ {\sigma _j} = \sqrt {\frac{{\sum\nolimits_{i = 1}^{NP} {{{({x_{ij}}-{u_j})}^2}} }}{{NP}}} $ (33)

b) 根据公式(34)构建概率模型, 并从中采样, 得到NP个新样本, 构成新种群:

$ P(x) = \prod\nolimits_{j = 1}^D {\frac{1}{{\sqrt {2\pi {\sigma _j}} }}{e^{\frac{1}{2}{{\left( {\frac{{{x_j}-{u_j}}}{{{\sigma _j}}}} \right)}^2}}}} $ (34)

算法EDA生成的实验种群及适应度值见表 6.

Table 6 The EDA population and its fitness 表 6 EDA实验种群及适应度值

c) 假设此时为算法初期, 决策因子n=4.每个个体被选中的概率与适应度值大小成正比.适应度值越大, 被选中的概率越高.此时, 采用轮盘赌方法选择4个适应度值较高的实验个体, 组成EDA候选实验种群, 其种群及适应度值见表 7.

Table 7 The EDA candidate population and its fitness 表 7 EDA候选实验种群及适应度值

第3步, 通过SCDE算法对初始种群进行优化.

a) 假设初始变异算子F0=0.1, 当前迭代次数为1, 依据公式(6)自适应变异生成变异个体v, 例如v2=x2+0.2× (x5-x4).变异种群及适应度值见表 8.

Table 8 The SCDE mutation population and its fitness 表 8 SCDE变异种群及适应度值

b) 假设交叉算子CR0=0.4, CR1=0.7, 依据公式(9)和图 1进行自适应交叉, 生成实验个体u.SCDE实验种群及适应度值见表 9.

Table 9 The SCDE population and its fitness 表 9 SCDE实验种群及适应度值

c) 根据第2步中假设的决策因子n=4, 此时, 轮盘赌选择1个适应度值较高的实验个体5, 组成SCDE候选实验种群.

第4步, 合并EDA的候选实验个体1, 3, 5, 7和SCDE的候选实验个体5为新种群, 其种群及适应度值见表 10.

Table 10 The new population and its fitness 表 10 新种群及适应度值

第5步, 依据公式(8)对当前种群和新种群进行选择, 选择更优向量产生下一代.

第6步, 依据公式(10)更新决策因子n.

第7步, 若终止条件满足, 则算法终止; 否则, 转向第2步继续执行.

参考文献
[1]
Kuo W, Prasad VR. An annotated overview of system reliability optimization. IEEE Trans. on Reliability, 2000, 49(2): 176–187. [doi:10.1109/24.877336]
[2]
Ravi V, Reddy PJ, Zimmermann HJ. Fuzzy global optimization of complex system reliability. IEEE Trans. on Fuzzy Systems, 2000, 8(3): 241–248. [doi:10.1109/91.855914]
[3]
Nakagawa Y, Nakashima K. A heuristic method for determining optimal reliability allocation. IEEE Trans. on Reliability, 2009, R-26(3): 156–161. http://d.old.wanfangdata.com.cn/NSTLQK/10.1109-TR.1977.5220101/
[4]
Ramirez-Marque JE, Rocco CM. Evolutionary optimization technique for multi-state two-terminal reliability allocation in multi-objective problems. ⅡE Transactions, 2010, 42(8): 539–552. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=JJ0219796549
[5]
Hsieh TJ, Yeh WC. Penalty guided bees search for redundancy allocation problems with a mix of components in series-parallel systems. Computers & Operations Research, 2012, 39(11): 2688–2704. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=JJ0226743659
[6]
Khalili-Damghani K, Abtahi AR, Tavana M. A new multi-objective particle swarm optimization method for solving reliability redundancy allocation problems. Reliability Engineering & System Safety, 2013, 111(2): 58–75. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=JJ0229324872
[7]
Tran DH, Cheng MY, Cao MT. Hybrid multiple objective artificial bee colony with differential evolution for the time-cost-quality trade off problem. Knowledge-Based Systems, 2015, 74(1): 176–186.
[8]
Zhang J, Lei H. A pre-distribution algorithm of component reliability in Internetware system. Computing, 2015, 97(7): 755–768. [doi:10.1007/s00607-015-0459-4]
[9]
Zhang E, Chen Q. Multi-Objective reliability redundancy allocation in an interval environment using particle swarm optimization. Reliability Engineering & System Safety, 2016, 145: 83–92.
[10]
Goševa-Popstojanova K, Trivedi KS. Architecture-based approach to reliability assessment of software systems. Performance Evaluation, 2001, 45(2-3): 179–204. [doi:10.1016/S0166-5316(01)00034-7]
[11]
Wang WL, Pan D, Chen MH. Architecture-Based software reliability modeling. Journal of Systems & Software, 2006, 79(1): 132–146. http://d.old.wanfangdata.com.cn/Periodical/jsjxtyy200904024
[12]
Cheung RC. A user-oriented software reliability model. Trans. on Software Engineering, 1980, 6(2): 118–125. http://d.old.wanfangdata.com.cn/NSTLQK/10.1109-TSE.1980.234477/
[13]
Helander ME, Zhao M, Ohlsson N. Planning models for software reliability and cost. IEEE Trans. on Software Engineering, 1998, 24(6): 420–434. [doi:10.1109/32.689400]
[14]
Li F, Wu T, Hu M, Dong J. An accurate penalty-based approach for reliability-based design optimization. Research in Engineering Design, 2010, 21(2): 87–98. [doi:10.1007/s00163-009-0083-4]
[15]
Mettas A. Reliability allocation and optimization for complex systems. In: Proc. of the Annual Reliability and Maintainability Symp. 2000, 30(6): 216-221.
[16]
Wang SY, Wang L, Xu Y. An effective estimation of distribution algorithm for the flexible job-shop scheduling problem with fuzzy processing time. Int'l Journal of Production Research, 2013, 51(12): 3778–3793. [doi:10.1080/00207543.2013.765077]
[17]
Das S, Suganthan PN. Differential evolution:A survey of the state-of-the-art. IEEE Trans. on Evolutionary Computation, 2011, 15(1): 4–31. [doi:10.1109/TEVC.2010.2059031]
[18]
Qin AK, Huang VL, Suganthan PN. Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans. on Evolutionary Computation, 2009, 13(2): 398–417. [doi:10.1109/TEVC.2008.927706]
[19]
Wang S, Li Y, Yang H, Liu H. Self-Adaptive differential evolution algorithm with improved mutation strategy. Applied Intelligence, 2017, 6: 1–15. [doi:10.3390/jintelligence6010001]
[20]
Alguliev RM, Aliguliyev RM, Isazade NR. DESAMC+DocSum:Differential evolution with self-adaptive mutation and crossover parameters for multi-document summarization. Knowledge-Based Systems, 2012, 36(36): 21–38.
[21]
Lipowski A, Lipowska D. Roulette-Wheel selection via stochastic acceptance. Physica A Statistical Mechanics & Its Applications, 2011, 391(6): 2193–2196. http://d.old.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ0225520253/
[22]
Zhang B, Pan QK, Gao L, Zhang XL, Sang HY, Li JQ. An effective modified migrating birds optimization for hybrid flowshop scheduling problem with lot streaming. Applied Soft Computing, 2016, 52(C): 14–27.
[23]
Kempthorne O, Montgomery DC. Design and analysis of experiments. Journal of the American Statistical Association, 2008, 101(474): 853–854. http://d.old.wanfangdata.com.cn/OAPaper/oai_pubmedcentral.nih.gov_3513475
[24]
Lo JH, Huang CY, Chen IY, Kuo SY, Lyu MR. Reliability assessment and sensitivity analysis of software reliability growth modeling based on software module structure. Journal of Systems & Software, 2005, 76(1): 3–13.
[25]
Yu Y, Qian C. Running time analysis: Convergence-based analysis reduces to switch analysis. In: Proc. of the IEEE Congress on Evolutionary Computation. New York: IEEE, 2015. 2603-2610.