基于適應度函數(shù)改進的IGA在多項目沖突中的應用

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

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

一、引言

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

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

二、相關(guān)工作

（一）問題的描述

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

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

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

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

（二）問題的解決方法

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

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

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

三、算法的描述與改進

（一）算法的改進

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

基于以上的分析，改進的遺傳算法描述如下：

Step 1.在初始種群中，對所有的個體按其適應度大小進行排序，然后計算個體的支持度和置信度；

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

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

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

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

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

（二）算法的實驗測試

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

測試函數(shù)1：

測試函數(shù)2：

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

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

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

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

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

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

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

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

四、結(jié)束語

本文對標準遺傳算法進行了改進，提出一種改進遺傳算法對多項目資源沖突問題進行研究。這種改進遺傳算法更加適用于多項目資源沖突問題，提高了初始解的質(zhì)量，并保證了初始解的多樣性。同時，對遺傳算法的交叉操作和變異操作進行了改進可以避免產(chǎ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)鍵鏈方法的多項目管理[J]，工業(yè)工程與管理，2005，10（2）：48～52

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

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

作者簡介：

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