摘要:针对大规模软件项目管理中使用手工方法生成PERT网络图不方便等问题,对PERT网路图的优化问题进行了研究,分析了节点间的布局优化问题,给出了基于蚁群算法(ACO)和遗传算法(GAs)来实现对PERT中的节点进行优化的新方法.利用GAs很强的自适应性和种群优化技术,通过引入ACO算法实现节点布局全局范围的调整.计算和仿真结果表明,该方法能使用计算机自动生成的PERT网络图节点达到最小,布局能更有效合理有效,从而有效地解决了大规模软件项目中工程评审评估问题.
关键词:计划评价技术；软件项目管理；蚁群算法；遗传算法；
1概述
PERT网络图是工程评价技术的一个重要的工具,可以直观的反映出任务间的前后调度关系.由于工程评估评审技术主要用于大规模的项目开发和项目管理,因此通常使用计算机辅助完成PERT图的绘制和生成.由于大规模的项目,任务节点比较多,任务间的关系也比较复杂,因此,对于计算机自动生成的PERT图质量是工程评估的关键要素.本文针对PERT网络图的优化问题进行了研究,分析了节点间的布局优化问题,给出了基于蚁群算法(ACO)和遗传算法(GAs)来实现对PERT中的节点进行优化的新方法.利用GAs很强的自适应性和种群优化技术,通过引入ACO算法实现节点布局全局范围的调整.计算和仿真结果表明,该方法能使用计算机自动生成的PERT网络图节点达到最小,布局能更有效合理有效,从而有效地解决了大规模软件项目中工程评审评估问题.
2PERT网络图的组成结构
PERT网络是一种类似流程图的箭线图.它描绘出项目包含的各种活动的先后次序,标明每项活动的时间或相关的成本[1-2].图1为一个简单的PERT网络图,其中A、B、C、D分别表示活动的权重.
对于PERT网络图,项目管理者必须考虑要做哪些工作,确定时间之间的依赖关系,辨认出潜在的可能出问题的环节.借助PERT网络图还可以方便地比较不同行动方案在进度和成本方面的效果.构造PERT图,需要明确三个概念:事件、活动和关键路线.其中,事件表示主要活动结束的那一点；活动表示从一个事件到另一个事件之间的过程；关键路线是PERT网络中花费时间最长的事件和活动的序列.它采用加权平均得到期望值
E=(O+4M+P)/6.(1)
其中,O是最小估算值:乐观(Optimistic),P是最大估算值:悲观(Pessimistic),M是最大可能估算(MostLikely).该算法把非肯定型问题转化为肯定型问题来计算,用概率论的观点分析,其偏差仍不可避免,但趋向总是有明显的参考价值,当然,这并不排斥每个估计都尽可能做到可能精确的程度.
计划评审技术中的活动期望时间(ET)公式和活动时间方差公式都是在活动时间被假设为服从参数为p=4,q=4的β分布时得到的,而该假设是基于以下两个前提,一是最可能时间的可能性4倍于乐观时间和悲观时间的可能性,二是最可能时间恰好是乐观时间和悲观时间的平均值.实际在项目管理实践中,这两个前提都不一定成立,因而活动时间服从参数为p=4,q=4的β分布也是站不住脚的.那么,怎么才能使参数也趋于合理呢?本文针对PERT网络图的优化问题进行了研究,分析了节点间的布局优化问题,给出了基于蚁群算法(ACO)和遗传算法(GAs)来实现对PERT中的节点进行优化的新方法.
3基于蚁群算法和遗传算法结合的PERT网络图的生成方法
3.1蚁群算法及遗传算法描述
蚁群算法[2-4]的基本思想是蚁群总是寻找食物源与蚁巢间的最短路径.该算法具有正反馈性、协同性、并行性和鲁棒性、易于与其它方法结合等优点,但是,该算法一般需要较长的搜索时间,而且容易出现早熟和停滞的现象,而得不到全局最优解.为了提高蚁群算法的全局搜索能力和搜索速度,这里利用遗传算法的基于种群数量最优化技术,防止种群收敛并停滞在任何局部的最优点.
遗传算法有选择,交换,变异[5-9]3个基本操作数.选择操作是从当前一代生成一组新的种群,它决定哪些个体是参与生成下一代的个体,即产生下一代交配池的过程.个体基因链按照它们的适应性函数值被复制在交配池中；交换处理分为:(1)来自交配池的成员随机交配.(2)每对基因链按照下列方式交换:位置l沿着基因链在区间[1,l−1]随机被选择(l是链的长度).两个链通过在位置k和l之间交换产生；变异是基因链位置的值随机交替的过程.它能防止整个种群在任何局部的任一位收敛到一个值,更重要的是它能防止种群收敛并停滞在任何局部的最优点.因此,由交换操作中得到的好染色体不会丢失.
3.2PERT网络图自动生成的步骤
PERT网络图自动生成的步骤如下:
(1)任务节点的逻辑定位.这个是指暂时不考虑节点的实际物理位置,只确定节点所在行列的相对位置；(2)任务节点逻辑位置的优化分布.按边集交点最少的要求对统一列中的节点顺序进行调整,使节点的布局合理；(3)任务节点的物理位置.节点的逻辑位置确定后,按边的分布紧凑和拐角最少的原则确定节点及边的实际物理位置.
3.3基于蚁群算法和遗传算法结合的PERT网络图的生成方法
算法主要包括选择策略、信息量的局部更新和求局部最优解遍历算法3部分.具体实现原理如下:(1)为了减少计算时间,在最初的迭代中,取较大的转移概率.(2)为了防止陷入局部最优解,漏掉全局最优解,可在搜索进行到一定时间后,通过遗传算法的一些交叉、变异对信息素进行调整,缩小最好和最差路径上信息量的差距,适当加大随机选择的概率,从而使搜索空间更完全,扩大搜索范围.(3)在信息素的更新上,通过改变更新策略,更好地把全局特点考虑进去.基于蚁群算法和遗传算法结合的PERT网络图的生成算法实现过程如图2所示.
4结束语
大规模的软件项目中,PERT网络图是计划评审技术的关键,这样,对于自动化生成PERT网络图的算法的设计提出了更高的要求.为解决PERT中的节点的优化问题,本文对此提出了基于交叉、变异的蚁群算法来实现对PERT中的节点进行优化的新方法.利用GAs很强的自适应性和种群优化技术,通过引入ACO算法实现节点布局全局范围的调整.计算和仿真结果表明,该方法能使用计算机自动生成的PERT网络图节点达到最小,布局能更有效合理有效,从而有效地解决了大规模软件项目中工程评审评估问题.该算法扩大了搜索范围,自适应地调整路径选择概率的确定策略和信息量更新策略,可以使选择的路径尽量短以满足实时性应用,又能实现节点布局全局范围的调整.
参考文献:
[1] 韩万江, 吕勇. 软件项目管理[M]. 北京: 电子工业出版社, 2010.
[2] 王颖, 谢剑英. 一种基于蚁群算法的多媒体网络多播路由算法[J]. 上海交通大学学报, 2002, 36(4): 526-531.
[3] MANIEZZO V, CARBONARO A. An ants heuristic for the frequency assignment problem[J]. Future Generation Computer Systems, 2000, 16 (8): 927-935.
[4] DORIGO M, GAMBARDELLA L M. Ant colony system: acooperative learninig approach to the traveling sales man problem [J]. IEEE Tran sactions on Evolutionary Computation, 1997, 1(1): 53- 66.
[5] 王海枚, 游志胜. 基于遗传算法与模糊控制的建模方法[J]. 电子科技大学学报, 2002, 31(3): 266-269.
[6] 毕军, 付梦印, 张宇河. 计算机工程与应用[J]. 电子科技大学学报, 2003, 35(3): 77-81.
[7] 刘评, 高飞, 杨云. 基于遗传算法和蚁群算法融合的QoS 路由算法[J]. 计算机应用研究, 2007, 35(9): 224-227.
[8] 徐刚, 马光文. 基于蚁群算法的梯级水电站群优化调度[J]. 水力发电学报, 2005, 36(8): 78: 1-5.
[9] 崔梦天, 钟勇, 赵海军. ACOGA算法的多媒体网络QoS路由实现[J]. 电子科技大学学报, 2009, 38(2), 266-269.
[10] 周洞汝. PERT图的计算机自动生成[J]. 机电工程, 1989(4): 22-23.
作者介绍：
崔梦天： 西南民族大学计算机科学与技术学院，电子科技大学计算机科学与工程学院,
张荣虎：四川邮电职业技术学院
程国忠：西华师范大学(本文于2012年发表于《西南民族大学学报(自然科学版)》)
