融入邏輯關(guān)系的項(xiàng)目調(diào)度遺傳算法

劉 堯,宋元斌,李云祥

(上海交通大學(xué) 船舶海洋與建筑工程學(xué)院,上海 200240)

0 概述

隨著工程項(xiàng)目規(guī)模的不斷擴(kuò)大,解決施工進(jìn)度計(jì)劃的快速編制問(wèn)題變得越發(fā)重要。施工進(jìn)度計(jì)劃的快速編制主要包括兩項(xiàng)關(guān)鍵技術(shù),即施工順序的表述模型和與之對(duì)應(yīng)的求解算法。施工順序知識(shí)用于推導(dǎo)進(jìn)度計(jì)劃編制中施工活動(dòng)的先后順序,為工程模型到數(shù)學(xué)模型的轉(zhuǎn)換提供依據(jù);調(diào)度模型的求解是一種典型的NP難問(wèn)題,根據(jù)不同的調(diào)度模型有不同的求解方法。

復(fù)雜施工排序方案中的表述問(wèn)題主要分為兩類。第一類為施工活動(dòng)的時(shí)間順序表述問(wèn)題,主要用于推理進(jìn)度計(jì)劃中的施工活動(dòng)先后順序。文獻(xiàn)[1]用時(shí)間區(qū)間描述活動(dòng)的持續(xù)狀態(tài),并定義了2個(gè)時(shí)間區(qū)間之間的13種關(guān)系。后續(xù)研究者在其基礎(chǔ)上擴(kuò)展引入了最大時(shí)間間隔[2]、負(fù)時(shí)間間隔[3]和時(shí)間約束柔性[4]等概念,解決了施工活動(dòng)順序表達(dá)上的大部分難題。第二類為施工計(jì)劃中的邏輯關(guān)系表述問(wèn)題,即施工活動(dòng)與時(shí)間關(guān)系間的邏輯關(guān)系,許多學(xué)者對(duì)其進(jìn)行了研究。文獻(xiàn)[5]使用Disjoint描述2個(gè)時(shí)間關(guān)系之間存在“Or”邏輯關(guān)系。文獻(xiàn)[6]用包含(→)、等價(jià)(?)和異或(?)3個(gè)邏輯運(yùn)算符來(lái)描述邏輯關(guān)系。文獻(xiàn)[7]提出活動(dòng)之間的互斥和共存關(guān)系,用以描述備擇施工方案之間的關(guān)系。

研究者在調(diào)度模型的算法設(shè)計(jì)中,會(huì)依據(jù)時(shí)間約束[8]、資源約束[9]等條件改進(jìn)算法,也會(huì)直接使用調(diào)度工具[10]進(jìn)行求解。文獻(xiàn)[11]在電網(wǎng)規(guī)劃上使用布爾變量來(lái)簡(jiǎn)單表示區(qū)域電網(wǎng)投運(yùn)與否的狀態(tài),從而計(jì)算電網(wǎng)的最小成本。文獻(xiàn)[12]將傳統(tǒng)遺傳算法與模擬退火算法相結(jié)合來(lái)解決Web服務(wù)組合質(zhì)量?jī)?yōu)化問(wèn)題。文獻(xiàn)[13]用改進(jìn)的遺傳算法對(duì)BP神經(jīng)網(wǎng)絡(luò)的初始權(quán)重進(jìn)行賦值,用以加快神經(jīng)網(wǎng)絡(luò)的收斂速率。上述規(guī)劃模型采用互相獨(dú)立的布爾變量表示簡(jiǎn)單邏輯關(guān)系進(jìn)行遺傳算法的改進(jìn)設(shè)計(jì),均未解決復(fù)雜邏輯關(guān)系的計(jì)算難題。

求解調(diào)度模型主要分為精確式算法和啟發(fā)式算法。精確式算法受線性規(guī)劃求解器容許決策變量數(shù)目的限制,在求解中小規(guī)模的調(diào)度問(wèn)題時(shí)具有速度快、結(jié)果精確的優(yōu)點(diǎn),但在求解帶有大量邏輯關(guān)系的超大型復(fù)雜調(diào)度模型時(shí),卻表現(xiàn)出時(shí)間效率低下的問(wèn)題,不能滿足一些規(guī)模龐大的優(yōu)化調(diào)度問(wèn)題求解需求。啟發(fā)式算法主要用于快速有效地求解大規(guī)模問(wèn)題的較優(yōu)解。因此,采用啟發(fā)式算法求解帶有較多邏輯關(guān)系的復(fù)雜調(diào)度問(wèn)題是合理的選擇。

遺傳算法是一種經(jīng)典的啟發(fā)式算法,被廣泛應(yīng)用于工程計(jì)劃,如施工項(xiàng)目[14]、流水作業(yè)[15]、高速公路建設(shè)[16]等。為了滿足特定領(lǐng)域的需求,研究者也會(huì)對(duì)遺傳算法進(jìn)行相應(yīng)改進(jìn)。文獻(xiàn)[17]通過(guò)改進(jìn)交叉算子,解決了含有多個(gè)目標(biāo)的最優(yōu)化模型求解問(wèn)題。文獻(xiàn)[18]在處理裝配式建筑構(gòu)件運(yùn)輸問(wèn)題上,加入運(yùn)輸節(jié)點(diǎn)的權(quán)重計(jì)算,加快種群的收斂速度。由于上述算法沒(méi)有考慮工程模型中的備擇和依存關(guān)系,因此難以描述復(fù)雜調(diào)度模型中的邏輯關(guān)系。

本文基于文獻(xiàn)[6]的邏輯運(yùn)算符,增加了邏輯符XOR、XNOR和IF-THEN來(lái)表示活動(dòng)之間和時(shí)間關(guān)系之間的邏輯關(guān)系,編程實(shí)現(xiàn)復(fù)雜調(diào)度模型到混合整數(shù)規(guī)劃模型[19]的自動(dòng)轉(zhuǎn)換,并提出一種解決該問(wèn)題的改進(jìn)遺傳算法,采取基于工程邏輯關(guān)系布爾變量劃分的順序編碼方式,將染色體劃分為獨(dú)立變量和半獨(dú)立變量編碼基因段,從而解決帶有大量依賴邏輯關(guān)系的調(diào)度模型求解問(wèn)題。

1 調(diào)度模型中邏輯關(guān)系的表述

本節(jié)在探究時(shí)間關(guān)系之間的互斥(XOR)與共存(XNOR)邏輯關(guān)系基礎(chǔ)上,提出用“IF-THEN”表示活動(dòng)或時(shí)間關(guān)系之間存在的依賴邏輯關(guān)系,同時(shí)探究將其轉(zhuǎn)化進(jìn)入混合整數(shù)線性規(guī)劃的數(shù)學(xué)理論方法。文中符號(hào)說(shuō)明如表1所示。

表1 符號(hào)定義說(shuō)明

為說(shuō)明包含時(shí)間關(guān)系的邏輯關(guān)系,本文引入布爾決策變量ER(i,j)用以描述時(shí)間關(guān)系之間的邏輯關(guān)系,下標(biāo)中R表示該變量為時(shí)間關(guān)系的布爾變量,(i,j)表示此為描述活動(dòng)i和活動(dòng)j的時(shí)間關(guān)系。如果一個(gè)時(shí)間關(guān)系R(i,j)被選擇執(zhí)行,則對(duì)應(yīng)的決策變量ER(i,j)被賦值為1,否則賦值為0。

(1)

邏輯關(guān)系的線性約束表達(dá)如表2所示。

表2 邏輯關(guān)系與線性約束的關(guān)系

Table 2 Relationship between logical relations and linear constraints

邏輯關(guān)系線性約束活動(dòng)i與j為互斥關(guān)系Ei + Ej = 1活動(dòng)i與j為共存關(guān)系Ei = Ej活動(dòng)i與j為依賴關(guān)系Ei ≤ Ej活動(dòng)i與時(shí)間關(guān)系R(j,k)為互斥關(guān)系Ei + ER(j,k) = 1活動(dòng)i與時(shí)間關(guān)系R(j,k)為共存關(guān)系Ei = ER(j,k)活動(dòng)i與時(shí)間關(guān)系R(j,k)為依賴關(guān)系Ei ≤ ER(j,k)時(shí)間關(guān)系R(i,j)與R(k,l)為互斥關(guān)系ER(i,j) + ER(k,l) = 1時(shí)間關(guān)系R(i,j)與R(k,l)為共存關(guān)系ER(i,j) = ER(k,l)時(shí)間關(guān)系R(i,j)與R(k,l)為依賴關(guān)系ER(i,j) ≤ ER(k,l)

2 復(fù)雜調(diào)度模型的建立與求解

為克服精確式算法求解帶有大量邏輯關(guān)系的超大型工程存在的不足,本文設(shè)計(jì)了基于布爾變量劃分的順序編碼方式,在遺傳算法中對(duì)違反約束規(guī)則的個(gè)體進(jìn)行了修正。

2.1 調(diào)度模型

施工調(diào)度計(jì)劃最主要的任務(wù)之一是確定最短工期下的施工排序方案。本文的調(diào)度模型優(yōu)化目標(biāo)使項(xiàng)目結(jié)束時(shí)間FP最小。計(jì)算工期的混合整數(shù)線性規(guī)劃模型如下:

目標(biāo)函數(shù)如式(2)所示。

MinZ=FP

(2)

約束條件如式(3)～式(17)所示。

a′×Si-a′×Sj+Di+L(i,j)≤0

?R(i,j),1≤i≤n,1≤j≤n

(3)

a′×Si-a′×Sj+EAi×Di+L(i,j)≤0

?R(i,j),1≤i≤n,1≤j≤n

(4)

a′×Si-a′×Sj+Di+L(i,j)-M(1-ER(i,j))≤0

?R(i,j),1≤i≤n,1≤j≤n

(5)

a′×Si-a′×Sj+EiA×Di+L(i,j)-

M(1-ER(i,j))≤0,?R(i,j),1≤i,j≤n

(6)

Si≥0,i=1,2,…,n

(7)

Si+Di≤Fp,i=1,2,…,n

(8)

Ei+Ej=1,iXORj

?i,j,1≤i≤n,1≤j≤n

(9)

Ei=Ej,iXNORj,?i,j,1≤i≤n,1≤j≤n

(10)

ER(i,j)+ER(k,l)=1,R(i,j) XORR(k,l)

?R(i,j),R(k,l),1≤i,j,k,l≤n

(11)

ER(i,j)=ER(k,l),R(i,j) XNORR(k,l)

?R(i,j),R(k,l),1≤i,j,k,l≤n

(12)

Ei≤Ej,IFiTHENj

?i,j,1≤i≤n,1≤j≤n

(13)

Ei≤ER(k,l),IFiTHENR(k,l)

?i,1≤i≤n,1≤k,l≤n

(14)

ER(k,l)≤Ej,IFR(k,l) THENj

?i,1≤k,l≤n,1≤j≤n

(15)

ER(i,j)≤ER(k,l),IFR(i,j) THENR(k,l)

?i,j,1≤i,j,k,l≤n

(16)

Ei,Ej,ER(i,j),ER(k,l)∈{0,1}

(17)

目標(biāo)函數(shù)是項(xiàng)目工期的最小化,式(3)是2個(gè)確定執(zhí)行的活動(dòng)之間的時(shí)間關(guān)系約束的一般形式,式(4)～式(6)是活動(dòng)時(shí)間關(guān)系的邏輯表示,式(7)限定了所有活動(dòng)的開(kāi)始時(shí)間均大于等于0,式(8)則限定所有活動(dòng)必須在工期之內(nèi)完成,式(9)～式(16)是2個(gè)備擇活動(dòng)或備擇時(shí)間關(guān)系之間的邏輯關(guān)系表達(dá)式,式(17)定義各決策變量為布爾變量。

2.2 遺傳算法求解

基于布爾變量劃分的順序編碼方式,本節(jié)提出一種遺傳算法,將染色體分為獨(dú)立變量和半獨(dú)立變量編碼基因段,以原調(diào)度模型中的最短工期的倒數(shù)為適應(yīng)度函數(shù),進(jìn)行最優(yōu)解的搜索,編程實(shí)現(xiàn)帶有較多邏輯關(guān)系調(diào)度模型的啟發(fā)式求解。該算法借鑒動(dòng)態(tài)規(guī)劃的思想[20-22],采用單點(diǎn)交叉與變異,存儲(chǔ)了父代種群運(yùn)算結(jié)果,將新生成的子代與父代進(jìn)行比對(duì),相同編碼即可采用同樣的適應(yīng)度運(yùn)算結(jié)果,有效提高了遺傳算法的運(yùn)算效率。在遺傳操作后進(jìn)行沖突檢測(cè),消除由于種群初始化、交叉和變異操作生成的違反約束規(guī)則的個(gè)體。

2.2.1 布爾變量的順序編碼

在解決傳統(tǒng)調(diào)度優(yōu)化問(wèn)題的大多數(shù)遺傳算法中,染色體編碼中的各個(gè)基因相互獨(dú)立,迭代過(guò)程中各基因取值不受其他基因取值的影響,但式(13)～式(16)表明決策變量Ei及ER(i,j)之間存在依賴關(guān)系。為描述該依賴關(guān)系,本文在基因鏈編碼設(shè)計(jì)中加入半獨(dú)立變量。

在本文模型中所有布爾變量共分為3類:獨(dú)立變量,半獨(dú)立變量和派生變量。獨(dú)立變量指在眾多變量中不受其他變量取值影響的變量,半獨(dú)立變量指在其他變量確定后仍有一定取值范圍的變量,派生變量指在獨(dú)立變量和半獨(dú)立變量確定后取值就確定的變量。

本文算法采用基于布爾變量劃分的順序編碼方式,將整個(gè)編碼區(qū)域分為獨(dú)立變量區(qū)域(I區(qū))和半獨(dú)立變量區(qū)域(II區(qū))。

1)布爾變量編碼規(guī)則

在遺傳算法的改進(jìn)過(guò)程中,為了保證后續(xù)進(jìn)行遺傳編碼的沖突檢測(cè)和修正,確保新產(chǎn)生的染色體的有效性,設(shè)計(jì)編碼規(guī)則如下:

(1)在約束中被運(yùn)算的次數(shù)多的布爾變量?jī)?yōu)先編碼并賦值。

(2)在運(yùn)算次數(shù)相同的條件下,模型中原始序號(hào)靠前的布爾變量?jī)?yōu)先編碼并賦值。

(3)等式約束條件分別對(duì)應(yīng)一對(duì)獨(dú)立變量與派生變量,不等式中對(duì)應(yīng)的約束條件Ei≤Ej中,Ei優(yōu)先考慮是否為獨(dú)立變量。

假定模型中有n個(gè)獨(dú)立變量(Ii表示第i個(gè)獨(dú)立變量),m個(gè)半獨(dú)立變量(Sj表示第j個(gè)半獨(dú)立變量),基于布爾變量劃分的順序編碼方式將染色體編碼基因鏈分成I區(qū)編碼區(qū)和II區(qū)編碼區(qū),如圖1所示。

圖1 染色體編碼基因鏈

在包含n個(gè)變量的等式或不等式中,總會(huì)存在一個(gè)獨(dú)立變量和派生變量,其余變量為半獨(dú)立變量。

在該編碼原則下,II區(qū)編碼基因改變對(duì)其他基因位的影響程度將呈降序排列,后續(xù)沖突檢測(cè)中對(duì)II區(qū)編碼自前向后依據(jù)約束規(guī)則進(jìn)行修改,這樣可以確保修改后的染色體仍然是有效的個(gè)體,同時(shí)也可保證對(duì)染色體編碼影響最大的編碼改動(dòng)最小,盡量保持原編碼的有效性。該編碼以線性時(shí)間檢測(cè)修改染色體,相對(duì)于算法適應(yīng)度線性規(guī)劃求解部分的速度影響可以忽略不計(jì)。

2)編碼規(guī)則示例

為形象化展示本文算法染色體順序編碼規(guī)則,本節(jié)以一個(gè)項(xiàng)目調(diào)度算例來(lái)說(shuō)明,圖2為該工程算例調(diào)度網(wǎng)絡(luò)。

圖2 包含時(shí)間關(guān)系和邏輯關(guān)系的工程算例

本算例包含互斥、共存和依賴邏輯關(guān)系,式(18)～式(20)表示3個(gè)互斥邏輯關(guān)系,式(21)～式(23)表示3個(gè)共存邏輯關(guān)系,式(24)表示一個(gè)依賴邏輯關(guān)系。

E2+E5=1

(18)

ER(2,3)+ER(3,2)=1

(19)

ER(3,4)+ER(4,3)=1

(20)

ER(2,3)=ER(3,4)

(21)

ER(3,2)=ER(4,3)

(22)

E5=E6

(23)

E6≤E7

(24)

為了求出最少個(gè)數(shù)的獨(dú)立變量,設(shè)目標(biāo)函數(shù)為:

?i,R(j,k),1≤i,j,k≤n

(25)

計(jì)算求出一組符合本文算例布爾變量的可行解為:獨(dú)立變量E5和ER(2,3),派生變量E2、E6、ER(3,2)、ER(3,4)和ER(4,3),半獨(dú)立變量E7。根據(jù)基于布爾變量劃分的順序編碼方式和變量編碼賦值規(guī)則,算例的染色體編碼基因鏈如圖3所示。

圖3 算例中染色體編碼基因鏈

2.2.2 遺傳算子

本文針對(duì)施工活動(dòng)和時(shí)間關(guān)系間存在的大量邏輯關(guān)系,采用了獨(dú)立變量和半獨(dú)立變量的順序編碼機(jī)制。

1)算子的選擇

調(diào)度模型的目標(biāo)是最小化項(xiàng)目工期,求解過(guò)程需要最小化適配值,在選擇過(guò)程中將使用輪盤賭的選擇操作,因此,采用項(xiàng)目總工期的倒數(shù)作為適配值。令f(i)表示個(gè)體的適配值,在總數(shù)為λ的種群(POP)中個(gè)體生存概率為:

(26)

2)交叉算子

本文采用編碼基因鏈單點(diǎn)交叉,即各對(duì)應(yīng)編碼基因段分別交叉的方式對(duì)個(gè)體進(jìn)行交叉操作。

3)變異算子

本文采用編碼基因鏈基本點(diǎn)位變異。

2.2.3 沖突檢測(cè)與消除

傳統(tǒng)遺傳算法采用2種方法求解染色體中存在互相約束的基因編碼問(wèn)題:

方法1在編碼時(shí)剔除掉能夠根據(jù)其他編碼推理得到的變量編碼,之后在適應(yīng)度計(jì)算時(shí)再對(duì)被剔除編碼進(jìn)行計(jì)算,得到適合該染色體的最佳適應(yīng)度值和染色體編碼。

方法2在遺傳操作之后檢測(cè)染色體編碼中是否存在沖突的基因編碼,如果存在則將該染色體舍去或者設(shè)置染色體適應(yīng)度值為極低。

在大型復(fù)雜施工項(xiàng)目中,II區(qū)編碼數(shù)量較大,方法1雖然可以降低迭代次數(shù),但每一代種群的求解效率將極低。方法2會(huì)產(chǎn)生大量不可行的染色體編碼,導(dǎo)致算法收斂過(guò)快,因此,需要設(shè)置比較大的種群數(shù)量來(lái)保證種群在整個(gè)迭代過(guò)程中的多樣性,在工程規(guī)模較大時(shí),求解效率無(wú)法令人滿意。

本文算法在進(jìn)行適應(yīng)度計(jì)算之前,依據(jù)I區(qū)獨(dú)立變量和II區(qū)其他半獨(dú)立變量的約束不等式進(jìn)行反饋修正II區(qū)基因段,消除違反約束條件的個(gè)體。在沖突檢測(cè)之后,染色體編碼的I區(qū)獨(dú)立編碼部分不受影響,保留原染色體的I區(qū)編碼的有效性,II區(qū)編碼的修改程度依次降低。該修正使II區(qū)部分無(wú)效的編碼變?yōu)橛行?同時(shí)也保留了有效的編碼區(qū)域。

2.2.4 調(diào)度問(wèn)題的遺傳算法描述

采用本文遺傳算法計(jì)算最短工期的流程如圖4所示。

圖4 遺傳算法計(jì)算最短工期的流程

Fig.4 Flowchart of genetic algorithm calculating the shortest construction period

本文遺傳算法的具體實(shí)現(xiàn)步驟如下:

步驟1根據(jù)布爾變量順序編碼機(jī)制,對(duì)調(diào)度模型中的獨(dú)立變量和半獨(dú)立變量進(jìn)行順序編碼,并隨機(jī)產(chǎn)生初始種群POP,種群規(guī)模為pop,當(dāng)前代數(shù)為GEN=0。

步驟2計(jì)算種群中的個(gè)體適配值。

步驟3GEN=GEN+1。

步驟4根據(jù)交叉概率參數(shù)Pc,選出參與遺傳操作的子種群POPope,每個(gè)個(gè)體的染色體由獨(dú)立變量基因段和半獨(dú)立變量基因段構(gòu)成。

步驟5采用各對(duì)應(yīng)編碼基因段分別交叉的方式對(duì)POPope中個(gè)體進(jìn)行交叉操作,得到子代種群CHI。

步驟6根據(jù)變異規(guī)則和概率Pm對(duì)子代種群CHI中個(gè)體的每個(gè)基因段進(jìn)行變異操作。

步驟7將CHI中基因段組合成個(gè)體,計(jì)算其中個(gè)體的適配值。

步驟8POP=POP∪CHI。

步驟9通過(guò)選擇操作從POP中選出λ個(gè)個(gè)體作為下一代的種群。

步驟10檢測(cè)II編碼區(qū),依據(jù)I編碼區(qū)獨(dú)立變量的約束規(guī)則進(jìn)行修正。

步驟11如果GEN≥Gmax,終止算法,否則轉(zhuǎn)步驟3。

3 算例仿真

本文在MATLAB(R2015b)下,分別編寫了精確算法與遺傳算法的求解方法。精確解將使用線性求解規(guī)劃器計(jì)算得到模型的最短工期解,用于驗(yàn)證遺傳算法的結(jié)果正確性。遺傳算法的主要參數(shù)如表3所示。

表3 遺傳算法參數(shù)設(shè)置

某后張預(yù)應(yīng)力橋梁采用平衡懸臂法進(jìn)行施工,2個(gè)移動(dòng)平臺(tái)用來(lái)支撐在建設(shè)過(guò)程中橋墩兩側(cè)的橋梁分段,橋梁結(jié)構(gòu)呈中跨對(duì)稱結(jié)構(gòu)。平衡懸臂結(jié)構(gòu)從中間橋墩向兩邊施工的過(guò)程中,為保持橋梁結(jié)構(gòu)的穩(wěn)定,在任何時(shí)候都必須保證橋梁結(jié)構(gòu)兩邊的澆筑分段數(shù)量之差不大于1 。由于左右平衡懸臂結(jié)構(gòu)的對(duì)稱性,本文只研究左邊結(jié)構(gòu)的施工過(guò)程,用于測(cè)試調(diào)度模型和算法的實(shí)用性。本工程共包含25個(gè)施工活動(dòng),調(diào)度網(wǎng)絡(luò)如圖5所示。

圖5 案例調(diào)度網(wǎng)絡(luò)

通過(guò)模型轉(zhuǎn)換引擎,生成混合整數(shù)規(guī)劃模型為:

MinZ=Fp

(27)

其約束條件為:

S1+20≤S2

(28)

S1+20≤S3

(29)

S2+1-(1-ER(2,3))×M≤S3

(30)

S3+1-(1-ER(3,2))×M≤S2

(31)

S2+1≤S4

(32)

S3+1≤S5

(33)

S4+9≤S6

(34)

S5+9≤S6

(35)

S6+1≤S7

(36)

S7+44≤S8

(37)

S7+44≤S9

(38)

S8+1≤S10

(39)

S9+1≤S11

(40)

S10+9≤S12

(41)

S11+9≤S12

(42)

S12+1≤S13

(43)

S12+1≤S14

(44)

S12+1≤S21

(45)

S13+E13≤S15

(46)

S14+E14≤S16

(47)

S15+E13≤S16

(48)

S15+E13≤S19

(49)

S16-(1-E14)×M+9≤S17

(50)

S16+9≤S23

(51)

S17+E14-(1-E14)×M≤S18

(52)

S18+E14-(1-E14)×M≤S19

(53)

S19+1≤S20

(54)

S20+9×E20≤S23

(55)

S21+1≤S22

(56)

S22+9≤S23

(57)

S23+1≤S24

(58)

S24+1≤S25

(59)

ER(2,3)+ER(3,2)=1

(60)

E13+E14=1

(61)

E13≤E20

(62)

E14≤E20

(63)

ER(2,3),ER(3,2),E13,E14,E20∈{0,1}

(64)

Si+Di≤PF,i=1,2,…,n

(65)

Si≥0,i=1,2,…,n

(66)

當(dāng)采用精確算法求解時(shí),計(jì)算得出該案例的最短工期為110天。在調(diào)度模型中備擇活動(dòng)和時(shí)間關(guān)系被選擇的情況為E13=1,E14=0,ER(2,3)=1,ER(3,2)=0,ER20=1。

采用遺傳算法求解的結(jié)果如圖6所示。由于本案例活動(dòng)數(shù)較少,包含的邏輯關(guān)系也較少,在迭代到12代時(shí),整個(gè)種群平均天數(shù)已經(jīng)達(dá)到最短工期,種群天數(shù)已經(jīng)趨于收斂。計(jì)算得到的最短工期仍為110天,案例中布爾變量的計(jì)算結(jié)果和精確解相同。

在共228個(gè)活動(dòng)的調(diào)度模型中采用遺傳算法求解,可以發(fā)現(xiàn)在遺傳代數(shù)迭代到45代時(shí),整個(gè)種群平均適配天數(shù)已經(jīng)趨于收斂,可得最小工期為689天,和精確解結(jié)果相同。

為驗(yàn)證設(shè)計(jì)的遺傳算法適用于帶有大量邏輯關(guān)系的超大型復(fù)雜調(diào)度模型,本文通過(guò)增加邏輯關(guān)系的數(shù)量和項(xiàng)目規(guī)模的來(lái)驗(yàn)證遺傳算法收斂效果。分別在活動(dòng)數(shù)為500、1 000、2 000的模擬工程仿真中對(duì)比精確解、傳統(tǒng)遺傳算法和本文算法的求解效率,其中,傳統(tǒng)遺傳算法A編碼部分將只考慮獨(dú)立變量,傳統(tǒng)遺傳算法B將在進(jìn)行遺傳操作之后對(duì)所得染色體進(jìn)行有效性分析,如果染色體無(wú)效將會(huì)選擇新的父染色體進(jìn)行交叉變異操作,計(jì)算結(jié)果取3次測(cè)試平均值并取整,結(jié)果如表4所示。

表4 模擬案例中的求解效率對(duì)比

由表4可以看出,雖然精確解對(duì)中小規(guī)模的調(diào)度模型求解速率確實(shí)較快,但是隨著工程規(guī)模的擴(kuò)大,求解效率逐漸弱于本文算法。傳統(tǒng)遺傳算法A受大型工程中約束關(guān)系過(guò)多的影響,求解速度極慢,無(wú)法在有效時(shí)間內(nèi)求解;傳統(tǒng)遺傳算法B對(duì)大型工程求解過(guò)程中出現(xiàn)交叉變異操作產(chǎn)生的有效染色體概率極低的情況,種群進(jìn)化速度緩慢,收斂速度降低,在長(zhǎng)時(shí)間內(nèi)無(wú)法得到收斂結(jié)果。

4 結(jié)束語(yǔ)

本文在互斥與共存邏輯關(guān)系的基礎(chǔ)上引入IF-THEN來(lái)進(jìn)一步描述依賴關(guān)系,討論3種邏輯關(guān)系之間的內(nèi)在聯(lián)系,探索更為底層的邏輯關(guān)系表述方法。在此基礎(chǔ)上,擴(kuò)展調(diào)度模型到混合整數(shù)規(guī)劃模型的轉(zhuǎn)換規(guī)則,并分析邏輯關(guān)系的計(jì)算規(guī)則,實(shí)現(xiàn)模型間的自動(dòng)轉(zhuǎn)換。通過(guò)對(duì)模型中的邏輯關(guān)系變量進(jìn)行分段編碼,在變異操作后加入沖突檢測(cè)環(huán)節(jié),消除由種群初始化與遺傳操作產(chǎn)生的違反約束個(gè)體。編程實(shí)現(xiàn)本文算法的自動(dòng)求解,并與精確算法進(jìn)行對(duì)比,仿真結(jié)果表明,隨著工程規(guī)模的擴(kuò)大,該算法能有效縮短求解工期的時(shí)間。下一步將探究染色體編碼中的層級(jí)劃分概念,通過(guò)改進(jìn)遺傳算子,在保證近似解合理的情況下提高算法效率。