决策者偏好交互项目组合选择模型及算法优化研究

罗淑娟, 白思俊, 郭云涛

(西北工业大学 管理学院, 陕西 西安　710072)



决策者偏好交互项目组合选择模型及算法优化研究

罗淑娟, 白思俊, 郭云涛

(西北工业大学 管理学院, 陕西 西安710072)

摘要：项目组合选择是战略项目管理决策的重要环节，目前基于决策者偏好的交互项目组合选择的研究仍然在模型和算法上存在不足。首先提出级别优先模型细致划分了项目间的偏好关系，并引入了项目间的协同交互，使模型更加完备。进而结合该模型改进了多目标粒子群算法，加快其收敛速度，并拓展其非劣解的多样性。在考虑决策者偏好和项目间交互约束的条件下，分别对偏好模型和模型求解算法进行了仿真验证。仿真结果表明，采用级别优先模型所得的非劣解更加接近项目组合选择的最优解，改进粒子群算法的搜索速度更快。

关键词：粒子群优化；项目组合选择；项目交互；决策者偏好；级别优先模型；改进粒子群优化

解决项目之间的交互作用及其在交互作用下的组合优化问题被认为是战略项目管理中一项非常重要的研究课题[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)式所示。

(1)

式中,p为目标个数,〈z1(x),z2(x),…,zp(x)〉为项目组合收益总和,RF是可行解空间,由可用预算、项目类型、社会定位和区域划分构成。

假设X为可行的项目组合集,其中一种项目组合选择办法可以表示为x={x1,x2,…,xN},N代表项目总数,xj表示第j个项目,如果该项目包含在项目组合中,则xj=1,如果不在,则xj=0。用f(j)={f1(j),f2(j),…,fp(j)}代表第j个项目的收益。项目组合x的总收益由(2)式表示。

(2)

定义zk(x)如下

(3)

(4)

式中,mi和Mi分别表示协同交互i发生时,受到交互影响的最小和最大的项目数量。cj,k表示第j个项目中第k类资源的内容,那么项目组合选择x对于第k类资源的总和如(5)式所示

(5)

(6)

假设在完成项目组合选择的过程中需要考虑q类不同的资源或约束,用{B1,B2,…,Bq}来表示每类资源的内容(例如:现金流,资源,人力等)。项目组合优化问题求解所受约束如下

(7)

由于建模过程中没有考虑到每个项目的进程,本文进行的是项目组合问题的静态分析。

1.2决策者偏好级别优先模型

结合Fernandez等[6]的工作,对偏好的类型进行细致划分,利用σ(x,y)表示“相比选择项目组合y更加偏好项目组合x”偏好参数λ,β和ε满足0≤ε≤β≤λ,λ>0.5。项目组合(x,y)确定偏好关系如表1所示。

表1　项目组合偏好关系条件表

从一个可行项目组合的解集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)式

(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]验证,结合模糊级别优先系数σ的最优项目组合是一个非严格级别优先解,同时也是非劣解

(9)

式中求解的三目标优化问题是(1)式问题的映射,(1)式的最优候选解就是(9)式的非劣解。(1)式所求解的问题及其所映射的三目标优化问题在目标空间维度上是独立的。决策者在优化过程中需要确定的参数分别为:σ(约束权重与阈值)和偏好系统的参数(λ、β和ε)。该过程需要通过决策分析的办法来辅助实现,偏好解集分析法(PDA)和多准则决策分析法(MCDA)是普遍认可的2种方法,PDA[10]可以通过决策者在一些明确的项目组合的决策过程推断出模型的约束权重和偏好参数。

2基于级别优先模型的改进粒子群优化算法

基于Rabbani等[11]提出的算法框架,通过对于粒子群优化算法搜索过程的改进来求解偏好模型(9)式的非劣解。采用粒子的跳跃改进来防止早熟收敛,当存在项目组合保持非严格级别优先状态超过γ代,则将其从解集中移除。通过聚类操作拓展非劣解的多样性,当算法找到最优非劣解集或者达到最大搜索代数时,搜索过程结束。

解集尺寸为s,xi表示一组项目组合解,vi表示粒子的飞行速度,用pbesti来表示以往最优的项目组合,gbest来表示全局最优组合解,粒子速度的更新公式如下

(10)

对于所有j∈1,…,N,vi,j是第i个粒子在第j维度的速度,c1和c2表示加速系数,r1和r2是在范围(0,1)内的2组随机数,g为迭代的次数。项目组合更新公式(11)所示

(11)

项目组合的局部最优位置更新方法如下

(12)

全局最优解定义如下

(13)

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

2.1粒子跳跃改进

采取跳跃改进来拓宽粒子搜索面,既维持了粒子的解的多样性,同时不影响PSO的收敛速度。在跳跃改进机制中包含向内跳跃和向外跳跃。向内跳跃旨在增强在已知搜索区域的搜索深度。向外跳跃可以增强搜索未知区域的能力,防止搜索陷入局部最优。跳跃改进过程如图1所示,其中s1和s2代表从非劣解集中随机选取的2个成员,将其作为搜索向量。2个对于未知空间的搜索向量Os1和Os2是通过公式(14)、(15)获得的,其中α1和α2是0到1的随机值。

(14)

(15)

图1　跳跃改进机制示意图

2.2聚类操作

本文提出聚类的方法从非劣解集中筛选相似非劣解来解决这个问题。每个粒子设定聚类半径为r。然后选定一个粒子作为聚类中心,如果在搜索中有其他粒子落以该粒子为中心,半径为r的范围内,则将其从候选解集中剔除。

多维目标解空间的聚类半径r定义如下

(16)

图2　聚类操作图例

基于决策者偏好模型求解的改进粒子群算法的伪代码如算法1所示。

算法1:改进粒子群优化算法(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跳跃粒子数不够(粒子跳跃改进)

从解集NSlocal中随机选取s1

从解集NSlocal中随机选取s2

产生新的Os1和Os2

Endif为非劣解集中的每个粒子设定编号(聚类操作)

计算聚类半径r

For对解集中的每个粒子根据他们的编号

把编号粒子放在搜索空间并形成一个聚类中心

If粒子坐落在聚类中心粒子的半径中

移除这个粒子

Endif

Endfor

rep=rep+1

Else

rep=0

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

ReturnNSglobal

3仿真实验对比分析

在项目组合选择实验过程中,需要考虑决策者的偏好和项目之间的交互,从而设定如下约束:

项目总数为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求解的解集中。仿真实验的结果证明了基于决策者偏好的级别优先模型的有效性。

表2　结合决策者偏好的粒子群优化算法对比分析

注:O1和O2分别为MOPSO和MOPSO-P搜索得到的非劣解集。最优候选解为在O1/O2中对于(9)式求解的最优解。

3.2NOPSO与SS-PPS算法对比实验

确定所求解为真实最优解的方法是取得所有正确的非劣解,至少所有的非严格级别优先解。然而,实验设计的项目总数过多,无法得出确定的非劣解。此时,可以利用本文中的方法在可接受的误差范围内近似这个非劣解。通过与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)式的最优解。

表3　NOPSO与SS-PPS算法对比分析

注:O1和O2分别为SS-PPS和NO-PSO搜索得到的非劣解集。最优候选解为在O1/O2中对于(9)式求解的最优解。

4结论

本文在优化Fernandez提出的偏好系统而得出级别优先模型的基础上，改进已有的多目标粒子群优化算法。研究结果解决了考虑决策者偏好同时项目间存在交互作用时的项目组合优化问题，使搜索集中于偏好区域，从而使求解非劣解更加贴近偏好的项目组合；同时降低搜索时间，避免早熟收敛，保证解的多样性。

不足之处在于，实验过程中没有考虑决策者偏好的变化，并且项目的维度和复杂程度不高。之后研究将致力于：

1) 在项目数量更多、项目间交互作用更复杂时，提高模型的可靠性和算法的搜索效率。

2) 根据决策者偏好的改变对模型中的偏好参数进行更新，求得最优的组合结果。

参考文献：

[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—)，女，西北工业大学博士研究生，主要从事项目组合管理与优化方法研究。

中图分类号：F273

文献标志码：A

文章编号:1000-2758(2016)04-0724-07