, 汪定伟11. 东北大学 信息科学与工程学院, 辽宁 沈阳 110819;
2. 东北大学秦皇岛分校 管理学院, 河北 秦皇岛 066004
收稿日期：2017-11-20
基金项目：国家自然科学基金资助项目(71401027)；河北省自然科学基金资助项目(G2016501086)；中央高校基本科研业务费专项资金资助项目(N172304016)；河北省高等学校科学技术研究重点项目(ZD2016202)。
作者简介：王雷震(1965-)，男，河北行唐人，东北大学副教授，博士;
汪定伟(1948-)，男，江西彭泽人，东北大学教授，博士生导师。
摘要：针对IT(information technology)外包项目的两层进度风险控制优化问题, 设计了两层混合遗传算法.该算法是在传统遗传算法中引入模拟退火和自适应机制, 并结合优化问题的两层特点而设计的, 能够克服传统遗传算法易于早熟、局部搜索能力较差的弱点.在算例分析中, 首先分析了两层数学模型在IT外包项目进度风险控制中的管理意义, 进而将两层混合遗传算法的仿真结果与两层粒子群优化算法和传统遗传算法的仿真结果进行比较, 验证了改进算法的效率和有效性.
关键词：IT外包进度风险混合算法遗传算法模拟退火
IT Outsourcing Schedule Risk Control Based on Two-Level Hybrid Genetic Algorithm
WANG Lei-zhen1,2, ZHU Jin-wen1, LU Fu-qiang1,2
, WANG Ding-wei11. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
2. School of Management, Northeastern University at Qinhuangdao, Qinhuangdao 066004, China
Corresponding author: LU Fu-qiang, E-mail: 19217238@qq.com
Abstract: Focusing on the optimization problem of schedule risk control in information technology(IT)outsourcing project, a two-level hybrid genetic algorithm(TLHGA)is proposed. The TLHGA incorporates simulated annealing, adaptive mechanism and the two-level feature of optimization problem to improve the traditional genetic algorithm(TGA), which could overcome the shortcomings of TGA such as early mature and weak local searching ability. In the experimental analyses, the management meanings of the two-level mathematical model in IT outsourcing schedule risk control is analyzed. Next, the simulation results of TLHGA are compared with the TGA and two-level particle swarm optimization algorithm, which verifies the rationality and effectiveness of the improved algorithm.
Key words: IT outsourcingschedule risk controlhybrid algorithmgenetic algorithmsimulated annealing
在IT外包项目管理中, 能否按时完工一直是委托方和承包商的关注重点, 工期控制的成功与否在一定程度上决定着项目的成败[1-2].在项目进度控制方面, 项目管理者常用的方法和技术包括Gantt图、关键路径法、基于挣值(earned value)的技术、基于里程碑的方法[3-5]等.在风险分析方面, 有等风险图法、模糊分析法、风险报酬法和蒙特卡罗模拟法等多种方法[6-7].本文采用的IT外包进度风险控制的结构化分布式决策模型[1], 不仅着眼于项目本身作业过程的进度风险的评估和控制, 还考虑了IT外包项目在执行过程中所涉及到的多方交互合作的实际情况.
用遗传算法求解项目进度相关的例子有很多.周方明等将主成分分析(PCA)、遗传算法(GA)与BP神经网络相结合, 提出基于PCA-GA-BP的工程项目工期风险预测模型, 并证明其对实际工程具有指导意义[6]; Dao等曾在项目日程安排的优化上使用遗传算法, 为该类问题提供了一种新的思路[7].
IT外包项目中进度风险控制是一个分布式优化问题, 具有两层复杂结构, 且决策变量存在离散和连续的混合情况，因此，该优化问题的求解难度较高.本文根据问题特点对传统遗传算法(traditional genetic algorithm, TGA)进行改进.首先, 设计两层遗传算法以分解问题的解空间, 降低求解难度；然后, 为了避免TGA易于早熟和局部搜索能力不强的问题, 引入模拟退火和自适应机制, 设计了TLHGA(two-level hybrid genetic algorithm), 以期为本优化问题提供一种有效的求解手段.
1 IT外包项目进度风险控制问题一个委托方按照开发流程将项目进行分解, 委托给多个承包商并使其完成相应的目标[1].模型分为上、下两层, 上层的决策者为委托方, 由委托方将风险控制的预算资金分配给各承包商; 下层的决策者为承包商, 有M个承包商接受资金分配并对所承包的子项目中的N个活动选择相应的进度风险控制措施.以承包商i为例, 将其得到的风险控制投入资金xi分配到其负责子项目的关键路径上的N个活动中.
问题定义:子项目i的进度风险由风险暴露(risk exposure)来定义, 即子项目出现拖期的概率乘以损失的程度(拖期的时间):
 | (1) |
1) 委托方在与各承包商签订的合同中规定各合同总价款均为Ui, 若各子项目发生延期, 则需赔款Vi, i=1, 2, …, M, M为承包商数量; xi为承包商i的预算资金; Bmax为总的预算资金的最大上限值; Rmax是各承包商负责的子项目的进度风险水平的最大上限值; Benifiti表示承包商i所获得的收益; P(Ai)表示承包商i项目的完成概率, P(Ai )表示承包商i的拖期概率.
2) 子项目i关键路径上的每一个活动j的直接费用为cij(j=1, …, Ni), 子项目计划工期为Ti0, 子项目实际工期为Ti.子项目i间接费用一般随着总工期的增加而增长, 假设单位时间的间接费用为Ci, tij(yij)是子项目i每个活动j的拖期时间, costij(yij)表示每个活动j上所投入的资金.
3) 承包商i的进度风险水平是Riski(xi).
4) 子项目之间在工序上是串行的.
上层模型:
 | (2) |
 | (3) |
 | (4) |
 | (5) |
下层模型:
 | (6) |
 | (7) |
 | (8) |
 | (9) |
 | (10) |
2 两层混合遗传算法设计IT外包项目进度风险控制问题是一个两层的、混合数学规划问题.当子项目和措施的数量较多时, 该问题的解空间将迅速增大, 导致其是一个NP难问题，因此, 选择GA作为本问题的求解方法.本文根据问题特点对TGA进行了改进.首先, 设计两层GA使问题的解空间得以分解, 降低求解难度.然后, 为了避免TGA易于早熟和局部搜索能力不强的问题[5-7], 引入模拟退火和自适应机制, 对上层模型采用模拟退火算法, 对下层模型采用自适应遗传算法, 设计了TLHGA, 以期为本优化问题提供一种有效的求解手段.
2.1 模拟退火机制对于上层种群中的最优个体, 实施模拟退火机制.模拟退火具有较强的局部搜索能力, 易于跳出局部最优解, 能弥补TGA易于早熟的缺陷.由于本文上层的自变量是具体的资金额, 且有一定的限制.因此, 模拟退火算法中产生函数的机制为:随机产生a, 将其与自变量相加或相减, 使最终结果符合限制条件.模拟退火机制的具体操作过程为:①利用产生函数, 产生新个体; ②判断新个体的适应值是否减小(求最小值), 若适应值减小, 则用新个体取代原个体, 否则按照接受准则判断是否接受新个体; ③在降温机制和每个温度条件一定的交换次数限制下, 重复步骤①和步骤②.接受准则采用Boltzmann概率分布[7], 公式为
 | (11) |
2.2 自适应机制遗传算法的核心部分在于选择、交叉和变异, 而算法中的交叉和变异过程受到交叉概率Pc与变异概率Pm影响, 所以实际上, Pc与 Pm的选择是影响遗传算法性能的关键[7].自适应机制使得Pc与 Pm的值在程序运行过程中能够随着当代种群适应值的改变而改变.
1) 将单点交叉与自适应交叉相结合.自适应交叉率的公式为
 | (12) |
 | (13) |
2.3 TLHGA流程图TLHGA算法流程图如图 1所示, 其中图 1b是图 1a中的虚线部分, 代表下层结构.在算法中, 上层搜索的终止由初始温度和每个温度下的迭代次数确定, 下层的终止由迭代次数确定.
图 1(Fig. 1)
 | 图 1 TLHGA流程图Fig.1 Flow chart of TLHGA (a)—TLHGA流程图；(b)—下层结构. |
3 算例及分析本节以国内某IT外包服务公司为背景, 设计仿真实例来验证算法的有效性.算例考虑有1个委托方和M个承包商的情况, M=1, 2, …, 5；这5种情况总的预算资金上限分别为Bmax=900, 1 800, 2 700, 3 600, 4 500, 进度风险水平约束为Rmax=0.05.各承包商与委托方通过签订合同开展合作, 合同中的总价款Ui=10 000, 项目延期的赔偿款Vi=3 000, i=1, 2, …, 5.承包商的利润率r=0.2.假定每个项目由10个活动组成(Ni=10), 且活动在工序上是串行的.各活动的费用cij=650, i=1, 2, …, 5, j=1, 2, …, 10.各活动的进度风险发生概率pij={0.93, 0.87, 0.79, 0.79, 0.75, 0.73, 0.71, 0.67, 0.65}.为了防止进度风险发生致使项目失败, 对于每个活动, 可以从4个(Q=4)风险控制措施中选择一个用于风险防范.在风险措施的控制下, 项目在执行过程中的工期会有相应的缩减, 由tij 变为tij(yij).在本算例中风险控制措施编号越大, 则活动工期缩减得越多.其中项目i的计划工期Ti0=1 000, 实际工期由式(14)表示：
 | (14) |
 | (15) |
3.1 算法参数设置算法上层需要确定的参数是模拟退火的初始温度T和温度变化率TR.以M=1为例，对T=60, 65, 70, 75, 80, 85和TR=0.4, 0.5, 0.6的情况进行组合，分别设计18组算例, 每组运行30次.以项目进度风险水平的最小值和平均值为评判指标，通过实验得到参数T=60和TR=0.6.其他参数包括:种群规模取10, 温度的下限Tmin取4.算法下层自适应遗传算法中Pc1=0.9, Pc2=0.6, Pm1=0.1, Pm2=0.01.种群规模取30, 迭代次数为60.
3.2 仿真结果及其分析使用TLHGA对模型进行求解, 得到的最优仿真结果见表 1, 其中pr是上层最优适应值, x是委托方为承包商分配的资金, prisks是承包商的进度风险值, p为所选的进度风险措施编号, Benefit是承包商的收益, tsum项目工期缩短量.
表 1(Table 1)
 表 1 最优仿真结果Table 1 Optimal simulation results
| 表 1 最优仿真结果 Table 1 Optimal simulation results |
以M=2的结果为例来说明仿真结果的含义.委托方将项目委托给2个承包商, 委托方分配给承包商1和2的资金分别为849和884.在风险控制措施的作用下, 整个项目的进度风险水平为80.63, 其中承包商1和承包商2的进度风险水平分别控制在40.74和39.89.在进行风险控制前各子项目的实际工期均为1 200, 采取相应的风险措施后, 承包商1和承包商2的子项目的工期分别缩短为35.42和27.73.与此同时, 承包商1和承包商2分别获得风险控制收益为2 450.31和2 485.72.
为了验证算法的有效性, 将TLHGA的仿真结果与TLPSO[1]和TGA的结果进行比较, 结果见图 2, 其中prBest是最优值、prAVG是最优值的平均值、prVAR是最优值的方差、CPUTimeAVG是平均CPU时间.由图 2a可以看出, 随着问题规模的增加, TGA的整体图线在TLPSO的下方, TLHGA的整体图线在TGA的下方, 显然, TGA比文献[1]中使用的TLPSO算法从结果上看更适合该问题, 而TLHGA得到了比TGA更好的最优解.图 2b描述的是仿真结果得到的目标值的平均值, 可以看出与图 2a中有相似的结论.由图 2c可以看出, TGA和TLHGA表现出来的稳定性不及TLPSO.在图 2d中, 随着问题规模的不断增加, TLPSO和TGA的平均CPU时间都有明显的增大, 但TLHGA的CPU时间并没有随着问题规模的增加而明显增大, 表明该算法的寻优效率较高.
图 2(Fig. 2)
 | 图 2 三种算法的性能对比Fig.2 Comparison of the performance of the three algorithms (a)—最优值；(b)—平均最优值；(c)—最优值方差；(d)—平均CPU时间. |
4 结语本文针对IT外包项目进度风险控制的两层分布式决策问题, 分别引入了模拟退火和自适应机制, 设计了两层混合遗传算法(TLHGA).在仿真实验中, 设计了五个数值算例, 分别采用TGA和TLHGA进行求解, 并将仿真结果与文献[1]中TLPSO的结果进行了对比.结果表明, 在最优适应值、平均适应值、方差和CPU时间等诸多方面, TLHGA都表现不错, 尤其是在时间效率方面表现尤为突出.
参考文献
| [1] | 卢福强, 毕华玲, 黄敏, 等. IT外包进度风险控制的结构化分布式决策模型[J].系统工程, 2016, 34(7): 138–145. ( Lu Fu-qiang, Bi Hua-ling, Huang Min, et al. Study on CDDM model of IT outsourcing schedule risk control[J].Systems Engineering, 2016, 34(7): 138–145.) |
| [2] | 曹萍, 陈福集, 张剑. 基于进度的软件外包项目风险优化控制决策[J].武汉大学学报(工学版), 2012, 45(3): 385–388. ( Cao Ping, Chen Fu-ji, Zhang Jian. Risk optimization control decision-making of software outsourcing project based on schedule[J].Engineering Journal of Wuhan University, 2012, 45(3): 385–388.) |
| [3] | Münch J, Heidrich J. Software project control centers:concepts and approaches[J].Journal of Systems & Software, 2004, 70(1): 3–19. |
| [4] | Yassine A A, Mostafa O, Browning T R. Scheduling multiple, resource-constrained, iterative, product development projects with genetic algorithms[J].Computers & Industrial Engineering, 2017, 107: 39–56. |
| [5] | Boehm B. Anchoring the software process[J].IEEE Software, 1996, 13(4): 73–82.DOI:10.1109/52.526834 |
| [6] | 周方明, 张明媛, 袁永博. 基于PCA-GA-BP的工程项目工期风险预测研究[J].工程管理学报, 2011, 25(5): 534–538. ( Zhou Fang-ming, Zhang Ming-yuan, Yuan Yong-bo. Risk of project time based on PCA-GA-BP[J].Journal of Engineering Management, 2011, 25(5): 534–538.DOI:10.3969/j.issn.1674-8859.2011.05.013) |
| [7] | Dao S D, Abhary K, Marian R. A bibliometric analysis of genetic algorithms throughout the history[J].Computers & Industrial Engineering, 2017, 110: 395–403. |
