改進(jìn)遺傳算法在MSPSP問(wèn)題中的驗(yàn)證①

宋 堯,仰燕蘭,葉 樺

1(東南大學(xué) 自動(dòng)化學(xué)院,南京 210096)

2(復(fù)雜工程系統(tǒng)測(cè)量與控制教育部重點(diǎn)實(shí)驗(yàn)室,南京 210096)

資源受限項(xiàng)目調(diào)度問(wèn)題(Resource-Constrained Project Scheduling Problem,RCPSP)是一種典型的NPhard 問(wèn)題[1],具有約束條件嚴(yán)苛、組合性強(qiáng)、求解范圍廣等特點(diǎn),其基本目標(biāo)是在一定資源的約束下得到合理的調(diào)度方案,使得時(shí)間或者項(xiàng)目成本得到最優(yōu)化.多技能資源受限項(xiàng)目調(diào)度問(wèn)題(Multi-Skilled Resource-Constrained Project Scheduling Problem,MS-RCPSP/MSPSP)是在其基礎(chǔ)上增加了技能約束的一種拓展性問(wèn)題,因其在軟件開(kāi)發(fā)、建筑工程、車(chē)間調(diào)度等方面的廣泛應(yīng)用而不斷受到越來(lái)越多的學(xué)者的關(guān)注,并衍生出許多求解方案.比如,任逸飛等人提出了一種包含雙層決策及局部?jī)?yōu)化策略的混合算法對(duì)MSPSP 進(jìn)行求解,并結(jié)合基于關(guān)鍵鏈的局部搜索算法提高了求解質(zhì)量[2];Skowronski 等人先后用基于調(diào)度優(yōu)先級(jí)規(guī)則的元啟發(fā)式算法[3]、禁忌搜索算法[4]和進(jìn)化算法[5]研究MSPSP,并生成了一套專門(mén)針對(duì)MSPSP 的基準(zhǔn)數(shù)據(jù)集iMOPSE[6],為后世研究該問(wèn)題提供了重要參考依據(jù).

總的來(lái)說(shuō),目前所使用的各種算法都僅能針對(duì)部分?jǐn)?shù)據(jù)對(duì)象而不斷靠近最優(yōu)解,如何提出合適的算法為MSPSP 求出更優(yōu)解是目前研究努力的一個(gè)方向.本文在對(duì)比了各種算法之后,考慮到發(fā)展已久的遺傳算法(Genetic Algorithm,GA)[7]在尋優(yōu)搜索能力、魯棒性和兼容性等方面的良好表現(xiàn),選擇其作為本文的基本算法.考慮到該算法存在早熟收斂和后期收斂速度慢的問(wèn)題,學(xué)者們?cè)谄浠A(chǔ)上進(jìn)行了相關(guān)改進(jìn),并用于求解MSPSP 問(wèn)題.比如,Laszczyk 等人在經(jīng)典的非支配遺傳算法的基礎(chǔ)上提出了一種新的選擇算子,提高了搜索效率[8];Lin 等人提出了一種遺傳規(guī)劃的超啟發(fā)式算法,將遺傳算法作為一種宏觀策略,統(tǒng)籌調(diào)度十種啟發(fā)式規(guī)則進(jìn)行求解[9].本文針對(duì)MSPSP 的特點(diǎn),在細(xì)化遺傳算法的求解過(guò)程的基礎(chǔ)上,對(duì)其選擇、交叉和排序過(guò)程分別進(jìn)行了改進(jìn).

1 MSPSP 介紹

1.1 問(wèn)題描述

MSPSP 的基本概念是:一個(gè)項(xiàng)目中涉及多個(gè)任務(wù),任務(wù)之間存在時(shí)間約束關(guān)系,項(xiàng)目中的各種資源都具備一種或多種技能,問(wèn)題的目標(biāo)是在滿足各種約束的條件下合理調(diào)度和分配已有的資源和任務(wù),使得完成整個(gè)項(xiàng)目的總時(shí)間或總成本最小化.

一般而言,問(wèn)題中的資源都指人力資源,以圖1為例,J1～J4 表示任務(wù),H1～H4 表示資源,以J1 為例,它需要具備技能S3 且技能等級(jí)達(dá)到3.2 的人員,在H1～H4 中只有H2 和H4 是滿足的,因此對(duì)于J1 來(lái)說(shuō)H2 和H4 可以被分配給它.當(dāng)確定人力資源的可分配權(quán)后,再結(jié)合相關(guān)時(shí)間約束和資源約束,才能進(jìn)一步確定最終的分配情況.

圖1 MSPSP 示意圖

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

為了便于描述MSPSP 的數(shù)學(xué)模型,首先引入如下符號(hào)定義:

J:任務(wù)集合,J={1,2,···,m};

H:資源集合,H={1,2,···,n};

S:技能集合;

dj:完成任務(wù)j的工期;

bj:任務(wù)j的開(kāi)始時(shí)間;

fj:任務(wù)j的結(jié)束時(shí)間;

kjh:任務(wù)j所需要的資源h的數(shù)量;

Pj:任務(wù)j的前置任務(wù)集合;

Kh:資源h的數(shù)量;

wh:資源h的單位成本;

Sh:資源h所擁有的技能集合;

Jh:資源h可完成的任務(wù)集合;

ls:技能s的等級(jí);

qs:技能s的類別;

α:優(yōu)化目標(biāo)的權(quán)重系數(shù);

T:工作持續(xù)時(shí)間;

Qjht:0-1 變量,資源h在t時(shí)刻作用于任務(wù)j時(shí)為1,否則為0.

MSPSP 的數(shù)學(xué)模型為:

目標(biāo)函數(shù):

其中,

約束條件:

式(1)中的Fτ和Fc分別表示工作的總時(shí)間和總成本,兩者是相互制約的關(guān)系,通過(guò)權(quán)重系數(shù) α關(guān)聯(lián)起來(lái),構(gòu)成總的優(yōu)化目標(biāo)Fs.α的取值將決定優(yōu)化對(duì)象是單目標(biāo)還是多目標(biāo),α=0時(shí) 是成本優(yōu)化,α=1時(shí)是時(shí)間優(yōu)化,α ∈(0,1)是綜合考慮時(shí)間和成本的多目標(biāo)優(yōu)化.本文主要考慮單目標(biāo)優(yōu)化.式(4)和式(5)表示任務(wù)的時(shí)間約束.式(6)～式(8)是對(duì)人力資源的約束:式(6)要求每種人力資源至少具備一種技能;式(7)體現(xiàn)了人員成本的合理性;式(8)表示單個(gè)資源在同一時(shí)間內(nèi)只能使用一種技能去執(zhí)行一項(xiàng)任務(wù).式(9)是技能約束,規(guī)定了在為各個(gè)任務(wù)節(jié)點(diǎn)分配資源時(shí),必須滿足該任務(wù)對(duì)資源的技能種類和技能等級(jí)的需求.式(10)的定義是為了方便計(jì)算成本消耗.

2 改進(jìn)遺傳算法

2.1 編解碼方案

根據(jù)問(wèn)題選擇合適的染色體編碼方式是遺傳算法的第一步,鑒于MSPSP 是要尋找滿足約束條件的任務(wù)和資源的最佳排列,本文選擇基于優(yōu)先級(jí)數(shù)組的整數(shù)編碼,以更直觀地展示和表達(dá)調(diào)度結(jié)果.在遺傳算法中,每條染色體對(duì)應(yīng)一個(gè)任務(wù)鏈,以優(yōu)先級(jí)數(shù)組進(jìn)行表示時(shí),數(shù)組中的元素(即染色體的基因)是任務(wù)的權(quán)重,數(shù)組的下標(biāo)表示任務(wù)編號(hào),數(shù)組的長(zhǎng)度等于任務(wù)總數(shù).

編碼之后還需要進(jìn)行解碼才能形成完整的調(diào)度方案.本文選擇串行調(diào)度機(jī)制[10]實(shí)行解碼操作,主要分為兩個(gè)部分:

(1)在不考慮技能約束的情況下,根據(jù)任務(wù)的權(quán)重生成任務(wù)序列,當(dāng)權(quán)重相等時(shí),任務(wù)編號(hào)小的優(yōu)先;

(2)根據(jù)技能約束和資源約束對(duì)資源進(jìn)行分配,在此過(guò)程中如果發(fā)現(xiàn)資源分配沖突則需要對(duì)任務(wù)序列進(jìn)行調(diào)整,如果無(wú)法通過(guò)調(diào)整滿足需求則放棄該方案.

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

遺傳算法一般會(huì)選擇問(wèn)題的目標(biāo)函數(shù)作為適應(yīng)度函數(shù),但MSPSP 的目標(biāo)函數(shù)是最小化目標(biāo),不滿足適應(yīng)度函數(shù)的最大化需求,因此需要做一定轉(zhuǎn)化,最終的適應(yīng)度函數(shù)如式(11)所示.

其中,fg(ck)是個(gè)體ck的適應(yīng)度函數(shù),Fs是當(dāng)前個(gè)體的目標(biāo)值(即目標(biāo)函數(shù)值),Fs_max和Fs_min分別是當(dāng)前群體中的最大目標(biāo)值和最小目標(biāo)值.

2.3 基于群體共享的小生境選擇

得到種群的適應(yīng)度后,需要根據(jù)適應(yīng)度大小對(duì)種群中的個(gè)體進(jìn)行初步篩選,挑選出適應(yīng)度較好的一批個(gè)體,為后續(xù)的交叉和變異做準(zhǔn)備.傳統(tǒng)的直接通過(guò)比較個(gè)體適應(yīng)度大小來(lái)決定生存權(quán)的方式會(huì)帶來(lái)一些問(wèn)題:

(1)算法搜索初期,適應(yīng)度很好的一批個(gè)體不但擁有更長(zhǎng)的生存時(shí)間,而且易被視為優(yōu)良父代將本身的基因傳承下去,進(jìn)而影響整個(gè)種群的進(jìn)化方向,從而削弱了算法的全局搜索能力;

(2)算法搜索后期,經(jīng)過(guò)多代的進(jìn)化,個(gè)體間的差異變小,種群多樣性降低,演變成了近親繁殖,在此基礎(chǔ)上生成的后代也很難有新的變化,最終算法可能會(huì)陷入局部最優(yōu).

為了防止種群的多樣性被破壞,本文在遺傳算法的選擇階段融入基于群體共享的小生境技術(shù)[11].其基本過(guò)程是:首先將原始種群分為若干子種群,接著從中挑選出一個(gè)優(yōu)質(zhì)種群作為共享種群,然后在共享種群和普通種群內(nèi)部獨(dú)立進(jìn)行交叉、變異操作,生成新一代種群,并不斷重復(fù)這種操作,直到滿足終止條件為止.將小生境技術(shù)與遺傳算法相融合,能夠增強(qiáng)算法的全局搜索的能力,加快算法的收斂速度.

2.3.1 定義說(shuō)明

為了實(shí)現(xiàn)上述算法,首先給出如下定義:

定義1.個(gè)體間距離

在基于群體共享機(jī)制的小生境方法中,可以利用海明距離來(lái)輔助判斷個(gè)體之間的相似程度,相似度不高的個(gè)體才能進(jìn)行交配,以保證種群的多樣性.為了方便計(jì)算海明距離,需要先將個(gè)體由實(shí)數(shù)編碼轉(zhuǎn)為二進(jìn)制編碼,然后再根據(jù)式(12)求得個(gè)體ci和cj之間的海明距離,其中,binLen表示染色體二進(jìn)制編碼的長(zhǎng)度,G表示整個(gè)種群.

定義2.個(gè)體共享度

個(gè)體共享度是借助個(gè)體間海明距離來(lái)度量其相似程度的一種表達(dá),如式(13)所示,個(gè)體之間相似度越大,個(gè)體共享度就越大.

定義3.群體共享度

群體共享度是對(duì)個(gè)體在群體中的特異性的度量,是個(gè)體與群體中的其他個(gè)體間的個(gè)體共享度之和,如式(14)所示.

2.3.2 確定式采樣選擇

在各個(gè)子群體的進(jìn)化過(guò)程中,為了保證優(yōu)質(zhì)基因能夠遺傳下去,與文獻(xiàn)[11]不同的是,本文采用確定式采樣選擇法[12]進(jìn)行個(gè)體選擇,避開(kāi)傳統(tǒng)輪盤(pán)賭方式帶來(lái)的統(tǒng)計(jì)誤差.具體操作過(guò)程是:

Step 1.計(jì)算各個(gè)子種群中的個(gè)體在下一代中的期望數(shù)目:

Step 3.根據(jù)Nexp(ci)的小數(shù)部分對(duì)所有個(gè)體進(jìn)行排序,選擇最大的個(gè)個(gè)體進(jìn)入到下一代種群中.

這種方式能夠確保每個(gè)子群體中適應(yīng)度較大的個(gè)體都能存活到下一代.

2.3.3 子種群適應(yīng)度和規(guī)模調(diào)整

為了減少算法中相似個(gè)體的不斷聚合,需要根據(jù)子群體的群體共享度不斷調(diào)整其適應(yīng)度和種群規(guī)模.

調(diào)整的基本規(guī)則是:

(1)根據(jù)共享種群的群體共享度占總?cè)后w共享度的比值,略微調(diào)高共享種群的適應(yīng)度;

(2)當(dāng)普通種群的群體共享度大于共享種群的群體共享度時(shí),調(diào)低普通種群的適應(yīng)度,反之調(diào)高;

(3)在總的種群規(guī)模不變的情況下,根據(jù)種群的適應(yīng)度比例重新分配子種群的規(guī)模.

對(duì)于共享種群的適應(yīng)度調(diào)整:

對(duì)于普通種群的適應(yīng)度調(diào)整:

對(duì)于各個(gè)子種群規(guī)模的調(diào)整:

其中,sshare表示共享種群的群體共享度,subS ize(i)表示第i個(gè)子種群的規(guī)模,fg(i)表示第i個(gè)子種群的適應(yīng)度值.

2.4 基于修復(fù)機(jī)制的單點(diǎn)交叉

遺傳算法中的交叉操作能夠生成繼承了父代基因的新個(gè)體,提高算法的全局搜索能力,其中最常見(jiàn)的是單點(diǎn)交叉法.傳統(tǒng)的單點(diǎn)交叉的過(guò)程是:在父輩個(gè)體中隨機(jī)選擇一個(gè)交叉點(diǎn),將該交叉點(diǎn)之后的基因互換,從而生成了兩個(gè)新的子個(gè)體.本文的染色體是任務(wù)時(shí)序鏈,使用基本的單點(diǎn)交叉后容易打破時(shí)序約束,且新生成的子個(gè)體中可能出現(xiàn)重復(fù)項(xiàng)和缺失項(xiàng).為了保證子代個(gè)體的有效性,本文結(jié)合隨機(jī)生成的交叉概率Pc,在基本的單點(diǎn)操作基礎(chǔ)上增加了相關(guān)修復(fù)策略,如圖2所示.

具體的修復(fù)過(guò)程是:經(jīng)過(guò)基本的單點(diǎn)交叉后,首先找到子代個(gè)體中重復(fù)的編號(hào),子代c1中是1 和3,c2中是4 和6;然后將c1交叉點(diǎn)前的重復(fù)編號(hào)與c2交叉點(diǎn)后的重復(fù)編號(hào)依次進(jìn)行交換,即c1中交叉點(diǎn)前的1 和3 分別與c2交叉點(diǎn)后的4 和6 交換,同理,也將c2交叉點(diǎn)前的重復(fù)編號(hào)與c1交叉點(diǎn)后的重復(fù)編號(hào)依次進(jìn)行交換,即c2中交叉點(diǎn)前的4 和6 分別與c1交叉點(diǎn)后的3 和1 交換;最后交換后的結(jié)果即為修復(fù)的子代個(gè)體,該子代個(gè)體都滿足任務(wù)的時(shí)序約束,且沒(méi)有重復(fù)項(xiàng).

但是,交叉完后的子代個(gè)體的適應(yīng)度并不一定比父代強(qiáng),為了在交叉后盡量保留適應(yīng)度相對(duì)較好的個(gè)體,在此引入父子競(jìng)爭(zhēng)機(jī)制來(lái)進(jìn)一步篩選出能夠進(jìn)入下一代繁殖的個(gè)體:對(duì)父代c1、c2和子代c1、c2四個(gè)個(gè)體的適應(yīng)度進(jìn)行排序,選擇適應(yīng)度最好的兩個(gè)作為最終的新生代個(gè)體進(jìn)入下一次繁殖和進(jìn)化.

圖2 基于修復(fù)機(jī)制的單點(diǎn)交叉示意圖

2.5 基于多重驗(yàn)證的變異

除了交叉外,遺傳算法中的變異操作也能生成新的個(gè)體,輔助交叉操作維護(hù)種群的多樣性,增強(qiáng)算法的局部搜索能力.與交叉不同的是,變異是根據(jù)變異率Pm在單個(gè)染色體上對(duì)其部分基因進(jìn)行突變,從而產(chǎn)生新的個(gè)體.

對(duì)于MSPSP 問(wèn)題而言,為了使變異后的個(gè)體仍舊滿足約束條件,在執(zhí)行傳統(tǒng)的變異操作后,還需對(duì)新個(gè)體進(jìn)行時(shí)序約束驗(yàn)證,只有驗(yàn)證通過(guò)的個(gè)體才能保留下來(lái),否則變異失效.另外,如果變異后的個(gè)體適應(yīng)度太低,則表明該方案不太可取,且會(huì)影響整個(gè)子群體的適應(yīng)度,因此還需對(duì)新個(gè)體進(jìn)行適應(yīng)度檢驗(yàn).

本文設(shè)計(jì)的基于多重驗(yàn)證的變異過(guò)程如下:

Step 1.隨機(jī)為子種群中的所有個(gè)體分配概率p(ci);

Step 2.選擇一個(gè)個(gè)體,判斷是否滿足p(ci)≤Pm,如果是則執(zhí)行變異操作,否則另選個(gè)體進(jìn)行判斷;

Step 3.在所選個(gè)體上隨機(jī)選擇兩個(gè)任務(wù)和進(jìn)行交換;

Step 4.判斷新個(gè)體是否滿足時(shí)序約束,且適應(yīng)度比舊個(gè)體高,如果都滿足則用新個(gè)體代替舊個(gè)體;否則拋棄新個(gè)體,保留舊個(gè)體;Step 5.判斷當(dāng)前種群中的所有個(gè)體是否都檢測(cè)完畢,如果是,則結(jié)束變異操作;否則轉(zhuǎn)到Step 2.

2.6 算法總流程

改進(jìn)遺傳算法的詳細(xì)步驟為:

Step 1.設(shè)置遺傳算法的相關(guān)參數(shù)(種群規(guī)模popS ize,變異概率Pm,最大迭代次數(shù)Niter),并用貪心算法初始化種群;

Step 2.劃分子種群;

Step 3.計(jì)算個(gè)體的適應(yīng)度,并在各個(gè)子種群內(nèi)獨(dú)立執(zhí)行進(jìn)化操作:首先按照確定式采樣規(guī)則進(jìn)行個(gè)體選擇,然后執(zhí)行基于修復(fù)機(jī)制的單點(diǎn)交叉操作,最后完成基于多重驗(yàn)證的變異操作;

Step 4.判斷子群體進(jìn)化次數(shù)ksub是否達(dá)到上限值Ne,如果是則先將ksub清零,再轉(zhuǎn)到Step 5;否則轉(zhuǎn)到Step 3;

Step 5.計(jì)算子種群的平均適應(yīng)度,選擇適應(yīng)度值最高的作為共享種群;

Step 6.根據(jù)群體共享度和適應(yīng)度調(diào)整所有子種群的適應(yīng)度和規(guī)模;

Step 7.淘汰連續(xù)幾代表現(xiàn)最差的子群體,并產(chǎn)生相同規(guī)模的新群體進(jìn)行替換;

Step 8.判斷當(dāng)前迭代次數(shù)是否達(dá)到上限,或者連續(xù)幾代的求解結(jié)果偏差是否滿足收斂條件,如果滿足任意一條則結(jié)束算法,輸出結(jié)果;否則轉(zhuǎn)到Step 3.

算法的流程圖如圖3所示.

3 實(shí)驗(yàn)分析

用Python 實(shí)現(xiàn)了針對(duì)MSPSP 的改進(jìn)遺傳算法后,為了驗(yàn)證算法的性能,本文在iMOPSE[6]數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn),并與其他算法的求解結(jié)果進(jìn)行了對(duì)比.實(shí)驗(yàn)中,算法的參數(shù)設(shè)置如表1所示.

在取相同參數(shù)的情況下,改進(jìn)遺傳算法和傳統(tǒng)遺傳算法在10_20_46_15 算例上的求解效果如圖4所示,可以看出,改進(jìn)算法的收斂速度更快,求解結(jié)果更優(yōu).

使用改進(jìn)遺傳算法對(duì)整個(gè)iMOPSE 數(shù)據(jù)集進(jìn)行求解,分別取α=1(時(shí)間最優(yōu))和α=0(成本最優(yōu)),每個(gè)實(shí)例運(yùn)行20 次,將結(jié)果與文獻(xiàn)[13]中的混合蟻群算法的結(jié)果進(jìn)行對(duì)比,如表2所示.可以看出,不管是以時(shí)間最優(yōu)還是成本最優(yōu)為目標(biāo),改進(jìn)遺傳算法都能求得更優(yōu)的解,且從多次求解的標(biāo)準(zhǔn)差來(lái)看,大部分情況下改進(jìn)遺傳算法都更加穩(wěn)定.

圖3 改進(jìn)遺傳算法流程圖

表1 改進(jìn)遺傳算法參數(shù)設(shè)置

圖4 改進(jìn)GA 和傳統(tǒng)GA 在10_20_46_15 上的求解對(duì)比圖(α=1)

表2 改進(jìn)遺傳算法和混合蟻群算法在iMOPSE 上的求解結(jié)果對(duì)比

續(xù)表2

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

本文針對(duì)MSPSP 問(wèn)題的特點(diǎn),在傳統(tǒng)遺傳算法的基礎(chǔ)上,融入了基于群體共享的小生境技術(shù),提高了種群信息的利用率,并針對(duì)MSPSP 的時(shí)序約束,分別為交叉和變異操作增加了修復(fù)和驗(yàn)證機(jī)制,進(jìn)一步確保了個(gè)體的合法性.經(jīng)實(shí)驗(yàn)驗(yàn)證分析可知,改進(jìn)后的遺傳算法相較于傳統(tǒng)遺傳算法和混合蟻群算法的收斂速度更快,求解結(jié)果更優(yōu),穩(wěn)定性更強(qiáng),且能在iMOPSE 數(shù)據(jù)集上取得良好效果,為研究相關(guān)實(shí)際問(wèn)題提供了一定參考價(jià)值.