基于模擬遺傳退火算法的RCPSP問題研究

趙衛東 林雙雙

摘要：在資源有限項目調度問題中，針對可更新資源的單項目如何求得資源約束下的最短工期，提出了一種基于種群穩定度的遺傳模擬退火算法。設計了一種滿足任務前后約束的種群初始化方法，將種群進行交叉、變異產生新的種群后加入模擬退火算法，計算是否以新的種群替換當前新種群。提出了種群穩定度概念。為避免一般遺傳算法的進化早熟現象，當種群穩定度超過給定的穩定度時應用模擬退火算法，通過多次試驗設定種群穩定度。通過標準測試問題庫中的數值驗證表明，該算法能擴大解空間得到更優解，使收斂加快。

關鍵詞：遺傳算法;模擬退火;資源約束;種群穩定度

RCPSP Study Based on Simulated Annealing and Genetic Algorithm

ZHAO Wei?dong， LIN Shuang?shuang

（Shandong University of Science and Technology， College of Computer Scienceand Engineering，Qingdao 266590，China）

Abstract：In order to find the shortest duration for a single project with renewable resources under resource constraints， a genetic simulated annealing algorithm based on population stability is proposed. A population initialization method which satisfies the demand of precedence constraints is developed from this algorithm. After the new population is generated by crossing and mutating， the simulated annealing algorithm is?added to calculate whether the current population is replaced by a new population. Meanwhile， the concept of population stability is put forward. In order to avoid the prematurity of general genetic algorithm， simulated annealing algorithm should be applied when the population stability exceeds the given stability which is determined by several experiments. Finally， the numerical results of PSPLIB show that this algorithm can expand the solution space， optimize the solution and accelerate the convergence.

Key Words：genetic algorithm; simulated annealing algorithm;?resource constrained; population stability

0?引言

資源約束項目調度問題（Resource Constrained Project Scheduling Problem， RCPSP）是一類在滿足既定的資源約束下，如何將項目中的各項任務進行合理調度以達到既定目標最優化的問題[1]。RCPSP問題是一個基本模型，最終目標是實現在最短時間內完成項目，屬于“資源有限-工期最短”問題。在資源約束的同時，項目中的各項活動也有優先順序約束，因此該問題也屬于組合優化問題。工期最短化具有實際意義，在數學上RCPSP問題幾乎都屬于NP-hard問題[2]，其研究方法一直在不斷改進。分支定界法[3?4]、動態規劃[5]等精確算法可在理論上取得最優解，但在實際應用中因為計算時間長和計算方法多而顯得力不從心。基于優先規則的啟發式方法是解決大規模問題的重要方法之一[6]。文獻[7]提出在分層遺傳算法中融入模擬退火思想能夠避免種群過早收斂，同時能克服遺傳算法局部尋優能力較差的缺陷。文獻[8]提出基于磁石的交叉算子算法，能保證在相鄰的部分兩點交叉基因來自同一母體，與其它工序相比其性能較好。對于簡單的可更新多資源及活動繁多的單項目優化研究不多，而在現代工廠的離散制造加工流程中單項目最短工期研究有一定的現實意義。因此本文在遺傳算法后期設計一種能滿足優先順序關系約束的初始化種群，以有序的次序交叉法保證每一代個體的正確性和有效性，解決了可更新多資源約束下的單項目工期最短問題。實驗證明本文算法允許以一定的概率接受較差解，可增加種群多樣性，擺脫局部最優解，使收斂加快。

1?問題定義

資源受限的項目調度（RCPSP）問題[9]是用元組（A，D，E，R，B，W）表示的組合優化問題。

構成項目的活動由集合?A={a?0，…，a?n+1}確定。a?0代表調度計劃表的第一個活動，a?n+1代表調度計劃表的最后一個活動，二者是虛活動。為了繪圖方便，引入一種特殊的活動，既不消耗時間也不消耗資源，僅僅表示工序的優先次序，稱為虛活動。虛活動的工期和資源使用量都是0，實際參與活動集合是A′={a?1，…，a?n}。

D是每個活動完成所需的時間集合，D={d?0，d?1，d?2，…，d?i，…，d?n，d?n+1，0≤i≤n}，d?i是活動a?i完成所需的時間，因此d?0=0，d?n+1=0。

集合E給出了項目的優先順序關系集合。如果（a?i，a?j）∈E，意味著活動a?i必須先于活動a?j發生。

可更新資源集合為R={r?1，…，r?q}，表示有r?1，r?2，…，r?q共q種可更新資源。可更新資源的可用量在項目的每一時間段內都有約束，但消耗之后可在下一階段更新。資源的可用性由B={b?1，…b?k…，b?q，1≤k≤q}表示，b?k表示在任何時刻所有活動消耗資源r?k的最大總量。活動對于資源的需求量用W表示。w?ik表示執行活動a?i的單位時間內消耗的資源r?k的數量。單個工作日內所有作業對某一資源的需求量之和不得大于該種資源的供給上限，見式（1）?：

用s?i表示活動a?i的開始時間，c?i表示活動a?i的結束時間，因此，c?i=s?i+d?i，s?0=0，同時有s?j≥c?i，（a?i，a?j）∈E。如果設計的某個活動開始時間不滿足這個約束，則需要將開始時間延后一天繼續判斷，直到滿足這個約束為止，見式（2）。

“資源約束，工期最短”的RCPSP問題求最短工期的目標函數見式（3）。

2?算法設計

2.1?算法介紹

遺傳算法（Genetic Algorithm，GA）由密歇根大學的Holland教授[10]于1975年提出，是借鑒自然界生物進化現象發展而來的。該算法將問題可能的解隨機生成初始化種群，設定適應度函數（目標函數），將種群中的個體進行交叉（crossover）和變異（mutation）操作，根據適應度的值決定下一代種群的個體，循環操作直至達到終止條件。遺傳算法擅長解決全局最優化問題，但是解決大規模計算量問題時容易陷入“早熟”[11?12]。而由Kirkpatrick等在1983年所發明的模擬退火算法，其最大特點是易于實現、運行效率高，而且允許以一定的概率接收差解，可有效解決遺傳算法容易陷入局部最優解問題。同時遺傳算法[13]具有很強的全局搜索能力，彌補了模擬退火對于解空間覆蓋不足的缺陷，二者結合取長補短，可更有效地解決問題。

遺傳和模擬退火算法結合仍有需要改進的地方。遺傳算法每一代的種群都是隨機生成的，最終遺傳結果受初始種群影響較大，可設計一種符合資源約束的初始化種群生成方法，以保證進化一開始就是合格的個體[14?15]。遺傳算法[16]對訓練參數的依賴性較大，對參數的設定大部分依靠經驗，并沒有利用進化網絡的反饋信息，故搜索速度較慢。增加種群穩定度概念，根據實驗計算出合理的種群穩定度。當種群穩定度超過給定的穩定度值時，應用模擬退火算法，以新的種群替換當前種群[17]。

2.2?遺傳算法實現

采用活動列表方式進行染色體編碼，編碼個體為?A?j，0≤j≤n+1，表示項目中共有n+1個活動，每個活動（基因）可在滿足活動的優先順序關系約束下進行變動，這也是交叉變異操作的根據。

目標函數F（x）是滿足資源約束時完成給定活動的最小時間。編碼時僅考慮了活動的優先順序關系約束。為了避免在算法進行中有不滿足資源約束的非法個體參與[18]，在種群初始化以及交叉變異等遺傳算子操作時都要考慮資源約束。因此，這里的適應度函數f（x）直接取目標函數的倒數，即f（x）=1/F（x）。

初始化過程之前，先設定集合P=[p?1，p?2，…p?i…，p?j]，1≤i≤j是活動的后繼關系數組，p?i是活動a?i的后繼關系約束數組，該數組可由優先關系集合E求得。假設E中共有4對關于a?i的優先關系，分別是（a?i，a?j）、（a?i，a?z）、（a?i，a?w）和（a?k，a?i），由于活動a?k是先于a?i發生的，所以a?i的后繼活動有a?j、a?w和a?z，所以pi=（a?j，a?w，a?z）。種群初始化過程：假設某工程共有j個活動，給定兩個有序集合A?1和A?2，A?1是所有活動的集合，A?2是空集合：① 從集合A?1中隨機取出一個活動;② 如果活動a?i是第一個取出的活動就直接放入A?2中，返回第①步，同時將a?i從A?1中刪除，如果不是則進行③步，當取出的作業為最后一個時轉向步驟④;③ 判斷p?iA?2是否成立，如果成立，由于p?i是a?i的后繼關系集合，說明a?i的后繼關系集合中的某個元素在A?2當前的活動集合中存在，因此將a?i放在A?2中集合的最前方，以保證滿足優先順序關系集合E，同時將a?i從A?1中刪除;如果不成立，則將a?i放回A?2中不作其它操作，返回步驟①;④ 將最后的活動放入A?2中當前集合的最前方，返回A?2，結束。

種群初始化中，要判斷p?i是否包含于A?2以保證個體符合后繼數組約束關系，從集合A?1隨機取一個活動保證個體隨機生成。?遺傳算子設計如下：

（1）選用經典的輪盤賭選擇法，同時采用精英保留策略，將最優個體直接替代后代中最差的個體，保證最優個體最大程度得以保留，加快收斂速度。

（2）根據文獻的次序交叉法思想，提出一種適用于RCPSP問題的交叉算法——有序的次序交叉算法（Orderly Cross Method）。取兩個父代個體，隨機選擇兩個交叉的點?x?1和x?2?，父代一中兩點之間的部分按照對應父代二兩點之間的部分順序放入子代一中，兩點之外的部分不變，直接放入子代中，再采用相同方法產生子代二。由于子代跟父代相比變化的部分順序依照另一父代，父代完全滿足工序的緊前關系約束，因此產生的子代不會產生非法個體。需要指出的是，該方法在個體工序數較少時基因變化數目不多，類似于個體變異，因此可應用于基因數比較多的個體。

例如：

父代一：1 3 2 7 8 6 5 4 9

父代二：1 7 8 5 6 3 2 4 9

隨機取第2和第5個位置，則父代一中取出“3 2 7 8”，相應父代二的順序為“7 8 3 2”，先將父代一剩余的部分放入子代一中，則此時子代一為“1 x x x x 6 5 4 9”，取出的部分再按照父代二中的順序替代子代中“xxx”部分，則生成的子代為：

子代一：1 7 8 3 2 6 5 4 9

子代二：1 7 8 6 5 3 2 4 9

（3）變異算子。本文遺傳算子采用集中搜索策略，結合鄰域技術尋求變異的最優后代。任取兩個位置點，對兩點之間的部分進行全排列。考慮到兩點之間的個數較多，全排列產生的候選項過多會增大計算復雜度，因此此處規定兩點之間的長度為4。全排列計算有可能產生不滿足工序緊前約束的個體。將非法個體排除后，計算剩余個體適應度，選擇適應度值最高的作為新變異個體。如果全排列操作后除原本個體外全是非法個體，則重新選擇兩個位置點再次計算選擇。考慮到如果多次選擇位置點仍不能得到有效個體算法會陷入死循環，增加計算時間，因此規定重新選擇10次后仍不能得到有效個體則重新以種群初始化方式新生成一個有效個體，替代原來需要變異的個體。

當算法達到最大遺傳代數時算法終止，或者種群中個體不再發生變化時算法終止。

2.3?種群穩定度

在遺傳算法后期，平均適應度對應的個體和最大適應度個體被選擇進入下一代的概率趨于一致，容易使收斂停滯，為解決這一問題提出了種群穩定度（Population Stability，PS）概念[19]。種群穩定度（PS）指當前種群中個體適應度的離散程度，這里用方差記錄。

決定算法能否得出一個較準確的結果，PS值的確定尤為重要。選取RCPSP標準測試問題庫PSPLIB中J30數據集和J60數據集中各10組數據進行實驗，利用上文給出的遺傳算法進行計算，求出每一代的穩定度和目標值。通過多組數據多次計算可以得出，穩定度和目標值是負相關的。以j3019_5為例，穩定度和目標值兩組數據擬合的2次函數結果見式（4）。

得到的相關系數矩陣見式（5）。

擬合的圖像如圖1所示，橫坐標為穩定度，縱坐標為目標值。

從圖1很容易看出，穩定度和目標值呈負相關，即穩定度越高目標值越低，效果越優。要想獲得更優的目標值，也就是更短的工期，需要群體的穩定度更高，群體的離散程度更高，因此設定種群穩定度的指定值是種群最差的目標值所對應的穩定度的平均值。

2.4?模擬退火算法實現

仿照自然界物種滅絕的自然法則，當種群穩定度低于上節算出的平均值時，應用模擬退火操作判斷是否以新的種群替換原來的種群進行算法迭代[20]。

加入模擬退火算法步驟：

（1）在滿足條件的種群v?0鄰域內隨機選取一個可行解v?i。

（2）隨機生成[0，1]之間的雙精度型小數p。

（3）判斷由式（6）計算出的結果R（T）是否大于p，若大于則用v?i替換v?0，反之不替換。

其中，f（v?i）和f（v?0）分別為v?i和v?0的種群最小目標值，T為進化代數，由此可見R（T）是隨著T的增大而減小的，因此能使算法在進化前期更多地接受惡化解，在后期更多地接受優化解。

3?實驗設計與結果分析

3.1?實驗設計

PSGASA算法驗證采用RCPSP標準測試問題庫PSPLIB中的數據，選取j30、j60數據集，在每個數據集中隨機選取10組數據。每組數據共享4種單模式資源，每個活動用到一種或多種資源且資源可再生，即可更新資源。每組數據中詳細介紹了項目的活動與資源的需求匹配關系、資源類型及總量、活動資源需求量、活動的后繼數組關系集合以及單個活動的計劃工期等參數。

采用MATLAB語言編程。遺傳算法開始的種群規模設定為50個個體，進化代數為100代，交叉率0.8，變異率0.1，j30數據集中個體數32個（包含第一個和最后一兩個虛活動），j60數據集的個體數是62個。

3.2?結果分析

最終優化結果如表1所示。數據文件一欄是j30和j60中各自隨機選取的10組數據，初始目標值是第一次循環迭代后計算出的目標值，最優目標值是在應用PSGASA算法后再次循環迭代計算出的目標值，可以看出大部分都得到了優化。j301_3的最佳調度方法如圖2所示，其余數據由于篇幅所限不再列出。

圖3給出了應用PSGASA算法前后取得最優解時的進化代數對比。結合表1和圖3可以看出，在j30的10組數據中，有4組數據找到了更優解，4組數據持平， 3組解較差，但尋找到解的進化代數得以提前;在j60的10組數據中，有3組數據找到了更優解，6組數據持平， 1組解較差，持平的數據中尋找到解的進化代數得以提前且趨于穩定。由此可知，算法收斂性得到了加強，擴大了解空間，性能有所提高。

4?結語

PSGASA算法具有GA的全局搜索能力及SA的局部搜索能力，能使SA算法充分利用GA的全局信息，對全局解空間有詳細了解[21]。通過建立滿足資源和優先順序約束的初始種群，提出種群穩定度概念。通過實驗求得種群穩定度值，避免進化過度依賴初始參數。當種群達到一定的種群穩定度時，應用模擬退火算法判斷是否以新的種群替換原來的種群，繼續進行算法迭代，擴大解空間，找到更加準確的解。

通過實例驗證，該改進算法能在全局空間中更準確地得到更優解。需要注意的是，PAGASA算法只是在相同進化代數中加快了速度，找到更優的解，與增大進化代數相比性能要差，但后者卻需要更多的計算資源。此外，該算法只針對可更新資源，現實中有很多可更新資源與不可更新資源并存的項目，如何求單項目中兩種資源類型并存的資源工期最短問題是下一步的研究重點。

參考文獻：

[1]?CHAKRABORTTY R K， SARKER R A， ESSAM D L. Multi?mode resource constrained project scheduling under resource disruptions[J]. Computers & Chemical Engineering， 2016（88）：13?29.

[2]?DEB S， FONG S， TIAN Z， et al. Finding approximate solutions of NP?hard optimization and tsp problems using elephant search algorithm[J]. Journal of Supercomputing， 2016， 72（10）：1?33.

[3]?CHEN C， ATAMTüRK A， OREN S S. A spatial branch?and?cut method for nonconvex qcqp with bounded complex variables[J]. Mathematical Programming， 2016（6）：1?29.

[4]?ERENGUC S S，AHN T，CONWAY D G.The resource con?strained project scheduling problem with multiple crashable modes：an exact solution method[J].Naval Research Logistics，2001，48（2）：107?127.

[5]?HINDELANG T J，MUTH J F. A dynamic programming algorithm for decision CPM networks[J].Operations Research，1979，27（2）：225?241.

[6]?KOLISCH R.Efficent priority rules for the resource?constrained project scheduling problem[J].Journal of Operations Management，1996，14（3）：179?192.

[7]?李敬花，胡載萍，呂慧超，等.多資源約束下海工裝備多項目調度優化[J].哈爾濱工程大學學報，2013，34（10）：1214?1217.

[8]?ZAMANI R. A competitive magnet?based genetic algorithm for solving the resource?constrained project scheduling problem[J]. European Journal of Operational Research ，2013，229（2）：552?559.

[9]?方晨，王凌.資源約束項目調度研究綜述[J].控制與決策，2010，25（5）：641?650.

[10]?BRUCKER P， DREXL A， M¨OHRING R. Resource?constrained project scheduling： notation， classication， models， and methods[J]. European J of Operational Research， 1999， 112（1）： 3?41.

[11]?KOLISCH R.Efficent priority rules for the resource?constrained project scheduling problem[J].Journal of Operations Management，1996，14（3）：179?192.

[12]?何杰光，陳新度，陳新，等. 求解資源受限項目調度的動態多樣性進化策略[J]. 計算機集成制造系統， 2015，21（8）：2091?2093.

[13]?LIU S X，?CHEN D， WANG Y F.Memetic algorithm for multi?mode resource?constrained project scheduling problems[J].Journal of Systems Engineering and Electronics，2014，25（4）：609?617.

[14]?ZOULFAGHARI H，NEMATIAN J，MAHMOUDI N，et al.A new genetic algorithm for the RCPSP in large scale[J].International Journal of Applied Evolutionary Computation， 2013， 4 （2）：29?40.

[15]?DONG N， GE D D， FISCHER M，et al.A genetic algorithm?based method for look?ahead scheduling in the finishing phase of construction projects[J].Advanced Engineering Informatics，2012，26 （4）：737?748.

[16]?CHEN W N ，ZHANG J . Scheduling multi?mode projects under uncertainty to optimize cash flows： a Monte Carlo ant colony system approach[J].Journal of Computer Science & Technology，2012，27（5）：950?965.

[17]?梁亞瀾，聶長海. 覆蓋表生成的遺傳算法配置參數優化[J].計算機學報，2012，35（7）：1523?1526.

[18]?ZHANG G H， GAO L，?SHI Y.An effective genetic algorithm for the flexible job?shop scheduling problem[J].Expert Systems with Applications，2011，38（4）：3563?3573.

[19]?方晨，王凌.資源約束項目調度研究綜述[J].控制與決策，2010，25（5）：642?643.

[20]?GONCALVES J F，MENDES J J M，RESENDE M G C.A genetic algorithm for the resource constrained multi?project scheduling problem[J]. European Journal of Operational Research. 2008，189（3）：1171?1190.

[21]?FLESZAR K，HINDI K S.?Solving the resource?constrained project scheduling problem by a variable neighbourhood search[J]. European Journal of Operational Research，2003（2）：402?413.