遺傳算法在項(xiàng)目管理多目標(biāo)決策模型中的應(yīng)用

周紅

摘要

項(xiàng)目管理工作中成本、工期、質(zhì)量和資源構(gòu)成互為約束條件的基本要素，各個(gè)要素之間有多種組合模式可以實(shí)現(xiàn)項(xiàng)目目標(biāo)。但如何在多種組合模式、多種約束條件和多種資源之間取得平衡，以達(dá)成項(xiàng)目目標(biāo)是本文論述的重點(diǎn)。本文提供一種模型用于綜合考慮成本、工期和資源，并使用基本遺傳算法建立解決問題的數(shù)學(xué)模型，最后通過(guò)實(shí)際應(yīng)用說(shuō)明該模型在項(xiàng)目管理多目標(biāo)決策中的有效性。

【關(guān)鍵詞】遺傳算法 項(xiàng)目管理 多目標(biāo)決策

1 引言

項(xiàng)目管理通過(guò)建立在時(shí)間軸上一系列項(xiàng)目活動(dòng)使用資源，凝聚價(jià)值，達(dá)成項(xiàng)目目標(biāo)。隨著項(xiàng)目的復(fù)雜度和成本的不斷提高，對(duì)項(xiàng)目管理有效性的要求也越來(lái)越高。項(xiàng)目管理者擬定項(xiàng)目計(jì)劃時(shí)需要綜合考慮多個(gè)項(xiàng)目管理目標(biāo)，如工期、成本、資源等。過(guò)去我們經(jīng)常使用PERT/CPM方法安排項(xiàng)目計(jì)劃，但是它在復(fù)雜項(xiàng)目應(yīng)用中有著較大的局限性。本文主要闡述實(shí)際項(xiàng)目中存在多種組合模式、多個(gè)資源約束條件下，對(duì)項(xiàng)目管理多目標(biāo)決策問題進(jìn)行研究，從而指導(dǎo)項(xiàng)目管理者制定有效的項(xiàng)目計(jì)劃。

每個(gè)項(xiàng)目活動(dòng)均存在多種實(shí)現(xiàn)途徑，即多種成本、工期和資源的組合模式，每種組合模式中完成項(xiàng)目活動(dòng)所需的資源種類、數(shù)量和工期也就不同，并且，項(xiàng)目資源在項(xiàng)目活動(dòng)的時(shí)間軸上是互斥的，一種資源安排到項(xiàng)目活動(dòng)A，則就不能再同時(shí)安排到項(xiàng)目活動(dòng)B，即項(xiàng)目的資源之間存在約束關(guān)系，尤其在信息技術(shù)領(lǐng)域這種情況尤為突出。下面我們將建立一種數(shù)學(xué)模型，在多種組合模式、多個(gè)項(xiàng)目資源的情況下對(duì)項(xiàng)目的成本、工期和資源分配進(jìn)行綜合決策，安排比較合理的項(xiàng)目計(jì)劃，實(shí)現(xiàn)項(xiàng)目管理目標(biāo)。

2 數(shù)學(xué)模型

2.1 問題描述

已知：某項(xiàng)目有i個(gè)項(xiàng)目活動(dòng)，分別記為T_i;有j種資源，分別記為R_j，每種資源的總量分別為N_j，第i種資源的單位成本為C_j;M_im表示項(xiàng)目活動(dòng)i的第m種組合模式;在組合模式M_im下，對(duì)各資源的需求量為（a_im^（1），_im^（2），a_im^（3），……，a_im^（j）），所需的工期為D_im;

問題：計(jì)算各個(gè)項(xiàng)目活動(dòng)的組合模式集（M₁₁]，m_2k2，……M_iki，使得：

（1）成本較低;

（2）工期較短;

（3）資源分配較平衡。

約束條件：

（1）Nk，其中k=1，2 ....... j;即每種資源的需求量不能超過(guò)其總量;

（2）總成本在Co_max以內(nèi);

（3）總工期在D_max以內(nèi)。

2.2 幾點(diǎn)假設(shè)

（1）資源是指消耗性資源，或時(shí)間點(diǎn)上互斥的人力資源;

（2）項(xiàng)目活動(dòng)邏輯關(guān)系一定，不隨組合模式而變化;

（3）成本僅考慮直接成本和間接成本，且間接成本和工期存在線性函數(shù)關(guān)系。

（4）構(gòu)造度量函數(shù)評(píng)價(jià)項(xiàng)目管理目標(biāo)，且度量函數(shù)權(quán)重之和為1。

2.3 問題模型

（1）在組合模式集（M_1k1，M_2k2，M_3k3，，……M_{iki）下對(duì)i種資源的需求量為則資}

源的直接成本為。根據(jù)假設(shè)，間接成本是工期的一個(gè)線性函數(shù)，記為Co_i=a*D+b（其中a、b為系數(shù)），則總成本CO=Co_d+CO_i;

（2）在組合模式集（M_1k1，M_2k2，M_3k3，，……M_iki）下對(duì)應(yīng)的工期為（D_1k1，D_2k2，D_3k3，……，D_iki），根據(jù)項(xiàng)目活動(dòng)之間的邏輯關(guān)系可以計(jì)算出在該組合模式集下項(xiàng)目活動(dòng)的關(guān)鍵路徑，并計(jì)算出總工期D;

（3）資源平衡的效果采用標(biāo)準(zhǔn)差度量，第k種資源的標(biāo)準(zhǔn)差記為;D為總工期;P_d^（k）為第d天對(duì)資源k的需求量;p^（k）為在D天內(nèi)平均每天對(duì)資源k的需求量。

2.4 度量函數(shù)

綜上，我們構(gòu)造一個(gè)項(xiàng)目管理目標(biāo)的度量函數(shù)F，用于度量項(xiàng)目計(jì)劃是否合理。上面三個(gè)項(xiàng)目管理目標(biāo)的度量函數(shù)分別為F_工期、F_成本、F_資源平衡，每個(gè)度量函數(shù)的權(quán)重分別為ω_工期、ω_成本、ω_資源平衡，根據(jù)假設(shè)ω_工期+ω_成本+ω_資源平衡=1。

度量函數(shù)的構(gòu)造基于以下原則：

（1）是無(wú)量綱函數(shù)，可比性較強(qiáng);

（2）滿足工期D，成本Co和資源分配的標(biāo)準(zhǔn)差S_k越小，度量函數(shù)的值越高;

（3）度量函數(shù)的取值范圍比較相近，從而避免某一項(xiàng)目管理目標(biāo)的函數(shù)值過(guò)大而掩蓋其余目標(biāo)的度量效果。

根據(jù)以上度量函數(shù)的構(gòu)造原則，構(gòu)造如下三個(gè)目標(biāo)函數(shù)：

其中D₁，Co₁，S_k1參照基準(zhǔn)，分別為當(dāng)所有項(xiàng)目活動(dòng)都選擇第一種組合模式時(shí)對(duì)應(yīng)的工期、成本和第k種資源分配的標(biāo)準(zhǔn)差;若S_k1為0，則另外選取其他組合模式，使之不為零作為對(duì)比值;ω_k為第k種資源分配標(biāo)準(zhǔn)差的權(quán)重。

根據(jù)度量函數(shù)并考慮約束條件，可得如下具有懲罰性的綜合度量函數(shù)，記為（如圖1所示）。

因此，問題就轉(zhuǎn)化為求項(xiàng)目活動(dòng)所在組合模式的最大值，具體實(shí)踐中可以利用遺傳算法進(jìn)行搜索，找出多目標(biāo)情況下的最優(yōu)解。

3 遺傳算法模型

遺傳算法的基本理論是借鑒自然界生物從簡(jiǎn)單到復(fù)雜、低級(jí)到高級(jí)的優(yōu)勝劣汰、適者生存的進(jìn)化機(jī)制，其本質(zhì)是一種求解優(yōu)化問題的高效并行全局搜索方法。

遺傳算法的主要計(jì)算過(guò)程是：從隨機(jī)產(chǎn)生的一個(gè)初始種群開始，通過(guò)一些算子（選擇、交叉、變異）的作用，產(chǎn)生下一代種群，再以新產(chǎn)生的種群為出發(fā)點(diǎn)，重復(fù)上述過(guò)程，直到滿足結(jié)束準(zhǔn)則為止。算法主要流程可描述為：

（1）編碼。編碼規(guī)則：設(shè)項(xiàng)目活動(dòng)共有i個(gè)，則基因長(zhǎng)度為i位，基因位置序號(hào)代表項(xiàng)目活動(dòng)的序號(hào)，基因值代表項(xiàng)目活動(dòng)所選的組合模式。例如，某項(xiàng)目有8個(gè)項(xiàng)目活動(dòng)，則基因編碼長(zhǎng)度為8位，碼串23432311代表項(xiàng)目活動(dòng)T1選用組合模式2，項(xiàng)目活動(dòng)T2選用組合模式3，以此類推。

（2）產(chǎn)生初始種群。先隨機(jī)生成一定數(shù)目的個(gè)體，然后從中挑選出最好的個(gè)體加入到初始群體中，此過(guò)程不斷迭代，直到初始群體規(guī)模達(dá)到預(yù)期值。

（3）計(jì)算每個(gè)個(gè)體的適應(yīng)值。遺傳算法在進(jìn)化搜索中是以適應(yīng)度函數(shù)為依據(jù)的。如果問題帶有約束條件，則可采用懲罰函數(shù)將約束轉(zhuǎn)化為一個(gè)帶生存代價(jià)或懲罰因子的非約束問題。

對(duì)適應(yīng)度函數(shù)的另一個(gè)問題是定標(biāo)問題，即在遺傳算法初期，因超常個(gè)體所占比例太大，導(dǎo)致選擇過(guò)程過(guò)早收斂的早熟現(xiàn)象;另一方面，在進(jìn)化過(guò)程中，有可能會(huì)出現(xiàn)群體的平均適應(yīng)度已接近最佳個(gè)體適應(yīng)度，此時(shí)每個(gè)個(gè)體有著計(jì)劃相等的選擇機(jī)會(huì)，從而使有目標(biāo)的優(yōu)化過(guò)程趨向無(wú)目標(biāo)隨機(jī)漫游現(xiàn)象。對(duì)前者，須設(shè)法降低某些超常個(gè)體的競(jìng)爭(zhēng)力，而對(duì)后者則應(yīng)提高個(gè)體的競(jìng)爭(zhēng)力。針對(duì)這種現(xiàn)象可通干預(yù)個(gè)體適應(yīng)度函數(shù)來(lái)實(shí)現(xiàn)，就就是適應(yīng)度定標(biāo)技術(shù)。

本文中項(xiàng)目管理目標(biāo)的度量函數(shù)的構(gòu)造同時(shí)考慮了以上兩個(gè)問題。本算法計(jì)算適應(yīng)度的步驟為：首先根據(jù)數(shù)碼串譯碼，得到每個(gè)項(xiàng)目活動(dòng)的模式;然后根據(jù)項(xiàng)目活動(dòng)之間的邏輯關(guān)系和各模式下資源需求量和對(duì)應(yīng)工期，計(jì)算項(xiàng)目的關(guān)鍵路徑以及項(xiàng)目總工期、總成本和各資源平衡標(biāo)準(zhǔn)差;最后計(jì)算綜合評(píng)價(jià)函數(shù)F。

（4）選出N/2對(duì)個(gè)體進(jìn)入交配池，這里需要用到選擇算子，目的是把優(yōu)化的個(gè)體直接遺傳下一代或通過(guò)配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇算子有很多種，一般在實(shí)際應(yīng)用中，可以根據(jù)問題的求解特點(diǎn)采用幾種方法相結(jié)合的混合選擇機(jī)制，這比單獨(dú)使用某種選擇方法效果要好。另外，Gunter Rundolph關(guān)于遺傳算法收斂性問題有如下結(jié)論：

結(jié)論1：以變異概率p_m，交叉概率p_c，同時(shí)采用比例選擇法的標(biāo)準(zhǔn)遺傳算法不能收斂至全局最優(yōu)解。

結(jié)論2：具有如結(jié)論1的參數(shù)設(shè)置，且在選擇后保留當(dāng)前最優(yōu)解的遺產(chǎn)算法最終可收斂到全局最優(yōu)解。

結(jié)論3：具有如結(jié)論1的參數(shù)設(shè)置，且在選擇前保留當(dāng)前最優(yōu)解的遺產(chǎn)算法最終可收斂到全局最優(yōu)解。

基于以上的結(jié)論，本算法采用蒙特卡洛法和最佳個(gè)體保留法相結(jié)合的選擇算子。

（5）對(duì)每對(duì)個(gè)體依概率P_c執(zhí)行交叉操作產(chǎn)生兩個(gè)新個(gè)體，交叉算子是遺傳算法的核心算子，本算法中的交叉算子采用部分匹配交叉（PMX）法。

（6）對(duì)每對(duì)個(gè)體依概率P_m執(zhí)行變異操作，本算法中的變異算子采用基本變異算子。

（7）評(píng)價(jià)新產(chǎn)生的種群。

（8）判斷是否滿足終止準(zhǔn)則，當(dāng)群體中相同的個(gè)體數(shù)達(dá)到一定百分比時(shí)算法終止。

（9）輸出最優(yōu)解。

4 應(yīng)用實(shí)例

假設(shè)某項(xiàng)目有8個(gè)項(xiàng)目活動(dòng)，項(xiàng)目活動(dòng)的邏輯關(guān)系見圖2，其總工期不得超過(guò)30天，總成本不得超過(guò)130萬(wàn)元，項(xiàng)目中有3種資源，其總量分別為25個(gè)，30個(gè)，35個(gè)，三種資源的單價(jià)分別為1.2萬(wàn)元，1.5萬(wàn)元和1.萬(wàn)千元;間接成本按照公式：Co_i=0.2*D+1.5，ω₁、ω₂、ω₃分別為0.3，0.3，0.4;ω_工期、ω_成本、ω_資源平衡分別為0.6，0.35，0.05;每個(gè)項(xiàng)目活動(dòng)對(duì)應(yīng)的模式及其在該模式下資源的需求量和所需工期見表1。

按照上面所述模型及其算法，得到結(jié)果表2。

由表2可以看出，綜合度量的結(jié)果中成本、工期均在預(yù)計(jì)范圍內(nèi)，資源分配基本均衡，使用本文所構(gòu)造的模型在項(xiàng)目管理多目標(biāo)決策時(shí)能夠提供一個(gè)較優(yōu)解，用于指導(dǎo)項(xiàng)目管理者安排項(xiàng)目計(jì)劃。

5 結(jié)論與展望

本文首先提出項(xiàng)目管理多目標(biāo)決策所面臨的問題，經(jīng)過(guò)綜合分析建立數(shù)據(jù)模型和遺傳算法模型，并通過(guò)具體項(xiàng)目的實(shí)踐案例驗(yàn)證模型的可行性，用于指導(dǎo)項(xiàng)目管理者安排項(xiàng)目計(jì)劃。不過(guò)，本文還存在一些問題需要深入分析研究，例如現(xiàn)實(shí)工作中的資源成本比較復(fù)雜，與工期的關(guān)系也不一定是線性的，項(xiàng)目活動(dòng)之間的邏輯關(guān)系也可能對(duì)組合模式的工期、成本造成一定影響，后續(xù)將持續(xù)優(yōu)化上文所述的模型，改進(jìn)遺傳算法模型中適應(yīng)度函數(shù)的懲罰性因子，提高模型的客觀性和穩(wěn)定性。

參考文獻(xiàn)

[1]葉平.基于PERT/CPM的甘特圖應(yīng)用研究[J].浙江建筑，2011.

[2]邱菀華，楊敏.項(xiàng)目?jī)r(jià)值管理理論與實(shí)務(wù)[J].機(jī)械工業(yè)出版社，2007.

[3]徐澤水.部分權(quán)重信息下多目標(biāo)決策方法研究[J].系統(tǒng)工程理論與實(shí)踐，2002（01）.

[4]周瑞芬.改進(jìn)的遺傳算法[J].企業(yè)技術(shù)開發(fā)，2011（11）.

[5]闞峻嶺，李鋒剛.基于相關(guān)性分析和遺傳算法的屬性選擇[J].計(jì)算機(jī)工程，2010（36）：24.

[6]任江濤，黃煥宇，孫婧昊.印鑒，基于相關(guān)性分析及遺傳算法的高維數(shù)據(jù)特征選擇[J].計(jì)算機(jī)應(yīng)用，2006（26）：6.

[7]哈羅德.科茲納著，楊愛華，王麗珍，石一辰譯.項(xiàng)目管理（計(jì)劃、進(jìn)度和控制的系統(tǒng)方法）[M].電子工業(yè)出版社，2011.

[8]潘光欽.項(xiàng)目進(jìn)度管理中CPM、PERT和CCPM的比較研究[J].科學(xué)實(shí)踐，2014.