一種多項(xiàng)目調(diào)度的改進(jìn)蟻群算法研究

張勇明　陳曄　吳志飛

【摘 要】提出一種用于資源約束下多項(xiàng)目調(diào)度問題的改進(jìn)蟻群算法，該算法基于最大最小螞蟻基礎(chǔ)算法，在解的構(gòu)建過程中使用偽隨機(jī)比例行為選擇規(guī)則，并在每一次迭代中應(yīng)用禁忌搜索算法進(jìn)行局部優(yōu)化。最后仿真實(shí)例表明該算法在多項(xiàng)目調(diào)度中有良好的優(yōu)化性能。

【關(guān)鍵詞】多項(xiàng)目調(diào)度；蟻群算法；禁忌搜索

資源約束下多項(xiàng)目調(diào)度問題RCMPSP（Resource-Constrained Multi-Project Scheduling Problems）是一類重要調(diào)度問題，優(yōu)化目標(biāo)是有資源競爭時(shí)的多個(gè)項(xiàng)目的總工期最短。目前主要求解算法包括兩類：基于規(guī)則的啟發(fā)式算法[1]和智能優(yōu)化算法[2]。本文針對(duì)該問題，提出一種改進(jìn)的蟻群算法[3]，以最大最小螞蟻算法[4]為基礎(chǔ)，選擇最早可行起始時(shí)間作為螞蟻搜索的啟發(fā)式指導(dǎo)信息，同時(shí)對(duì)每次迭代結(jié)果引入禁忌搜索算法進(jìn)一步優(yōu)化。

1 RCMPSP問題蟻群算法描述

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

step1： 數(shù)據(jù)初始化，包括讀入問題實(shí)例的網(wǎng)絡(luò)圖，初始化信息素矩陣和啟發(fā)式信息矩陣，初始化信息素的上界與下界，初始化螞蟻的記憶；

step2： 算法開始一次迭代；

step3： 一只螞蟻被分配到開始虛擬節(jié)點(diǎn)0開始；

step4： 當(dāng)前螞蟻選擇下一個(gè)被調(diào)度的任務(wù)，其選擇規(guī)則即狀態(tài)轉(zhuǎn)移規(guī)則采用以輪盤賭（roulette wheel）選擇程序?yàn)楹诵牡膫坞S機(jī)比例選擇規(guī)則；

step5： 更新當(dāng)前螞蟻的記憶，包括螞蟻當(dāng)前已調(diào)度任務(wù)列表，還有螞蟻對(duì)任務(wù)的調(diào)度記憶標(biāo)示，即將已調(diào)度過的任務(wù)標(biāo)示為true，未調(diào)度的任務(wù)仍標(biāo)示為flase；

step6： 若當(dāng)前螞蟻已調(diào)度完實(shí)例中所有N個(gè)項(xiàng)目的D個(gè)任務(wù)，則計(jì)算當(dāng)前螞蟻構(gòu)建的路徑的長度，轉(zhuǎn)setp7，否則跳轉(zhuǎn)到step4；

step7： 若所有的m只螞蟻都已完成了對(duì)任務(wù)的調(diào)度，轉(zhuǎn)step8，否則跳轉(zhuǎn)step3；

step8： 針對(duì)每只螞蟻所構(gòu)建的路徑，采用禁忌搜索進(jìn)行局部優(yōu)化；

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

step10： 滿足算法迭代結(jié)束條件，迭代結(jié)束，否則跳轉(zhuǎn)step2。算法迭代結(jié)束條件是連續(xù)Nd次迭代不能縮短最優(yōu)方案的路徑長度即多項(xiàng)目的最小總工期，Nd根據(jù)算法運(yùn)行時(shí)實(shí)際條件取值。

2 針對(duì)多項(xiàng)目調(diào)度的蟻群算法改進(jìn)

2.1 狀態(tài)轉(zhuǎn)移規(guī)則

所有螞蟻都從多項(xiàng)目總網(wǎng)絡(luò)圖的源點(diǎn)出發(fā)，直到所有螞蟻都將所有任務(wù)調(diào)度完畢，即到達(dá)多項(xiàng)目總網(wǎng)絡(luò)圖的匯點(diǎn)時(shí)解的構(gòu)建過程才結(jié)束，具體見上文中算法步驟的step3-step7。開始構(gòu)建解時(shí)，螞蟻首先調(diào)度開始虛節(jié)點(diǎn)任務(wù)0，而后每經(jīng)過一次迭代螞蟻就向解中添加一道未調(diào)度的任務(wù)。在螞蟻k出現(xiàn)在構(gòu)建步驟i時(shí)，按偽隨機(jī)比例規(guī)則選擇下一道調(diào)度任務(wù)j。這個(gè)規(guī)則由如下式子給出：

其中q為均勻分布在區(qū)間[0，1]中的一個(gè)隨機(jī)變量，q0（0≤q0≤1）是一個(gè)參數(shù)，J是根據(jù)式（2）給出的概率分布產(chǎn)生出來的一個(gè)隨機(jī)變量（其中α=1）。

對(duì)式（1），如果q≥q0，則螞蟻k按照隨機(jī)比例規(guī)則的概率行為選擇規(guī)則來決定下一道將調(diào)度的任務(wù)，選擇任務(wù)j作為下一道調(diào)度的任務(wù)的概率為

其中ηij代表由式（3）確定的啟發(fā)式信息，而參數(shù)α針對(duì)信息素，參數(shù)β針對(duì)啟發(fā)式信息， Nik表示還沒有被螞蟻k調(diào)度的任務(wù)。選擇任務(wù)j作為后續(xù)調(diào)度任務(wù)的概率由該任務(wù)所對(duì)應(yīng)的信息素τij及啟發(fā)式信息ηij決定。

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

2.2 信息素的更新規(guī)則

信息素更新的第一個(gè)步驟是蒸發(fā)：

其中ρ是信息素的蒸發(fā)率，有0<ρ≤1。信息素蒸發(fā)后，第二個(gè)步驟信息素釋放，本文算法中只允許至今構(gòu)建出最優(yōu)方案的螞蟻釋放信息素，以此強(qiáng)調(diào)對(duì)最優(yōu)路徑的開發(fā)。釋放規(guī)則如下：

算法中任意一個(gè)任務(wù)調(diào)度迭代后的信息素量的上界是1/ρC*，其中C*代表最優(yōu)方案即最小總修理周期的大小。基于上述結(jié)論，可以使用對(duì)1/ρC*的估計(jì)值1/ρCbs來定義τmax。更新τmax值的時(shí)機(jī)為每次發(fā)現(xiàn)新的至今最優(yōu)方案時(shí)。相應(yīng)地，信息素的下界被設(shè)定為τmin=τmax/a，其中a是一個(gè)可根據(jù)需要?jiǎng)討B(tài)取值的參數(shù)。

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

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

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

禁忌局部搜索的結(jié)束條件是算法搜索過程經(jīng)過一定步數(shù)之后，仍不能得到改進(jìn)的解，則禁忌搜索結(jié)束。

3 仿真實(shí)例

為驗(yàn)證算法性能，本文采用一個(gè)模具生產(chǎn)實(shí)例，該實(shí)例包括3個(gè)相同網(wǎng)絡(luò)結(jié)構(gòu)的項(xiàng)目，其網(wǎng)絡(luò)圖結(jié)構(gòu)如圖1所示。

實(shí)例中共有3個(gè)項(xiàng)目，13種資源，48個(gè)任務(wù)。給定項(xiàng)目的權(quán)重系數(shù)分別為a1=0.5、a2=0.3、a3=0.2。設(shè)3個(gè)項(xiàng)目獨(dú)立完成時(shí)間分別為33d、43d、38d，最晚完成期限分別為48

本文算法結(jié)束條件為連續(xù)1000次迭代不能縮短最優(yōu)方案的最小總工期，算法參數(shù)值為：α=1，β=3，ρ=0.02，m=50。表2中的仿真結(jié)果表明，本文改進(jìn)蟻群算法對(duì)于多項(xiàng)目調(diào)度問題具有良好的優(yōu)化性能。

4 結(jié)束語

本文針對(duì)多項(xiàng)目調(diào)度問題，提出一種改進(jìn)蟻群算法，其以最大最小螞蟻算法為基礎(chǔ)，選擇最早可行起始時(shí)間作為螞蟻搜索的啟發(fā)式指導(dǎo)信息，并在局部搜索部分引入禁忌算法。仿真實(shí)例表明該蟻群算法對(duì)于多項(xiàng)目調(diào)度問題具有良好的優(yōu)化性能。

【參考文獻(xiàn)】

[1]鄧林義，等.資源約束下多項(xiàng)目調(diào)度的拓?fù)鋬?yōu)化方法[J].系統(tǒng)仿真學(xué)報(bào)，2007，19（16）：3846-3849.

[2]林晶晶，周國華.基于粒子群算法的關(guān)鍵鏈多項(xiàng)目調(diào)度管理[J].統(tǒng)計(jì)與決策，2012（10）：44-48.

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

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

[責(zé)任編輯：湯靜]