基于遺傳算法的汽輪機(jī)項(xiàng)目計(jì)劃研究

洪超（上海電氣電站設(shè)備有限公司上海汽輪機(jī)廠，上海 200240）

基于遺傳算法的汽輪機(jī)項(xiàng)目計(jì)劃研究

洪超
（上海電氣電站設(shè)備有限公司上海汽輪機(jī)廠，上海 200240）

交貨期已成為企業(yè)繼關(guān)鍵技術(shù)之后的又一核心競(jìng)爭(zhēng)力。因此通過合理安排排產(chǎn)計(jì)劃變得尤其重要。本文系統(tǒng)闡述了基于遺傳算法的方法論，并結(jié)合汽輪機(jī)行業(yè)特點(diǎn)，尋求出復(fù)雜產(chǎn)品的全生命周期項(xiàng)目的計(jì)劃，通過MARLAB多次迭代運(yùn)算，能迅速得出滿足資源約束的工期最短的項(xiàng)目調(diào)度計(jì)劃。有效地解決了企業(yè)項(xiàng)目調(diào)度的優(yōu)化問題，值得在企業(yè)級(jí)項(xiàng)目管理中運(yùn)用。

項(xiàng)目計(jì)劃；遺傳算法；RCPSP問題；汽輪機(jī)

1　前言

隨著“十三五”“五大發(fā)展”論述將綠色發(fā)展理念放在更突出位置、社會(huì)對(duì)霧霾國(guó)家為降低經(jīng)濟(jì)下行壓力，加大對(duì)固定資產(chǎn)投入；本著電力是經(jīng)濟(jì)發(fā)展“先行官”理念，大功率、低熱耗的發(fā)電機(jī)組需求疊加式增長(zhǎng)。汽輪機(jī)廠時(shí)隔數(shù)十年，再次迎來在手訂單數(shù)量的井噴，2016年達(dá)到歷史極值。汽輪機(jī)設(shè)計(jì)采購(gòu)制造是系統(tǒng)工程，具有明顯的“私人訂制”項(xiàng)目化特征。當(dāng)下，產(chǎn)品的交貨期作為除技術(shù)外，產(chǎn)品的核心競(jìng)爭(zhēng)力，做好執(zhí)行計(jì)劃，將成為企業(yè)提升管理的又一抓手。

作為裝備制造業(yè)典型代表：汽輪機(jī)其全生命周期，可分解出：招投標(biāo)、方案評(píng)審、詳細(xì)設(shè)計(jì)、采購(gòu)、制造、裝配、成套、安裝、服務(wù)等階段。每階段都有一些特定的相互制約具體活動(dòng)組成，這些邏輯網(wǎng)狀活動(dòng)，將占用不同的資源。一個(gè)最優(yōu)的可執(zhí)行計(jì)劃，將成為企業(yè)在產(chǎn)能高位時(shí)期是否能夠順利組織日常經(jīng)營(yíng)活動(dòng)的基礎(chǔ)。提供基準(zhǔn)計(jì)劃可成為后續(xù)計(jì)劃的基礎(chǔ)?？梢哉f，合理的計(jì)劃就是一切經(jīng)營(yíng)活動(dòng)的指揮棒。

傳統(tǒng)項(xiàng)目計(jì)劃獲取方法：關(guān)鍵路徑法、計(jì)劃評(píng)審技術(shù)法，都未考慮資源在項(xiàng)目執(zhí)行過程中的約束問題。顯然，這兩種方法，對(duì)汽輪機(jī)這種大型項(xiàng)目，略顯狹隘。因此需要謀求新的解決方案。實(shí)踐證明：為解決這類問題，可以采用資源約束項(xiàng)目（Resource Constrained Project Scheduling Problem，RCPSP）數(shù)學(xué)工具來解決，且相當(dāng)有效。

2　優(yōu)化方向及其數(shù)學(xué)依據(jù)

在RCPSP問題中，數(shù)學(xué)模型的搭建是為滿足目標(biāo)函數(shù)。這些函數(shù)按優(yōu)化方向，分為時(shí)間類、資源類、財(cái)務(wù)類、質(zhì)量類等。其中，時(shí)間類和資源類的目標(biāo)函數(shù)最常見。在實(shí)際工程問題中，關(guān)于資源和工期的優(yōu)化方向分兩方面：一是資源條件有限的情況下，力求通過合理計(jì)劃安排達(dá)到工期最??；二是在規(guī)定的較為寬松的工期下，力求通過合理安排，達(dá)到系統(tǒng)對(duì)各類資源平衡的需求，以達(dá)到承載項(xiàng)目的系統(tǒng)沖擊最小。前者更適合市場(chǎng)化運(yùn)作的企業(yè)單位，后者則更適合計(jì)劃需求穩(wěn)定的事業(yè)單位。

由于RCPSP問題已被證實(shí)為NP－HARD問題，因此，在數(shù)學(xué)上精確求解很困難。針對(duì)汽輪機(jī)這樣的大型項(xiàng)目，活動(dòng)較多，精確求解將變得不切實(shí)際。因此一些元啟發(fā)式求解算法（metaheuristic）被提出，并成為當(dāng)下項(xiàng)目管理計(jì)劃體系研究的熱點(diǎn)領(lǐng)域。

目前流行的元啟發(fā)式算法有：參考基因理論，模擬種群的遺傳算法；運(yùn)用物理現(xiàn)象，模擬物質(zhì)冷卻的模擬退火算法；參照社會(huì)行為學(xué)中的禁忌概念，避免局部最優(yōu)而忽略整體最優(yōu)的禁忌搜索算法；模擬生物昆蟲學(xué)，螞蟻利用信息素尋找蟻穴和食物源，體現(xiàn)群體智慧的蟻群優(yōu)化算法等等；目前在RCPSP問題

3　遺傳算法理論依據(jù)

項(xiàng)目管理中當(dāng)隨探討對(duì)象的擴(kuò)大（數(shù)量、復(fù)雜度的提升），考慮因素的增加，針對(duì)組合優(yōu)化、調(diào)度問題的搜索解空間也急劇增加。甚至在目前性能的計(jì)算機(jī)上，都無法通過枚舉法求解。同時(shí)在搭建數(shù)學(xué)模型時(shí)，力求簡(jiǎn)化，但所得解與實(shí)際現(xiàn)實(shí)情況相差甚遠(yuǎn)。模型復(fù)雜，雖貼合實(shí)際，但卻造成了求解的困難。精確求最優(yōu)解幾乎不可能。針對(duì)這類問題，學(xué)者們通過研究的主要方向?yàn)橥硕笃浯蔚臐M意解。遺傳算法是尋求滿意解的最佳工具。實(shí)踐證明，遺傳算法對(duì)組合優(yōu)化NP-Hard問題非常有效。遺傳算法（Genetic Algorithms GA）是仿制于生物遺傳、進(jìn)化進(jìn)程。他從本質(zhì)上說是一種使用范圍很廣的全局概率搜索算法。最初由Michigan大學(xué)的Holland教授提出。其核心思想是基于“自然選擇說”，在算法中模擬引入優(yōu)勝劣汰、適者生存的進(jìn)化原理，通過一系列技術(shù)手段，將目標(biāo)值，朝預(yù)定方向進(jìn)行漸進(jìn)演化。

4　RCPSP數(shù)學(xué)模型描述

設(shè)有項(xiàng)目N有ni（i=1，2，3，…，m）個(gè)活動(dòng)，項(xiàng)目各活動(dòng)消耗r種資源，要求同時(shí)滿足緊前關(guān)系和每時(shí)刻資源雙重限制條件。假設(shè)：

STi和di為第i活動(dòng)的時(shí)間開始時(shí)間和活動(dòng)執(zhí)行時(shí)間；

Rk為資源K在某一時(shí)間段的系統(tǒng)組織能夠提供的總量；Rik為第i活動(dòng)在單位時(shí)間內(nèi)對(duì)K中資源的需求量；Rikt為時(shí)刻t（t=1，2，3，…，T）處對(duì)K種資源的需求量。Pi為i個(gè)活動(dòng)的緊前活動(dòng)集合。

STi≤t≤STi+di

t取其他數(shù)值

s.t.STi≥STh+di其中h∈Pi，?i；Rikt≤Rk其中?k，t，i；

5　解決問題整體方案設(shè)計(jì)

5.1染色體編碼

染色體編碼是將問題數(shù)學(xué)化后啟用遺傳算法的基礎(chǔ)。編碼是將問題的可行解從其解空間轉(zhuǎn)換到遺傳算法能處理的搜索空間。針對(duì)項(xiàng)目管理的遺傳算法，目前文獻(xiàn)中主要存在五類編碼設(shè)計(jì)方案：任務(wù)列表表達(dá)法（Activity List Representation，ALR）；任務(wù)優(yōu)先規(guī)則表達(dá)法（Priority Rule Representation，PRR）；隨機(jī)鍵表達(dá)法（Random Key Representation，RKP）；移位向量表達(dá)法（Shift Vector Representation，SVR）；直接表達(dá)法（Direct Representation，DR）。其中，任務(wù)列表表達(dá)法，由于內(nèi)嵌活動(dòng)的緊前關(guān)系，因此也被數(shù)值實(shí)驗(yàn)證明為一種有效的表達(dá)方式，因此是目前運(yùn)用遺傳算法解決RCPSP問題的最常用的染色體編碼方式。

5.2適應(yīng)度函數(shù)

工期最短問題是求解目標(biāo)函數(shù)的最小數(shù)值。因此項(xiàng)目最后一個(gè)活動(dòng)的結(jié)束時(shí)間就是目標(biāo)值，須將原始的目標(biāo)值轉(zhuǎn)換為適應(yīng)值，以確保優(yōu)秀個(gè)體應(yīng)具有更大的適應(yīng)值。所以應(yīng)對(duì)目標(biāo)函數(shù)做適應(yīng)度尺度變化，假設(shè)vk是種群第k個(gè)染色體。f（vk）是vk的活動(dòng)最短時(shí)間，即目標(biāo)函數(shù)。g（vk）是vk的適應(yīng)度函數(shù)，fmax和fmin和分別是當(dāng)代種群中最大目標(biāo)和最小目標(biāo)值，即項(xiàng)目的持續(xù)時(shí)間，變化方法：其中，ε∈（0，1）

ε的存在是為了防止fmax=fmin情況的出現(xiàn)，導(dǎo)致g（vk）無解。

5.3染色體初始化獲取初始種群

初始種群的定義是一個(gè)可行的解，也就是一個(gè)選擇一個(gè)多項(xiàng)目可行的計(jì)劃方案的表述方式。具體方法是按照從左到右的順序依次確定染色體各個(gè)基因位對(duì)應(yīng)的活動(dòng)序號(hào)。首先定義可調(diào)度活動(dòng)集合φ，即所有緊前活動(dòng)已被安排在基因位上的活動(dòng)序號(hào)集合。每個(gè)項(xiàng)目開始活動(dòng)的序號(hào)，組成可調(diào)度的活動(dòng)集合φ，每次從 φ中隨機(jī)選擇項(xiàng)目i，活動(dòng) j，并且將其序號(hào) i，j安排在基因位上，同事將活動(dòng)從集合 φ中移除，并且修正0-1方陣A=aij第i行j列元素值。如：aij=1，修正為 aij=0，當(dāng)0-1方陣aij=0，則說明所有的活動(dòng)，都被基因序列表述出來。

5.4標(biāo)準(zhǔn)遺傳操作

選擇（Selection）——模擬自然選擇

選擇也稱復(fù)制，是在群體中選擇更好個(gè)體產(chǎn)生新的群體過程。體現(xiàn)自然界中優(yōu)勝劣汰的思想選擇算子用來對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰過濾和篩選，好的選擇算子，可把適應(yīng)度更高個(gè)體，以更高的概率遺傳到下一代。通過多代選擇，使得解不斷接近最優(yōu)解。選擇常用的有比例選擇，精英選擇，聯(lián)賽選擇，排序選擇。經(jīng)典遺傳算法常常采用比例選擇，每個(gè)個(gè)體進(jìn)入下一代的概率就是他適應(yīng)度與整個(gè)種群中個(gè)體使用度的比例。以此來表示該個(gè)體在選擇過程中被選擇作為父本的概率。

交叉（Crossover）——模擬雜交繁殖

交叉是將兩父本的信息進(jìn)行交換，以產(chǎn)生新個(gè)體，其作用是將優(yōu)良的解，傳給下一代。具體操作為：將代表解的有序數(shù)對(duì)，隨機(jī)選擇一個(gè)交叉位置。根據(jù)確定的交叉概率Pc，執(zhí)行交叉操作。在交叉位置交換彼此對(duì)應(yīng)部分的數(shù)據(jù)片段，從而形成新的個(gè)體。

變異（mutation）——模擬突變

變異是模擬基因突變的過程，在父本產(chǎn)生下代染色體時(shí)，因某一些因素，出現(xiàn)了復(fù)制差錯(cuò)，從而表現(xiàn)出新生物特性。模仿此法，遺傳算法通過變異其目的是為了跳脫出目前收斂，防止解集過早地收斂于局部最優(yōu)解，而無法獲得全局最優(yōu)解。

遺傳算法的基本流程是：首先對(duì)優(yōu)化問題的可行解進(jìn)行編碼（EnCoding，EC）形成染色體（Chromosome，C），構(gòu)造出包含了系統(tǒng)優(yōu)化的目標(biāo)合適的適值函數(shù)（Fitness Function，F(xiàn)F）作為評(píng)價(jià)指標(biāo)。對(duì)種群中的個(gè)體用適值函數(shù)進(jìn)行評(píng)估（Evaluation E）進(jìn)行后進(jìn)行選擇（Seletion，S），將適應(yīng)值高的染色體獲得更高的保留生存概率，實(shí)在優(yōu)勝劣汰。得到的新染色體后，經(jīng)復(fù)制、交叉、變異等形成子染色體，再用適值函數(shù)，進(jìn)行選擇，再次獲得更優(yōu)秀的染色體，這樣循環(huán)，新群體更優(yōu)于上一代同時(shí)也繼承了上一代的信息，周而復(fù)始，種群中個(gè)體的個(gè)體（解）不斷地提高適應(yīng)度，直到滿足一定的條件（譬如：預(yù)先設(shè)定的循環(huán)代數(shù)），在合理的計(jì)算時(shí)間內(nèi)，得到一可接受的最優(yōu)解。（詳見圖1）。

6　試驗(yàn)驗(yàn)證

6.1WBS活動(dòng)結(jié)構(gòu)分解和活動(dòng)、資源的預(yù)估

在實(shí)際工程項(xiàng)目運(yùn)用遺傳算法，首先需對(duì)項(xiàng)目活動(dòng)的前后邏輯順序進(jìn)行判別，生成一任務(wù)列表，同時(shí)，汽輪機(jī)的研發(fā)設(shè)計(jì)制造活動(dòng)的全生命周期，按模塊來分解大致涵蓋：期初招投標(biāo)管理、研發(fā)設(shè)計(jì)、采購(gòu)毛坯、精加工、成套、發(fā)運(yùn)、現(xiàn)場(chǎng)安裝、聯(lián)調(diào)168小時(shí)并網(wǎng)發(fā)電等階段，這些特定的階段又有一些細(xì)分的活動(dòng)，如研發(fā)設(shè)計(jì)往往細(xì)分成方案設(shè)計(jì)、詳細(xì)設(shè)計(jì)、設(shè)計(jì)收尾及服務(wù)等。而設(shè)計(jì)收尾又穿插進(jìn)入了制造加工。因此這項(xiàng)系統(tǒng)工程龐大，活動(dòng)數(shù)量繁多，持續(xù)時(shí)間長(zhǎng)，占用資源多。通過列表將活動(dòng)和活動(dòng)時(shí)間進(jìn)行羅列，并形成邏輯圖（圖 2），體現(xiàn)活動(dòng)前后邏輯，同時(shí)通過德爾菲法得出各項(xiàng)活動(dòng)所需要的時(shí)間和所需要的資源，形成報(bào)表。

圖1　遺傳算法解決流程

圖2　汽輪機(jī)全生命周期活動(dòng)示意

6.2 本文通過MATLAB實(shí)現(xiàn)上述的程序

硬件環(huán)境為普通工作站，軟件環(huán)境為基于Windows 10的MATLAB 2015；通過編寫程序，獲得進(jìn)化代數(shù)和最優(yōu)解（資源限定下工期最短，見圖3）。

當(dāng)人為設(shè)置循環(huán)代數(shù)為500代后自動(dòng)結(jié)束程序循環(huán)。通過運(yùn)算，發(fā)現(xiàn)工期最優(yōu)解在第23次迭代后，完成收斂，達(dá)到最優(yōu)解，迭代效率很高。

7　結(jié)語

在經(jīng)濟(jì)新常態(tài)下，充分利用現(xiàn)有企業(yè)資源，在不加大資源投入的情況下，縮短在制品流轉(zhuǎn)周期，在更短時(shí)間內(nèi)將產(chǎn)品推向市場(chǎng)，做到及時(shí)響應(yīng)，已成為飽和電力市場(chǎng)搶奪市場(chǎng)訂單的重要手段之一。本文運(yùn)用遺傳算法，解決了資源有限條件下，項(xiàng)目的活動(dòng)時(shí)間最短化。同時(shí)通過合理的數(shù)學(xué)假設(shè)和簡(jiǎn)化，最終獲得了一個(gè)可行解，最后通過MATLAB運(yùn)算后，得到驗(yàn)證。

主要參考文獻(xiàn)

［1］周明，孫樹棟.遺傳算法原理及應(yīng)用［M］.北京：國(guó)防工業(yè)出版社，1999.

［2］［日］玄關(guān)男，程潤(rùn)偉.遺傳算法與工程優(yōu)化［M］.于杰，周根貴，譯.北京：清華大學(xué)出版社，2005.

［3］壽永毅.資源受限多項(xiàng)目調(diào)度的模型與方法［M］.杭州：浙江大學(xué)出版社，2010.

［4］史峰，王輝，等.MATLAB智能算法30個(gè)案例分析［M］.北京：航空航天大學(xué)出版社，2011.

［5］雷英杰.Matlab遺傳算法工具箱及應(yīng)用［M］.西安：電子科技大學(xué)出版社，2006.

10.3969/j.issn.1673-0194.2016.17.039

TP312

A

1673-0194（2016）17-0083-04

2016-05-10

洪超（1984－），男，浙江奉化人，工程師，上海交通大學(xué)在職研究生，主要研究方向：企業(yè)級(jí)項(xiàng)目管理。中，運(yùn)用最廣泛的是：遺傳算法。且被證明是一種最有效的求解算法，其提供了標(biāo)準(zhǔn)的求解框架，尤其對(duì)項(xiàng)目調(diào)度問題一般都有比較里理想的求解效果。