解决项目之间的交互作用及其在交互作用下的组合优化问题被认为是战略项目管理中一项非常重要的研究课题[1]。同时考虑决策者偏好的项目组合问题研究更加切合实际情况，从战略决策者的角度配置公司的人力、技术和财务等资源的分配，有利于提高企业核心竞争力，促进公司更快更好发展。
为解决上述优化问题，Doerner等人[2]在对比ACO和0-1动态数学编程的基础上，提出了利用增强解来初始化搜索进程。Carazo等人[3]考虑到项目之间的交互和临时交互，提出了相对比较完整的解决方案，使资源可以分配到项目组合过程中的不同阶段,并利用SPEA2方法解决6个目标函数优化问题，表现优异。启发式算法以不受目标函数和问题约束，搜索速度快等特性成为项目组合优化问题的主流解决方法。然而在目标函数和项目数量增多的情况下，如何选择合适的个体将种群引导到非劣解显得十分困难，尤其在解决多约束决策分析(MCDA)领域问题时，启发式算法的表现差强人意。为使决策过程更加容易，研究者在搜索过程中引入决策者偏好，将搜索信息引导到决策者感兴趣的区域(ROI)。Deb等[4]对每项目标函数设置参数和权重，成对的比较已有解集，从而获得解集的排序。Molina等[5]利用每个目标函数的期望值来表达决策者偏好。Fernandez等[6]通过决策者构建模型参数来创建模糊级别优先关系，Wagner等[7]通过设置期望阈值来构建期望函数，令其表征决策者偏好。然而在上述论文中运用的模型和方法中，仍然存在考虑决策者偏好时偏好关系划分不够细致，收敛速度慢，非劣解缺乏多样性等缺点。
本文首先给出交互项目组合选择模型并根据偏好关系进行细化得出级别优先模型，然后针对该模型的求解提出改进粒子群优化算法，最后给出模型和算法相应的仿真对比实验。 1 项目组合选择模型建立 1.1 问题描述
结合Carazo等[8]提出的项目组合选择模型。在资源约束的情况下，求解结果需要满足最大收益条件，如(1)式所示。
假设X为可行的项目组合集,其中一种项目组合选择办法可以表示为x=｛x1,x2,…,xN｝,N代表项目总数,xj表示第j个项目,如果该项目包含在项目组合中,则xj=1,如果不在,则xj=0。用f(j)=｛f1(j),f2(j),…,fp(j)｝代表第j个项目的收益。项目组合x的总收益由(2)式表示。
定义zk(x)如下
为在第k个目标函数时所选项目收益总和,
为项目间发生交互的协同收益总和,S为发生协同交互的数量,ai,k表示当第i个项目交互发生时第k个目标的值,当ai,k的值为负时,称之为负交互。假设这些交互过程均由决策者来设定,那么函数gi(x)表示第i个交互发生在项目组合x中。那么,Ai=｛Ai,1,Ai,2,…,Ai,N｝表示项目收到了第i个交互影响(Ai,j=1表示第j个项目受到第i个项目交互的影响)。定义gi(x)为
表示不考虑项目交互的项目x的该类资源总和,
表示考虑项目交互时该类资源的总和。R表示发生交互的次数,hi(x)是一个二值函数表示是否第i个交互发生,bj,k表示第i个交互发生时对第k类资源的改变。(6)式中hi(x)的定义与gi(x)的定义类似。利用ni和Ni来表达协同交互是否发生,hi(x)的定义如(6)式所示。其中,Ci=｛Ci,1,Ci.2,…,Ci,N｝为一个二值向量,表示某项目受到第i个项目交互的影响。
假设在完成项目组合选择的过程中需要考虑q类不同的资源或约束,用｛B1,B2,…,Bq｝来表示每类资源的内容(例如:现金流,资源,人力等)。项目组合优化问题求解所受约束如下
由于建模过程中没有考虑到每个项目的进程,本文进行的是项目组合问题的静态分析。
1.2 决策者偏好级别优先模型结合Fernandez等[6]的工作,对偏好的类型进行细致划分,利用σ(x,y)表示“相比选择项目组合y更加偏好项目组合x”偏好参数λ,β和ε满足0≤ε≤β≤λ,λ>0.5。项目组合(x,y)确定偏好关系如表 1所示。
| 偏好关系 | 符号 | σ(x,y)满足条件 |
| 明显偏好 | xPy | 1) σ(x,y)≥λ∧σ(y,x)＜0.5 2) σ(x,y)≥λ∧ [0.5≤σ(y,x)<λ］∧ [σ(x,y)-σ(y,x)］≥β |
| 无明显偏好 | xIy | 1) σ(x,y)≥λ∧σ(y,x)≥λ 2) |σ(x,y)-σ(y,x)|≤ε |
| 稍微偏好 | xQy | 1) σ(x,y)≤λ∧ σ(x,y)≥σ(y,x) 2) xPy∧xIy |
| 无法比较 | xRy | 1) xRyσ(x,y)＜0.5∧ σ(y,x)＜0.5 |
| k阶偏好 | xKy | 1) 0.5≤σ(x,y)≤λ 2) σ(x,y)＜0.5 3) σ(x,y)-σ(y,x)>β/2 |
从一个可行项目组合的解集O中,定义偏好解集如下:
1) S(O,x)=｛y∈O|yPx｝;对于y明显偏好级别优先x的解构成。
2) NS(O)=｛x∈O|S(O,x)=
｝;由非严格级别优先解构成。
3) W(O,x)=｛y∈NS(O)|yQx∧yKx｝对于y偏好级别稍微优先x的解构成。
同时定义(8)式
如果Fn(x)>Fn(y)表明相比于选择项目组合y更加倾向选择项目组合x,则定义解集如下:
1) F(O,x)=｛y∈NS(O)|Fn(y)>Fn(x)｝求解出的是非严格级别优先解。
2) NF(O)=｛x∈NS(O)|F(O,x)=｝求解出的是非级别优先非劣解。
Fernandez等人[9]验证,结合模糊级别优先系数σ的最优项目组合是一个非严格级别优先解,同时也是非劣解
基于Rabbani等[11]提出的算法框架,通过对于粒子群优化算法搜索过程的改进来求解偏好模型(9)式的非劣解。采用粒子的跳跃改进来防止早熟收敛,当存在项目组合保持非严格级别优先状态超过γ代,则将其从解集中移除。通过聚类操作拓展非劣解的多样性,当算法找到最优非劣解集或者达到最大搜索代数时,搜索过程结束。
解集尺寸为s,xi表示一组项目组合解,vi表示粒子的飞行速度,用pbesti来表示以往最优的项目组合,gbest来表示全局最优组合解,粒子速度的更新公式如下
对于所有j∈1,…,N,vi,j是第i个粒子在第j维度的速度,c1和c2表示加速系数,r1和r2是在范围(0,1)内的2组随机数,g为迭代的次数。项目组合更新公式(11)所示
项目组合的局部最优位置更新方法如下
全局最优解定义如下
速度向量vi的值要严格在范围[-vmax,vmax]中,以保证粒子不超出搜索范围。
2.1 粒子跳跃改进采取跳跃改进来拓宽粒子搜索面,既维持了粒子的解的多样性,同时不影响PSO的收敛速度。在跳跃改进机制中包含向内跳跃和向外跳跃。向内跳跃旨在增强在已知搜索区域的搜索深度。向外跳跃可以增强搜索未知区域的能力,防止搜索陷入局部最优。跳跃改进过程如图 1所示,其中s1和s2代表从非劣解集中随机选取的2个成员,将其作为搜索向量。2个对于未知空间的搜索向量Os1和Os2是通过公式(14)、(15)获得的,其中α1和α2是0到1的随机值。
|
| 图 1 跳跃改进机制示意图 |
本文提出聚类的方法从非劣解集中筛选相似非劣解来解决这个问题。每个粒子设定聚类半径为r。然后选定一个粒子作为聚类中心,如果在搜索中有其他粒子落以该粒子为中心,半径为r的范围内,则将其从候选解集中剔除。
多维目标解空间的聚类半径r定义如下
|
| 图 2 聚类操作图例 |
基于决策者偏好模型求解的改进粒子群算法的伪代码如算法1所示。
算法1:改进粒子群优化算法(NOPSO)
输入:X(可用项目集),B(约束信息)
输出:NS(O)
初始化: NSglobal=,NSglobal*=,NSlocal=,xi,j,vi,j,
gbest,pbest,rep=0,iter=1
Repeat:
1) O=
2) 采用粒子群算法求得非劣解集O
O=O∪NSlocal
NSlocal=argminx∈O｛＜|S(O,x)|,|W(O,x)|,|
F(O,x)|>｝
If跳跃粒子数不够(粒子跳跃改进)
从解集NSlocal中随机选取s1
从解集NSlocal中随机选取s2
产生新的Os1和Os2
Endif为非劣解集中的每个粒子设定编号(聚类操作)
计算聚类半径r
For对解集中的每个粒子根据他们的编号
把编号粒子放在搜索空间并形成一个聚类中心
If粒子坐落在聚类中心粒子的半径中
移除这个粒子
Endif
Endfor
3) NSglobal*=NSglobal∪NSlocal
4) If NSglobal*=NSglobal
rep=rep+1
Else
rep=0
5) Update: NSglobal*=NSglobal
Until(rep=repmax)∪(iter=itermax)
Return NSglobal
在项目组合选择实验过程中,需要考虑决策者的偏好和项目之间的交互,从而设定如下约束:
项目总数为100个;总预算为2亿元; 项目分为3种类别和2个地域;单个项目类别预算占总预算20％~60％;单个区域预算占总预算30％~70％;由决策者定义20种相关的项目交互作用;交互作用包括4种项目间分流,6种项目间冲突和10种项目间协同促进,每种协同中包含至多5个项目。
下面给出文中提出模型和方法的验证性实验,以并阐述该方法的有效性和优势,基于决策者偏好的交互项目组合优化模型和改进的粒子群算法在解决实际的资源分配和选择决策过程中有较大的优势。
3.1 偏好模型对比实验MOPSO广泛应用于交互项目组合选择问题[11]中,为了解决考虑决策者偏好的多目标优化问题,结合偏好模型,提出了改进的粒子群优化算法(MOPSO-P),通过搜索(9)式中的非劣解来近似式(1)的最优候选解。其中偏好模型的参数根据Fernandez[6]来设置,保证可靠的决策环境。MOPSO和MOPSO-P均用MATLAB编程实现。参数设置方面,MOPSO-P与MOPSO使用相同的参数设置,参考Tsai[12]中的定义。
在表 2中列出了5次实验的结果。从表中可以得出结合偏好的粒子群优化搜索过程更加集中在决策者感兴趣的区域,MOPSO-P比MOPSO在非严格级别优先解数量上多17.2％。在大多数情况下,MOPSO在搜索过程中受到劣解的影响比较大。在偏好模型与实际决策者偏好相匹配的情况下,项目组合最优解均包含在MOPSO-P求解的解集中。仿真实验的结果证明了基于决策者偏好的级别优先模型的有效性。
| 实验 | 算法 | 时间/s | 解集尺寸 | O1/O2中的非劣解 | NS(O1)/NS(O2)中的解 | O1/O2中包含最优解 |
| 1 | MOPSO | 3 568.45 | 2 304 | 836 | 12 | |
| MOPSO-P | 5 498.87 | 16 | 16 | 12 | √ | |
| 2 | MOPSO | 3 458.75 | 2 045 | 1 245 | 8 | |
| MOPSO-P | 4 558.32 | 19 | 19 | 12 | √ | |
| 3 | MOPSO | 3 287.67 | 2 104 | 658 | 18 | |
| MOPSO-P | 4 167.97 | 42 | 42 | 18 | √ | |
| 4 | MOPSO | 3 812.34 | 2 384 | 1 183 | 10 | √ |
| MOPSO-P | 4 729.91 | 36 | 35 | 11 | √ | |
| 5 | MOPSO | 3 276.43 | 1 873 | 1 145 | 10 | |
| MOPSO-P | 4 532.34 | 42 | 22 | 15 | √ | |
| 注:O1和O2分别为MOPSO和MOPSO-P搜索得到的非劣解集。最优候选解为在O1/O2中对于(9)式求解的最优解。 | ||||||
确定所求解为真实最优解的方法是取得所有正确的非劣解,至少所有的非严格级别优先解。然而,实验设计的项目总数过多,无法得出确定的非劣解。此时,可以利用本文中的方法在可接受的误差范围内近似这个非劣解。通过与Carazo等[8]提出的SS-PPS方法做对比实验来验证本文提出的NO-PSO方法可以近似非劣解,即项目组合选择的最优解。算法采用MATLAB编程实现。参数设置为c1=2,c2=2,ps=8,repmax=50,itermax=100 000。通过实验数据分析,上述参数设置具有鲁棒性。
在表 3中列出了5次实验的结果,从结果可以得出,在偏好区域,NO-PSO比SS-PPS搜索到的解更好的接近非严格级别高于前沿,其中没有一个SS-PPS所求解比NO-PSO所求解占优。在解的数量上,本文所提出的方法比对比方法在非严格级别高于前沿解平均多出53.1％。在搜索时间上,仅仅为对比算法速度的11.3％。结合决策者偏好的改进的粒子群优化算法极大地降低了工作量,提高了算法搜索效率,拓展了非劣解的多样性。并且NO-PSO算法求解的解集包含(1)式的最优解。
| 实验 | 算法 | 时间/s | 解集尺寸 | O1/O2中的非劣解 | NS(O1)/NS(O2)中的解 | O1/O2中包含最优解 |
| 1 | SS-PPS | 37 942.67 | 4 839 | 4 832 | 13 | √ |
| NO-PSO | 5 102.73 | 18 | 18 | 13 | √ | |
| 2 | SS-PPS | 23 493.32 | 4 893 | 4 823 | 12 | |
| NO-PSO | 4 832.54 | 16 | 16 | 15 | √ | |
| 3 | SS-PPS | 33 422.14 | 4 992 | 2 932 | 10 | |
| NO-PSO | 3 429.21 | 18 | 18 | 18 | √ | |
| 4 | SS-PPS | 38 423.23 | 4 821 | 4 812 | 12 | |
| NO-PSO | 3 094.21 | 29 | 29 | 24 | √ | |
| 5 | SS-PPS | 37 493.43 | 4 722 | 4 712 | 17 | √ |
| √ | NO-PSO | 2 933.86 | 32 | 30 | 28 | |
| 注:O1和O2分别为SS-PPS和NO-PSO搜索得到的非劣解集。最优候选解为在O1/O2中对于(9)式求解的最优解。 | ||||||
本文在优化Fernandez提出的偏好系统而得出级别优先模型的基础上，改进已有的多目标粒子群优化算法。研究结果解决了考虑决策者偏好同时项目间存在交互作用时的项目组合优化问题，使搜索集中于偏好区域，从而使求解非劣解更加贴近偏好的项目组合；同时降低搜索时间，避免早熟收敛，保证解的多样性。
不足之处在于，实验过程中没有考虑决策者偏好的变化，并且项目的维度和复杂程度不高。之后研究将致力于：
1) 在项目数量更多、项目间交互作用更复杂时，提高模型的可靠性和算法的搜索效率。
2) 根据决策者偏好的改变对模型中的偏好参数进行更新，求得最优的组合结果。
| [1] | Salo A, Keisler J, Morton A. Portfolio Decision Analysis: Improved Methods for Resource Allocation[M]. Springer Science & Business Media, 2011 |
| Click to display the text | |
| [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 |
| Click to display the text | |
| [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 |
| Click to display the text | |
| [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 |
| Click to display the text | |
| [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 |
| Click to display the text | |
| [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 |
| Click to display the text | |
| [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 |
| Click to display the text | |
| [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 |
| Click to display the text | |
| [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 |
| Click to display the text | |
| [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 |
| Click to display the text | |
| [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 |
| Click to display the text | |
| [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 |
| Click to display the text |
