冗余及监控混合策略的优化配置算法研究

何　盼　谭　春　袁　月　吴开贵

1(中国科学院重庆绿色智能技术研究院　重庆　400714)

2　　　(重庆大学计算机学院　重庆　400044)

(hepan@cigit.ac.cn)



冗余及监控混合策略的优化配置算法研究

何盼1谭春1袁月1吴开贵2

1(中国科学院重庆绿色智能技术研究院重庆400714)

2(重庆大学计算机学院重庆400044)

(hepan@cigit.ac.cn)

Optimal Resources Allocation Algorithm for Optional Redundancy and Monitoring Strategies

He Pan1, Tan Chun1, Yuan Yue1, and Wu Kaigui2

1(ChongqingInstituteofGreenandIntelligentTechnology,ChineseAcademyofScience,Chongqing400714)

2(CollegeofComputerScience,ChongqingUniversity,Chongqing400044)

AbstractIn big data environment, the use of optional redundancy and monitoring strategy in one system increases the usage of resource and causes state space expansion for optimal resources allocation model. The performance of existing evolutionary search algorithms should be improved for the solution space formed by both integer and non-integer variables. To improve the algorithm efficiency, a memetic algorithm based on triple element array is proposed on the analysis of search neighborhood. First of all, the impact of change of variables such as monitoring rate on the system reliability increase is analyzed and then changing-length neighbor generation method is proposed for monitoring rate on neighbor analysis. The neighbor generation method is also proposed for strategy options considering the relations between components. After that, local search operator is refined through the iterative search among components, which increases the search range while maintaining the local advantage of individuals. This operator is used for improving the whole framework of memetic algorithm. Experiment results indicates that this algorithm can be used to get the solution of strategy option of each component and the corresponding optimized parameters for multiple optional strategies. Compared with existing multi-strategy search algorithms, the improved memetic algorithm could get better resources allocation results under the same reliability constraint. The local search operator does not have great impact on the stability of the whole algorithm.

Key wordsredundancy allocation; monitoring resources allocation; reliability optimization; memetic algorithm; sensitivity analysis

摘要大数据环境中监控和冗余混合策略的采用引起资源优化配置模型的状态空间膨胀，进化搜索算法在整型与非整型变量结合的解空间中的搜索效率有待提高，为此提出了基于搜索邻域分析的三元组模因算法.在分析了监控频率等参数变化对组件及系统可靠性增长影响的基础上，针对监控频率提出了基于变长邻域的近邻生成方法，针对策略选项提出了与组件关联的近邻生成方法.采用模因算法框架并改进了局部搜索算子，通过组件间的迭代搜索在保持个体优势的同时增大搜索范围.该算法能够用于求解混合策略下的组件保障措施选项及相应优化配置参数；与现有多策略搜索算法相比，在相同可靠性约束下，该算法能够得到消耗更低的资源配置结果；局部搜索策略对算法稳定性未造成明显影响.

关键词冗余度分配；监控资源分配；可靠性优化；模因算法；敏感度分析

大数据环境中系统规模的增大和复杂性的提升为系统可靠性保障引入了新的研究焦点.大数据存储及处理系统一般持续运行时间较长，并且各个组件组成复杂，通常采用分布式系统架构进行数据运算[1]，单种可靠性保障策略在其中具有一定局限性[2]，系统可能同时出现多种可靠性策略的混合应用方式[3-4].但是任一可靠性保障策略的采用和多策略混合都会引起资源消耗增多，而大数据环境下的巨大能源消耗已成为亟待解决的问题[5]，需要从适时节约资源的角度出发对每个组件中采用的不同策略及其相应参数进行优化选择和替换.虽然已有文献面向可靠性优化建立了混合多种保障策略如不同冗余机制[6-8]、软件重配置与周期再生[3]、冗余与非完美排错结合[4]的资源优化配置模型，但均未针对大数据环境下的可靠性保障策略进行分析.在分布式计算环境中，为不中断系统的正常持续执行，自适应策略如监控也是常用的系统可靠性维护机制[9].在保留一定积极冗余[10]资源的同时，基于监控的动态替换作为一种常用手段被用于系统可靠性的维护中[11].虽然现有研究提出了监控策略优化配置[12-13]及冗余与监控结合策略的优化模型[14]，但在策略类型及参数的求解方面仍有一定不足.由于冗余或监控策略对系统可靠性影响的不同，资源优化配置通常为NP-难非线性优化问题，难以采用精确解法进行求解[15].而多保障策略的采用将增加优化模型中待求解变量的数量，使解变量的搜索空间呈指数级增长，增加进化算法搜索的难度.所以如何对冗余监控混合策略的变量空间进行深入分析并提高进化算法的搜索效率是本文主要需要解决的难题.

针对2种冗余机制混合的可靠性优化模型，Coit[16]采用了0-1整型规划方法求解每个组件所采取的冗余方式并得到相应的冗余度，Tavakkoli-Moghaddam等人[17]在三元组编码的基础上，采用改进遗传算法进行求解.以上文献主要针对单目标的冗余配置模型，Chambari等人[18]提出了面向多目标的多冗余策略配置优化模型，并采用了第2代快速非支配排序方法(NSGA Ⅱ)[19]进行个体选择.其后，Chambari等人[20]和Safari[21]分别采用了模拟退火算法以及基于Max-Min变异算子的遗传算法求解该多目标优化问题.以上2种算法中均采用了三元组编码方式，适用于搜索范围较大的整型参数变量，其搜索效果优于传统的遗传算法.以上2类研究虽然采用了不同的策略配置方式，但都局限于在冗余策略中进行选择，算法未对非整型变量的搜索作详细讨论.Nourelfath等人[4]考虑冗余与非完美排错结合的可靠性优化模型，采用划分空间的进化搜索算法搜索近优解，其中遗传算法被用于子空间的划分，禁忌搜索被用于子空间内部的局部搜索.在改进了非完美排错模型的基础上，Liu等人[22]采用遗传算法对冗余与非完美排错结合的优化模型进行求解.虽然以上算法适用于整型与非整型参数混合的变量求解，但对非整型数据的特征未做进一步分析，采用通用的搜索或选择算子，在复杂状态空间的搜索中仍存在一定问题.针对更为一般的软件系统，Levitin[23]采用遗传算法寻找不同软件版本的组合以及确定它们之间的执行顺序.Ahmadizar等人[24]采用了蚁群算法解决通用的优化配置模型，但仅用不同组件可靠性值及约束作为算法的输入，没有考虑具体保障策略的配置参数.

考虑大数据环境下冗余与监控策略并存的分布式系统，现有研究提供了基于三元组编码的模因算法进行求解[14]，该算法的交叉变异及选择算子能够保证算法在搜索广度中的效果，但未对连续非整型变量的搜索进行深入讨论，在搜索深度方面还有待提高：

1) 对整型离散冗余变量和非整型连续监控频率变量采用相同结构或类似的搜索算子，虽然在离散的搜索域中能够获得较好效果，但在连续空间搜索域中将受到限制，容易陷入局部最优解.

2) 对不同参数变量如冗余变量和监控频率变量之间的内在制约关系未做深入分析，对单个组件资源配置参数与整体系统资源配置参数间的关系也未作分析，将不同组件、不同策略的变量视为相互独立的参数进行搜索，在解的搜索深度上将受到限制.

所以，本文提出了对混合的监控策略和冗余策略同时进行优化选择配置的改进模因算法，为保留进化算法搜索广度的要求，保留了已有算法中的交叉、变异以及选择算子，同时针对连续的监控频率变量的特征，建立了变长邻域的迭代局部搜索算子用于增加搜索的深度.分析了积极冗余机制与基于监控的冗余替换机制的关系，在局部搜索过程中考虑了单个组件配置参数的变化对整体系统配置参数的影响，建立了改进的模因算法提高算法搜索效率和效果.本文首先分析了已有的冗余及监控混合策略的资源优化模型以及现有搜索算法的缺点；其次基于可靠性敏感度分析建立了监控频率局部搜索的变长邻域范围.在改进的局部搜索算子基础上建立了模因算法框架，并通过实验对比分析了改进算法与现有搜索算法的优缺点，验证了该算法在多策略优化配置问题上的优越性.

1冗余及监控混合策略的资源优化模型

1.1假设条件

对采用了冗余及监控混合可靠性保障策略的系统作4点假设：

1) 假设未采用任何保障机制时，组件i及其冗余组件的有效工作时间Xi满足指数分布，即Xi～EXP(λi)，其中λi表示未配置保障措施的单个组件i的失效率.

2) 假设在同一时刻1个组件只能采取积极冗余或基于监控的冗余替换其中一种机制，不同的组件可以采用不同的机制.

3) 为评估监控频率对组件可靠性的影响，假设基于监控的冗余替换机制中组件的冗余度固定为2，每个组件中设置监控的单元时间平均代价相同.

4) 假设针对的系统均为分布式系统，即系统可靠性与组件可靠性间的关系可通过层次方法[12]计算获得.

1.2融合2种保障策略的资源优化配置模型

针对可靠性保障策略进行资源优化的目的在于在有限的配置资源内达到系统可靠性的最大化或在保障系统可靠性的情况下进行资源的最小化配置.选用后者的优化思想建立融合冗余与监控2种保障策略的资源优化配置模型.

(1)

在式(1)中，Ri(t)表示时刻t系统中组件i的可靠性，Vi表示组件i的平均访问次数，m表示系统中的组件个数.λmi表示组件i的监控频率，Ci表示组件i的冗余代价.式(1)的约束条件为系统可靠性Rsys(t)达到可靠性约束R0的要求，优化目标为达到冗余配置资源Csys与监控配置资源Msys的最小化.xi与yi分别为组件冗余代价及监控代价的系数.

当组件i采用单纯的积极冗余机制时，该组件的可靠性Ri(t)如式(2)所示：

(2)

其中，λi表示未配置冗余的单个组件i的失效率，ni表示组件的冗余度(1≤ni≤p，p表示每个组件i的最大冗余度).此时冗余代价系数xi=ni，监控代价系数yi=0.

利用Markov链理论对组件可靠性及其与监控频率间的相关关系进行分析[25].当组件i采用基于监控的冗余替换机制时，该组件的可靠性Ri(t)如式(3)所示[12]：

(3)

其中,

组件i的监控周期为1λmi(0≤λmi≤q，q表示每个组件i的最大监控频率).此时xi=2，yi=1.

1.3基于三元组编码的传统模因算法

对每个组件而言，式(1)中的待求参数包括组件策略选项、冗余度以及监控频率3个变量xi=[ni,λmi,αi]，其中αi表示策略选择，故该优化问题是复杂的多元多目标非线性规划问题，难以采用传统线性规划的方法进行求解.为获取该问题的近似最优解，基于NSGA Ⅱ[19]的模因算法T-MOMA[14]被用于求解该问题.T-MOMA中采用了三元数组的编码方式对每个组件的策略选择方式、冗余度及监控频率进行编码.图1表示了6个组件组成的系统三元组编码，数组行1表示系统组件的冗余度，行2表示组件监控频率，行3代表可靠性保障策略选项(R：积极冗余，M：基于监控的冗余替换).

T-MOMA算法中的搜索策略存在2个弊端：

Fig. 1　Example of triple element encoding mechanism.图1 三元组编码示例

1) 与传统进化搜索算法的解相比，三元编码方式的解空间范围增大，传统基于三元组编码的交叉、变异、局部搜索算子针对三元组中的某行或某列数据采取相同操作，在数据类型相同且搜索范围相近时(如针对不同类型的冗余度搜索)，对不同参数可达到相似搜索效果.而监控频率参数为连续变量，监控频率参数的搜索空间远大于冗余参数的搜索范围.以m个组件的系统为例，冗余度范围在[1，5]内的整型变量，遍历搜索需要5m次，而对监控频率在[0，1]之内的连续变量，建设搜索间隔为0.01，则遍历搜索需要100m次(减小搜索间隔还将增大搜索次数).此时对两者采用相同方法将很难对监控策略的解空间进行深入搜索，所以针对不同类型变量需要采用不同类型的搜索策略.

2) 现有算法将三元组数据中的每行数据作为孤立的变量进行搜索.而在优化搜索过程中保障策略选项的改变对组件以及系统可靠性的影响较大，在交叉、变异算子中可采用此方法，但在局部搜索中产生的新个体可能丧失局部优势，难以适应近邻产生的条件，降低了局部搜索的效果，此时需要同时对组件乃至系统中其他配置参数进行相应调整.

由于在模因算法中，局部搜索算子是增强算法搜索效率的重要因素[26]，所以在第2节中主要针对局部搜索算子对以上2个问题进行改进.

2基于邻域分析的局部搜索近邻生成算法

局部搜索算子中为了对选定个体的近邻进行搜索选择，首先需要确定近邻的选择方法以及范围.在现有T-MOMA算法中，对xi=[ni,λmi,αi]中的3个变量分别在邻域范围内进行变化并产生相应的近邻.冗余度变量为离散变量，其近邻选择的邻域为[-1,1].监控频率为连续变量，其近邻选择的邻域范围为[-q2，q2]，近邻产生的改变值为[-q2，q2]中均匀分布的随机值，其中q为λmi的取值范围，同式(3).虽然监控频率的近邻产生是通过随机变量实现，但其邻域取值固定，在监控频率取值较大时容易产生更优的近邻，但在取值较小时反而不能对较小范围内的λmi值进行深入搜索.所以本节在可靠性参数敏感度分析的基础上，通过建立变长的邻域范围，改进局部搜索算子中的近邻生成方法.

2.1基于敏感度分析的变长邻域范围确定

根据式(1)～(3)的可靠性分析模型，参数变量(包括冗余度或监控频率)的增加将引起组件及系统可靠性增长，但随着参数变量值的增大，可靠性的增长趋势将逐渐减弱.图2和图3分别表示了示例组件的可靠性随冗余度或监控频率增加的变化趋势.

Fig. 2　Component reliability changing with the increase of redundancy.图2　组件可靠性随冗余度增加的变化趋势

Fig. 3　Component reliability changing with the increase of monitoring rate.图3　组件可靠性随监控频率增加的变化趋势

为对该影响关系作进一步分析，建立参数变量的变化对组件及系统可靠性增长的敏感度分析模型.

1) 参数变量对组件可靠性敏感度

冗余度及监控频率变化对组件的可靠性增长敏感度如式(4)～(5)所示，其中ai与bi同式(3).

(4)

(5)

2) 参数变量对系统可靠性敏感度

冗余度及监控频率变化对系统的可靠性增长敏感度如式(6)所示.

(6)

根据组件敏感度分析的结果，虽然冗余度增长对可靠性变化的影响呈下降趋势，但其为固定范围内的离散变量，故对冗余度的局部搜索可选择[-1,1]的邻域范围.与冗余度变化相比，监控频率的变化对可靠性增长的影响曲线较陡，同时，监控频率取值连续，难以对其影响进行评估.如图4所示，当监控频率值较小(如λm1<0.005)时，其细微的变化也将引起组件可靠性较大的增长，此时应选取范围较小的邻域进行近邻搜索；反之当监控频率值较大(如λm2>0.01)时，频率值的变化对可靠性增长的影响较小，则此时的邻域范围需要相应增大.

Fig. 4　The neighbor search range of different monitoring rate.图4　不同监控频率取值的邻域范围

采用固定长度的邻域或随机分布的邻域范围无法达到上述搜索目标.所以基于敏感度分析，建立监控频率的局部搜索变化范围为[-Δλmi，Δλmi]，如式(7)所示.在选取固定ΔRsys(t)值的前提下，λmi取值越大，[-Δλmi，Δλmi]范围越大，反之λmi取值越小，邻域范围越小.

(7)

2.2基于邻域分析的近邻生成方法

对组件xi=[ni,λmi,αi]中的3个变量分别进行不同变化可生成不同新个体用于局部算法搜索.

1) 基于冗余度变化的近邻生成

算法1. genNeighbour_N.

输入：需要进行局部搜索的个体pj、选定组件i；

① 生成新个体pj1.ni=pj.ni+1，其他值与pj相同；

2) 基于监控频率变化的近邻生成

1.3.4 树脂的静态吸附及解吸试验 2.0 g树脂加入已知浓度的红薯叶总黄酮提取溶液中室温吸附24 h，计算树脂静态吸附率。将吸附后树脂，加入到一定体积的解吸液中，于室温下解吸24 h，按下式计算树脂静态解吸率：

(8)

算法2. genNeighbour_Lambda.

输入：需要进行局部搜索的个体pj、选定组件i；

① 根据式(7)以及pj.λmi,计算相应Δλmi；

② 定义近邻搜索最大循环次数z；

③ fory=1：z

④ 利用式(8)、y值以及第①行获得的Δλmi计算εi；

⑤ 生成新个体pj2.λmi=pj.λmi+εi，其他值与pj相同；

⑦ 停止计算pj2；

⑧ end if

3) 基于策略选项混合变化的近邻生成

Fig. 5　Neighbor generation based on the redundancy and strategy change.图5　基于冗余度及策略选项混合变化的近邻生成方法

Fig. 6　Neighbor generation based on the monitoring rate and strategy change.图6　基于监控频率及策略选项混合变化的近邻生成方法

算法3. genNeighbour_Strategy.

输入：需要进行局部搜索的个体pj、选定组件i；

① 生成新个体pj3.αi=pj.αi的反值，其他值与pj相同；

② ifpj3.αi==R

④ else

⑥ ifpj3.ni==2

⑦ 生成新个体pj6=pj3；

⑧ fork=1：m

⑨ ifpj3.αk==M

⑩ 根据式(8)、式(9)以及pj3.λmi计算相应εk；

3基于迭代局部搜索策略的改进模因算法

在已有的局部搜索算子中，文献[21]采用了Max-Min变异方法选定个体中具有最大可靠性和最小可靠性的三元组进行变异，将某一组件的参数变量视为整体进行操作，在保证可靠性接近约束条件的同时可能减少资源消耗，但算法针对特定的三元组进行变化可能减低个体的部分优势.文献[14]针对3种变量分别进行迭代搜索，即对不同组件的同一变量采取统一操作.该方法能够提高搜索的范围，但搜索过程脱离了组件自身的可靠性分析，容易进入局部最优解.本节中结合以上2种方法各自的优点建立改进的迭代局部搜索算子并用以改进模因算法.

3.1迭代局部搜索算法

Fig. 7　Iterative search strategy in local search algorithm.图7　局部搜索算法中迭代搜索策略

针对选定的个体pj的近邻，局部搜索算法迭代的搜索该个体的近邻，在每一次迭代中，随机选择个体中的任意组件i，利用第2节中的近邻生成方法对其三元组数据xi=[ni,λmi,αi]进行变化产生近邻.该方法每次主要对个体中的1个组件进行特定改变，能够保持该个体的优势特征；同时通过多次迭代过程增大局部搜索的范围.每次迭代产生近邻个体的详细步骤如图7所示:

在迭代搜索每次近邻产生的同时检查其约束值以及目标值与原个体之间的支配关系，能够支配原始个体或不被原始个体支配的新个体将被加入子种群，继续下一次交叉变异计算.局部搜索算法的完整框架所示如下：

算法4. 迭代局部搜索算法localsearch.

输入：需要进行局部搜索的个体pj、可行解集Q、算法迭代次数l、最大迭代次数lmax；

输出：更新后的可行解集Q.

① ifl≤lmax，执行后续搜索；

② 在个体pj中随机选择一个组件i；

③ ifpj.αi==R

⑤ ifpj1与pj互为非支配解，或pj1支配pj

⑥ 将pj1加入可行解Q中；

⑦ end if

⑧localsearch(pj1,Q,l+1,lmax) ；

(pj，i)；

genNeighbour_Strategy(pj，i)；

3.2改进模因算法框架

基于3.1节的迭代局部搜索算法4，改进模因算法(UD-TMOMA)框架所示如下：

算法5. UD-TMOMA.

输入：父种群P0=∅、子种群Q=∅、进化代数t=0、最大进化代数tmax；

输出：结果子种群Q、进化代数t.

① 种群初始化：P0=(p1,p2,…,pN)，其中p1,p2,…,pN为随机生成的个体；

② whilet=0：tmax

③ 对Pt执行以下操作：基于三元组编码的交叉以及变异操作产生子种群Q；

④ forj=1：N×局部搜索概率

⑤ 从子种群Q中随机选择1个个体pj；

⑥localsearch(pj,Q,0,lmax)得到局部优化后的子种群Q；

⑦ end for

⑧ 合并父种群Pt和子种群Q生成新种群R；

⑨ 计算种群R中各个体的约束值和目标值；

⑩ 采用第2代快速非支配排序方法，按照非支配字体和聚集距离对R进行倒序排序；

算法中的种群初始化、交叉变异及排序操作与T-MOMA算法类似，可参见文献[14]，在本文中不作详细阐述.

3.3算法时间复杂度分析

与T-MOMA算法或传统基于Max-Min算子的遗传算法(GA)相比，UD-TMOMA算法的其他操作与其相同，时间复杂度的主要差别体现在局部搜索算子中.假设每次局部搜索迭代次数为n，根据个体的情况，UD-TMOMA算法的局部搜索算子每次可能产生3～6个新个体，所以时间复杂度在O(3n)到O(6n)之间，传统T-MOMA算法对每行向量分别采用迭代搜索，每行向量每次产生2个新个体，时间复杂度为O(3×2n)，而GA算法每次仅对2个特定组件进行操作，时间复杂度为O(1).所以UD-TMOMA算法的局部搜索算子时间复杂度有一定增加，在迭代过程中迭代次数的选择对算法时间增长有较显著效果.

4实验过程与结果分析

4.1实验设置

本节我们采用文献[27]中的系统结构和相应参数进行实验.系统的组织结构如图8所示:

Fig. 8　Example of system architecture.图8　系统结构示例

系统中采用的示例实验参数如表1所示:

Table 1　The Input Parameters of Units

Fig. 9　Example of component redundancy.图9　系统冗余示例

图8所示的系统被抽象为2部分：组件及组件间的状态转移关系.采用基于体系结构的可靠性分析方法[28]，原始状态下的系统可靠性Rsys≈R1R2R33.03R4R5R60.7R70.2R80.1R9R10R11R12.系统中的单个组件提供了特定的功能，为了保障系统可靠性，在实际运行过程中，可能存在多个具有相同功能的组件，其中,1个为正在使用的组件而其他组件均作为它的冗余备份存在，如图9所示.

每个组件中均可采用积极冗余[10]以及基于监控的冗余替换[12]2类机制进行冗余组件的替换.当组件采用积极冗余替换机制时，可替换的组件均处于运行状态中，组件可靠性主要取决于可替换的备份数量.采用监控替换机制时，被监测到故障的组件可以得到及时的替换，组件的可靠性主要依赖于监控机制的频率.考虑到2类机制共存于系统组件中，则需要同时对组件的冗余度以及监控频率进行计算，建立该系统的优化模型同式(1)，故将该系统模型用于本文中的UD-TMOMA算法实验.

经过多次实验，UD-TMOMA算法的参数设置如下：在邻域范围确定中，ΔRsys(t)=0.001，种群个位为100，循环次数tmax=500，交叉概率为0.9，变异概率为0.1，局部搜索概率为0.05，为减少局部搜索引起的时间消耗，局部搜索迭代次数lmax=3，局部搜索中监控频率搜索的最大循环次数z=3.

4.2案例分析

为对冗余及监控混合策略的优化配置结果做详细说明，在本实验中采用UD-TMOMA对特定条件下的系统进行运算，得到相应的资源配置结果如表2所示.其中，t表示选定的系统时间，R0表示相应的可靠性约束条件.由于UD-TMOMA算法的计算结果是1组平衡解集，表2中针对每组实验数据仅选择了其中具有代表性的2组结果.

Table 2　An Case Study of Example System

表2显示在不同约束条件下，该算法均可用于同时计算每个组件的可靠性保障措施选项以及相应的保障策略参数(如冗余度或监控频率).当时间增加或系统可靠性需求增长时，需要消耗更多的资源配置，不同组件冗余度或监控频率之间的增长相互影响，该特性与T-MOMA算法体现的结果一致.

4.3算法对比分析

为了证明算法在局部搜索中的优势，在本节中，将UD-TMOMA算法与已有文献中采用了三元组编码的GA[21]和T-MOMA[14]算法比较.目前基于三元组的GA算法是在多选择策略的系统冗余度分配领域的通用算法.为了增强算法的搜索效率，GA算法中采用了Max-Min变异算子，T-MOMA算法则采用了其他局部搜索策略.

1) 不同可靠性约束

在不同的可靠性约束条件下，采用3种算法分别计算近似最有资源优化配置模型，计算获得的2种资源消耗的解集如图10所示.其中假设t=10 h，选用了表1所示的系统输入值，设置可靠性约束从0.90变化至0.99.

图10显示UD-TMOMA算法获得配置方法所消耗的资源均低于其他2种方法计算获得的资源.为了对算法的效果进行定量比较，采用了覆盖率[29]作为度量标准，覆盖率体现了2种解集相互支配的程度.由于以上算法均为近似算法，具有一定随机性，所以对每种算法运行10次，所得到的每组优化配置结果对应的2种系统代价值的覆盖率如表3所示.

Fig. 10　Results of three algorithms using different reliability constraints.图10　3种算法对不同可靠性约束的实验结果

ReliabilityConstraintGA∕T-MOMAT-MOMA∕GAGA∕UD-TMOMAUD-TMOMA∕GAT-MOMA∕UD-TMOMAUD-TMOMA∕T-MOMA0.900.43640.99140.00000.99920.00100.99920.910.36470.98500.00120.99960.00060.99960.920.52150.62510.00001.00000.00050.99870.930.13620.89330.00000.99910.00001.00000.940.35220.89570.00000.99910.00000.99950.950.12090.80960.00000.99840.00000.99950.960.09090.71030.00001.00000.00000.99850.970.24170.44920.00000.99940.00001.00000.980.29980.57330.00000.99560.00510.99210.990.12000.83050.00000.93180.00000.8864Average0.26840.77630.00010.99220.00070.9874

Note: AB stands for A covers B.

2) 不同系统参数

除了不同的约束条件外，在t=10 h时也采用不同的系统组件失效率对3种算法进行实验，实验结果所消耗的资源如图11所示，该实验中设定可靠性约束为0.95，选取10组随机的系统组件失效率值进行实验.表4显示了不同测试用例下相应的覆盖率.

Fig. 11　Results of three algorithms using different system parameters.图11　3种算法对不同系统参数的实验结果

TestCaseGA∕T-MOMAT-MOMA∕GAGA∕UD-TMOMAUD-TMOMA∕GAT-MOMA∕UD-TMOMAUD-TMOMA∕T-MOMA10.06060.76610.00170.99750.00001.000020.10280.98530.00001.00000.00001.000030.36200.99540.00150.99930.00001.000040.18600.98340.00000.99920.00001.000050.52400.93490.00001.00000.00001.000060.25570.97590.00000.99950.00001.000070.26010.90690.00000.99960.00001.000080.35080.89540.00160.99650.00000.999590.32210.89600.00000.99960.00001.0000100.09910.88830.00000.99890.00001.0000Average0.25230.92280.00050.99900.00001.0000

Note: AB stands for A covers B.

从解集覆盖率的结果可以看到GA算法与T-MOMA算法的结果基本都被新算法UD-TMOMA所支配，在可靠性约束较低即解空间较大时尤为明显.为体现不同算法的解集在解空间的覆盖程度，以上解集计算的超体积指标(hypervolume indicator, HI)[30]值如表5所示.HI值体现了解集在空间的分布程度.

从HI值可以看出3种算法在解空间的分布情况基本相同，其中UD-TMOMA算法的分布结果比T-MOMA算法略差.

3) 与单策略算法比较

在本节中，基于混合多策略的资源优化配置方法与已有文献中基于单策略的可靠性优化方法包括积极冗余配置方法[31]以及监控替换配置方法[12]进行了对比.t=10 h时同样设置可靠性约束从0.90变化至0.99，在各种参数环境下分别运行基于UD-TMOMA的多策略方法以及基于MOMA[12]的监控资源分配和基于线性规划的冗余资源优化方法[31].不同方法进行可靠性优化后的资源消耗结果集如图12所示，为了更好地进行对比分析，T-MOMA算法的结果也在图12中有所体现.然后设定可靠性约束为0.95，选取10组随机的系统组件失效率值，得到的相应资源消耗结果如图13所示.

Table 5　Hypervolume Indicator of Different Algorithms under Different Conditions

Fig. 12　Resources comparison under different availability constraint.图12　不同可靠性约束下的资源消耗对比

Fig.13　Resources comparison using different system parameters.图13　不同系统参数下的资源消耗对比

上述实验结果中可以看到在可靠性约束较低的情况下(如R0=0.91,0.94)，单种监控策略在同等监控频率下消耗的冗余资源略少于混合策略计算得到的结果，对于T-MOMA算法尤其明显.采用UD-TMOMA算法，该情况略有改善.

4.4实验结果分析

从4.3节实验中我们可以得出2个结论：

1) 虽然UD-TMOMA算法中局部搜索策略的改变对解集在解空间的分布情况稍有降低，但没有对算法的稳定性造成明显影响，但在搜索性能方面有明显增加.

2) 由于单策略的搜索算法的参数变量较少，解空间小于混合策略的搜索算法，所以当可靠性约束较低时，单策略的搜索算法比混合策略的搜索算法获得的解略好，随着解空间减小，这种优势逐渐减弱.在与单策略搜索算法的比较中，UD-TMOMA算法的结果仍然优于T-MOMA算法.

总的来说，与其他多策略资源搜索算法相比，在不影响算法稳定性的前提下，UD-TMOMA能够获得更优的资源配置结果.在搜索空间较大的情况下，与单策略资源搜索算法相比还略有不足.

5结束语

本文中我们主要研究了面向可靠性优化设计的冗余和监控混合可靠性保障策略的资源优化配置算法.针对现有进化搜索算法在多元多维解空间中搜索力度的不足，建立了基于邻域分析的改进模因算法.首先对冗余度及监控频率等参数变量变化对组件及系统可靠性增长影响进行了分析.基于敏感度分析的结果建立了针对3种参数变量的近邻生成方法，例如针对监控频率搜索提出了基于变长邻域的近邻生成方法，针对策略选项搜索提出了与组件关联的系统近邻生成方法.采用改进近邻生成方法建立了局部搜索算子，通过组件间的迭代搜索在保持个体优势的同时增大搜索范围，并用以改进模因算法框架.通过实验验证了：该算法能够用于求解每个组件保障措施的选择以及相应的配置参数；与现有2种多策略搜索算法相比，改进模因算法能够获得取得更优的资源配置结果，在待求解空间较大时，优化效果尤为明显；虽然局部搜索策略使解集在解空间的分布略有降低，但对算法稳定性未造成明显影响.在本文中监控策略与冗余策略作为独立的措施被应用于系统组件中，在后续的研究中将考虑两者结合的措施，即同一组件同一时刻采取了2种或多种保障策略，在系统运行的过程中，考虑随时间变化的资源分配机制及相应的进化搜索算法.

参考文献

[1]Zhou Jiang, Wang Weiping, Meng Dan, et al. Key technology in distributed file system towards big data analysis[J]. Journal of Computer Research and Development, 2014, 51(2): 382-394 (in Chinese)(周江, 王伟平, 孟丹, 等. 面向大数据分析的分布式文件系统关键技术[J]. 计算机研究与发展, 2014, 51(2): 382-394)

[2]Amari S V, Dugan J B, Misra R B. Optimal reliability of systems subject to imperfect fault-coverage[J]. IEEE Trans on Reliability, 1999, 48(3): 275-284

[3]Du Xiaozhi, Qi Yong, Hou Di, et al. Software rejuvenation model based on reconfiguration and periodical rejuvenation[J]. Journal of Xi’an Jiaotong University, 2010, 44(1): 91-95 (in Chinese)(杜小智, 齐勇, 侯迪, 等. 重配置与周期再生相结合的软件再生模型[J]. 西安交通大学学报, 2010, 44(1): 91-95)

[4]Nourelfath M, Chatelet E, Nahas N. Joint redundancy and imperfect preventive maintenance optimization for series-parallel multi-state degraded systems[J]. Reliability Engineering & System Safety, 2012, 103: 51-60

[5]Mi Haibo, Wang Huaimin, Yin Gang, et al. Resource on-demand reconfiguration method for virtualized data centers[J]. Journal of Software, 2011, 22(9): 2193-2205 (in Chinese)(米海波, 王怀民, 尹刚, 等. 一种面向虚拟化数字中心资源按需重配置方法[J]. 软件学报, 2011, 22(9): 2193-2205)

[6]He Jialang, Zhang Kun, Meng Jin, et al. Hybrid software fault-tolerant model based on evolvable-modules redundancy[J]. Journal of Nanjing University of Science and Technology, 2012, 36(2): 272-277, 284 (in Chinese)(何加浪, 张琨, 孟锦, 等. 可进化模块冗余软件混合容错模型[J]. 南京理工大学学报, 2012, 36 (2): 272-277, 284)

[7]Coit D W. Cold-standby redundancy optimization for nonrepairable systems[J]. IIE Transactions, 2001, 33(6): 471-478

[8]Jia Jia, Yang Xuejun, Li Zhiling. A redundancy-multithread-based multiple GPU copies fault-Tolerance technique[J]. Journal of Computer Research and Development, 2013, 50(7): 1551-1562 (in Chinese)(贾佳, 杨学军, 李志凌. 一种基于冗余线程的GPU多副本容错技术[J]. 计算机研究与发展, 2013, 50(7): 1551-1562)

[9]Zhu Jun, Guo Changguo, Wu Quanyuan. A runtime monitoring web services interaction behaviors method based on CPN[J]. Journal of Computer Research and Development, 2011, 48(12): 2277-2289 (in Chinese)(朱俊, 郭长国, 吴泉源. 一种基于CPN的运行时监控服务交互行为的方法[J]. 计算机研究与发展, 2011, 48(12): 2277-2289)

[10]Romera R, Valdes J E, Zequeira R I. Active-redundancy allocation in systems[J]. IEEE Trans on Reliability, 2004, 53(3): 313-318

[11]Ben Halima R, Fki E, Drira K, et al. A large-scale monitoring and measurement campaign for web services-based applications[J]. Concurrency Computation Practice and Experience, 2010, 22(10): 1207-1222

[12]He Pan, Yuan Yue, Wu Kaigui. Optimal multi-objective monitoring resources allocation in distributed systems[J]. Computer Science, 2014, 41(5): 64-67, 77 (in Chinese)(何盼, 袁月, 吴开贵. 分布式系统监控资源多目标优化分配[J]. 计算机科学, 2014, 41(5): 64-67, 77)

[13]He Pan, Wu Kaigui, Wen Junhao, et al. Monitoring resources allocation for service composition under different monitoring mechanisms[C]Proc of the 5th Int Conf on Complex, Intelligent and Software Intensive Systems. Los Alamitos, CA: IEEE Computer Society, 2011: 263-270

[14]He Pan. Research on resources allocation in distributed systems oriented at optimal reliability design[D]. Chongqing: Chongqing University, 2012 (in Chinese)(何盼. 面向可靠性优化设计的分布式系统资源分配研究[D]. 重庆: 重庆大学, 2012)

[15]Chern M S. On the computational complexity of reliability redundancy allocation in a series system[J]. Operations Research Letters, 1992, 11(5): 309-315

[16]Coit D W. Maximization of system reliability with a choice of redundancy strategies[J]. IIE Transactions, 2003, 35(6): 535-543

[17]Tavakkoli-Moghaddam R, Safari J, Sassani F. Reliability optimization of series-parallel systems with a choice of redundancy strategies using a genetic algorithm[J]. Reliability Engineering and System Safety, 2008, 93(4): 550-556

[18]Chambari A, Rahmati S H A, Najafi A A, et al. A bi-objective model to optimize reliability and cost of system with a choice of redundancy strategies[J]. Computers and Industrial Engineering, 2012, 63(1): 109-119

[19]Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Trans on Evolutionary Computation, 2002, 6(2): 182-97

[20]Chambari A, Najafi A A, Rahmati S H A, et al. An efficient simulated annealing algorithm for the redundancy allocation problem with a choice of redundancy strategies[J]. Reliability Engineering and System Safety, 2013, 119: 158-164

[21]Safari J. Multi-objective reliability optimization of series-parallel systems with a choice of redundancy strategies[J]. Reliability Engineering and System Safety, 2012, 108: 10-20

[22]Liu Y, Huang H Z, Wang Z, et al. A joint redundancy and imperfect maintenance strategy optimization for multi-state systems[J]. IEEE Trans on Reliability, 2013, 62(2): 368-378

[23]Levitin G. Optimal structure of fault-tolerant software systems[J]. Reliability Engineering and System Safety, 2005, 89(3): 286-295

[24]Ahmadizar F, Soltanpanah H. Reliability optimization of a series system with multiple-choice and budget constraints using an efficient ant colony approach[J]. Expert Systems with Applications, 2011, 38(4): 3640-3646

[25]Zhuang Lu, Cai Mian, Shen Changxiang. Trusted dynamic measurement based on interactive Markov chains[J]. Journal of Computer Research and Development, 2011, 48(8): 1464-1472 (in Chinese)(庄琭, 蔡勉, 沈昌祥. 基于交互式马尔可夫链的可信动态度量研究[J]. 计算机研究与发展, 2011, 48(8): 1464-1472)

[26]Krasnogor N, Smith J. A tutorial for competent memetic algorithms: Model, taxonomy, and design issues[J]. IEEE Trans on Evolutionary Computation, 2005, 9(5): 474-488

[27]Xia Y, Wang H P, Huang Y, et al. A stochastic model for workflow QoS evaluation[J]. Scientific Programming, 2006, 14(34): 251-265

[28]Wu Caihua, Liu Juntao, Peng Shirui, et al. Deriving Markov chain usage model from UML model[J]. Journal of Computer Research and Development, 2012, 49(8): 1811-1819 (in Chinese)(吴彩华, 刘俊涛, 彭世蕤, 等. 基于UML的软件Markov链使用模型的构建[J]. 计算机研究与发展, 2012, 49(8): 1811-1819)

[29]Zitzler E, Deb K, Thiele L. Comparison of multiobjective evolutionary algorithms: Empirical results[J]. Evolutionary Computing, 2000, 8(2): 173-195

[30]Auger A, Bader J, Brockhoff D, et al. Theory of the hypervolume indicator: Optimalμ-distributions and the choice of the reference point[C]Proc of the 10th ACM SIGRVO Conf on Foundations of Genetic Algorithms. New York: ACM, 2009: 87-102

[31]He P, Xie Q. Reliability analysis of service composition with service pools and optimal configuration of service pool size

中图法分类号TP302.7; TP311.5

通信作者：袁月(yuanyue@cigit.ac.cn)

基金项目：国家自然科学基金项目(61309005)；重庆市基础与前沿研究计划一般项目(cstc2014jcyjA40015)

收稿日期：2014-11-05；修回日期：2015-03-19

This work was supported by the National Natural Science Foundation of China (61309005) and the Basic and Frontier Research Program of Chongqing (cstc2014jcyjA40015)