一種多項目調度的改進蟻群算法研究

張勇明　陳曄　吳志飛

【摘 要】提出一種用于資源約束下多項目調度問題的改進蟻群算法，該算法基于最大最小螞蟻基礎算法，在解的構建過程中使用偽隨機比例行為選擇規則，并在每一次迭代中應用禁忌搜索算法進行局部優化。最后仿真實例表明該算法在多項目調度中有良好的優化性能。

【關鍵詞】多項目調度；蟻群算法；禁忌搜索

資源約束下多項目調度問題RCMPSP（Resource-Constrained Multi-Project Scheduling Problems）是一類重要調度問題，優化目標是有資源競爭時的多個項目的總工期最短。目前主要求解算法包括兩類：基于規則的啟發式算法[1]和智能優化算法[2]。本文針對該問題，提出一種改進的蟻群算法[3]，以最大最小螞蟻算法[4]為基礎，選擇最早可行起始時間作為螞蟻搜索的啟發式指導信息，同時對每次迭代結果引入禁忌搜索算法進一步優化。

1 RCMPSP問題蟻群算法描述

為解決蟻群算法在多項目調度問題中易陷入局部最優的問題，本文對最大最小螞蟻算法MMAS進行了改進，在解的構建過程中使用偽隨機比例行為選擇規則，并采用積極的行為選擇規則以加快算法收斂速度。在引入的禁忌搜索中采用2-opt交換局部搜索，幫助算法跳出可能的局部最優，同時通過將存在未完成緊前任務的任務和等待資源的任務加入禁忌表，能降低算法運算時間。本文提出的改進蟻群算具體迭代步驟如下：

step1： 數據初始化，包括讀入問題實例的網絡圖，初始化信息素矩陣和啟發式信息矩陣，初始化信息素的上界與下界，初始化螞蟻的記憶；

step2： 算法開始一次迭代；

step3： 一只螞蟻被分配到開始虛擬節點0開始；

step4： 當前螞蟻選擇下一個被調度的任務，其選擇規則即狀態轉移規則采用以輪盤賭（roulette wheel）選擇程序為核心的偽隨機比例選擇規則；

step5： 更新當前螞蟻的記憶，包括螞蟻當前已調度任務列表，還有螞蟻對任務的調度記憶標示，即將已調度過的任務標示為true，未調度的任務仍標示為flase；

step6： 若當前螞蟻已調度完實例中所有N個項目的D個任務，則計算當前螞蟻構建的路徑的長度，轉setp7，否則跳轉到step4；

step7： 若所有的m只螞蟻都已完成了對任務的調度，轉step8，否則跳轉step3；

step8： 針對每只螞蟻所構建的路徑，采用禁忌搜索進行局部優化；

step9：信息素的更新規則為所有信息素以同一比率蒸發，但僅允許構建出最優方案的螞蟻釋放信息素，要求所有路徑上的信息素滿足[τmin，τmax]的限制。算法的一次迭代結束；

step10： 滿足算法迭代結束條件，迭代結束，否則跳轉step2。算法迭代結束條件是連續Nd次迭代不能縮短最優方案的路徑長度即多項目的最小總工期，Nd根據算法運行時實際條件取值。

2 針對多項目調度的蟻群算法改進

2.1 狀態轉移規則

所有螞蟻都從多項目總網絡圖的源點出發，直到所有螞蟻都將所有任務調度完畢，即到達多項目總網絡圖的匯點時解的構建過程才結束，具體見上文中算法步驟的step3-step7。開始構建解時，螞蟻首先調度開始虛節點任務0，而后每經過一次迭代螞蟻就向解中添加一道未調度的任務。在螞蟻k出現在構建步驟i時，按偽隨機比例規則選擇下一道調度任務j。這個規則由如下式子給出：

其中q為均勻分布在區間[0，1]中的一個隨機變量，q0（0≤q0≤1）是一個參數，J是根據式（2）給出的概率分布產生出來的一個隨機變量（其中α=1）。

對式（1），如果q≥q0，則螞蟻k按照隨機比例規則的概率行為選擇規則來決定下一道將調度的任務，選擇任務j作為下一道調度的任務的概率為

其中ηij代表由式（3）確定的啟發式信息，而參數α針對信息素，參數β針對啟發式信息， Nik表示還沒有被螞蟻k調度的任務。選擇任務j作為后續調度任務的概率由該任務所對應的信息素τij及啟發式信息ηij決定。

其中estj是任務j的最早可行起始時間，N包含了所有到目前為止還沒有被調度的任務，并且這些未調度任務的所有緊前任務都已經被調度過了。

2.2 信息素的更新規則

信息素更新的第一個步驟是蒸發：

其中ρ是信息素的蒸發率，有0<ρ≤1。信息素蒸發后，第二個步驟信息素釋放，本文算法中只允許至今構建出最優方案的螞蟻釋放信息素，以此強調對最優路徑的開發。釋放規則如下：

算法中任意一個任務調度迭代后的信息素量的上界是1/ρC*，其中C*代表最優方案即最小總修理周期的大小?；谏鲜鼋Y論，可以使用對1/ρC*的估計值1/ρCbs來定義τmax。更新τmax值的時機為每次發現新的至今最優方案時。相應地，信息素的下界被設定為τmin=τmax/a，其中a是一個可根據需要動態取值的參數。

2.3 帶2-opt的禁忌局部搜索

為解決蟻群算法易陷入局部最優的問題，本文采用了帶2-opt的禁忌搜索TS作為局部搜索算法。禁忌搜索TS以蟻群算法每次迭代完成后形成的解作為初始解，其關鍵為鄰域的搜索和禁忌表的處理。

禁忌搜索TS中的鄰域搜索采用2-opt的搜索策略，所謂2-opt策略即用兩條邊取代原有的2兩條邊來生成解。禁忌搜索以鄰域中最好的解作為新解，它與其它優化方法不同的是即使新解劣于目前解也暫時接受，這樣能避免陷入局部最優，從而利于尋找全局最優。2-opt策略中使用了含長度限制的最近鄰列表，列表的長度L決定了算法執行時間的增長，其值大小可根據問題的規模來確定。

禁忌局部搜索的結束條件是算法搜索過程經過一定步數之后，仍不能得到改進的解，則禁忌搜索結束。

3 仿真實例

為驗證算法性能，本文采用一個模具生產實例，該實例包括3個相同網絡結構的項目，其網絡圖結構如圖1所示。

實例中共有3個項目，13種資源，48個任務。給定項目的權重系數分別為a1=0.5、a2=0.3、a3=0.2。設3個項目獨立完成時間分別為33d、43d、38d，最晚完成期限分別為48

本文算法結束條件為連續1000次迭代不能縮短最優方案的最小總工期，算法參數值為：α=1，β=3，ρ=0.02，m=50。表2中的仿真結果表明，本文改進蟻群算法對于多項目調度問題具有良好的優化性能。

4 結束語

本文針對多項目調度問題，提出一種改進蟻群算法，其以最大最小螞蟻算法為基礎，選擇最早可行起始時間作為螞蟻搜索的啟發式指導信息，并在局部搜索部分引入禁忌算法。仿真實例表明該蟻群算法對于多項目調度問題具有良好的優化性能。

【參考文獻】

[1]鄧林義，等.資源約束下多項目調度的拓撲優化方法[J].系統仿真學報，2007，19（16）：3846-3849.

[2]林晶晶，周國華.基于粒子群算法的關鍵鏈多項目調度管理[J].統計與決策，2012（10）：44-48.

[3]張軍，胡曉敏，等，譯.蟻群優化[M].北京：清華大學出版社，2007.

[4]Stuzle，T.，Hoos，H.H. MAX-MIN Ant System[J]. Future Generation Computer Systems，2000，16（8）：889-914.

[責任編輯：湯靜]