閆 森，王玉玫

(1.華北計(jì)算技術(shù)研究所系統(tǒng)三部，北京 100083； 2.華北計(jì)算技術(shù)研究所總體部，北京 100083)

0 引 言

活動(dòng)工期的不確定性和多模式問(wèn)題在項(xiàng)目調(diào)度中往往難以避免，為了如期完成任務(wù)，廠家往往通過(guò)增加資源投入來(lái)減少工期，由此產(chǎn)生了工期不確定的多模式資源約束項(xiàng)目調(diào)度問(wèn)題(Multi-mode Resource Constrained Project Scheduling Problem， MRCPSP)[1]。多模式指同一活動(dòng)的不同執(zhí)行模式會(huì)有不同的活動(dòng)工期以及相應(yīng)的資源需求量。

MRCPSP中活動(dòng)的執(zhí)行除了要受到其緊前事件的限制，還要受到多種資源的約束。MRCPSP作為一種復(fù)雜的非線性NP難問(wèn)題，很難利用精確算法[2]去求得最優(yōu)解，而啟發(fā)式算法[3-4]和智能優(yōu)化算法(遺傳算法[5-7]、模擬退火算法[8-9]、粒子群算法[10-11]和蟻群算法[12])往往能在求解精度和效率之間取得令人滿意的效果，并且因?yàn)榛顒?dòng)工期常來(lái)源于經(jīng)驗(yàn)與主觀預(yù)測(cè)，具有不準(zhǔn)確性，因此往往采取隨機(jī)任務(wù)工期的方法[13-15]。

自然界中，蟻群通過(guò)釋放信息素，指導(dǎo)后續(xù)螞蟻尋找目標(biāo)，由此概念產(chǎn)生的蟻群算法在解決NP難問(wèn)題方面功效尤為顯著[16]。Chen等[17]將云工作流調(diào)度建模為一個(gè)多目標(biāo)優(yōu)化問(wèn)題，使用2個(gè)蟻群分別處理這2個(gè)目標(biāo)，提出了一種新的信息素更新規(guī)則。Zhou等[18]提出了一種新的混合互補(bǔ)啟發(fā)式策略，該策略包含3種啟發(fā)式信息方案，以避免蟻群只關(guān)注自己的目標(biāo)。Mutar等[19]使用改進(jìn)的蟻群算法解決CVRP問(wèn)題，依賴于利用以前迭代中的子路徑經(jīng)驗(yàn)進(jìn)行的信息素更新。迄今為止，對(duì)于改進(jìn)蟻群算法的優(yōu)化研究有些單純?cè)谛畔⑺馗虏呗苑矫孢M(jìn)行改進(jìn)而忽略了其他參數(shù)的影響[17-18，20]，有些在迭代過(guò)程中不能很好地對(duì)參數(shù)進(jìn)行自適應(yīng)更新[21]，于二者的平衡問(wèn)題仍缺乏相關(guān)深入探索，有必要進(jìn)行進(jìn)一步的研究探索，加以優(yōu)化。

因此，本文基于MRCPSP問(wèn)題的特點(diǎn)，針對(duì)啟發(fā)式蟻群優(yōu)化算法收斂速度與解的質(zhì)量之間的平衡問(wèn)題，提出一種改進(jìn)的自適應(yīng)混合蟻群算法(Adaptive Hybrid Ant Colony System algorithm， AHACS)，并通過(guò)仿真實(shí)驗(yàn)結(jié)果驗(yàn)證該算法較其他算法的優(yōu)越性。針對(duì)任務(wù)工期不確定問(wèn)題，本文再基于改進(jìn)的AHACS算法，采用模糊理論的方法，為項(xiàng)目工期的不確定性預(yù)留時(shí)間緩沖區(qū)。

1 問(wèn)題建模和蟻群算法

1.1 MRCPSP問(wèn)題

采用由活動(dòng)及其可選模式組成的AOA(Activity-On-Arrow)圖的方式對(duì)MRCPSP問(wèn)題中的活動(dòng)時(shí)序約束進(jìn)行描述，可以清晰地顯示出項(xiàng)目中活動(dòng)的時(shí)序約束關(guān)系，如圖1所示。對(duì)某一活動(dòng)的正常執(zhí)行，必須滿足箭頭緊前事件執(zhí)行完成這一要求。為方便求解，引入虛事件0和N+1作為項(xiàng)目“開(kāi)始”和“結(jié)束”虛擬活動(dòng)，且只有一種執(zhí)行模式(不占用資源和執(zhí)行時(shí)間)。

圖1 AOA圖

求解MRCPSP問(wèn)題，實(shí)質(zhì)是尋求項(xiàng)目中每個(gè)活動(dòng)的執(zhí)行模式與開(kāi)工時(shí)間之間的最佳組合。問(wèn)題優(yōu)化目標(biāo)是在滿足項(xiàng)目調(diào)度問(wèn)題資源和時(shí)序條件約束下，通過(guò)合理地選擇執(zhí)行模式和時(shí)序使項(xiàng)目工期最短(網(wǎng)絡(luò)圖最短路徑)，目標(biāo)函數(shù)表達(dá)式如式(1)所示：

f(x)=Min(TN+1)

(1)

數(shù)學(xué)模型中的資源約束條件如式(2)所示，時(shí)序約束條件如式(3)所示：

(2)

(3)

其中，TN+1表示從初始任務(wù)到任務(wù)N+1所耗費(fèi)的最短工時(shí)；(i,j)表示從任務(wù)i到任務(wù)j的活動(dòng)；At表示t時(shí)刻正在進(jìn)行的活動(dòng)集合；Mij表示活動(dòng)(i,j)的可選執(zhí)行模式集合；rijkm表示以模式m執(zhí)行活動(dòng)(i,j)在單位工時(shí)內(nèi)所耗費(fèi)k類型資源的數(shù)量；Rk表示k類型資源的總量；xijm表示模式的選擇，當(dāng)活動(dòng)(i,j)使用模式m時(shí),xijm為1，否則為0；djlm表示完成活動(dòng)(j,l)的工期，P(j)表示任務(wù)j的緊前任務(wù)集合，N(j)表示事件j的后繼任務(wù)集合；如果活動(dòng)(i,j)在處于[STij,ETij]時(shí)間窗內(nèi)的時(shí)刻t被完成，則yijt為1，否則為0。

1.2 ACS算法

蟻群算法起源于自然界中蟻群尋找最短路徑的策略，螞蟻每到達(dá)岔路口時(shí)，都需要結(jié)合之前螞蟻留下來(lái)的信息素含量及貪心算法進(jìn)行道路選擇。信息素含量可以幫助每只螞蟻判斷每條路徑上走過(guò)螞蟻的數(shù)量，貪心算法則可以從候選集中篩選出距離最短的點(diǎn)。信息素以一定的概率消失，可以避免信息素過(guò)多。

在MRCPSP中，由于在相應(yīng)活動(dòng)及活動(dòng)對(duì)應(yīng)模式的選擇過(guò)程中，蟻群算法中的信息素會(huì)被釋放并且隨著迭代次數(shù)的增加而不斷更新，因此在最優(yōu)路徑(最短項(xiàng)目工期)所包含的各個(gè)路徑上信息素得以積累，這使得后繼螞蟻選擇該路徑的概率增大，并逐漸收斂到最優(yōu)路徑。

2 改進(jìn)的AHACS算法

2.1 初始化過(guò)程

初始化啟發(fā)項(xiàng)矩陣中值的大小由所選貪心策略來(lái)決定，用于記錄項(xiàng)目調(diào)度中每個(gè)活動(dòng)被選擇的概率。在MRCPSP問(wèn)題中，固有概率設(shè)為選取該活動(dòng)所需的各類型資源總量與各類資源總資源量之和的比值，計(jì)算公式如式(4)所示:

(4)

信息素是MRCPSP中后續(xù)螞蟻對(duì)路徑選擇的主要依據(jù)，本文采用信息素強(qiáng)度因子與活動(dòng)數(shù)的比值對(duì)路徑的信息素含量矩陣初始化，如式(5)所示：

(5)

引入多態(tài)蟻群思想，設(shè)置先驅(qū)偵察蟻來(lái)優(yōu)化信息素的初始化分布。當(dāng)啟發(fā)因子α、期望啟發(fā)因子β、信息素強(qiáng)度Q和信息素?fù)]發(fā)因子ρ取值較小時(shí)，蟻群算法的搜索隨機(jī)性增強(qiáng)，但收斂性變差。因此賦予偵察蟻的α、β、ρ值趨于極小，并設(shè)置適中的Q值，讓其盡可能大范圍地進(jìn)行全局搜索，這有利于增加解的多樣性，從而對(duì)信息素矩陣進(jìn)行進(jìn)一步的更新。

2.2 參數(shù)自適應(yīng)閾值與混合蟻群

啟發(fā)因子α表示信息素的重要性，期望啟發(fā)因子β表示在指導(dǎo)蟻群搜索過(guò)程中啟發(fā)式信息的相對(duì)重要程度。因此，為了優(yōu)化MRCPSP問(wèn)題中后續(xù)螞蟻對(duì)路徑(活動(dòng)時(shí)序和模式)的選擇策略，更好地平衡解的多樣性與收斂速度，算法前期應(yīng)該盡量搜索整個(gè)解值空間，α、Q應(yīng)趨于極小值，而β、1-ρ應(yīng)趨于極大值；算法后期則應(yīng)加強(qiáng)正反饋?zhàn)饔脧亩涌焓諗康乃俣?，α、Q應(yīng)趨于極大值，β、1-ρ應(yīng)趨于極小值[21]。螞蟻參數(shù)均在自適應(yīng)調(diào)整后的閾值區(qū)間內(nèi)隨機(jī)取得，形成每只螞蟻參數(shù)不同的混合蟻群。對(duì)于第t次迭代的第i只螞蟻，其α、β取值如式(6)、式(7)所示。

αi(t)=random(αmin(t),αmax(t))

(6)

βi(t)=random(βmin(t),βmax(t))

(7)

算法初期，考慮到需要在一定的迭代次數(shù)內(nèi)保證算法擁有足夠的全局搜索能力，避免算法陷入局部最優(yōu)，參數(shù)的自適應(yīng)增量應(yīng)較??；算法迭代后期，α、β的取值對(duì)算法解的質(zhì)量影響越發(fā)弱化，因此應(yīng)加快參數(shù)調(diào)整速度以促進(jìn)算法的收斂速度加快，這個(gè)過(guò)程如式(8)、式(9)所示：

(8)

(9)

算法迭代后期，一味增加全局搜索能力不僅沒(méi)有必要，而且會(huì)嚴(yán)重影響算法收斂速度，故應(yīng)調(diào)整相關(guān)參數(shù)，推動(dòng)整個(gè)算法的收斂。

采取傳統(tǒng)的輪盤(pán)賭方式作為狀態(tài)轉(zhuǎn)移策略，根據(jù)當(dāng)前活動(dòng)的啟發(fā)項(xiàng)信息和信息素含量進(jìn)行綜合考慮，決定螞蟻下一活動(dòng)的選取概率，計(jì)算公式如式(10)所示：

(10)

2.3 信息素?fù)]發(fā)因子改進(jìn)

改進(jìn)信息素?fù)]發(fā)因子能夠控制算法正反饋過(guò)程，優(yōu)化信息素更新策略。當(dāng)ρ取值越大，全局搜索能力也隨之變小，但收斂速度快；取值越小，收斂速度減慢，但全局搜索能力增強(qiáng)。本文所研究的算法，對(duì)每次迭代中ρ的取值都限制在(ρmin,ρmax)內(nèi)隨機(jī)取值，如式(11)所示。ρmax的取值隨著迭代次數(shù)的增加自適應(yīng)調(diào)整，如式(12)所示。ρ在范圍內(nèi)隨機(jī)取值，可以避免其調(diào)整過(guò)程中出現(xiàn)ρ過(guò)快趨近于ρmin，最終導(dǎo)致某條路徑信息素強(qiáng)度過(guò)大。

ρ(t)=random(ρmin(t),ρmax(t))

(11)

(12)

2.4 信息素更新策略改進(jìn)

精英螞蟻策略中，對(duì)每輪迭代中精英螞蟻(全局最優(yōu)螞蟻)路徑上的信息素進(jìn)行自適應(yīng)獎(jiǎng)勵(lì)，以增加該路徑被選擇的概率[20]。本文在此基礎(chǔ)上做出進(jìn)一步優(yōu)化，引入排名因子對(duì)應(yīng)權(quán)重值μ，以賦予排名靠前的螞蟻更高的權(quán)重。螞蟻更新信息素含量的策略中按排名因子規(guī)則引入相應(yīng)的權(quán)重值μ，如式(13)所示。這種改進(jìn)不僅是為了提高發(fā)現(xiàn)更優(yōu)路徑螞蟻的話語(yǔ)權(quán)，還可以避免落后的經(jīng)驗(yàn)形成自鎖或壓制更優(yōu)解的產(chǎn)生。為防止最優(yōu)路徑被遺忘，每輪迭代中的最優(yōu)路徑劣于目前發(fā)現(xiàn)的全局最優(yōu)路徑時(shí)，將全局最優(yōu)路徑排到首位，以保證最優(yōu)路徑在被更優(yōu)的路徑取代之前不會(huì)被遺忘。

(13)

局部信息素的更新以及精英螞蟻的選取，可能令信息素含量過(guò)大而導(dǎo)致算法過(guò)早停滯。針對(duì)這一問(wèn)題，本文參考最大最小蟻群算法(MMAS)[22]的思想，定義信息素含量上下限的概念，信息素上限如式(14)所示。在算法運(yùn)行后期，可以通過(guò)提高信息素上限，實(shí)現(xiàn)加速收斂。設(shè)定信息素上下限，能夠有效增強(qiáng)蟻群的全局搜索能力，對(duì)提升解的質(zhì)量有一定幫助。

(14)

2.5 信息素強(qiáng)度系數(shù)改進(jìn)

AHACS算法中信息素強(qiáng)度Q的取值會(huì)在信息素更新過(guò)程中逐漸增大。當(dāng)Q的取值較大時(shí)，會(huì)導(dǎo)致算法過(guò)早陷入局部最優(yōu)解；取值較小時(shí)，會(huì)拖慢算法收斂速度。綜合考慮，在算法運(yùn)行的初期，Q應(yīng)該取較小值，以增強(qiáng)全局搜索能力；算法運(yùn)行到后期時(shí)，自適應(yīng)選擇較大的Q值，從而加快算法收斂速度。因此，可在算法中用式(15)所示的線性函數(shù)代替常數(shù)信息素強(qiáng)度。

(15)

3 仿真實(shí)驗(yàn)

3.1 AHACS算法解決MRCPSP問(wèn)題

本文在文獻(xiàn)[23]的基礎(chǔ)上產(chǎn)生多組數(shù)據(jù)集驗(yàn)證算法的有效性，為了便于凸顯比較結(jié)果，選擇如圖2所示的24事件37活動(dòng)的較大規(guī)模的項(xiàng)目調(diào)度數(shù)據(jù)集，來(lái)對(duì)比驗(yàn)證AHACS算法在解決MRCPSP問(wèn)題上的有效性，使用PyCharm進(jìn)行仿真實(shí)驗(yàn)。引入3種可動(dòng)態(tài)調(diào)度的資源R1、R2和R3，單位工期的可使用數(shù)量上限分別設(shè)為8、16和20。除0與N+1活動(dòng)外，項(xiàng)目中每個(gè)活動(dòng)包括普通工期模式(N)和資源換工期的壓縮工期模式(C)這2種可執(zhí)行模式。

圖2 AOA仿真圖

仿真實(shí)驗(yàn)分別將AHACS算法與自適應(yīng)調(diào)整信息素?fù)]發(fā)系數(shù)的QAACO算法[24]、帶有局部更新策略和精英螞蟻系統(tǒng)(EAS)的EACS算法[12]和遺傳算法(GA)[5]在項(xiàng)目調(diào)度數(shù)據(jù)集上執(zhí)行20次，求解最優(yōu)目標(biāo)函數(shù)，并對(duì)所得結(jié)果進(jìn)行對(duì)比。經(jīng)過(guò)大量的重復(fù)實(shí)驗(yàn)，將迭代次數(shù)上限均定為400。其中EACS算法將初始參數(shù)α、β、ρ分別設(shè)置為1、3、0.3，QAACO算法中ρ的上下限分別為0.6和0.1，GA算法中變異概率和交叉概率分別為0.01和0.6。

AHACS算法實(shí)驗(yàn)中參數(shù)初始化如表1所示。

表1 AHACS參數(shù)初始化

統(tǒng)計(jì)結(jié)果中總體偏差值的計(jì)算公式如式(16)所示：

(16)

4種算法在項(xiàng)目調(diào)度數(shù)據(jù)集上分別執(zhí)行20次，記錄的實(shí)驗(yàn)仿真數(shù)據(jù)如表2所示。

表2 實(shí)驗(yàn)仿真數(shù)據(jù)

實(shí)驗(yàn)求得最優(yōu)解的迭代次數(shù)如圖3所示。由于算法前期擁有較強(qiáng)全局搜索能力時(shí)，算法多樣性高，解集范圍大，在較少的迭代次數(shù)內(nèi)找到較優(yōu)路徑集合的可能性就大。因此由實(shí)驗(yàn)結(jié)果可知，AHACS算法最早在第24次就找到了最終輸出的最優(yōu)解，收斂速度更快，而GA算法在較少的迭代次數(shù)得到的解的質(zhì)量較差，容易早熟。比較算法的最少迭代次數(shù)和平均迭代次數(shù)，AHACS算法也同樣優(yōu)于QAACO算法和EACS算法。

20次仿真實(shí)驗(yàn)中，AHACS算法最優(yōu)解出現(xiàn)101和102，找到了另外3種算法沒(méi)有求得的更優(yōu)解，說(shuō)明其擁有更強(qiáng)的全局尋優(yōu)能力，使得解標(biāo)準(zhǔn)差較其他3種算法更大。無(wú)論是從最優(yōu)解或者是最差解的角度來(lái)看，AHACS算法都優(yōu)于另外3種算法。同時(shí)，相比QAACO算法、EACS算法和GA算法，AHACS算法最優(yōu)解平均值分別提高了1.4%、1.2%和0.7%。相比于QAACO算法和EACS算法，AHACS算法運(yùn)行20次的總時(shí)長(zhǎng)分別縮短了20.3%和13.7%。而GA算法在小規(guī)模數(shù)據(jù)集中效果較好[5]，但在本文數(shù)據(jù)集上會(huì)出現(xiàn)編碼長(zhǎng)、運(yùn)行時(shí)間久的問(wèn)題，性能較差。因此總體來(lái)說(shuō)，AHACS算法相比于其他3種算法，在優(yōu)化收斂速度的同時(shí)能有效跳出局部最優(yōu)，成功提高了最終解的質(zhì)量。

(a) QAACO

(b) EACS

(c) AHACS

(d) GA

3.2 工期不確定MRCPSP問(wèn)題

第3.1節(jié)對(duì)MRCPSP問(wèn)題的研究與仿真以活動(dòng)工期確定為前提，往往很難與實(shí)際情況相吻合。事實(shí)上活動(dòng)工期往往是人為估計(jì)的，具有不精確的特點(diǎn)。因此，本文參考模糊理論中的相關(guān)概念[25]，采用模糊任務(wù)工期的三點(diǎn)估計(jì)法以解決MRCPSP問(wèn)題中的工期不確定問(wèn)題。

三點(diǎn)估計(jì)法是不確定環(huán)境下常用的活動(dòng)工期估計(jì)方法，應(yīng)用概率的方法估算項(xiàng)目完成的樂(lè)觀工期a、最可能工期m和悲觀工期b，隨后計(jì)算項(xiàng)目工期的估計(jì)值和標(biāo)準(zhǔn)差。樂(lè)觀工期和工期時(shí)間之間形成了一個(gè)時(shí)間緩沖區(qū)，這就為項(xiàng)目工期的不確定性預(yù)留了時(shí)間緩沖，可以作為工期不確定MRCPSP問(wèn)題最短工時(shí)的參考范圍。項(xiàng)目工期估計(jì)值用me表示，計(jì)算方法如式(17)所示：

(17)

為使研究成果更具有普適性，本文放寬了約束條件，不假設(shè)活動(dòng)工期服從特定的概率分布。對(duì)于項(xiàng)目調(diào)度中每個(gè)活動(dòng)工期不確定的問(wèn)題，以第3.1節(jié)中項(xiàng)目調(diào)度數(shù)據(jù)集的活動(dòng)工期為中心(基準(zhǔn))，隨機(jī)生成每個(gè)活動(dòng)的樂(lè)觀工期和悲觀工期，并以二者均值作為活動(dòng)最可能工期。三點(diǎn)估計(jì)法中，可以將區(qū)間數(shù)看作2點(diǎn)模糊數(shù)，表示為a=(amin,amax)，2個(gè)區(qū)間數(shù)的極大值如式(18)所示，2個(gè)區(qū)間數(shù)的極小值如式(19)所示：

max(a,b)=(max(amin,bmin),max(amax,bmax))

(18)

min(a,b)=(min(amin,bmin),min(amax,bmax))

(19)

表3 模糊工期實(shí)驗(yàn)仿真數(shù)據(jù)

4種算法在項(xiàng)目調(diào)度數(shù)據(jù)集上分別執(zhí)行20次求解工期模糊區(qū)間和估計(jì)值，分別記錄4種算法運(yùn)行結(jié)果工期估計(jì)值me的最優(yōu)值、最差值、平均值和總體標(biāo)準(zhǔn)偏差，以及模糊區(qū)間的極大值和極小值。將所記錄的實(shí)驗(yàn)仿真數(shù)據(jù)繪制成表，如表3所示。從me的計(jì)算結(jié)果以及模糊區(qū)間數(shù)的極大值和極小值來(lái)看，在模糊任務(wù)工期的情況下，AHACS算法仍能得到比另外3種算法更優(yōu)的解。

AHACS算法對(duì)項(xiàng)目工期的平均工期估計(jì)值和根據(jù)基準(zhǔn)活動(dòng)工期求得的項(xiàng)目平均工期誤差約為1.20%，并且模糊區(qū)間最大值和最小值分別為(92,127)和(84,120)，均包含了第3.1節(jié)中求得的全部可能的最短項(xiàng)目工期，因此認(rèn)為使用三點(diǎn)估計(jì)法求得的模糊工期估計(jì)值和模糊區(qū)間數(shù)可有效地應(yīng)對(duì)各種不確定因素對(duì)項(xiàng)目工期的影響。

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

針對(duì)MRCPSP問(wèn)題的特點(diǎn)，通過(guò)對(duì)蟻群算法的學(xué)習(xí)，本文提出了一種自適應(yīng)混合蟻群算法(AHACS)，創(chuàng)新參數(shù)自適應(yīng)策略和混合機(jī)制，引入信息素上下限的概念，先驅(qū)偵查蟻思想和精英蟻群系統(tǒng)排名獎(jiǎng)勵(lì)機(jī)制。仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)的AHACS算法能有效平衡解的多樣性和收斂速度之間的關(guān)系。同時(shí)，面對(duì)MRCPSP問(wèn)題中工期不確定的情況，基于模糊理論中的三點(diǎn)估計(jì)法求解項(xiàng)目工期估計(jì)值和模糊區(qū)間，使項(xiàng)目調(diào)度更加靈活。分析發(fā)現(xiàn)本算法能夠較好地解決工期不確定的MRCPSP問(wèn)題，具備有效性和可行性，因此AHACS算法能夠有效地應(yīng)用到實(shí)際問(wèn)題中，擁有廣闊的應(yīng)用空間。