摘要:針對大規模軟件項目管理中使用手工方法生成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年發表于《西南民族大學學報(自然科學版)》)
