羅淑娟, 白思俊, 郭云濤

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

?

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

羅淑娟, 白思俊, 郭云濤

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

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

關鍵詞：粒子群優(yōu)化；項目組合選擇；項目交互；決策者偏好；級別優(yōu)先模型；改進粒子群優(yōu)化

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

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

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

1項目組合選擇模型建立

1.1問題描述

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

(1)

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

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

(2)

定義zk(x)如下

(3)

(4)

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

(5)

(6)

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

(7)

由于建模過程中沒有考慮到每個項目的進程,本文進行的是項目組合問題的靜態(tài)分析。

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

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

表1　項目組合偏好關系條件表

從一個可行項目組合的解集O中,定義偏好解集如下:

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

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

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

同時定義(8)式

(8)

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

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

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

Fernandez等人[9]驗證,結合模糊級別優(yōu)先系數(shù)σ的最優(yōu)項目組合是一個非嚴格級別優(yōu)先解,同時也是非劣解

(9)

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

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

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

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

(10)

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

(11)

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

(12)

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

(13)

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

2.1粒子跳躍改進

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

(14)

(15)

圖1　跳躍改進機制示意圖

2.2聚類操作

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

多維目標解空間的聚類半徑r定義如下

(16)

圖2　聚類操作圖例

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

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

輸入:X(可用項目集),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ù)不夠(粒子跳躍改進)

從解集NSlocal中隨機選取s1

從解集NSlocal中隨機選取s2

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

Endif為非劣解集中的每個粒子設定編號(聚類操作)

計算聚類半徑r

For對解集中的每個粒子根據(jù)他們的編號

把編號粒子放在搜索空間并形成一個聚類中心

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

移除這個粒子

Endif

Endfor

rep=rep+1

Else

rep=0

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

ReturnNSglobal

3仿真實驗對比分析

在項目組合選擇實驗過程中,需要考慮決策者的偏好和項目之間的交互,從而設定如下約束:

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

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

3.1偏好模型對比實驗

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

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

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

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

3.2NOPSO與SS-PPS算法對比實驗

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

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

表3　NOPSO與SS-PPS算法對比分析

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

4結論

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

不足之處在于，實驗過程中沒有考慮決策者偏好的變化，并且項目的維度和復雜程度不高。之后研究將致力于：

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

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

參考文獻：

[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

基金項目：國家自然科學基金(71172123)與陜西省軟科學研究計劃-重點項目(2015KRM039)資助

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

中圖分類號：F273

文獻標志碼：A

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