考虑采购成本与组合风险的构件优化选择方法

吴志樵，卢祥远，牟立峰，唐加福

(1.东北财经大学管理科学与工程学院，辽宁 大连 116025;2.上海大学悉尼工商学院，上海 200444)

考虑采购成本与组合风险的构件优化选择方法

吴志樵1，卢祥远1，牟立峰2，唐加福1

(1.东北财经大学管理科学与工程学院，辽宁 大连 116025;2.上海大学悉尼工商学院，上海 200444)

本文围绕着采购成本和组合风险这两个重要的系统非功能需求，将构件选择问题定义为在满足系统需求的情况下，为各模块选择具体的实施构件，实现系统总体设计最优。针对所建立的双目标整数规划模型，结合麦克劳林展开式二阶拉格朗日余项，给出了精确的关于系统组合风险预测的误差分析方法，据此得出应用该模型估计系统总体风险的适用条件。进一步设计了求解全部有效解集的启发式算法。并对由小到大四种规模的算例，采用衡量多目标优化算法的重要指标——生成有效解向量的比率(ONVGR)，比较了本文提出算法与NSGA-II算法。

系统构件选择；优化模型；多目标优化

1 引言

基于构件的产品开发(CBD)是以构件为中心组织整个产品开发过程，主要包括构件设计、构件选择、构件测试与适配、构件更新、构件集成及产品规划设计等多阶段。区别于传统的从零开始开发方式，构件选择是通过采购市场中已有构件来实现。构件选择既是CBD开发的基础工作，也是贯穿整个开发过程的核心工作。目前针对这部分的研究多数都是关于构件技术的实现细节[1], 而缺少宏观上的决策指导构件的选择。当建立一个由若干模块(或称子系统)构成的系统时，为每一模块从一组具有相似功能属性，而具有不同非功能属性(如成本与组合风险)的备选构件集合中选择一个构件实施，达到系统总体最优是统筹学研究中的关键问题。

自上世纪九十年代以来，许多的优化方法被引入构件选择问题中，按照优化目标的不同，主要分为风险最优问题[2]或成本最优问题[3-6]。然而，在实际的系统开发过程中对构件选择问题，仅单独考虑成本或者风险的最优解往往不是决策者真正需要的，有时决策者也并不需要单纯最优解。而协同考虑这两个目标的有效解却显得更为重要并有意义[7-8]。由于这两个目标间复杂的非线性关系，有学者通过设计非支配排序算法(Nondominated Sorting Genetic Algorithm, NSGA)来求解近似最优解[9]。但亚启发式算法NSGA本身有两个缺陷：1)不能保证求出全部的有效解；2)求出的有效解中没有平衡成本与风险两个目标的决策信息，使决策者面临从有效解集中选择适合组织的有效解的困难[9-10]。

本文通过对构件的成本与组合风险两项指标关系进行研究，建立一个双目标0-1整数规划模型，为开发者提供满足系统需求情况下考虑成本与组合风险最优的构件选择方法。同时，根据模型特点设计基于支持有效解集的启发式算法求解全部有效解集。采用衡量多目标优化算法的重要指标——生成有效解向量的比率(ONVGR)来比较本文提出算法与NSGA-II算法。

1.1 考虑成本与组合风险的构件选择问题描述

文中使用的参数分别是：

n为完成目标系统需要开发的模块个数；

mj为模块j可以选择的构件个数；

cij表示第j个模块选择第i种构件实施时的采购成本($)；

ηij表示第j个模块选择第i种构件实施时的失败率(%)；

sj为第j个模块在此产品架构实现时被调用的平均次数(次)；

Satij(k)表示当第j个模块选择第i种构件开发时，第k个目标的可满足性水平。

文中使用的变量为：

不同于简单的产品开发，CBD可以系统地组织一组产品同时开发。从产品线管理角度来说，产品线可视为在一组共享资源基础上建立的产品组合，产品组合中各产品分别满足特定领域市场的需求。不失一般性地，为了便于理解产品线中的共享资源通过抽象的模块进行表示，并且每一模块可以通过使用一个构件进行实施，而且每一模块需要实现至少一个功能目标。根据面向目标的需求工程(The Goal-Oriented Requirement Engineering Approach，GORE)[11-12]，需求经过抽象、细分均转化为可以量化考核的目标，这些目标可以根据组织的需要被划分为若干评分档次，决策者可以通过测试、分析和匹配各构件资产执行时的效果，使用可满足性函数对资产进行度量评分。图1表示在面向目标的需求工程下构件选择的框架，以模块为基本单元来衡量质量目标和构件。

图1 面向目标的需求工程下构件选择框架

在此框架下，围绕着成本和组合风险这两个重要的非功能需求，构件选择决策问题可以定义为在满足系统需求的情况下，为各模块选择具体实施的构件，最终实现总体开发成本和组合风险最优的目标。

1.2 组合风险的描述与误差分析

根据Berman[2]的研究，模块的错误发生概率服从指数分布。那么，假设以pj表示模块j在系统执行时至少发生一次错误的概率，则模块j没有错误发生的概率可以表示为：

(1)

(2)

最优化系统的组合风险也就可以表示成为最小化至少一次发生错误的概率。这样，目标函数表示为：

(3)

假设系统中任意模块出现错误，便导致整个系统错误。根据麦克劳林前两阶展开式，可以将原组合风险目标方程(3)近似表示为：

(4)

其中，将(3)式展开为(4)式的麦克劳林展开式的二阶拉格朗日余项为：

(5)

下面考虑该拉格朗日余项，即(5)式趋于零的条件。

故此，(5)式在完成目标系统需要开发的模块个数n趋于无穷的时候接近于零。而事实上为完成目标系统需要开发的模块个数n总会是有限个，并且n越大，系统出错的概率就会越高，进而导致组合风险存在近似误差。

(6)

假设系统对组合风险估计误差的可接受波动大小为δ，则由(5)式导致的误差在δ范围内时，所提出的求解模型是有效的。根据上述，显然t满足(6)式时，(5)式取得最大值。若已知系统的误差可接受波动大小δ，则：

θ∈(0,e-1/2)

(7)

当系统组合风险估计误差的可接受波动满足(7)式时，我们认为模型是有效的。

1.3 系统需求约束的描述

本文采用目前被业界广泛使用的面向目标的需求工程(GORE)[11-12]来衡量系统的系统需求。GORE主要是通过抽象和细分将需求转化成为可以量化考核的目标，再把这些目标根据组织的需要划分为若干评分档次，决策者可以通过测试、分析和匹配各构件执行时的效果，使用可满足性水平反映各构件(功能模块)的度量评分。假设满意度水平参数(Satisfaction Level，Satij(k))在[0,1]区间上，并且已经通过匹配各目标档次得到。通过对各目标的加权求和，可以得到第j个模块选择第i种构件开发时的总体可满足性水平Satij：

(8)

其中，τk表示各目标k的权重。

则整个系统的需求约束可以描述为：

(9)

表示整个系统的运行至少需要达到某一可接受水平R。式中，ωj表示模块j的权重。

1.4 数学模型

通过以上对成本、组合风险和系统需求的描述，可以得到满足系统需求下考虑成本和组合风险最优的优化模型(Model of Cost and combinational Risk Optimization under a goal satisfaction constraint，C&R)：

(10)

(11)

(12)

(13)

xij=0/1,∀i,j

(14)

其中，式(10)表示整个系统的总成本。式(13)表示对于各模块而言，无论选择何种构件，只使用一种构件实施。

2 启发式算法

可以看出，C&R模型为双目标整数规划模型(The Bi-objective 0-1 Integer Programming)，决策者使用目前如ILOG Cplex 10、Lindo和Lingo12.0等优化软件不能求解，而使用如遗传算法、模拟退火算法和分散搜索算法等智能优化算法仅能求出部分有效解。为此，本文根据该模型的特点设计了三阶段启发式算法对其进行求解，提供全部非劣解集 (Non-dominated Solution)，以方便模型使用。

2.1 启发式算法的假设条件与相关概念

假设系统中任意模块出现错误，便导致整个系统错误。根据麦克劳林前两阶展开式(The First Two Terms of Maclaurin Series Expansion)，可以将原组合风险目标方程(4)近似表示为：

(15)

不同于单目标优化模型具有唯一的最优解，一般来讲，多目标优化问题并不存在唯一最优解，而是往往通过一个解的集合来表示求解结果。该集合描述的是与集合之外的解相比较，集合中的解至少有一个目标值优于集合之外的一个解，且其他目标值均不比这个集合外的解劣，这种解集中的解我们称之为非支配解(Non-dominated Solution)或者Pareto解，并将这种解集称为有效解集(Efficient Solution)[13]。

为了更有效地描述本算法，下面给出C&R模型中非支配解的具体定义。

假设引入一个在 [0,1]之间取值的偏好值λ(Preferences)，通过对两个原目标函数加权求和，构成一个新的目标函数：

z(x,λ)=λzCOS(x)+(1-λ)zREL(x)

(16)

这个偏好值反应决策者对成本与组合风险的偏好信息，通过将原来的两个目标加权成为一个目标，再求解该优化模型，可以得到原问题的一个有效解，并且这一有效解反应了决策者事先定义好的对成本与组合风险的偏好信息。

从理论上讲，如果可以遍历偏好值λ在[0,1]之间的取值，并以各加权后的目标函数作为新的目标，在满足约束(12)～(14)的条件下对模型进行求解，在凸可行域上就可以得到全部非支配解。然而这种方法存在两个局限性：第一，遍历所有偏好值λ的取值在实际中是不能实现的；第二，对于非凸可行域的问题，使用该方法不能求解出全部非支配解。为此，本文提出一种可以获得全部非支配解的算法。通过在满足约束(12)～(14)下，最小化加权后的目标函数(16)可以获得部分有效解，这部分有效解我们将其称之为支持的有效解(Supported Efficient Solutions，Supported-ES)；同时，将有效解集中的其他有效解称之为非支持的有效解(Non-supported Efficient Solutions，Non- supported-ES)。此算法应用非支持的有效解必存在于两个连续的支持有效解之间的理论[14]，基于此理论，在本文提出的三阶段算法中：第一阶段对全部可能的联合效用值(Aggregated Efficiency)进行排序，由于排序的变化取决于偏好λ的取值，得到排序稳定的λ的区间范围，以此有效地解决了遍历全部偏好λ的取值的困境；第二阶段通过引入贪婪启发式规则，遍历得出全部支持的有效解；第三阶段中，通过遍历任意两个连续的支持有效解构成的区间，得到全部非支持的有效解。至此，全部的有效解就得到了。

为了更清楚地说明算法的求解过程，引入如下定义：

通过上述定义可以进一步得到考虑带偏好值的联合效率值(Aggregated Efficiency)eij(λ)为：

eij(λ)=αijλ+βij(1-λ)=βij+(αij-βij)λ

(17)

它表示第j个模块选择第i种构件实施时，每单位满足度增加所付出的成本与组合风险联合作用。

因此，对于一个给定的λ′，可以得到其联合效用值排序：

el1j(λ′)≤…≤elij(λ′)≤eli+1j(λ′)≤…≤elmjj(λ′)，

where=<1,2,…,mj>

(18)

遍历所有可能存在的联合效用值的排序，就得到所有的确定支持有效解，相应的每一对应有效解的排序，我们称之为有效排序(Efficient Order，EO)。

2.2 第一阶段：确定联合效用值的有效排序

本小节中将确定所有可能的有效排序(EO)，以及各EO的对应偏好值λ的区间。随着偏好值λ在可行域[0, 1]的变化，EO不是固定不变的，首先介绍确定各模块有效排序的λ子区间([0,u1j],…,[utj,ut+1j],…,[uTj,1]))的算法。

第一阶段算法的流程如下：

开始

第1步：初始化t←0，λt←0，utj←0；

第2步：以λt的取值，将所有构件按照式(18)进行排序；

第3步：通过求解下面优化问题确定有效的偏好值的上界(upper bounds)

Maxλ

s.t.elij(λ)≤eli+1j(λ)

i=1,…,mj-1，0≤λ≤1

(19)

假设用λmax来表示(19)模型的最优解，如果λmax≥1，则令t←t+1，utj←1

即表示模块j的全部有效的偏好值区间已经确定完毕，进行第4步；

第4步： 令t←t+1,utj←λmax,λt←λmax+ε(其中ε为干扰项(perturbation factor),ε>0)。进行第2步；

结束

此外，式(19)可以使用αij和βij参数，通过如下优化模型(20)进行求解：

(αi+1j-βi+1j-(αij-βij))<0,i=1,…,mj}

(20)

推论1 各模块的有效排序个数等于模型(20)在从0遍历到1的过程中所取得的偏好值λmax的个数。

根据第一阶段启发式(Procedure-1)可以得出各模块的有效排序及其对应的子区间，并通过合并全部子区间可以得出有效排序不改变的偏好值区间([0,v1],…, [vg,vg+1],…, [vG,1])。

2.3 第二阶段：求解支持有效解

对于每一个有效排序不变的偏好值λ的区间，通过贪婪启发式过程求解出支持有效解，遍历全部区间便可以得到全部的支持有效解。

第二阶段算法的流程如下：

开始

第1步：初始化h←0,g←0,λh←0,EfficientSet←{φ},ExploreSet←{φ}；

第3步：循环直到满足系统需求约束(12)为止：

如果xli+1j=non，则将xlij锁定为必选解；

否则对ExploreSet∪{xli+1j}，EfficientSet←{xli+1j}使用构件xli+1j更新}

第4步：如果满足Dantzig检验条件 (17)；则保存支持到支持有效解集中，

并初始化EfficientSet←{φ},ExploreSet←{φ}。

第5步：λh=vg+1+ε(其中ε为干扰项(perturbation factor),ε>0)；

如果λh≥1, 则终止算法(说明所有空间已经搜索完毕)；,

否则返回第2步；

结束

在此过程中需要用到的Dantzig规则如下：

(21)

s.t.ρ1j≥βij+(αij-βij)λ,i∈EfficientSet

ρ1j≥0,ρ2j≥0,1≥λ≥0

使用z*和λ*表示优化模型(21)的最优解。根据Dantzig 规则，可以进一步得到推论2。

通过对每一模块使用(Procedure-2)，可以获得全部支持有效解，并且每一支持有效解都会带有相应的成本与组合风险的偏好信息(Trade-off Information ofλ)，以辅助决策者进行有效解选择。

2.4 第三阶段：求解非支持有效解

而对于剩余的有效解，也就是之前提到的非支持有效解必存在于两个连续的支持有效解之间的理论，将通过本阶段启发式算法进一步搜索，以确保全部有效解被遍历。

第三阶段算法的流程如下：

开始

第1步：初始化支持有效解集(Supported-ES set)

第2步：构造搜索空间，空间中的下界(Lower bound)由有效解的连线构成，而上界(Upper bound)为将C&R模型松弛为0-1连续背包问题后有效解的连线。

第3步：通过建立典型搜索技术分支定界算法(Branch-and-bound)[14]或者动态规划算法(Dynamic programming)[15]搜索各目标值下降空间(Reduced objective Space)，当遍历过所有解空间之后，全部的非支持有效解也就确定完毕。

结束

此外，加权目标函数(Aggregated Functions)可以进一步用来确定分支定界搜索(Branch-and-Bound)下降空间。

特别地，为了方便大规模问题的求解，由于各模块的处理过程间具有平行关系(Procedure-1)，因此可以在不同的处理器上进行运算，最后通过合成得到有效排序稳定的区间。

3 案例分析

本节以邮箱系统为例来验证前文所提优化模型及其启发式算法在实际应用中的有效性。

一个邮件数据请求从发件人所处的用户代理服务器(Mail User Agent，MUA)，可以由四个模块构成：Web Mail Servers、Wap Mail Servers、Secure Mail、Network Communication(为方便表述，后文将其分别缩写为模块1、模块2、模块3、模块4)。考虑到产品的多样性，产品1、产品2、产品3三类可如图2进行开发。

图中的连线表示不同产品开发时需要用到的模块。例如开发产品1，将用到Web Mail Servers和 Wap Mail Servers模块作为产品的构成模块。

各构件所需操作成本均使用成本表示，其可以通过平均的工时成本(Man-hours)来计算。求解出各模块在不同的可选择构件下所对应的成本参数cij、及组合风险值ηij，结果见表1。并根据各模块的使用频率得到各模块的权重值为(0.472, 0.311, 0.087, 0.066)。

图2 邮件系统产品线架构图

构件序号模块1模块2模块3模块4成本组合风险满意度成本组合风险满意度成本组合风险满意度成本组合风险满意度110005.10.7118007.20.6110004.60.671155.10.5124207.10.734208.70.724206.50.74855.30.5834606.80.634608.10.664106.80.68954.90.6244106.90.645107.10.683606.90.791004.60.7358504.80.6514505.60.558005.50.751553.70.5765455.20.8310156.10.746425.80.8312150.710.9676805.10.9118645.50.913997.10.785293.40.88

表2描述了当R=0.8时得到的支持有效解，每个解由编码给出。编码“7716”表示四个模块分别使用的是构件7、构件7、构件1、构件6。图3反映的是支持有效解在成本与组合风险这两个目标空间上的情况。

表2 启发式算法获得的支持有效解

图3 R=0.8时得到的支持有效解

4 算法性能的评估

算法性能的评估是多目标优化问题重点研究的内容之一。本文针对从小到大4个规模的问题, 采用衡量多目标优化算法的重要指标——生成有效解向量的比率(Overall Nondominated Vector Generation Ratio， ONVGR)来比较本文提出算法与NSGA-II算法。本文用PFt表示本文提出算法获得的有效解的个数，其值越大说明决策者有越多的选择。类似地，用PFn来表示NSGA-II算法获得的有效解的个数；则生成效解数比率可表示为ONVGR=PFn/PFt。

首先随机生成四组算例，算例规模分别为10×10、 25×25、25×50和50×100(模块数×备选构件数)， 缩写为P-1、P-2、P-3和P-4。它们各自的成本, 失败率和可满足性水平均在区间[100, 5000]、[0.0001, 0.001]和[0.5, 1]内随机生成, 并将可接受可满足性水平设置为0.6。NSGA-II算法的种群数设置为100， 迭代次数设置为200。本文所列出结果为NSGA-II算法执行10次的平均值。为了客观地比较上述两种算法，本文采用两种NSGA-II参数设置策略: 1) 交叉率设置为0.5、0.7、0.9，同时变异率设置为0.03；2)变异率设置为 0.01、0.03、0.05，同时交叉率设置为0.9。

上述两个算法比较结果如表3和表4所示，依据ONVGR指标，NSGA-II算法有效性仅相当于本文提出算法71%～96%。而且NSGA-II的不同变异率和交叉率下的ONVGR比率均劣于本文提出算法。

表3 NSGA-II.不同变异率下ONVGR比率

表4 NSGA-II.不同交叉率下ONVGR比率

5 结语

本文通过建立了一个双目标0-1整数规划模型，提供满足系统需求情况下的成本最小且组合风险最低的解决方案。通过分析麦克劳林展开式的二阶拉格朗日余项，给出了该解决方案的适用条件，指出在系统组合风险估计误差的波动在一定可接受范围内时，该估计模型是有效的。并设计三阶段启发式算法对其进行求解，前两阶段确定支持有效解集、第三阶段得到非支持有效解集，以提供全部非劣解集，用于从非劣解集中选择最适合方案实施。最后，通过算例分析验证了该模型和算法的适用性。

[1] 邵良杉, 张照. 组件、COM与Windows DNA技术在MIS中应用研究[J]. 中国管理科学,2000,8(S1): 131-135.

[2] Berman O，Cutler M. Optimal software implementation considering reliability and cost[J]. Computers & Operations Research，1997，25(10)： 857-868.

[3] Cortellessa V，Marinelli F，Potena P. Automated selection of software components based on cost/reliability tradeoff[C]//Proceedings of European Workshop on Software Architectwre，2006，4344：66-81.

[4] Cortellessa V，Marinelli F， Potena P. An optimization framework for "build-or-buy" decisions in software architecture[J]. Computers & Operations Research，2008，35(10)： 3090-3106.

[5] Boehm B W，Valerdi R. Achievements and challenges in Cocomo-based software resource estimation[J]. IEEE Software，2008，25(5)：74-83.

[6] Wu Zhiqiao, Kwong C K. Integrated model for software component selection with simultaneous consideration of implementation and verification[J]. Computers & Operations Research, 2012，39(12)：3376-3393.

[7] Wang Zai, Tang Ke, Yao Xin. Multi-objective approaches to optimal testing resource allocation in modular software systems[J]. IEEE Transactions on reliablity，2010， 59 (3)：563-575.

[8] Zhang Yuanyuan, Harman M, Mansouri A. The multi-objective next release problem[C]//Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation，ACM，London，England，July 7-11,2007.

[9] Stummer C，Kiesling E. A multicriteria decision support system for competence-driven project portfolio selection[J]. International Journal of Information Technology & Decision Making， 2009，8(2)：379-401.

[10] Wu Zhiqiao, Tang Jiafu,Kwong C K, et al. A model and its algorithm for software reuse optimization problem with simultaneous reliability and cost consideration[J]. International Journal of Innovative Computing, Information and Control，2011，7(5)：2611-2622.

[11] Lamsweerde A V，Letier E. Handling obstacles in goal-oriented requirements engineering[J]. IEEE Transactions on software engineering，2000，26(10)：978-1005.

[12] Letier E，Kramer J,Magee J,et al. Deriving event-based transition systems from goal-oriented requirements models[J]. Automated Software Engineering，2008,15(2)：175-206.

[13] Chen Jiangyong, Lin Qiuzhen, Hu Qingbin. Application of novel clonal algorithm in multiobjective optimization[J]. International Journal of Information Technology & Decision Making，2010, 9(2)：239-266.

[14] Visee M,Teghem J,Pirlot M, et al. Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem[J]. Journal of Global Optimization，1998，12(2)：139-155.

[15] Bazgan C， Hugot H， Vanderpooten D. Solving efficiently the 0-1 multi-objective knapsack problem[J]. Computers & Operations Research，2009，36(1)：260-279.

An Optimization Model for System Component Selection to Minimize Cost and Combinational Risk

WU Zhi-qiao1，LU Xiang-yuan1, MU Li-feng2, TANG Jia-fu1

(1.College of Management Science and Engineering，Dongbei University of Finance and Economics，Dalian 116025， China;2.SHU-UTS SILC Business School, Shanghai University, Shanghai 200444,China)

In contrast to the traditional process of product development, Component-Based Development (CBD) focuses on building products by integrating previously-existing components. So to start with, an available set of components should be identified. In this paper, this major problem of component-based system development involves the effective evaluation and selection alternative system components is addressed by considered the cost and combinational risk factors. Based on a bi-objective 0-1 integer programming, an optimization model is proposed that can assist decision-makers in selecting system components for minimizing cost and combinational risk, and satisfying system requirements. The condition of application of the proposed model is further proposed based on the Maclaurin expansion with second order Lagrange remained term. To solve the model efficiently, a supported efficient solution based algorithm is presented that can find the entire set of efficient solutions. Computational experience also describes in solving the problems using the Metaheuristics and the proposed algorithm.

component selection；optimization model；multiple objective programming

1003-207(2017)08-0158-08

10.16381/j.cnki.issn1003-207x.2017.08.017

2015-05-25；

2015-11-24

国家自然科学基金资助项目(71301107，71671028)

吴志樵(1981-)，男(锡伯族)，辽宁沈阳人，东北财经大学科学与工程学院副教授，博士生导师，博士，研究方向：服务系统工程,E-mail: wuzhiqiao@dufe.edu.cn.

TP311.5

A