考慮采購成本與組合風(fēng)險的構(gòu)件優(yōu)化選擇方法

吳志樵，盧祥遠(yuǎn)，牟立峰，唐加福

(1.東北財經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，遼寧 大連 116025;2.上海大學(xué)悉尼工商學(xué)院，上海 200444)

考慮采購成本與組合風(fēng)險的構(gòu)件優(yōu)化選擇方法

吳志樵1，盧祥遠(yuǎn)1，牟立峰2，唐加福1

(1.東北財經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，遼寧 大連 116025;2.上海大學(xué)悉尼工商學(xué)院，上海 200444)

本文圍繞著采購成本和組合風(fēng)險這兩個重要的系統(tǒng)非功能需求，將構(gòu)件選擇問題定義為在滿足系統(tǒng)需求的情況下，為各模塊選擇具體的實(shí)施構(gòu)件，實(shí)現(xiàn)系統(tǒng)總體設(shè)計最優(yōu)。針對所建立的雙目標(biāo)整數(shù)規(guī)劃模型，結(jié)合麥克勞林展開式二階拉格朗日余項，給出了精確的關(guān)于系統(tǒng)組合風(fēng)險預(yù)測的誤差分析方法，據(jù)此得出應(yīng)用該模型估計系統(tǒng)總體風(fēng)險的適用條件。進(jìn)一步設(shè)計了求解全部有效解集的啟發(fā)式算法。并對由小到大四種規(guī)模的算例，采用衡量多目標(biāo)優(yōu)化算法的重要指標(biāo)——生成有效解向量的比率(ONVGR)，比較了本文提出算法與NSGA-II算法。

系統(tǒng)構(gòu)件選擇；優(yōu)化模型；多目標(biāo)優(yōu)化

1 引言

基于構(gòu)件的產(chǎn)品開發(fā)(CBD)是以構(gòu)件為中心組織整個產(chǎn)品開發(fā)過程，主要包括構(gòu)件設(shè)計、構(gòu)件選擇、構(gòu)件測試與適配、構(gòu)件更新、構(gòu)件集成及產(chǎn)品規(guī)劃設(shè)計等多階段。區(qū)別于傳統(tǒng)的從零開始開發(fā)方式，構(gòu)件選擇是通過采購市場中已有構(gòu)件來實(shí)現(xiàn)。構(gòu)件選擇既是CBD開發(fā)的基礎(chǔ)工作，也是貫穿整個開發(fā)過程的核心工作。目前針對這部分的研究多數(shù)都是關(guān)于構(gòu)件技術(shù)的實(shí)現(xiàn)細(xì)節(jié)[1], 而缺少宏觀上的決策指導(dǎo)構(gòu)件的選擇。當(dāng)建立一個由若干模塊(或稱子系統(tǒng))構(gòu)成的系統(tǒng)時，為每一模塊從一組具有相似功能屬性，而具有不同非功能屬性(如成本與組合風(fēng)險)的備選構(gòu)件集合中選擇一個構(gòu)件實(shí)施，達(dá)到系統(tǒng)總體最優(yōu)是統(tǒng)籌學(xué)研究中的關(guān)鍵問題。

自上世紀(jì)九十年代以來，許多的優(yōu)化方法被引入構(gòu)件選擇問題中，按照優(yōu)化目標(biāo)的不同，主要分為風(fēng)險最優(yōu)問題[2]或成本最優(yōu)問題[3-6]。然而，在實(shí)際的系統(tǒng)開發(fā)過程中對構(gòu)件選擇問題，僅單獨(dú)考慮成本或者風(fēng)險的最優(yōu)解往往不是決策者真正需要的，有時決策者也并不需要單純最優(yōu)解。而協(xié)同考慮這兩個目標(biāo)的有效解卻顯得更為重要并有意義[7-8]。由于這兩個目標(biāo)間復(fù)雜的非線性關(guān)系，有學(xué)者通過設(shè)計非支配排序算法(Nondominated Sorting Genetic Algorithm, NSGA)來求解近似最優(yōu)解[9]。但亞啟發(fā)式算法NSGA本身有兩個缺陷：1)不能保證求出全部的有效解；2)求出的有效解中沒有平衡成本與風(fēng)險兩個目標(biāo)的決策信息，使決策者面臨從有效解集中選擇適合組織的有效解的困難[9-10]。

本文通過對構(gòu)件的成本與組合風(fēng)險兩項指標(biāo)關(guān)系進(jìn)行研究，建立一個雙目標(biāo)0-1整數(shù)規(guī)劃模型，為開發(fā)者提供滿足系統(tǒng)需求情況下考慮成本與組合風(fēng)險最優(yōu)的構(gòu)件選擇方法。同時，根據(jù)模型特點(diǎn)設(shè)計基于支持有效解集的啟發(fā)式算法求解全部有效解集。采用衡量多目標(biāo)優(yōu)化算法的重要指標(biāo)——生成有效解向量的比率(ONVGR)來比較本文提出算法與NSGA-II算法。

1.1 考慮成本與組合風(fēng)險的構(gòu)件選擇問題描述

文中使用的參數(shù)分別是：

n為完成目標(biāo)系統(tǒng)需要開發(fā)的模塊個數(shù)；

mj為模塊j可以選擇的構(gòu)件個數(shù)；

cij表示第j個模塊選擇第i種構(gòu)件實(shí)施時的采購成本($)；

ηij表示第j個模塊選擇第i種構(gòu)件實(shí)施時的失敗率(%)；

sj為第j個模塊在此產(chǎn)品架構(gòu)實(shí)現(xiàn)時被調(diào)用的平均次數(shù)(次)；

Satij(k)表示當(dāng)?shù)趈個模塊選擇第i種構(gòu)件開發(fā)時，第k個目標(biāo)的可滿足性水平。

文中使用的變量為：

不同于簡單的產(chǎn)品開發(fā)，CBD可以系統(tǒng)地組織一組產(chǎn)品同時開發(fā)。從產(chǎn)品線管理角度來說，產(chǎn)品線可視為在一組共享資源基礎(chǔ)上建立的產(chǎn)品組合，產(chǎn)品組合中各產(chǎn)品分別滿足特定領(lǐng)域市場的需求。不失一般性地，為了便于理解產(chǎn)品線中的共享資源通過抽象的模塊進(jìn)行表示，并且每一模塊可以通過使用一個構(gòu)件進(jìn)行實(shí)施，而且每一模塊需要實(shí)現(xiàn)至少一個功能目標(biāo)。根據(jù)面向目標(biāo)的需求工程(The Goal-Oriented Requirement Engineering Approach，GORE)[11-12]，需求經(jīng)過抽象、細(xì)分均轉(zhuǎn)化為可以量化考核的目標(biāo)，這些目標(biāo)可以根據(jù)組織的需要被劃分為若干評分檔次，決策者可以通過測試、分析和匹配各構(gòu)件資產(chǎn)執(zhí)行時的效果，使用可滿足性函數(shù)對資產(chǎn)進(jìn)行度量評分。圖1表示在面向目標(biāo)的需求工程下構(gòu)件選擇的框架，以模塊為基本單元來衡量質(zhì)量目標(biāo)和構(gòu)件。

圖1 面向目標(biāo)的需求工程下構(gòu)件選擇框架

在此框架下，圍繞著成本和組合風(fēng)險這兩個重要的非功能需求，構(gòu)件選擇決策問題可以定義為在滿足系統(tǒng)需求的情況下，為各模塊選擇具體實(shí)施的構(gòu)件，最終實(shí)現(xiàn)總體開發(fā)成本和組合風(fēng)險最優(yōu)的目標(biāo)。

1.2 組合風(fēng)險的描述與誤差分析

根據(jù)Berman[2]的研究，模塊的錯誤發(fā)生概率服從指數(shù)分布。那么，假設(shè)以pj表示模塊j在系統(tǒng)執(zhí)行時至少發(fā)生一次錯誤的概率，則模塊j沒有錯誤發(fā)生的概率可以表示為：

(1)

(2)

最優(yōu)化系統(tǒng)的組合風(fēng)險也就可以表示成為最小化至少一次發(fā)生錯誤的概率。這樣，目標(biāo)函數(shù)表示為：

(3)

假設(shè)系統(tǒng)中任意模塊出現(xiàn)錯誤，便導(dǎo)致整個系統(tǒng)錯誤。根據(jù)麥克勞林前兩階展開式，可以將原組合風(fēng)險目標(biāo)方程(3)近似表示為：

(4)

其中，將(3)式展開為(4)式的麥克勞林展開式的二階拉格朗日余項為：

(5)

下面考慮該拉格朗日余項，即(5)式趨于零的條件。

故此，(5)式在完成目標(biāo)系統(tǒng)需要開發(fā)的模塊個數(shù)n趨于無窮的時候接近于零。而事實(shí)上為完成目標(biāo)系統(tǒng)需要開發(fā)的模塊個數(shù)n總會是有限個，并且n越大，系統(tǒng)出錯的概率就會越高，進(jìn)而導(dǎo)致組合風(fēng)險存在近似誤差。

(6)

假設(shè)系統(tǒng)對組合風(fēng)險估計誤差的可接受波動大小為δ，則由(5)式導(dǎo)致的誤差在δ范圍內(nèi)時，所提出的求解模型是有效的。根據(jù)上述，顯然t滿足(6)式時，(5)式取得最大值。若已知系統(tǒng)的誤差可接受波動大小δ，則：

θ∈(0,e-1/2)

(7)

當(dāng)系統(tǒng)組合風(fēng)險估計誤差的可接受波動滿足(7)式時，我們認(rèn)為模型是有效的。

1.3 系統(tǒng)需求約束的描述

本文采用目前被業(yè)界廣泛使用的面向目標(biāo)的需求工程(GORE)[11-12]來衡量系統(tǒng)的系統(tǒng)需求。GORE主要是通過抽象和細(xì)分將需求轉(zhuǎn)化成為可以量化考核的目標(biāo)，再把這些目標(biāo)根據(jù)組織的需要劃分為若干評分檔次，決策者可以通過測試、分析和匹配各構(gòu)件執(zhí)行時的效果，使用可滿足性水平反映各構(gòu)件(功能模塊)的度量評分。假設(shè)滿意度水平參數(shù)(Satisfaction Level，Satij(k))在[0,1]區(qū)間上，并且已經(jīng)通過匹配各目標(biāo)檔次得到。通過對各目標(biāo)的加權(quán)求和，可以得到第j個模塊選擇第i種構(gòu)件開發(fā)時的總體可滿足性水平Satij：

(8)

其中，τk表示各目標(biāo)k的權(quán)重。

則整個系統(tǒng)的需求約束可以描述為：

(9)

表示整個系統(tǒng)的運(yùn)行至少需要達(dá)到某一可接受水平R。式中，ωj表示模塊j的權(quán)重。

1.4 數(shù)學(xué)模型

通過以上對成本、組合風(fēng)險和系統(tǒng)需求的描述，可以得到滿足系統(tǒng)需求下考慮成本和組合風(fēng)險最優(yōu)的優(yōu)化模型(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)表示整個系統(tǒng)的總成本。式(13)表示對于各模塊而言，無論選擇何種構(gòu)件，只使用一種構(gòu)件實(shí)施。

2 啟發(fā)式算法

可以看出，C&R模型為雙目標(biāo)整數(shù)規(guī)劃模型(The Bi-objective 0-1 Integer Programming)，決策者使用目前如ILOG Cplex 10、Lindo和Lingo12.0等優(yōu)化軟件不能求解，而使用如遺傳算法、模擬退火算法和分散搜索算法等智能優(yōu)化算法僅能求出部分有效解。為此，本文根據(jù)該模型的特點(diǎn)設(shè)計了三階段啟發(fā)式算法對其進(jìn)行求解，提供全部非劣解集 (Non-dominated Solution)，以方便模型使用。

2.1 啟發(fā)式算法的假設(shè)條件與相關(guān)概念

假設(shè)系統(tǒng)中任意模塊出現(xiàn)錯誤，便導(dǎo)致整個系統(tǒng)錯誤。根據(jù)麥克勞林前兩階展開式(The First Two Terms of Maclaurin Series Expansion)，可以將原組合風(fēng)險目標(biāo)方程(4)近似表示為：

(15)

不同于單目標(biāo)優(yōu)化模型具有唯一的最優(yōu)解，一般來講，多目標(biāo)優(yōu)化問題并不存在唯一最優(yōu)解，而是往往通過一個解的集合來表示求解結(jié)果。該集合描述的是與集合之外的解相比較，集合中的解至少有一個目標(biāo)值優(yōu)于集合之外的一個解，且其他目標(biāo)值均不比這個集合外的解劣，這種解集中的解我們稱之為非支配解(Non-dominated Solution)或者Pareto解，并將這種解集稱為有效解集(Efficient Solution)[13]。

為了更有效地描述本算法，下面給出C&R模型中非支配解的具體定義。

假設(shè)引入一個在 [0,1]之間取值的偏好值λ(Preferences)，通過對兩個原目標(biāo)函數(shù)加權(quán)求和，構(gòu)成一個新的目標(biāo)函數(shù)：

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

(16)

這個偏好值反應(yīng)決策者對成本與組合風(fēng)險的偏好信息，通過將原來的兩個目標(biāo)加權(quán)成為一個目標(biāo)，再求解該優(yōu)化模型，可以得到原問題的一個有效解，并且這一有效解反應(yīng)了決策者事先定義好的對成本與組合風(fēng)險的偏好信息。

從理論上講，如果可以遍歷偏好值λ在[0,1]之間的取值，并以各加權(quán)后的目標(biāo)函數(shù)作為新的目標(biāo)，在滿足約束(12)～(14)的條件下對模型進(jìn)行求解，在凸可行域上就可以得到全部非支配解。然而這種方法存在兩個局限性：第一，遍歷所有偏好值λ的取值在實(shí)際中是不能實(shí)現(xiàn)的；第二，對于非凸可行域的問題，使用該方法不能求解出全部非支配解。為此，本文提出一種可以獲得全部非支配解的算法。通過在滿足約束(12)～(14)下，最小化加權(quán)后的目標(biāo)函數(shù)(16)可以獲得部分有效解，這部分有效解我們將其稱之為支持的有效解(Supported Efficient Solutions，Supported-ES)；同時，將有效解集中的其他有效解稱之為非支持的有效解(Non-supported Efficient Solutions，Non- supported-ES)。此算法應(yīng)用非支持的有效解必存在于兩個連續(xù)的支持有效解之間的理論[14]，基于此理論，在本文提出的三階段算法中：第一階段對全部可能的聯(lián)合效用值(Aggregated Efficiency)進(jìn)行排序，由于排序的變化取決于偏好λ的取值，得到排序穩(wěn)定的λ的區(qū)間范圍，以此有效地解決了遍歷全部偏好λ的取值的困境；第二階段通過引入貪婪啟發(fā)式規(guī)則，遍歷得出全部支持的有效解；第三階段中，通過遍歷任意兩個連續(xù)的支持有效解構(gòu)成的區(qū)間，得到全部非支持的有效解。至此，全部的有效解就得到了。

為了更清楚地說明算法的求解過程，引入如下定義：

通過上述定義可以進(jìn)一步得到考慮帶偏好值的聯(lián)合效率值(Aggregated Efficiency)eij(λ)為：

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

(17)

它表示第j個模塊選擇第i種構(gòu)件實(shí)施時，每單位滿足度增加所付出的成本與組合風(fēng)險聯(lián)合作用。

因此，對于一個給定的λ′，可以得到其聯(lián)合效用值排序：

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

where=<1,2,…,mj>

(18)

遍歷所有可能存在的聯(lián)合效用值的排序，就得到所有的確定支持有效解，相應(yīng)的每一對應(yīng)有效解的排序，我們稱之為有效排序(Efficient Order，EO)。

2.2 第一階段：確定聯(lián)合效用值的有效排序

本小節(jié)中將確定所有可能的有效排序(EO)，以及各EO的對應(yīng)偏好值λ的區(qū)間。隨著偏好值λ在可行域[0, 1]的變化，EO不是固定不變的，首先介紹確定各模塊有效排序的λ子區(qū)間([0,u1j],…,[utj,ut+1j],…,[uTj,1]))的算法。

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

開始

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

第2步：以λt的取值，將所有構(gòu)件按照式(18)進(jìn)行排序；

第3步：通過求解下面優(yōu)化問題確定有效的偏好值的上界(upper bounds)

Maxλ

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

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

(19)

假設(shè)用λmax來表示(19)模型的最優(yōu)解，如果λmax≥1，則令t←t+1，utj←1

即表示模塊j的全部有效的偏好值區(qū)間已經(jīng)確定完畢，進(jìn)行第4步；

第4步： 令t←t+1,utj←λmax,λt←λmax+ε(其中ε為干擾項(perturbation factor),ε>0)。進(jìn)行第2步；

結(jié)束

此外，式(19)可以使用αij和βij參數(shù)，通過如下優(yōu)化模型(20)進(jìn)行求解：

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

(20)

推論1 各模塊的有效排序個數(shù)等于模型(20)在從0遍歷到1的過程中所取得的偏好值λmax的個數(shù)。

根據(jù)第一階段啟發(fā)式(Procedure-1)可以得出各模塊的有效排序及其對應(yīng)的子區(qū)間，并通過合并全部子區(qū)間可以得出有效排序不改變的偏好值區(qū)間([0,v1],…, [vg,vg+1],…, [vG,1])。

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

對于每一個有效排序不變的偏好值λ的區(qū)間，通過貪婪啟發(fā)式過程求解出支持有效解，遍歷全部區(qū)間便可以得到全部的支持有效解。

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

開始

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

第3步：循環(huán)直到滿足系統(tǒng)需求約束(12)為止：

如果xli+1j=non，則將xlij鎖定為必選解；

否則對ExploreSet∪{xli+1j}，EfficientSet←{xli+1j}使用構(gòu)件xli+1j更新}

第4步：如果滿足Dantzig檢驗(yàn)條件 (17)；則保存支持到支持有效解集中，

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

第5步：λh=vg+1+ε(其中ε為干擾項(perturbation factor),ε>0)；

如果λh≥1, 則終止算法(說明所有空間已經(jīng)搜索完畢)；,

否則返回第2步；

結(jié)束

在此過程中需要用到的Dantzig規(guī)則如下：

(21)

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

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

使用z*和λ*表示優(yōu)化模型(21)的最優(yōu)解。根據(jù)Dantzig 規(guī)則，可以進(jìn)一步得到推論2。

通過對每一模塊使用(Procedure-2)，可以獲得全部支持有效解，并且每一支持有效解都會帶有相應(yīng)的成本與組合風(fēng)險的偏好信息(Trade-off Information ofλ)，以輔助決策者進(jìn)行有效解選擇。

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

而對于剩余的有效解，也就是之前提到的非支持有效解必存在于兩個連續(xù)的支持有效解之間的理論，將通過本階段啟發(fā)式算法進(jìn)一步搜索，以確保全部有效解被遍歷。

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

開始

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

第2步：構(gòu)造搜索空間，空間中的下界(Lower bound)由有效解的連線構(gòu)成，而上界(Upper bound)為將C&R模型松弛為0-1連續(xù)背包問題后有效解的連線。

第3步：通過建立典型搜索技術(shù)分支定界算法(Branch-and-bound)[14]或者動態(tài)規(guī)劃算法(Dynamic programming)[15]搜索各目標(biāo)值下降空間(Reduced objective Space)，當(dāng)遍歷過所有解空間之后，全部的非支持有效解也就確定完畢。

結(jié)束

此外，加權(quán)目標(biāo)函數(shù)(Aggregated Functions)可以進(jìn)一步用來確定分支定界搜索(Branch-and-Bound)下降空間。

特別地，為了方便大規(guī)模問題的求解，由于各模塊的處理過程間具有平行關(guān)系(Procedure-1)，因此可以在不同的處理器上進(jìn)行運(yùn)算，最后通過合成得到有效排序穩(wěn)定的區(qū)間。

3 案例分析

本節(jié)以郵箱系統(tǒng)為例來驗(yàn)證前文所提優(yōu)化模型及其啟發(fā)式算法在實(shí)際應(yīng)用中的有效性。

一個郵件數(shù)據(jù)請求從發(fā)件人所處的用戶代理服務(wù)器(Mail User Agent，MUA)，可以由四個模塊構(gòu)成：Web Mail Servers、Wap Mail Servers、Secure Mail、Network Communication(為方便表述，后文將其分別縮寫為模塊1、模塊2、模塊3、模塊4)?？紤]到產(chǎn)品的多樣性，產(chǎn)品1、產(chǎn)品2、產(chǎn)品3三類可如圖2進(jìn)行開發(fā)。

圖中的連線表示不同產(chǎn)品開發(fā)時需要用到的模塊。例如開發(fā)產(chǎn)品1，將用到Web Mail Servers和 Wap Mail Servers模塊作為產(chǎn)品的構(gòu)成模塊。

各構(gòu)件所需操作成本均使用成本表示，其可以通過平均的工時成本(Man-hours)來計算。求解出各模塊在不同的可選擇構(gòu)件下所對應(yīng)的成本參數(shù)cij、及組合風(fēng)險值ηij，結(jié)果見表1。并根據(jù)各模塊的使用頻率得到各模塊的權(quán)重值為(0.472, 0.311, 0.087, 0.066)。

圖2 郵件系統(tǒng)產(chǎn)品線架構(gòu)圖

構(gòu)件序號模塊1模塊2模塊3模塊4成本組合風(fēng)險滿意度成本組合風(fēng)險滿意度成本組合風(fēng)險滿意度成本組合風(fēng)險滿意度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描述了當(dāng)R=0.8時得到的支持有效解，每個解由編碼給出。編碼“7716”表示四個模塊分別使用的是構(gòu)件7、構(gòu)件7、構(gòu)件1、構(gòu)件6。圖3反映的是支持有效解在成本與組合風(fēng)險這兩個目標(biāo)空間上的情況。

表2 啟發(fā)式算法獲得的支持有效解

圖3 R=0.8時得到的支持有效解

4 算法性能的評估

算法性能的評估是多目標(biāo)優(yōu)化問題重點(diǎn)研究的內(nèi)容之一。本文針對從小到大4個規(guī)模的問題, 采用衡量多目標(biāo)優(yōu)化算法的重要指標(biāo)——生成有效解向量的比率(Overall Nondominated Vector Generation Ratio， ONVGR)來比較本文提出算法與NSGA-II算法。本文用PFt表示本文提出算法獲得的有效解的個數(shù)，其值越大說明決策者有越多的選擇。類似地，用PFn來表示NSGA-II算法獲得的有效解的個數(shù)；則生成效解數(shù)比率可表示為ONVGR=PFn/PFt。

首先隨機(jī)生成四組算例，算例規(guī)模分別為10×10、 25×25、25×50和50×100(模塊數(shù)×備選構(gòu)件數(shù))， 縮寫為P-1、P-2、P-3和P-4。它們各自的成本, 失敗率和可滿足性水平均在區(qū)間[100, 5000]、[0.0001, 0.001]和[0.5, 1]內(nèi)隨機(jī)生成, 并將可接受可滿足性水平設(shè)置為0.6。NSGA-II算法的種群數(shù)設(shè)置為100， 迭代次數(shù)設(shè)置為200。本文所列出結(jié)果為NSGA-II算法執(zhí)行10次的平均值。為了客觀地比較上述兩種算法，本文采用兩種NSGA-II參數(shù)設(shè)置策略: 1) 交叉率設(shè)置為0.5、0.7、0.9，同時變異率設(shè)置為0.03；2)變異率設(shè)置為 0.01、0.03、0.05，同時交叉率設(shè)置為0.9。

上述兩個算法比較結(jié)果如表3和表4所示，依據(jù)ONVGR指標(biāo)，NSGA-II算法有效性僅相當(dāng)于本文提出算法71%～96%。而且NSGA-II的不同變異率和交叉率下的ONVGR比率均劣于本文提出算法。

表3 NSGA-II.不同變異率下ONVGR比率

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

5 結(jié)語

本文通過建立了一個雙目標(biāo)0-1整數(shù)規(guī)劃模型，提供滿足系統(tǒng)需求情況下的成本最小且組合風(fēng)險最低的解決方案。通過分析麥克勞林展開式的二階拉格朗日余項，給出了該解決方案的適用條件，指出在系統(tǒng)組合風(fēng)險估計誤差的波動在一定可接受范圍內(nèi)時，該估計模型是有效的。并設(shè)計三階段啟發(fā)式算法對其進(jìn)行求解，前兩階段確定支持有效解集、第三階段得到非支持有效解集，以提供全部非劣解集，用于從非劣解集中選擇最適合方案實(shí)施。最后，通過算例分析驗(yàn)證了該模型和算法的適用性。

[1] 邵良杉, 張照. 組件、COM與Windows DNA技術(shù)在MIS中應(yīng)用研究[J]. 中國管理科學(xué),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

國家自然科學(xué)基金資助項目(71301107，71671028)

吳志樵(1981-)，男(錫伯族)，遼寧沈陽人，東北財經(jīng)大學(xué)科學(xué)與工程學(xué)院副教授，博士生導(dǎo)師，博士，研究方向：服務(wù)系統(tǒng)工程,E-mail: wuzhiqiao@dufe.edu.cn.

TP311.5

A