摘 要：在多項(xiàng)目資源沖突問題中，應(yīng)用標(biāo)準(zhǔn)遺傳算法時(shí)適應(yīng)度函數(shù)存在“早熟”的問題，遺傳算法對這類問題無法找到收斂的路?；谝陨蠁栴}，本文通過對遺傳算法進(jìn)行了適當(dāng)?shù)母倪M(jìn)，提出了一種改進(jìn)的遺傳算法，從適應(yīng)度函數(shù)、變異和選擇方式兩個(gè)角度對算法的改進(jìn)進(jìn)行了描述，改進(jìn)的遺傳算法將更能結(jié)合多項(xiàng)目沖突實(shí)際，能夠更好的解決多項(xiàng)目中有限資源的最佳配置問題，并將算法運(yùn)用到鹽城市電子政務(wù)建設(shè)項(xiàng)目中，驗(yàn)證了該算法的有效性。

關(guān)鍵詞 適應(yīng)度遺傳算法 多項(xiàng)目沖突 改進(jìn) 多項(xiàng)目管理 資源最優(yōu)化

一、引言

遺傳算法（Genetic Algorithm，GA）[1]是模擬自然界生物進(jìn)化過程與機(jī)制求解極值問題的一類自組織、自適應(yīng)的人工智能技術(shù)，能提供一個(gè)有效的解決優(yōu)化問題途徑和通用框架，是一種新的全局優(yōu)化搜索算法。文獻(xiàn)[2]指出傳統(tǒng)優(yōu)化算法是從單個(gè)初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。文獻(xiàn)[3]指出遺傳算法的適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點(diǎn)使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。

對于企業(yè)而言，同時(shí)運(yùn)行多個(gè)項(xiàng)目的能力需求越來越強(qiáng)烈，多項(xiàng)目管理面臨著眾多過去單一項(xiàng)目管理技術(shù)無法解決的各類難題。如果不能在整個(gè)組織的范圍內(nèi)對所有項(xiàng)目進(jìn)行統(tǒng)一有效的資源管理和分配，多個(gè)項(xiàng)目之間為得到有限的關(guān)鍵資源而發(fā)生沖突和爭論。當(dāng)前對多項(xiàng)目中的沖突管理并沒有較好的解決方法[4]。由于遺傳算法對所求解的優(yōu)化問題沒有太多的數(shù)學(xué)要求，只需利用目標(biāo)函數(shù)的取值信息，特別適合求解組合優(yōu)化問題[5]。因此，本文嘗試將遺傳算法應(yīng)用到多項(xiàng)目沖突管理上。

二、相關(guān)工作

（一）問題的描述

項(xiàng)目之間產(chǎn)生資源沖突是由資源的特性決定的，資源的特性具體表現(xiàn)在以下幾點(diǎn)：

1.資源是有價(jià)的。任何資源都是有價(jià)的，假若資源占用太多會(huì)造成資源閑置浪費(fèi)，或者資源沒有得到合理利用時(shí)，為實(shí)現(xiàn)項(xiàng)目目標(biāo)而付出的成本會(huì)很大。

2.資源是有限的[6]。任何資源都是有限的，因此不可能在任何時(shí)間、任何地點(diǎn)都能同時(shí)供多個(gè)項(xiàng)目使用。因此對多項(xiàng)目管理來說，若不能有機(jī)地配置和有效地平衡資源，必然會(huì)出現(xiàn)項(xiàng)目間為爭奪資源而爆發(fā)激烈沖突的現(xiàn)象。

在多項(xiàng)目管理時(shí)，核心的問題就在于如何實(shí)現(xiàn)有限資源的最佳配置，這往往需要進(jìn)行多項(xiàng)目的資源配置管理。 因?yàn)槌杀?、熟練水平、時(shí)間和競爭等因素，幾乎所有的項(xiàng)目都受到資源的約束。目前在項(xiàng)目管理過程中，大部分的討論主要集中在時(shí)間問題上，而沒有重視資源的可能性及其能力，以及他們與項(xiàng)目進(jìn)度的聯(lián)系。由于人員、儀器、機(jī)器、場地、設(shè)備和工具之間的搭配不合理，項(xiàng)目常常在關(guān)鍵時(shí)段發(fā)生延誤。此外，若管理不當(dāng)，人力成本也會(huì)隨項(xiàng)目推遲或項(xiàng)目成員加班加點(diǎn)而增加，而設(shè)備成本也可能會(huì)因提前租賃或在需要時(shí)得不到而增加。

（二）問題的解決方法

改進(jìn)遺傳算法（Improved Genetic Algorithm，IGA）中，改進(jìn)的三個(gè)算子通常是GA算法中的交叉操作，是隨機(jī)取兩個(gè)染色體進(jìn)行單點(diǎn)交叉操作（也可以用其他交叉操作，如多點(diǎn)交叉、數(shù)交叉等），即在以高適應(yīng)度為祖先的“家族”中取一點(diǎn)，但這種取法有其片面性。經(jīng)證明，簡單遺傳算法在任何情況下（交叉概率Pc，，變異概率Pm，任意初始化，任意交叉算子，任意適應(yīng)度函數(shù)）都是不收斂的，即不能搜索到全局最優(yōu)解。盡管人們證明了改進(jìn)的遺傳算法最終能收斂到最優(yōu)解，但收斂到最優(yōu)解所需時(shí)間可能是很長的，另外，早熟的問題也是遺傳算法中不可忽視的問題。

適應(yīng)度函數(shù)是評價(jià)個(gè)體適應(yīng)環(huán)境的能力，是選擇操作的依據(jù)，它的好壞能直接影響遺傳算法的性能。適應(yīng)度函數(shù)是由目標(biāo)函數(shù)轉(zhuǎn)換而成的。通常選擇的目的是保留更多高適應(yīng)度的個(gè)體，但是為了達(dá)到全局最優(yōu)，防止過早收斂，在選擇過程中要盡量保持個(gè)體的多樣性?；谶@種思想，為了使進(jìn)化前期原本函數(shù)值低的個(gè)體有更大的概率被選擇，保持種群多樣性防止“早熟”，而在后期可以轉(zhuǎn)成正常選擇操作，開始局部求精的搜索。本文將適應(yīng)度函數(shù)改進(jìn)為：

其中為上一代最優(yōu)解所對應(yīng)的函數(shù)值，t為當(dāng)前代數(shù)，T為預(yù)先設(shè)置好的最大迭代次數(shù)。

三、算法的描述與改進(jìn)

（一）算法的改進(jìn)

擇優(yōu)交叉在解決遭收斂問題時(shí)，通常習(xí)慣于采用限制優(yōu)良個(gè)體的競爭力（高適應(yīng)度的個(gè)體的復(fù)制份數(shù)）的方法，這樣無疑會(huì)降低算法的進(jìn)化速度，增大算法的時(shí)間復(fù)雜度，降低算法的性能。由于種群的基因多樣性可以減小陷入局最優(yōu)解的可能，而加快種群進(jìn)化速度又可以提高算法的整體性能。為了解決這一對矛盾，嘗試一種在不破壞種群的基因多樣性的前提下加快種群的進(jìn)化速度的方法，這一方法描述如下：在隨機(jī)選擇出父本和母本以后，按照交叉方法（單點(diǎn)交叉、多點(diǎn)交叉和一致交叉）進(jìn)行 次交叉，產(chǎn)生2 個(gè)個(gè)體，再從這2 個(gè)個(gè)體中挑選出最優(yōu)的的兩個(gè)個(gè)體加入新的種群中。這樣既保存了父本和母本的基因，又在進(jìn)化的過程中大大地提高了種群中個(gè)體的平均性能。

基于以上的分析，改進(jìn)的遺傳算法描述如下：

Step 1.在初始種群中，對所有的個(gè)體按其適應(yīng)度大小進(jìn)行排序，然后計(jì)算個(gè)體的支持度和置信度；

Step 2.按一定的比例復(fù)制（即將當(dāng)前種群中適應(yīng)度最高的兩個(gè)個(gè)體結(jié)構(gòu)完整復(fù)制到待配種群中）；

Step 3.按個(gè)體所處的位置確定其變異概率并變異；按優(yōu)良個(gè)體復(fù)制4份，劣質(zhì)個(gè)體不復(fù)制的原則復(fù)制個(gè)體；

Step 4.從復(fù)制組中隨機(jī)選擇兩個(gè)個(gè)體，對這兩個(gè)個(gè)體進(jìn)行多次交叉，從所得到的結(jié)果中選擇一個(gè)最優(yōu)個(gè)體存入新種群；

Step 5.若滿足結(jié)束條件，則停止，不然，跳轉(zhuǎn)第（1）步，直至找到所有符合條件的規(guī)則。

改進(jìn)的遺傳算法相對于簡單遺傳算法的優(yōu)點(diǎn)是在各代的每一次演化中，子代總是保留了父代中最好的個(gè)體，以在“高適應(yīng)度模式為祖先的家族方向”搜索出更好的樣本，從而保證最終可以搜索到全局最優(yōu)解。

（二）算法的實(shí)驗(yàn)測試

在下面的實(shí)驗(yàn)中，我們使用兩個(gè)經(jīng)典的函數(shù)來進(jìn)行測試，將改進(jìn)遺傳算法（IGA）與標(biāo)準(zhǔn)遺傳算法（GA）進(jìn)行比較，兩個(gè)函數(shù)在其定義域內(nèi)都只有一個(gè)全局最小點(diǎn)f（0，0）=0。兩個(gè)函數(shù)分別為：

測試函數(shù)1：

測試函數(shù)2：

本文分別采用改進(jìn)遺傳算法和標(biāo)準(zhǔn)遺傳算法對測試函數(shù)進(jìn)行了測試，對比兩種算法的平均值、最優(yōu)解和收斂性。

測試是在matlab環(huán)境下進(jìn)行的，分別運(yùn)行了30次，種群規(guī)模為100，進(jìn)化代數(shù)為80代。

測試函數(shù)1，設(shè)置精度為 1e-5 時(shí)，將每個(gè)算法獨(dú)立地運(yùn)行30 次的結(jié)果如下表：

表1 測試函數(shù)1結(jié)果對比分析

測試函數(shù)2，精度要求設(shè)置為較高1e-20，將每個(gè)算法獨(dú)立地運(yùn)行30 次的結(jié)果如下表：

表2 測試函數(shù)2結(jié)果對比分析

從對比結(jié)果可以看出，當(dāng)精度要求較低時(shí)，IGA算法和 GA算法的運(yùn)算時(shí)間相當(dāng)，結(jié)果比GA的精度高；當(dāng)精度要求較高時(shí)，IGA算法運(yùn)算時(shí)間高于 GA算法，而結(jié)果遠(yuǎn)遠(yuǎn)優(yōu)于 GA算法。

GA 算法和 IGA 算法都是以一定概率接近全局最優(yōu)解，而從對比結(jié)果可以看出，IGA算法接近全局最優(yōu)解的概率較大，陷入局部極值的概率很小。

四、結(jié)束語

本文對標(biāo)準(zhǔn)遺傳算法進(jìn)行了改進(jìn)，提出一種改進(jìn)遺傳算法對多項(xiàng)目資源沖突問題進(jìn)行研究。這種改進(jìn)遺傳算法更加適用于多項(xiàng)目資源沖突問題，提高了初始解的質(zhì)量，并保證了初始解的多樣性。同時(shí)，對遺傳算法的交叉操作和變異操作進(jìn)行了改進(jìn)可以避免產(chǎn)生非法個(gè)體，改進(jìn)的變異操作加強(qiáng)了算法的搜索能力，提高了算法的搜索效率。

參考文獻(xiàn)：

[1]Engwalla M， Jerbrantb A. The resource allocation syndrome： The prime challenge of multi-project management [J].International Journal of Project Management， 2003， 21：400～420

[2]ZhengguoWang，HongweiWang，Weihua Yi.Heuristic Approaches for The Time-Dependent Vehicle.Routing Problem with Backhauls. Advances in Systems Science and Applications， 2005，Vol.5，（4），581～58

[3]R. S. S. Guizzardi， A. Perini， V. Dignum， G.Wagner. Towards an Integrated Methodology to Develop KM Solutions with the Support of Agents[J]. In Proceedings of the international Conference on Integration of knowledge Intensive Multi-Agent Systems， Waltham， Massachusetts， April/2005

[4]楊雪松，胡昊.基于關(guān)鍵鏈方法的多項(xiàng)目管理[J]，工業(yè)工程與管理，2005，10（2）：48～52

[5]壽涌毅.資源約束下多項(xiàng)目調(diào)度的迭代算法[[J].浙江大學(xué)學(xué)報(bào)（工學(xué)版）2007， 38（8）： 1095～1099

[6]王振祿和蔡慧林.資源受限項(xiàng)目調(diào)度中基于鄰域搜索的混合遺傳算法[J].蘭州交通大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2008， 24 （3）：12～14

作者簡介：

王帥（1977），男，天津市人，碩士，研究方向：軟件工程，項(xiàng)目管理，網(wǎng)絡(luò)通信