改進遺傳算法在MSPSP問題中的驗證①

宋 堯,仰燕蘭,葉 樺

1(東南大學 自動化學院,南京 210096)

2(復雜工程系統測量與控制教育部重點實驗室,南京 210096)

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

總的來說,目前所使用的各種算法都僅能針對部分數據對象而不斷靠近最優解,如何提出合適的算法為MSPSP 求出更優解是目前研究努力的一個方向.本文在對比了各種算法之后,考慮到發展已久的遺傳算法(Genetic Algorithm,GA)[7]在尋優搜索能力、魯棒性和兼容性等方面的良好表現,選擇其作為本文的基本算法.考慮到該算法存在早熟收斂和后期收斂速度慢的問題,學者們在其基礎上進行了相關改進,并用于求解MSPSP 問題.比如,Laszczyk 等人在經典的非支配遺傳算法的基礎上提出了一種新的選擇算子,提高了搜索效率[8];Lin 等人提出了一種遺傳規劃的超啟發式算法,將遺傳算法作為一種宏觀策略,統籌調度十種啟發式規則進行求解[9].本文針對MSPSP 的特點,在細化遺傳算法的求解過程的基礎上,對其選擇、交叉和排序過程分別進行了改進.

1 MSPSP 介紹

1.1 問題描述

MSPSP 的基本概念是:一個項目中涉及多個任務,任務之間存在時間約束關系,項目中的各種資源都具備一種或多種技能,問題的目標是在滿足各種約束的條件下合理調度和分配已有的資源和任務,使得完成整個項目的總時間或總成本最小化.

一般而言,問題中的資源都指人力資源,以圖1為例,J1～J4 表示任務,H1～H4 表示資源,以J1 為例,它需要具備技能S3 且技能等級達到3.2 的人員,在H1～H4 中只有H2 和H4 是滿足的,因此對于J1 來說H2 和H4 可以被分配給它.當確定人力資源的可分配權后,再結合相關時間約束和資源約束,才能進一步確定最終的分配情況.

圖1 MSPSP 示意圖

1.2 數學模型

為了便于描述MSPSP 的數學模型,首先引入如下符號定義:

J:任務集合,J={1,2,···,m};

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

S:技能集合;

dj:完成任務j的工期;

bj:任務j的開始時間;

fj:任務j的結束時間;

kjh:任務j所需要的資源h的數量;

Pj:任務j的前置任務集合;

Kh:資源h的數量;

wh:資源h的單位成本;

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

Jh:資源h可完成的任務集合;

ls:技能s的等級;

qs:技能s的類別;

α:優化目標的權重系數;

T:工作持續時間;

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

MSPSP 的數學模型為:

目標函數:

其中,

約束條件:

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

2 改進遺傳算法

2.1 編解碼方案

根據問題選擇合適的染色體編碼方式是遺傳算法的第一步,鑒于MSPSP 是要尋找滿足約束條件的任務和資源的最佳排列,本文選擇基于優先級數組的整數編碼,以更直觀地展示和表達調度結果.在遺傳算法中,每條染色體對應一個任務鏈,以優先級數組進行表示時,數組中的元素(即染色體的基因)是任務的權重,數組的下標表示任務編號,數組的長度等于任務總數.

編碼之后還需要進行解碼才能形成完整的調度方案.本文選擇串行調度機制[10]實行解碼操作,主要分為兩個部分:

(1)在不考慮技能約束的情況下,根據任務的權重生成任務序列,當權重相等時,任務編號小的優先;

(2)根據技能約束和資源約束對資源進行分配,在此過程中如果發現資源分配沖突則需要對任務序列進行調整,如果無法通過調整滿足需求則放棄該方案.

2.2 適應度函數

遺傳算法一般會選擇問題的目標函數作為適應度函數,但MSPSP 的目標函數是最小化目標,不滿足適應度函數的最大化需求,因此需要做一定轉化,最終的適應度函數如式(11)所示.

其中,fg(ck)是個體ck的適應度函數,Fs是當前個體的目標值(即目標函數值),Fs_max和Fs_min分別是當前群體中的最大目標值和最小目標值.

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

得到種群的適應度后,需要根據適應度大小對種群中的個體進行初步篩選,挑選出適應度較好的一批個體,為后續的交叉和變異做準備.傳統的直接通過比較個體適應度大小來決定生存權的方式會帶來一些問題:

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

(2)算法搜索后期,經過多代的進化,個體間的差異變小,種群多樣性降低,演變成了近親繁殖,在此基礎上生成的后代也很難有新的變化,最終算法可能會陷入局部最優.

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

2.3.1 定義說明

為了實現上述算法,首先給出如下定義:

定義1.個體間距離

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

定義2.個體共享度

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

定義3.群體共享度

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

2.3.2 確定式采樣選擇

在各個子群體的進化過程中,為了保證優質基因能夠遺傳下去,與文獻[11]不同的是,本文采用確定式采樣選擇法[12]進行個體選擇,避開傳統輪盤賭方式帶來的統計誤差.具體操作過程是:

Step 1.計算各個子種群中的個體在下一代中的期望數目:

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

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

2.3.3 子種群適應度和規模調整

為了減少算法中相似個體的不斷聚合,需要根據子群體的群體共享度不斷調整其適應度和種群規模.

調整的基本規則是:

(1)根據共享種群的群體共享度占總群體共享度的比值,略微調高共享種群的適應度;

(2)當普通種群的群體共享度大于共享種群的群體共享度時,調低普通種群的適應度,反之調高;

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

對于共享種群的適應度調整:

對于普通種群的適應度調整:

對于各個子種群規模的調整:

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

2.4 基于修復機制的單點交叉

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

具體的修復過程是:經過基本的單點交叉后,首先找到子代個體中重復的編號,子代c1中是1 和3,c2中是4 和6;然后將c1交叉點前的重復編號與c2交叉點后的重復編號依次進行交換,即c1中交叉點前的1 和3 分別與c2交叉點后的4 和6 交換,同理,也將c2交叉點前的重復編號與c1交叉點后的重復編號依次進行交換,即c2中交叉點前的4 和6 分別與c1交叉點后的3 和1 交換;最后交換后的結果即為修復的子代個體,該子代個體都滿足任務的時序約束,且沒有重復項.

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

圖2 基于修復機制的單點交叉示意圖

2.5 基于多重驗證的變異

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

對于MSPSP 問題而言,為了使變異后的個體仍舊滿足約束條件,在執行傳統的變異操作后,還需對新個體進行時序約束驗證,只有驗證通過的個體才能保留下來,否則變異失效.另外,如果變異后的個體適應度太低,則表明該方案不太可取,且會影響整個子群體的適應度,因此還需對新個體進行適應度檢驗.

本文設計的基于多重驗證的變異過程如下:

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

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

Step 3.在所選個體上隨機選擇兩個任務和進行交換;

Step 4.判斷新個體是否滿足時序約束,且適應度比舊個體高,如果都滿足則用新個體代替舊個體;否則拋棄新個體,保留舊個體;Step 5.判斷當前種群中的所有個體是否都檢測完畢,如果是,則結束變異操作;否則轉到Step 2.

2.6 算法總流程

改進遺傳算法的詳細步驟為:

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

Step 2.劃分子種群;

Step 3.計算個體的適應度,并在各個子種群內獨立執行進化操作:首先按照確定式采樣規則進行個體選擇,然后執行基于修復機制的單點交叉操作,最后完成基于多重驗證的變異操作;

Step 4.判斷子群體進化次數ksub是否達到上限值Ne,如果是則先將ksub清零,再轉到Step 5;否則轉到Step 3;

Step 5.計算子種群的平均適應度,選擇適應度值最高的作為共享種群;

Step 6.根據群體共享度和適應度調整所有子種群的適應度和規模;

Step 7.淘汰連續幾代表現最差的子群體,并產生相同規模的新群體進行替換;

Step 8.判斷當前迭代次數是否達到上限,或者連續幾代的求解結果偏差是否滿足收斂條件,如果滿足任意一條則結束算法,輸出結果;否則轉到Step 3.

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

3 實驗分析

用Python 實現了針對MSPSP 的改進遺傳算法后,為了驗證算法的性能,本文在iMOPSE[6]數據集上進行了實驗,并與其他算法的求解結果進行了對比.實驗中,算法的參數設置如表1所示.

在取相同參數的情況下,改進遺傳算法和傳統遺傳算法在10_20_46_15 算例上的求解效果如圖4所示,可以看出,改進算法的收斂速度更快,求解結果更優.

使用改進遺傳算法對整個iMOPSE 數據集進行求解,分別取α=1(時間最優)和α=0(成本最優),每個實例運行20 次,將結果與文獻[13]中的混合蟻群算法的結果進行對比,如表2所示.可以看出,不管是以時間最優還是成本最優為目標,改進遺傳算法都能求得更優的解,且從多次求解的標準差來看,大部分情況下改進遺傳算法都更加穩定.

圖3 改進遺傳算法流程圖

表1 改進遺傳算法參數設置

圖4 改進GA 和傳統GA 在10_20_46_15 上的求解對比圖(α=1)

表2 改進遺傳算法和混合蟻群算法在iMOPSE 上的求解結果對比

續表2

4 結束語

本文針對MSPSP 問題的特點,在傳統遺傳算法的基礎上,融入了基于群體共享的小生境技術,提高了種群信息的利用率,并針對MSPSP 的時序約束,分別為交叉和變異操作增加了修復和驗證機制,進一步確保了個體的合法性.經實驗驗證分析可知,改進后的遺傳算法相較于傳統遺傳算法和混合蟻群算法的收斂速度更快,求解結果更優,穩定性更強,且能在iMOPSE 數據集上取得良好效果,為研究相關實際問題提供了一定參考價值.