決策者偏好交互項(xiàng)目組合選擇模型及算法優(yōu)化研究

羅淑娟, 白思俊, 郭云濤

(西北工業(yè)大學(xué) 管理學(xué)院, 陜西 西安　710072)

?

決策者偏好交互項(xiàng)目組合選擇模型及算法優(yōu)化研究

羅淑娟, 白思俊, 郭云濤

(西北工業(yè)大學(xué) 管理學(xué)院, 陜西 西安710072)

摘要：項(xiàng)目組合選擇是戰(zhàn)略項(xiàng)目管理決策的重要環(huán)節(jié)，目前基于決策者偏好的交互項(xiàng)目組合選擇的研究仍然在模型和算法上存在不足。首先提出級(jí)別優(yōu)先模型細(xì)致劃分了項(xiàng)目間的偏好關(guān)系，并引入了項(xiàng)目間的協(xié)同交互，使模型更加完備。進(jìn)而結(jié)合該模型改進(jìn)了多目標(biāo)粒子群算法，加快其收斂速度，并拓展其非劣解的多樣性。在考慮決策者偏好和項(xiàng)目間交互約束的條件下，分別對(duì)偏好模型和模型求解算法進(jìn)行了仿真驗(yàn)證。仿真結(jié)果表明，采用級(jí)別優(yōu)先模型所得的非劣解更加接近項(xiàng)目組合選擇的最優(yōu)解，改進(jìn)粒子群算法的搜索速度更快。

關(guān)鍵詞：粒子群優(yōu)化；項(xiàng)目組合選擇；項(xiàng)目交互；決策者偏好；級(jí)別優(yōu)先模型；改進(jìn)粒子群優(yōu)化

解決項(xiàng)目之間的交互作用及其在交互作用下的組合優(yōu)化問(wèn)題被認(rèn)為是戰(zhàn)略項(xiàng)目管理中一項(xiàng)非常重要的研究課題[1]。同時(shí)考慮決策者偏好的項(xiàng)目組合問(wèn)題研究更加切合實(shí)際情況，從戰(zhàn)略決策者的角度配置公司的人力、技術(shù)和財(cái)務(wù)等資源的分配，有利于提高企業(yè)核心競(jìng)爭(zhēng)力，促進(jìn)公司更快更好發(fā)展。

為解決上述優(yōu)化問(wèn)題，Doerner等人[2]在對(duì)比ACO和0-1動(dòng)態(tài)數(shù)學(xué)編程的基礎(chǔ)上，提出了利用增強(qiáng)解來(lái)初始化搜索進(jìn)程。Carazo等人[3]考慮到項(xiàng)目之間的交互和臨時(shí)交互，提出了相對(duì)比較完整的解決方案，使資源可以分配到項(xiàng)目組合過(guò)程中的不同階段,并利用SPEA2方法解決6個(gè)目標(biāo)函數(shù)優(yōu)化問(wèn)題，表現(xiàn)優(yōu)異。啟發(fā)式算法以不受目標(biāo)函數(shù)和問(wèn)題約束，搜索速度快等特性成為項(xiàng)目組合優(yōu)化問(wèn)題的主流解決方法。然而在目標(biāo)函數(shù)和項(xiàng)目數(shù)量增多的情況下，如何選擇合適的個(gè)體將種群引導(dǎo)到非劣解顯得十分困難，尤其在解決多約束決策分析(MCDA)領(lǐng)域問(wèn)題時(shí)，啟發(fā)式算法的表現(xiàn)差強(qiáng)人意。為使決策過(guò)程更加容易，研究者在搜索過(guò)程中引入決策者偏好，將搜索信息引導(dǎo)到?jīng)Q策者感興趣的區(qū)域(ROI)。Deb等[4]對(duì)每項(xiàng)目標(biāo)函數(shù)設(shè)置參數(shù)和權(quán)重，成對(duì)的比較已有解集，從而獲得解集的排序。Molina等[5]利用每個(gè)目標(biāo)函數(shù)的期望值來(lái)表達(dá)決策者偏好。Fernandez等[6]通過(guò)決策者構(gòu)建模型參數(shù)來(lái)創(chuàng)建模糊級(jí)別優(yōu)先關(guān)系，Wagner等[7]通過(guò)設(shè)置期望閾值來(lái)構(gòu)建期望函數(shù)，令其表征決策者偏好。然而在上述論文中運(yùn)用的模型和方法中，仍然存在考慮決策者偏好時(shí)偏好關(guān)系劃分不夠細(xì)致，收斂速度慢，非劣解缺乏多樣性等缺點(diǎn)。

本文首先給出交互項(xiàng)目組合選擇模型并根據(jù)偏好關(guān)系進(jìn)行細(xì)化得出級(jí)別優(yōu)先模型，然后針對(duì)該模型的求解提出改進(jìn)粒子群優(yōu)化算法，最后給出模型和算法相應(yīng)的仿真對(duì)比實(shí)驗(yàn)。

1項(xiàng)目組合選擇模型建立

1.1問(wèn)題描述

結(jié)合Carazo等[8]提出的項(xiàng)目組合選擇模型。在資源約束的情況下，求解結(jié)果需要滿足最大收益條件，如(1)式所示。

(1)

式中,p為目標(biāo)個(gè)數(shù),〈z1(x),z2(x),…,zp(x)〉為項(xiàng)目組合收益總和,RF是可行解空間,由可用預(yù)算、項(xiàng)目類型、社會(huì)定位和區(qū)域劃分構(gòu)成。

假設(shè)X為可行的項(xiàng)目組合集,其中一種項(xiàng)目組合選擇辦法可以表示為x={x1,x2,…,xN},N代表項(xiàng)目總數(shù),xj表示第j個(gè)項(xiàng)目,如果該項(xiàng)目包含在項(xiàng)目組合中,則xj=1,如果不在,則xj=0。用f(j)={f1(j),f2(j),…,fp(j)}代表第j個(gè)項(xiàng)目的收益。項(xiàng)目組合x(chóng)的總收益由(2)式表示。

(2)

定義zk(x)如下

(3)

(4)

式中,mi和Mi分別表示協(xié)同交互i發(fā)生時(shí),受到交互影響的最小和最大的項(xiàng)目數(shù)量。cj,k表示第j個(gè)項(xiàng)目中第k類資源的內(nèi)容,那么項(xiàng)目組合選擇x對(duì)于第k類資源的總和如(5)式所示

(5)

(6)

假設(shè)在完成項(xiàng)目組合選擇的過(guò)程中需要考慮q類不同的資源或約束,用{B1,B2,…,Bq}來(lái)表示每類資源的內(nèi)容(例如:現(xiàn)金流,資源,人力等)。項(xiàng)目組合優(yōu)化問(wèn)題求解所受約束如下

(7)

由于建模過(guò)程中沒(méi)有考慮到每個(gè)項(xiàng)目的進(jìn)程,本文進(jìn)行的是項(xiàng)目組合問(wèn)題的靜態(tài)分析。

1.2決策者偏好級(jí)別優(yōu)先模型

結(jié)合Fernandez等[6]的工作,對(duì)偏好的類型進(jìn)行細(xì)致劃分,利用σ(x,y)表示“相比選擇項(xiàng)目組合y更加偏好項(xiàng)目組合x(chóng)”偏好參數(shù)λ,β和ε滿足0≤ε≤β≤λ,λ>0.5。項(xiàng)目組合(x,y)確定偏好關(guān)系如表1所示。

表1　項(xiàng)目組合偏好關(guān)系條件表

從一個(gè)可行項(xiàng)目組合的解集O中,定義偏好解集如下:

1)S(O,x)={y∈O|yPx};對(duì)于y明顯偏好級(jí)別優(yōu)先x的解構(gòu)成。

2)NS(O)={x∈O|S(O,x)=?};由非嚴(yán)格級(jí)別優(yōu)先解構(gòu)成。

3)W(O,x)={y∈NS(O)|yQx∧yKx}對(duì)于y偏好級(jí)別稍微優(yōu)先x的解構(gòu)成。

同時(shí)定義(8)式

(8)

如果Fn(x)>Fn(y)表明相比于選擇項(xiàng)目組合y更加傾向選擇項(xiàng)目組合x(chóng),則定義解集如下:

1)F(O,x)={y∈NS(O)|Fn(y)>Fn(x)}求解出的是非嚴(yán)格級(jí)別優(yōu)先解。

2)NF(O)={x∈NS(O)|F(O,x)=?}求解出的是非級(jí)別優(yōu)先非劣解。

Fernandez等人[9]驗(yàn)證,結(jié)合模糊級(jí)別優(yōu)先系數(shù)σ的最優(yōu)項(xiàng)目組合是一個(gè)非嚴(yán)格級(jí)別優(yōu)先解,同時(shí)也是非劣解

(9)

式中求解的三目標(biāo)優(yōu)化問(wèn)題是(1)式問(wèn)題的映射,(1)式的最優(yōu)候選解就是(9)式的非劣解。(1)式所求解的問(wèn)題及其所映射的三目標(biāo)優(yōu)化問(wèn)題在目標(biāo)空間維度上是獨(dú)立的。決策者在優(yōu)化過(guò)程中需要確定的參數(shù)分別為:σ(約束權(quán)重與閾值)和偏好系統(tǒng)的參數(shù)(λ、β和ε)。該過(guò)程需要通過(guò)決策分析的辦法來(lái)輔助實(shí)現(xiàn),偏好解集分析法(PDA)和多準(zhǔn)則決策分析法(MCDA)是普遍認(rèn)可的2種方法,PDA[10]可以通過(guò)決策者在一些明確的項(xiàng)目組合的決策過(guò)程推斷出模型的約束權(quán)重和偏好參數(shù)。

2基于級(jí)別優(yōu)先模型的改進(jìn)粒子群優(yōu)化算法

基于Rabbani等[11]提出的算法框架,通過(guò)對(duì)于粒子群優(yōu)化算法搜索過(guò)程的改進(jìn)來(lái)求解偏好模型(9)式的非劣解。采用粒子的跳躍改進(jìn)來(lái)防止早熟收斂,當(dāng)存在項(xiàng)目組合保持非嚴(yán)格級(jí)別優(yōu)先狀態(tài)超過(guò)γ代,則將其從解集中移除。通過(guò)聚類操作拓展非劣解的多樣性,當(dāng)算法找到最優(yōu)非劣解集或者達(dá)到最大搜索代數(shù)時(shí),搜索過(guò)程結(jié)束。

解集尺寸為s,xi表示一組項(xiàng)目組合解,vi表示粒子的飛行速度,用pbesti來(lái)表示以往最優(yōu)的項(xiàng)目組合,gbest來(lái)表示全局最優(yōu)組合解,粒子速度的更新公式如下

(10)

對(duì)于所有j∈1,…,N,vi,j是第i個(gè)粒子在第j維度的速度,c1和c2表示加速系數(shù),r1和r2是在范圍(0,1)內(nèi)的2組隨機(jī)數(shù),g為迭代的次數(shù)。項(xiàng)目組合更新公式(11)所示

(11)

項(xiàng)目組合的局部最優(yōu)位置更新方法如下

(12)

全局最優(yōu)解定義如下

(13)

速度向量vi的值要嚴(yán)格在范圍[-vmax,vmax]中,以保證粒子不超出搜索范圍。

2.1粒子跳躍改進(jìn)

采取跳躍改進(jìn)來(lái)拓寬粒子搜索面,既維持了粒子的解的多樣性,同時(shí)不影響PSO的收斂速度。在跳躍改進(jìn)機(jī)制中包含向內(nèi)跳躍和向外跳躍。向內(nèi)跳躍旨在增強(qiáng)在已知搜索區(qū)域的搜索深度。向外跳躍可以增強(qiáng)搜索未知區(qū)域的能力,防止搜索陷入局部最優(yōu)。跳躍改進(jìn)過(guò)程如圖1所示,其中s1和s2代表從非劣解集中隨機(jī)選取的2個(gè)成員,將其作為搜索向量。2個(gè)對(duì)于未知空間的搜索向量Os1和Os2是通過(guò)公式(14)、(15)獲得的,其中α1和α2是0到1的隨機(jī)值。

(14)

(15)

圖1　跳躍改進(jìn)機(jī)制示意圖

2.2聚類操作

本文提出聚類的方法從非劣解集中篩選相似非劣解來(lái)解決這個(gè)問(wèn)題。每個(gè)粒子設(shè)定聚類半徑為r。然后選定一個(gè)粒子作為聚類中心,如果在搜索中有其他粒子落以該粒子為中心,半徑為r的范圍內(nèi),則將其從候選解集中剔除。

多維目標(biāo)解空間的聚類半徑r定義如下

(16)

圖2　聚類操作圖例

基于決策者偏好模型求解的改進(jìn)粒子群算法的偽代碼如算法1所示。

算法1:改進(jìn)粒子群優(yōu)化算法(NOPSO)

輸入:X(可用項(xiàng)目集),B(約束信息)

輸出:NS(O)

Repeat:

1) O=?

2) 采用粒子群算法求得非劣解集O

O=O∪NSlocal

NSlocal=argminx∈O{<|S(O,x)|,|W(O,x)|,|F(O,x)|>}

If跳躍粒子數(shù)不夠(粒子跳躍改進(jìn))

從解集NSlocal中隨機(jī)選取s1

從解集NSlocal中隨機(jī)選取s2

產(chǎn)生新的Os1和Os2

Endif為非劣解集中的每個(gè)粒子設(shè)定編號(hào)(聚類操作)

計(jì)算聚類半徑r

For對(duì)解集中的每個(gè)粒子根據(jù)他們的編號(hào)

把編號(hào)粒子放在搜索空間并形成一個(gè)聚類中心

If粒子坐落在聚類中心粒子的半徑中

移除這個(gè)粒子

Endif

Endfor

rep=rep+1

Else

rep=0

Until(rep=repmax)∪(iter=itermax)

ReturnNSglobal

3仿真實(shí)驗(yàn)對(duì)比分析

在項(xiàng)目組合選擇實(shí)驗(yàn)過(guò)程中,需要考慮決策者的偏好和項(xiàng)目之間的交互,從而設(shè)定如下約束:

項(xiàng)目總數(shù)為100個(gè);總預(yù)算為2億元; 項(xiàng)目分為3種類別和2個(gè)地域;單個(gè)項(xiàng)目類別預(yù)算占總預(yù)算20%～60%;單個(gè)區(qū)域預(yù)算占總預(yù)算30%～70%;由決策者定義20種相關(guān)的項(xiàng)目交互作用;交互作用包括4種項(xiàng)目間分流,6種項(xiàng)目間沖突和10種項(xiàng)目間協(xié)同促進(jìn),每種協(xié)同中包含至多5個(gè)項(xiàng)目。

下面給出文中提出模型和方法的驗(yàn)證性實(shí)驗(yàn),以并闡述該方法的有效性和優(yōu)勢(shì),基于決策者偏好的交互項(xiàng)目組合優(yōu)化模型和改進(jìn)的粒子群算法在解決實(shí)際的資源分配和選擇決策過(guò)程中有較大的優(yōu)勢(shì)。

3.1偏好模型對(duì)比實(shí)驗(yàn)

MOPSO廣泛應(yīng)用于交互項(xiàng)目組合選擇問(wèn)題[11]中,為了解決考慮決策者偏好的多目標(biāo)優(yōu)化問(wèn)題,結(jié)合偏好模型,提出了改進(jìn)的粒子群優(yōu)化算法(MOPSO-P),通過(guò)搜索(9)式中的非劣解來(lái)近似式(1)的最優(yōu)候選解。其中偏好模型的參數(shù)根據(jù)Fernandez[6]來(lái)設(shè)置,保證可靠的決策環(huán)境。MOPSO和MOPSO-P均用MATLAB編程實(shí)現(xiàn)。參數(shù)設(shè)置方面,MOPSO-P與MOPSO使用相同的參數(shù)設(shè)置,參考Tsai[12]中的定義。

在表2中列出了5次實(shí)驗(yàn)的結(jié)果。從表中可以得出結(jié)合偏好的粒子群優(yōu)化搜索過(guò)程更加集中在決策者感興趣的區(qū)域,MOPSO-P比MOPSO在非嚴(yán)格級(jí)別優(yōu)先解數(shù)量上多17.2%。在大多數(shù)情況下,MOPSO在搜索過(guò)程中受到劣解的影響比較大。在偏好模型與實(shí)際決策者偏好相匹配的情況下,項(xiàng)目組合最優(yōu)解均包含在MOPSO-P求解的解集中。仿真實(shí)驗(yàn)的結(jié)果證明了基于決策者偏好的級(jí)別優(yōu)先模型的有效性。

表2　結(jié)合決策者偏好的粒子群優(yōu)化算法對(duì)比分析

注:O1和O2分別為MOPSO和MOPSO-P搜索得到的非劣解集。最優(yōu)候選解為在O1/O2中對(duì)于(9)式求解的最優(yōu)解。

3.2NOPSO與SS-PPS算法對(duì)比實(shí)驗(yàn)

確定所求解為真實(shí)最優(yōu)解的方法是取得所有正確的非劣解,至少所有的非嚴(yán)格級(jí)別優(yōu)先解。然而,實(shí)驗(yàn)設(shè)計(jì)的項(xiàng)目總數(shù)過(guò)多,無(wú)法得出確定的非劣解。此時(shí),可以利用本文中的方法在可接受的誤差范圍內(nèi)近似這個(gè)非劣解。通過(guò)與Carazo等[8]提出的SS-PPS方法做對(duì)比實(shí)驗(yàn)來(lái)驗(yàn)證本文提出的NO-PSO方法可以近似非劣解,即項(xiàng)目組合選擇的最優(yōu)解。算法采用MATLAB編程實(shí)現(xiàn)。參數(shù)設(shè)置為c1=2,c2=2,ps=8,repmax=50,itermax=100 000。通過(guò)實(shí)驗(yàn)數(shù)據(jù)分析,上述參數(shù)設(shè)置具有魯棒性。

在表3中列出了5次實(shí)驗(yàn)的結(jié)果,從結(jié)果可以得出,在偏好區(qū)域,NO-PSO比SS-PPS搜索到的解更好的接近非嚴(yán)格級(jí)別高于前沿,其中沒(méi)有一個(gè)SS-PPS所求解比NO-PSO所求解占優(yōu)。在解的數(shù)量上,本文所提出的方法比對(duì)比方法在非嚴(yán)格級(jí)別高于前沿解平均多出53.1%。在搜索時(shí)間上,僅僅為對(duì)比算法速度的11.3%。結(jié)合決策者偏好的改進(jìn)的粒子群優(yōu)化算法極大地降低了工作量,提高了算法搜索效率,拓展了非劣解的多樣性。并且NO-PSO算法求解的解集包含(1)式的最優(yōu)解。

表3　NOPSO與SS-PPS算法對(duì)比分析

注:O1和O2分別為SS-PPS和NO-PSO搜索得到的非劣解集。最優(yōu)候選解為在O1/O2中對(duì)于(9)式求解的最優(yōu)解。

4結(jié)論

本文在優(yōu)化Fernandez提出的偏好系統(tǒng)而得出級(jí)別優(yōu)先模型的基礎(chǔ)上，改進(jìn)已有的多目標(biāo)粒子群優(yōu)化算法。研究結(jié)果解決了考慮決策者偏好同時(shí)項(xiàng)目間存在交互作用時(shí)的項(xiàng)目組合優(yōu)化問(wèn)題，使搜索集中于偏好區(qū)域，從而使求解非劣解更加貼近偏好的項(xiàng)目組合；同時(shí)降低搜索時(shí)間，避免早熟收斂，保證解的多樣性。

不足之處在于，實(shí)驗(yàn)過(guò)程中沒(méi)有考慮決策者偏好的變化，并且項(xiàng)目的維度和復(fù)雜程度不高。之后研究將致力于：

1) 在項(xiàng)目數(shù)量更多、項(xiàng)目間交互作用更復(fù)雜時(shí)，提高模型的可靠性和算法的搜索效率。

2) 根據(jù)決策者偏好的改變對(duì)模型中的偏好參數(shù)進(jìn)行更新，求得最優(yōu)的組合結(jié)果。

參考文獻(xiàn)：

[1]Salo A, Keisler J, Morton A. Portfolio Decision Analysis: Improved Methods for Resource Allocation[M]. Springer Science & Business Media, 2011

[2]Doerner K F, Gutjahr W J, Hartl R F, et al. Pareto ant Colony Optimization with ILP Preprocessing in Multiobjective Project Portfolio Selection[J]. European Journal of Operational Research, 2006, 171(3): 830-841

[3]Carazo A F, Gómez T, Molina J, et al. Solving a Comprehensive Model for Multiobjective Project Portfolio Selection[J]. Computers & Operations Research, 2010, 37(4): 630-639

[4]Deb K, Sinha A, Korhonen P J, et al. An Interactive Evolutionary Multiobjective Optimization Method Based on Progressively Approximated Value Functions[J]. IEEE Trans on Evolutionary Computation, 2010, 14(5): 723-739

[5]Molina J, Santana L V, Coello C A C, et al. G-Dominance: Reference Point Based Dominance for Multiobjective Metaheuristics[J]. European Journal of Operational Research, 2009, 197(2): 685-692

[6]Fernandez E, Lopez E, Lopez F, et al. Increasing Selective Pressure towards the Best Compromise in Evolutionary Multiobjective Optimization: The Extended NOSGA Method[J]. Information Sciences, 2011, 181(1): 44-56

[7]Wagner T, Trautmann H. Integration of Preferences in Hypervolume-Based Multiobjective Evolutionary Algorithms by Means of Desirability Functions[J]. IEEE Trans on Evolutionary Computation, 2010, 14(5): 688-701

[8]Carazo A F, Contreras I, Gomez T, et al. A Project Portfolio Selection Problem in a Group Decision-Making Context[J]. Journal of Industrial & Management Optimization, 2012, 8(1):243-261

[9]Fernandez E, Lopez E, Mazcorro G, et al. Application of the Non-Outranked Sorting Genetic Algorithm to Public Project Portfolio Selection[J]. Information Sciences An International Journal, 2013, 228(7):131-149

[10] Fernandez E, Navarro J, Mazcorro G. Evolutionary Multi-Objective Optimization for Inferring Outranking Model′S Parameters Under Scarce Reference Information and Effects of Reinforced Preference[J]. Foundations of Computing & Decision Sciences, 2012, 37:163-197

[11] Rabbani M, Aramoon M, Baharian Khoshkhou G, Bajestani A. A Multi-Objective Particle Swarm Optimization for Project Selection Problem[J]. Expert Systems with Applications An International Journal, 2010, 37(1): 315-321

[12] Tsai S J, Sun T Y, Liu C C, et al. An Improved Multi-Objective Particle Swarm Optimizer for Multi-Objective Problems[J]. Expert Systems with Applications, 2010, 37(8): 5872-5886

Research of Project Portfolio Selection Model and Optimization Considering Interdependencies based on Preferences Incorporation of Decision Maker

Luo Shujuan, Bai Sijun, Guo Yuntao

(School of Management, Northwestern Polytechnical University, Xi′an, 710072)

Abstract:Project Portfolio Selection is known as the essential element of strategic project management and decision. There are also some disadvantages in model and methods which are based on the project portfolio selection considering interdependencies and preference incorporation of decision maker. The paper proposes an novel outranking model to classify the preference relationship between different projects, and it also bring the synergies and interdependencies into consideration which makes the model more complete. Moreover, it proposes the improved particle swarm optimization algorithm based on the model which speeds up convergence an expand the diversity of non-dominant solutions simultaneously. In the restrained condition of preferences incorporation and interdependencies, the paper comes up with the experiments to verify the model and method respectively. The results indicate that the non-dominant solutions achieved by the outranking model are likely to the optimum of project portfolio selection, and the improved particle swarm optimization search the results faster.

Keywords:particle swarm optimization(PSO); project portfolio selection; interdependencies; preference incorporation; outranking model; improved particle swarm optimization

收稿日期：2016-03-01

基金項(xiàng)目：國(guó)家自然科學(xué)基金(71172123)與陜西省軟科學(xué)研究計(jì)劃-重點(diǎn)項(xiàng)目(2015KRM039)資助

作者簡(jiǎn)介：羅淑娟(1988—)，女，西北工業(yè)大學(xué)博士研究生，主要從事項(xiàng)目組合管理與優(yōu)化方法研究。

中圖分類號(hào)：F273

文獻(xiàn)標(biāo)志碼：A

文章編號(hào):1000-2758(2016)04-0724-07