面向資源約束項(xiàng)目調(diào)度的二階段帝國競爭算法

李 斌，黃起彬

1.福建理工大學(xué) 機(jī)械與汽車工程學(xué)院，福州 350118

2.福建理工大學(xué) 福建省大數(shù)據(jù)挖掘與應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室，福州 350118

3.福建理工大學(xué) 交通運(yùn)輸學(xué)院，福州 350118

資源約束項(xiàng)目調(diào)度問題（resource-constrained project scheduling problem，RCPSP）[1]研究的是如何在有限資源和優(yōu)先級(jí)關(guān)系的約束下尋求最佳的活動(dòng)調(diào)度計(jì)劃，以期實(shí)現(xiàn)項(xiàng)目工期的最小化。該類問題是調(diào)度領(lǐng)域中最為經(jīng)典且最具挑戰(zhàn)性的組合優(yōu)化問題之一，許多工程應(yīng)用問題本質(zhì)上都可歸結(jié)為資源約束項(xiàng)目調(diào)度問題，如建筑業(yè)、流水工作車間和裝配生產(chǎn)調(diào)度等，長久以來一直是學(xué)術(shù)界和工程應(yīng)用研究的重要課題[2-3]。

精確算法、啟發(fā)式算法和元啟發(fā)式算法是當(dāng)前研究和應(yīng)用中最主要的三類優(yōu)化方法[4]。精確算法，如分支定界法[5]、關(guān)鍵路徑法[6]和整數(shù)線性規(guī)劃[7]等，可精確地求得實(shí)例問題的最優(yōu)解，但由于其較高的計(jì)算成本，僅在小規(guī)模實(shí)例上具有競爭力[8]。啟發(fā)式算法主要分為基于優(yōu)先級(jí)規(guī)則的啟發(fā)式[9]和基于鄰域搜索策略的啟發(fā)式[10]兩類，其最大的優(yōu)勢是能夠以較少的計(jì)算成本獲取較高質(zhì)量的解決方案，但單種啟發(fā)式算法適用的問題類型較為有限[11]。元啟發(fā)式算法，如群聚智能算法[12]和進(jìn)化算法[13]等，有著更為出色的優(yōu)化精度和廣泛的適用性，以及強(qiáng)大的可拓展性，近年來更多地受到國內(nèi)外專家學(xué)者們的關(guān)注[8]。本文提出的二階段演化帝國競爭算法（two-stage evolutionary imperialist competitive algorithm，TSE-ICA）正是一種能夠利用小規(guī)模種群有效求解經(jīng)典RCPSP的元啟發(fā)式算法。

TSE-ICA將整個(gè)演化過程分為兩個(gè)階段，分別以種群多樣性的開發(fā)和高效的收斂為前后兩階段的搜索重點(diǎn)。該算法以探索階段開始，采用基于關(guān)鍵路徑法的組塊提取策略構(gòu)建組塊間同化算子，對(duì)精簡后的搜索空間進(jìn)行廣泛勘探；隨后的深度挖掘階段，采用一種結(jié)合相同元素保留策略的組塊間同化算子，將優(yōu)化問題劃分為多個(gè)以組塊內(nèi)最優(yōu)為目標(biāo)的子問題，實(shí)現(xiàn)收斂過程穩(wěn)步且高效的推進(jìn)。組塊提取策略同樣被用于革命機(jī)制，兩種基于子問題的鄰域搜索策略被用于增強(qiáng)種群的搜索效率和幫助算法跳出局部最優(yōu)。同時(shí)，帝國競爭機(jī)制通過交互各帝國之間的收斂信息，自適應(yīng)地為各帝國調(diào)整同化參數(shù)。最后，記憶庫[3]作為一種有效的收斂輔助工具被用于提高種群的進(jìn)化速率。

為了系統(tǒng)性地驗(yàn)證TSE-ICA對(duì)經(jīng)典RCPSP的求解能力，本文選擇PSPLIB（project scheduling library）[14]中的實(shí)例集J30、J60和J120進(jìn)行數(shù)值實(shí)驗(yàn)。首先，采用Taguchi法[15]確定TSE-ICA面對(duì)不同實(shí)例集時(shí)的最佳參數(shù)設(shè)置。接著，基于PSPLIB提供的當(dāng)前已知最優(yōu)解得到的實(shí)驗(yàn)結(jié)果，與3 種基于帝國競爭算法（imperialist competitive algorithm，ICA）的同源改進(jìn)算法和其他3種先進(jìn)的元啟發(fā)式算法對(duì)比，來驗(yàn)證改進(jìn)機(jī)制的有效性和運(yùn)行效率。最后，基于關(guān)鍵路徑值求得的實(shí)驗(yàn)數(shù)值，與11 種著名的優(yōu)化算法進(jìn)行對(duì)比，初步說明了TSE-ICA的適用性和優(yōu)化能力。

1 問題描述

RCPSP中，單個(gè)項(xiàng)目是由一個(gè)活動(dòng)集合J、一個(gè)代表活動(dòng)執(zhí)行優(yōu)先級(jí)的緊前關(guān)系集合Pr和一個(gè)資源集合K構(gòu)成。活動(dòng)集合J中包含n+2 個(gè)活動(dòng)，任一活動(dòng)j（j=1,2,…,n+2）都有一個(gè)緊前活動(dòng)集合Prj、工期dj和開始時(shí)間sj，以及執(zhí)行過程中對(duì)第k類資源的占用量rjk（k=1,2,…,K）。第k類資源的總量上限記為Rk（k∈K）。其中，活動(dòng)1和活動(dòng)n+2 為虛擬活動(dòng)，不消耗時(shí)間和資源，用以標(biāo)記項(xiàng)目的開始與結(jié)束，故d1+dn+2=0，r1k=r(n+2)k=0（k=1,2,…,K）。

RCPSP的數(shù)學(xué)模型如下：

目標(biāo)函數(shù)（1）是最小化項(xiàng)目完成時(shí)間，活動(dòng)n+2的結(jié)束時(shí)間（FTn+2）即是項(xiàng)目完成時(shí)間；約束（2）為優(yōu)先級(jí)約束，任一活動(dòng)的開始時(shí)間大于或等于所有緊前活動(dòng)的結(jié)束時(shí)間；約束（3）為資源限制，任一時(shí)刻的資源占用量不得超過可用資源上限，其中集合A(t)包含t時(shí)刻所有正在執(zhí)行的活動(dòng)；約束（4）表示任一活動(dòng)的開始時(shí)間都不為負(fù)數(shù)。

項(xiàng)目常用一個(gè)AoN（activity-on-node）有向網(wǎng)絡(luò)圖G=(N,A)來表示。節(jié)點(diǎn)集合N對(duì)應(yīng)n+2 個(gè)活動(dòng)，連接集合A對(duì)應(yīng)活動(dòng)間的緊前關(guān)系。圖1是一個(gè)由9個(gè)活動(dòng)組成的RCPSP示例，其僅涉及1類資源，該資源為可再生資源[14]且占用上限為8個(gè)資源單位。圖2為該示例的最佳調(diào)度計(jì)劃，對(duì)應(yīng)的最短項(xiàng)目工期為13個(gè)時(shí)間單位。

圖1 RCPSP實(shí)例Fig.1 RCPSP example

圖2 RCPSP示例的最優(yōu)解決方案Fig.2 Optimal solution of RCPSP example

2 相關(guān)工作回顧

2.1 基于元啟發(fā)式的優(yōu)化方法

2.1.1 概述

元啟發(fā)式算法具有優(yōu)秀的探索尋優(yōu)能力，但其算法設(shè)計(jì)和實(shí)現(xiàn)中也存在三個(gè)需要克服的困難：（1）元啟發(fā)式算法的隨機(jī)搜索特性令其難以保證求得精確解，盡管當(dāng)前已有不少相關(guān)算法展現(xiàn)出了強(qiáng)大的優(yōu)化能力，但它們在開放實(shí)例庫上的求解精度依然與最優(yōu)解下限或理論最優(yōu)解有一定差距；（2）元啟發(fā)式算法的求解精度與計(jì)算耗時(shí)往往難以兼顧，二者符合“沒有免費(fèi)的午餐定律”（no-free-lunch theorem）[16]；（3）元啟發(fā)式算法的參數(shù)敏感性使其面對(duì)不同規(guī)模或特性的問題時(shí)需要頻繁地調(diào)整參數(shù)來維持算法的魯棒性。

針對(duì)上述挑戰(zhàn)，基于元啟發(fā)式的混合型算法（hybrids）[3]框架在近二十年來獲得飛速發(fā)展。通常，一種混合型算法框架內(nèi)同時(shí)包含多種算法、搜索算子或優(yōu)化技術(shù)，因此構(gòu)造一個(gè)混合型算法往往運(yùn)用到多種方法。典型的構(gòu)造方法有：（1）超啟發(fā)式，用一種高層啟發(fā)式對(duì)多種底層算法進(jìn)行選擇[17-19]；（2）混合算法，將多種元啟發(fā)式算法結(jié)合[20-22]；（3）多重算子，為算法引入其他的啟發(fā)式或元啟發(fā)式搜索算子[23-25]；（4）異構(gòu)算子，改變搜索算子的演化行為[26-27]；（5）異構(gòu)算法，改進(jìn)算法的演化框架[28-31]。這些方法使得演化種群能夠在迭代過程中采取合適的搜索方式，以滿足不同演化階段下對(duì)種群多樣性或收斂性能的需求[28]。但是，算法框架的復(fù)雜化是計(jì)算成本增加的重要原因之一。對(duì)于這一問題，不少專家學(xué)者選擇通過設(shè)置較小的種群規(guī)模來平衡算法的計(jì)算復(fù)雜度[4]。

接下來，本節(jié)將回顧國內(nèi)外學(xué)者如何基于各類經(jīng)典的元啟發(fā)式算法實(shí)現(xiàn)混合型算法框架的構(gòu)建，以求解RCPSP及其衍生問題。

2.1.2 進(jìn)化算法

Kadri等[26]提出一種能有效求解多模式RCPSP的遺傳算法（genetic algorithm，GA），通過將優(yōu)先級(jí)規(guī)則與基于遺憾值的有偏取樣策略[10]結(jié)合，生成高質(zhì)量的初始種群，同時(shí)采用一種改進(jìn)的兩點(diǎn)交叉算子以更加適用RCPSP 的求解。Sallam 等[28]將整個(gè)迭代過程分為以種群多樣性與局部收斂為主要搜索目標(biāo)的前后兩個(gè)階段，提出一種兩階段、多算子的差分進(jìn)化算法（differential evolution，DE），該算法在每個(gè)階段設(shè)置兩種差分進(jìn)化算子，并根據(jù)不同算子對(duì)多樣性和收斂的貢獻(xiàn)程度對(duì)搜索算子進(jìn)行選擇。項(xiàng)前等[29]提出一種差分進(jìn)化參數(shù)控制及雙向調(diào)度算法，在差分進(jìn)化算法的基礎(chǔ)上加入自適應(yīng)參數(shù)控制策略、正逆向交替調(diào)度優(yōu)化（forward-backward improvement，F(xiàn)BI）[32]策略和一種保留精英個(gè)體的種群隨機(jī)重建策略，以盡可能滿足RCPSP對(duì)算法性能的要求。

2.1.3 群集智能算法

Dang 等[30]為了避免算法后期陷入局部最優(yōu)，在粒子群優(yōu)化算法（particle swarm optimization，PSO）中引入一種遷移策略，該策略能夠?qū)⑹諗客姆N群轉(zhuǎn)移至新的區(qū)域探索，以此跳出局部最優(yōu)。Chen等[23]為了加快PSO算法對(duì)最優(yōu)解的搜索效率，對(duì)每次迭代產(chǎn)生的新個(gè)體執(zhí)行活動(dòng)延遲鄰域搜索策略和FBI，通過提高種群對(duì)解空間的取樣數(shù)量，提高算法尋得最優(yōu)解的概率。安曉亭等[24]首先對(duì)蟻群算法（ant colony optimization，ACO）進(jìn)行適應(yīng)性改進(jìn)并求得Pareto 解集，接著利用帶邏輯約束的insert 和swap局部搜索啟發(fā)式對(duì)當(dāng)前種群中的非支配解進(jìn)行鄰域搜索。Ziarati 等[25]同時(shí)對(duì)蜜蜂算法（bee algorithm，BA）、人工蜂群（artificial bee colony，ABC）算法和蜂群優(yōu)化（bee swarm optimization，BSO）算法拓展三種局部搜索策略，并通過實(shí)例集J30、J60、J90和J120的測試實(shí)驗(yàn)證明結(jié)合了FBI 的BSO 是實(shí)驗(yàn)所涉算法中優(yōu)化性能最好的變種算法。

2.1.4 混合算法

Myszkowski 等[20]提出一種將差分進(jìn)化算法與貪婪局部搜索（greedy local search，GLS）算法結(jié)合的混合算法，該算法通過由DE 產(chǎn)生子代，再由基于GLS的調(diào)度生成策略為子代個(gè)體生成最優(yōu)的調(diào)度計(jì)劃。Tian等[21]采用相同思路，采用GA生成子代，然后混合一種基于多目標(biāo)馬爾可夫網(wǎng)絡(luò)的分布估計(jì)算法（estimation of distribution algorithm，EDA），為子代建立資源分配模型，進(jìn)而幫助每個(gè)子代個(gè)體獲得最優(yōu)的調(diào)度計(jì)劃。Bagherinejad等[22]提出一種新型混合算法，將非支配排序蟻群優(yōu)化（non-dominated sorting ACO）算法與GA 相結(jié)合，以實(shí)現(xiàn)對(duì)具有時(shí)間不確定性的RCPSP的魯棒調(diào)度。

2.1.5 基于元啟發(fā)式的超啟發(fā)式算法

結(jié)構(gòu)較為簡單的超啟發(fā)式算法根據(jù)概率隨機(jī)選擇底層算法。Elsayed 等[4]以多算子遺傳算法和多算子差分進(jìn)化算法為底層算法，構(gòu)建一種通過自適應(yīng)概率系數(shù)對(duì)4 種底層搜索算子進(jìn)行選擇的超啟發(fā)式算法COA（consolidated optimization algorithm）。COA將迭代過程分為多個(gè)周期，每一周期開始前會(huì)重新選擇搜索算子，而每種搜索算子的被選擇概率會(huì)根據(jù)之前的收斂表現(xiàn)進(jìn)行適用性調(diào)整。

基于強(qiáng)化學(xué)習(xí)的超啟發(fā)式，通過深度學(xué)習(xí)技術(shù)不斷學(xué)習(xí)底層算法在執(zhí)行過程中的歷史表現(xiàn)，以決定每一種底層算法在下一決策點(diǎn)被選擇的概率。Sallam等[17]以多算子差分進(jìn)化算法和禁忌搜索（cuckoo search，CS）為底層算法，提出一種基于強(qiáng)化學(xué)習(xí)策略的超啟發(fā)式算法DECSwRL-CC（DE and CS with reinforcement learning with chance constrained）。

還有一種常見的超啟發(fā)式設(shè)計(jì)范式，是將底層算法的選擇優(yōu)先級(jí)視作優(yōu)化問題，以元啟發(fā)式算法作為高層算法對(duì)其進(jìn)行求解。Koulinas 等[18]提出一種基于粒子群優(yōu)化算法的超啟發(fā)式算法，采用PSO對(duì)8 種啟發(fā)式搜索算子進(jìn)行選擇；Chand 等[19]提出了以9種優(yōu)先級(jí)規(guī)則為底層架構(gòu)的遺傳規(guī)劃超啟發(fā)式，利用GA 的交叉算子和變異算子挑選適合求解當(dāng)前問題的優(yōu)先級(jí)規(guī)則。

2.1.6 面向RCPSP的其他典型算法改進(jìn)

Wang 等[27]針對(duì)RCPSP 提出一種混合估計(jì)分布算法，采用一種新型概率模型更新機(jī)制對(duì)有挖掘潛力的搜索區(qū)域進(jìn)行更好的采樣，同時(shí)還引入FBI和基于置換的局部搜索策略來增強(qiáng)算法的收斂能力。Bouleimen等[31]利用兩種鄰域搜索策略改進(jìn)模擬退火（simulated annealing，SA）算法，新算法可用于標(biāo)準(zhǔn)RCPSP 和多模式RCPSP 的求解。但是，Wang 和Bouleimen 等提出的這兩種算法都沒能對(duì)標(biāo)準(zhǔn)實(shí)例庫PSPLIB的實(shí)例問題提出較有競爭力的解決方案。

2.2 帝國競爭算法

2.2.1 帝國競爭算法概述

ICA 是由Atashpaz-Gargari 和Lucas 于2007 年提出的一種群集智能算法[33]，其計(jì)算流程如算法1 所示。首先，生成一個(gè)個(gè)體規(guī)模為NP的初始種群Pop0={Xi|i=1,2,…,NP}，其中Xi為個(gè)體矢量，對(duì)應(yīng)優(yōu)化問題的一個(gè)可行解，Xi的成本值（即適應(yīng)度）為f(Xi)。挑選Pop0中成本值最低的Nimp個(gè)解作為帝國主義國家，其余解則作為殖民地分配給各帝國主義國家，組成多個(gè)帝國。隨后，各帝國在迭代過程中循環(huán)執(zhí)行同化、革命、交換和競爭四種機(jī)制。失去所有殖民地的帝國將會(huì)消亡。當(dāng)種群中僅剩一個(gè)帝國或算法達(dá)到最大迭代數(shù)時(shí)，結(jié)束運(yùn)行，輸出種群中的最優(yōu)個(gè)體。

算法1帝國競爭算法

輸入：帝國競爭算法參數(shù)（NP,Nimp,β,γ,UR）。

輸出：種群中的最優(yōu)個(gè)體Xbest。

步驟1隨機(jī)生成一個(gè)規(guī)模為NP的初始種群Pop0。

步驟2帝國劃分。Pop0中最優(yōu)的Nimp個(gè)解成為帝國主義國家，計(jì)算和比較各帝國主義國家的歸一化成本值cˉ，任一帝國e可獲得的殖民地?cái)?shù)量為Ncole（e=1,2,…,Nimp）。

步驟3同化。所有帝國內(nèi)，殖民地根據(jù)β和γ向其隸屬的帝國主義國家所在區(qū)域移動(dòng)。

步驟4革命。為帝國內(nèi)的每一個(gè)殖民地生成一個(gè)0到1之間的隨機(jī)數(shù)ri，ri小于UR的殖民地將被重新隨機(jī)生成（i=1,2,…,Ncole）。

步驟5交換。帝國中成本值最低的國家成為該帝國的帝國主義國家。

步驟6競爭。歸一化總成本值最小的帝國將其最弱的殖民地供給其余帝國爭奪，計(jì)算其余帝國的勢力POWe=[-re]，勢力最大的帝國獲得該殖民地。

步驟7算法達(dá)到終止條件前重復(fù)執(zhí)行步驟3至步驟6。

ICA中，帝國所代表的子種群之間屬于平行合作[3]關(guān)系。帝國內(nèi)部通過同化、革命和交換三個(gè)機(jī)制進(jìn)行演化，帝國間的交互由競爭機(jī)制完成。同化機(jī)制中，殖民地根據(jù)同化系數(shù)β和同化偏移角γ向其隸屬的帝國主義國家移動(dòng)，以通過對(duì)帝國主義國家鄰域的大量采樣實(shí)現(xiàn)搜索區(qū)域的快速收斂。根據(jù)革命概率UR，革命機(jī)制會(huì)重置部分殖民地的個(gè)體編碼，幫助種群保持多樣性。交換機(jī)制確保每輪迭代開始時(shí)帝國主義國家是帝國內(nèi)部成本值最低的個(gè)體。競爭機(jī)制根據(jù)各帝國的總成本值TC（total cost），通過將弱勢帝國的最弱殖民地轉(zhuǎn)移給演化效益更高的帝國，來強(qiáng)化種群對(duì)關(guān)鍵區(qū)域的收斂效率。更詳細(xì)的算法流程和參數(shù)說明請(qǐng)查閱文獻(xiàn)[34]。

2.2.2 帝國競爭算法在調(diào)度問題中的應(yīng)用

目前，ICA 還鮮有被用于RCPSP 及其衍生問題的求解，但大量的文獻(xiàn)資料顯示，ICA 有著較強(qiáng)的搜索性能和魯棒性[35]，且在調(diào)度優(yōu)化領(lǐng)域有著良好的應(yīng)用潛力，如：Li 等[36]開發(fā)出一種具有動(dòng)態(tài)反饋能力的ICA，為考慮運(yùn)輸與時(shí)序的流水車間調(diào)度問題提供了一種有效的解決方案；Akbari等[37]成功利用ICA實(shí)現(xiàn)VVER-1000 反應(yīng)堆堆芯在循環(huán)期間的最佳燃料布置；Behjati 等[38]采用一種分組式帝國競爭算法，處理大規(guī)模碼頭岸橋分配和內(nèi)集卡調(diào)度問題，在對(duì)實(shí)例的計(jì)算中取得了良好效果；Shokouhandeh等[39]利用一種改進(jìn)ICA，面向電動(dòng)汽車停車場與采用分布式發(fā)電單元供能的充電樁，實(shí)現(xiàn)兩種應(yīng)用場景下的24 h 能源優(yōu)化調(diào)度?？偟膩碚f，ICA在調(diào)度領(lǐng)域有著廣泛的應(yīng)用前景，且還有很多細(xì)分領(lǐng)域未曾涉獵?；诖?，本文嘗試提出一種TSE-ICA用于RCPSP的求解。

3 二階段演化帝國競爭算法

TSE-ICA是一種針對(duì)RCPSP所提出的具有多個(gè)搜索算子和優(yōu)化策略的混合型優(yōu)化算法。如前所述，該算法將優(yōu)化過程分為勘探與挖掘兩個(gè)階段，通過在不同階段選擇合適的搜索算子，實(shí)現(xiàn)種群多樣性與收斂性能的靈活側(cè)重。本文創(chuàng)新性地提出兩種新型同化算子用于二階段演化框架的構(gòu)建。同時(shí)，采用記憶庫技術(shù)異構(gòu)化ICA的種群演化模式。

TSE-ICA的優(yōu)化流程如圖3所示。首先，采用隨機(jī)數(shù)排序法[29]和編碼修正策略（算法2）生成初始種群，利用串行調(diào)度生成策略[40]計(jì)算個(gè)體成本值，并為初始種群劃分帝國。接著，建立一個(gè)與初始種群規(guī)模相當(dāng)?shù)挠洃泿霱，將初始種群存于其中。至此種群開始迭代，并根據(jù)預(yù)設(shè)的迭代數(shù)將演化過程分為兩個(gè)階段：階段1，采用組塊間同化算子開發(fā)種群多樣性；階段2，在組塊間同化算子中融入相同元素保留策略以加速收斂。同時(shí)，基于組塊的改進(jìn)革命機(jī)制能夠有效地對(duì)殖民地進(jìn)行鄰域搜索。而改進(jìn)后的帝國競爭機(jī)制可以交互各帝國的收斂信息，自適應(yīng)地調(diào)整各帝國的同化系數(shù)。同化機(jī)制和革命機(jī)制產(chǎn)生的高質(zhì)量子代會(huì)取代M中的較差解。在每一輪迭代結(jié)束前，使用M更新現(xiàn)有種群，并重新劃分帝國。算法達(dá)到終止條件（當(dāng)前迭代數(shù)g大于預(yù)設(shè)的最大迭代數(shù)G）時(shí)結(jié)束運(yùn)行，輸出種群中的最優(yōu)解。

圖3 TSE-ICA的流程圖Fig.3 Flowchart of TSE-ICA

3.1 個(gè)體編碼與初始種群

TSE-ICA 的Pop0中，個(gè)體的編碼形式是滿足優(yōu)先級(jí)約束的活動(dòng)列表Xi=(x1,x2,…,xn+2)。初始個(gè)體皆由隨機(jī)數(shù)排序法生成：首先，為每一個(gè)活動(dòng)生成一個(gè)0 至1 內(nèi)的隨機(jī)數(shù)，而活動(dòng)1 和活動(dòng)n+2 固定對(duì)應(yīng)數(shù)值0和1；接著，對(duì)所有隨機(jī)數(shù)進(jìn)行升序排列得到隨機(jī)數(shù)數(shù)列，進(jìn)而生成對(duì)應(yīng)的活動(dòng)列表；最后，對(duì)生成的活動(dòng)列表采取編碼修正策略，得到滿足優(yōu)先級(jí)約束的可行活動(dòng)列表。圖4為一個(gè)可行解的生成過程。

圖4 可行活動(dòng)列表的生成過程Fig.4 Process of generating feasible activity list

算法2 為非可行解的編碼修正策略。整個(gè)修正過程分為n+2個(gè)階段，每一個(gè)階段針對(duì)一個(gè)編碼位置進(jìn)行修正。若當(dāng)前位置的活動(dòng)不符合優(yōu)先級(jí)約束，便在活動(dòng)列表中找出該活動(dòng)的所有緊前活動(dòng)，然后將該活動(dòng)與編碼位置最靠后的緊前活動(dòng)調(diào)換位置，重復(fù)該過程直至當(dāng)前位置的活動(dòng)滿足優(yōu)先級(jí)約束，便進(jìn)入下一階段對(duì)下一個(gè)編碼進(jìn)行修正。

算法2編碼修正策略

初始種群建立后，需要將每個(gè)個(gè)體編碼轉(zhuǎn)換為調(diào)度計(jì)劃方可計(jì)算成本值（即項(xiàng)目完成時(shí)間）。串行調(diào)度生成策略（serial schedule generation scheme，SSGS）和并行調(diào)度生成策略（parallel schedule generation scheme，PSGS）是最常用的兩種轉(zhuǎn)換方法[40]?；诨顒?dòng)列表中的排序，SSGS能夠給予每一個(gè)活動(dòng)盡可能早的開始時(shí)間，令每個(gè)活動(dòng)被安排在允許其執(zhí)行的時(shí)間窗內(nèi)的最佳時(shí)刻，因此SSGS生成的調(diào)度計(jì)劃被稱為活躍的調(diào)度計(jì)劃（active schedule）；PSGS能夠在任一時(shí)刻t盡可能多地執(zhí)行活動(dòng)，在該策略下延遲任一活動(dòng)的開始時(shí)間都會(huì)導(dǎo)致項(xiàng)目完成時(shí)間被延遲，因此PSGS 生成的調(diào)度計(jì)劃被稱為不可延遲的調(diào)度計(jì)劃（non-delay schedule）。不可延遲的調(diào)度計(jì)劃是活躍的調(diào)度計(jì)劃的一個(gè)子集，最優(yōu)解決方案一定存在于活躍的調(diào)度計(jì)劃中。因此，本文選用SSGS計(jì)算個(gè)體的成本值。

隨機(jī)生成個(gè)體的計(jì)算復(fù)雜度為O(nNP)，編碼修正策略和SSGS 的計(jì)算復(fù)雜度同為O(n2NP)，因此初始化種群的計(jì)算復(fù)雜度為O(2n2NP+nNP)。

3.2 記憶庫

在基于種群的元啟發(fā)式算法中，記憶庫是一項(xiàng)常用的收斂輔助工具，更是GA 與DE 及其變種算法的核心組成部分[3]。記憶庫能夠存儲(chǔ)搜索過程中產(chǎn)生的精英解，并利用該信息引導(dǎo)種群進(jìn)化，進(jìn)而起到提高種群收斂速度的作用[41]。

為保證種群整體質(zhì)量的穩(wěn)定提高，TSE-ICA引入一個(gè)記憶庫M，用于存儲(chǔ)當(dāng)前質(zhì)量最高的NP個(gè)可行解，并在每一輪迭代結(jié)束前用其更新當(dāng)前種群。迭代開始前，M會(huì)對(duì)整個(gè)初始種群進(jìn)行備份，且M的存儲(chǔ)規(guī)模不再發(fā)生變化。每一輪迭代中，經(jīng)由同化機(jī)制（3.3節(jié)）與革命機(jī)制（3.4節(jié)）產(chǎn)生的新個(gè)體，若不與M中的任一個(gè)體重復(fù)（即所有活動(dòng)的開始時(shí)間一致）且優(yōu)于M中的最差解，便取代M中的最差解，反之舍棄這些新個(gè)體。最后，在每一輪迭代結(jié)束前，現(xiàn)有種群會(huì)被M中的種群替代，并重新進(jìn)行帝國劃分。利用記憶庫更新種群的計(jì)算復(fù)雜度為O(NPG)。

需要說明的是，因?yàn)楸疚乃惴〞?huì)在每一輪迭代中重置種群并重新劃分帝國，所以無需執(zhí)行標(biāo)準(zhǔn)ICA中的交換機(jī)制。

3.3 二階段同化機(jī)制

以探索階段開始、挖掘階段結(jié)束的二階段演化框架目前已被運(yùn)用于多種混合型元啟發(fā)式算法中，且都取得了較好的實(shí)驗(yàn)成果[28,42]。經(jīng)典的二階段演化過程常常將尋優(yōu)過程按照迭代次數(shù)分為兩個(gè)階段，然后在前后兩階段使用不同特性的搜索算子。同化是ICA最主要的搜索算子。因此，本文提出兩種專門用于RCPSP 的改進(jìn)同化算子，分別負(fù)責(zé)第一階段對(duì)搜索空間的廣泛勘探和第二階段對(duì)最優(yōu)解的快速收斂。比例系數(shù)St控制著兩個(gè)階段的轉(zhuǎn)換：當(dāng)g>St×G時(shí)，演化進(jìn)程由階段1進(jìn)入階段2。

3.3.1 組塊間同化算子

TSE-ICA在階段1，采用組塊間同化算子開發(fā)種群多樣性，即殖民地向其宗主國趨同的過程中，個(gè)體的編碼分量以組塊為單位進(jìn)行變動(dòng)來產(chǎn)生新個(gè)體。

通過關(guān)鍵路徑法[6]，可以得到實(shí)例網(wǎng)絡(luò)圖G=(N,A)的關(guān)鍵路徑和每一個(gè)活動(dòng)對(duì)應(yīng)的最早開始時(shí)間EST（earliest start time）和最晚結(jié)束時(shí)間LFT（latest finish time）。處于關(guān)鍵路徑上的活動(dòng)被稱為關(guān)鍵活動(dòng)，延遲關(guān)鍵活動(dòng)的完成時(shí)間會(huì)對(duì)項(xiàng)目工期造成直接影響[8]。以關(guān)鍵活動(dòng)為界，一個(gè)活動(dòng)列表可提取出若干個(gè)組塊，構(gòu)成一個(gè)組塊集合B。圖1中的關(guān)鍵活動(dòng)為1、2、6和9。基于圖1，一個(gè)組塊提取示例如圖5所示。在任一可行活動(dòng)列表內(nèi)部，關(guān)鍵活動(dòng)間的前后順序始終是固定的。因此，將關(guān)鍵活動(dòng)作為組塊的首個(gè)元素能夠起到標(biāo)記組塊位置的作用，并作為組塊的索引號(hào)使用。同化雙方具有相同索引號(hào)的兩個(gè)組塊在本文中被稱為對(duì)位組塊。

圖5 組塊提取示例Fig.5 Example of block extraction

上述的組塊提取策略能夠幫助算法實(shí)現(xiàn)特征選擇[43]，用以較好地去除搜索空間中的冗余部分。關(guān)鍵路徑之外的活動(dòng)被稱為非關(guān)鍵活動(dòng)，由于優(yōu)先級(jí)關(guān)系的約束，每一個(gè)非關(guān)鍵活動(dòng)只能進(jìn)入固定且數(shù)量有限的組塊中。比對(duì)非關(guān)鍵活動(dòng)與關(guān)鍵活動(dòng)的EST和LFT，便可得到每一個(gè)非關(guān)鍵活動(dòng)允許進(jìn)入的組塊集合（集合內(nèi)包含的是組塊索引號(hào)），如算法3 所示。通過將組塊信息與隨機(jī)搜索過程結(jié)合，每一個(gè)編碼分量的變動(dòng)范圍被限制在符合條件的組塊內(nèi)，即隨機(jī)搜索行為被限制在可行解所在的子空間內(nèi)，以此提高算法對(duì)解空間的搜索效率。

算法3獲取非關(guān)鍵元素的可進(jìn)入組塊集合

基于組塊提取策略構(gòu)建的組塊間同化算子，可以利用一個(gè)同化概率UA∈[0,1]控制子代的多樣性。組塊間同化的運(yùn)算流程如算法4 所示。通過采用0至1 內(nèi)的隨機(jī)數(shù)與UA進(jìn)行對(duì)比，殖民地個(gè)體的每一個(gè)非關(guān)鍵活動(dòng)編碼都有三種可能的變動(dòng)形式：當(dāng)隨機(jī)數(shù)rj,1>UA時(shí)（j∈Jnc，Jnc為非關(guān)鍵活動(dòng)集合），將待同化的活動(dòng)從當(dāng)前所在組塊隨機(jī)移入一個(gè)允許其進(jìn)入的組塊的末尾；若rj,1UA，該活動(dòng)的編碼位置不作更改；當(dāng)rj,1和rj,2同時(shí)小于UA時(shí)，該活動(dòng)的編碼位置同帝國主義國家一致。這意味著UA越接近1，同化產(chǎn)生的新個(gè)體與帝國主義國家越相似；反之，新個(gè)體與同化雙方的差異越大。因此，本文利用ICA的平行合作特性，通過為不同帝國設(shè)置不同的UA，并基于各帝國的信息交互動(dòng)態(tài)調(diào)整UA取值（見3.5節(jié)），進(jìn)行搜索空間的廣泛勘探。

3.3.2 保留相同元素的組塊間同化算子

TSE-ICA的階段2，采用保留相同元素的組塊間同化算子以加速收斂。

隨著種群的演化，一些有助生存的基因片段會(huì)越來越普遍地存在于個(gè)體編碼中。對(duì)于RCPSP，這些基因片段可表征為多個(gè)特定活動(dòng)有序組成的特定活動(dòng)塊。這些活動(dòng)塊能夠高效利用資源、有效壓縮工期。但很多傳統(tǒng)的優(yōu)化方法不具備分辨和保護(hù)特定活動(dòng)塊的能力，在搜索過程中對(duì)其造成破壞，從而產(chǎn)生大量的低質(zhì)量解[8]。針對(duì)這一問題，文獻(xiàn)[8]選擇將父代雙方編碼中的相同活動(dòng)塊保留至子代，來改善子代的整體質(zhì)量。本文受此啟發(fā)，為組塊間同化算子引入相同元素保留策略。

組塊本質(zhì)上就是由若干活動(dòng)組成的活動(dòng)塊，故優(yōu)化問題可被拆解為多個(gè)子問題：各組塊的最優(yōu)構(gòu)成。相同元素保留策略通過不變動(dòng)同化雙方在對(duì)位組塊中的相同元素，并以其在帝國主義國家（種群中的較優(yōu)解）中的編碼順序傳承至子代，實(shí)現(xiàn)組塊內(nèi)特定活動(dòng)塊的識(shí)別和保留。隨著迭代的進(jìn)行，組塊內(nèi)的特定構(gòu)成元素會(huì)不斷地積累和完善，進(jìn)而實(shí)現(xiàn)優(yōu)化子問題的逐個(gè)收斂。因此，相同元素保留策略的加入，能夠?qū)⒏复膬?yōu)秀特征繼承至下一代，保證子代的整體質(zhì)量。并且，子代在基因上與父代的帝國主義國家更加接近，有助于各帝國更快速地完成鄰域空間的收斂工作。

保留相同元素的組塊間同化算子的工作流程如算法4 所示。與階段1 相比，階段2 的同化算子在執(zhí)行過程中僅有兩處不同：（1）繼承至子代個(gè)體的特定活動(dòng)在排序上同帝國主義國家一致（算法4 的步驟2）；（2）對(duì)位組塊中的相同元素不執(zhí)行同化操作（算法4 的步驟3.1）。此外，算法4 的步驟3.3 中，將活動(dòng)插入組塊末尾同樣是為了不破壞已有的特定活動(dòng)塊。并且，由算法4 可得，二階段同化算子的最大時(shí)間復(fù)雜度為O[(n2+n+1)NPG]。

算法4二階段同化機(jī)制

3.4 基于組塊的改進(jìn)革命機(jī)制

TSE-ICA 的革命機(jī)制包含插入和亂序兩種領(lǐng)域搜索策略，主要功能是強(qiáng)化算法的搜索速率和避免陷入局部最優(yōu)。插入策略[3,10,24,28]指將一個(gè)活動(dòng)移動(dòng)至任意一個(gè)允許其進(jìn)入的組塊內(nèi)的隨機(jī)一個(gè)位置；亂序策略指對(duì)組塊內(nèi)的非關(guān)鍵活動(dòng)進(jìn)行一次亂序。

階段1 時(shí)，算法需要對(duì)搜索空間進(jìn)行廣泛勘探，插入策略和亂序策略能有效提高算法對(duì)解空間采樣次數(shù)。階段2時(shí)，一些基因片段會(huì)在演化過程中受到保護(hù)和傳承。假若這些固定的編碼片段尚未擁有最優(yōu)的元素構(gòu)成且一直沒有被完善，便會(huì)在同化機(jī)制的趨同作用下普及至每一個(gè)帝國成員，進(jìn)而陷入局部最優(yōu)。因此，采用插入策略適當(dāng)?shù)卣{(diào)整組塊內(nèi)的元素構(gòu)成，及采用亂序策略幫助組塊內(nèi)的元素嘗試不同的排序方案，有機(jī)率幫助帝國成員跳出局部最優(yōu)。

改進(jìn)后的革命機(jī)制依舊根據(jù)革命概率UR挑選部分殖民地進(jìn)行變異，具體流程如下：

首先，設(shè)置一個(gè)變異概率UM，并在殖民地個(gè)體對(duì)應(yīng)的組塊集合Bcol中隨機(jī)挑選一個(gè)組塊，該組塊至少包含一個(gè)非關(guān)鍵活動(dòng)。接著，生成一個(gè)隨機(jī)數(shù)rcol，若rcolUM，對(duì)該組塊執(zhí)行亂序策略。最后，合并Bcol內(nèi)的組塊，對(duì)其進(jìn)行優(yōu)先級(jí)關(guān)系修正后得到新個(gè)體。

相比插入策略，亂序策略會(huì)同時(shí)對(duì)更多活動(dòng)造成影響。而隨著演化過程的推進(jìn)，組塊內(nèi)的元素構(gòu)成趨于成熟，再對(duì)其進(jìn)行頻繁的亂序易造成子代個(gè)體的質(zhì)量低下。因此，受文獻(xiàn)[44]啟發(fā)，UM將隨著迭代數(shù)的增大而增大，其值由下式確定：

式中，UM,max為變異概率的最大取值。

由以上描述可知，改進(jìn)革命機(jī)制的時(shí)間復(fù)雜度為O(URNPG)。

3.5 改進(jìn)帝國競爭機(jī)制

由于每一輪迭代都會(huì)對(duì)帝國勢力進(jìn)行重新劃分，帝國間的強(qiáng)弱關(guān)系不再適用于引導(dǎo)子種群間的計(jì)算資源流動(dòng)。為了更好地利用不同子種群間的平行合作關(guān)系，TSE-ICA的帝國競爭機(jī)制通過交互各帝國的收斂信息，自適應(yīng)地為各帝國設(shè)置更適合的同化概率UA。

首先，在初始種群劃分帝國后，根據(jù)式（6）為每一個(gè)帝國設(shè)置不同取值的初始UA。

式中，UA,i,1為第i個(gè)帝國在第一輪迭代中使用的同化系數(shù)；UA,min為初始UA中的最小值。

在演化過程中，各帝國會(huì)向上一輪迭代中收斂效益最高的帝國進(jìn)行學(xué)習(xí)，自適應(yīng)地調(diào)整UA值；但是，若所有帝國在上一輪迭代中都未能讓同化后的殖民地得到提升，各帝國在當(dāng)前迭代的UA值會(huì)逐漸向各自的初始值靠近，以通過更廣泛的同化搜索范圍幫助種群挖掘出更具潛力的搜索區(qū)域。帝國競爭的操作流程如下：

（1）計(jì)算各帝國在同化過程中的收斂效益Cb，計(jì)算公式如下：

式中，下標(biāo)g和g-1 用于表示迭代數(shù)的前后關(guān)系，后同；表示第e個(gè)帝國的第i個(gè)殖民地；βe,i為同化后降低的成本值，如果殖民地未獲得提升，其對(duì)應(yīng)的βe,i=0。

（2）記收斂效益最高的帝國的收斂效益為Cbbest,g、同化概率為UA,best,g。若Cbbest,g>0，收斂效益最高的帝國在下一輪迭代繼續(xù)使用該UA值，其余帝國則通過式（9）更新UA值；若Cbbest,g=0，表示所有殖民地都未能在被同化后獲得提升，此時(shí)各帝國用式（10）更新UA值。

式中，N為高斯分布函數(shù)。需要注意的是，當(dāng)UA,i,g+1<0 時(shí)，令其值等于0；當(dāng)UA,i,g+1>1 時(shí)，令其值等于1。

由上，可得帝國競爭的時(shí)間復(fù)雜度為O(NPG)。

3.6 時(shí)間復(fù)雜度分析

將各組成部分的時(shí)間復(fù)雜度相加，TSE-ICA的時(shí)間復(fù)雜度為O{[(2n2+n)+(n2+n+3+UR)G]NP}，若只關(guān)注主體部分，可將其表示為O(n2NPG)。

表1 為3 種先進(jìn)的RCPSP 元啟發(fā)式優(yōu)化算法與TSE-ICA 的時(shí)間復(fù)雜度對(duì)比。通過如表1 所示的對(duì)比結(jié)果，可以發(fā)現(xiàn)TSE-ICA 有著較為合理的計(jì)算成本，這意味著TSE-ICA 對(duì)RCPSP 有著較好的應(yīng)用潛力。同時(shí)，經(jīng)典的ICA源于對(duì)連續(xù)優(yōu)化問題的求解，在以往工作中實(shí)現(xiàn)過3 種能夠較好求解連續(xù)優(yōu)化問題的改進(jìn)ICA，其與本文所提TSE-ICA的時(shí)間復(fù)雜度對(duì)比如表2 所示。用于組合優(yōu)化問題的TSE-ICA 相對(duì)于以往提出的ICA改進(jìn)算法，在時(shí)間復(fù)雜度上有一定的增加，但仍表現(xiàn)出較好的特性（隨后的計(jì)算實(shí)驗(yàn)中得到進(jìn)一步證明）。

表1 算法時(shí)間復(fù)雜度橫向?qū)Ρ萒able 1 Lateral comparison of time complexity

表2 算法時(shí)間復(fù)雜度縱向?qū)Ρ萒able 2 Vertical comparison of time complexity

4 仿真實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)置

本文實(shí)驗(yàn)是基于CPU為2.20 GHz i7-10870H、內(nèi)存16 GB、64位Windows 10操作系統(tǒng)的計(jì)算機(jī)完成，編程平臺(tái)為Python3.7。為了檢驗(yàn)本文算法的性能特點(diǎn)，仿真實(shí)驗(yàn)部分選用標(biāo)準(zhǔn)實(shí)例庫PSPLIB（http://www.om-db.wi.tum.de/psplib）的3 個(gè)實(shí)例集J30、J60和J120，共1 560 個(gè)實(shí)例，其中J30 和J60 皆包含480個(gè)實(shí)例，J120 包含600 個(gè)實(shí)例。這些實(shí)例的生成與3個(gè)參數(shù)密切相關(guān)[14]：

（1）網(wǎng)絡(luò)復(fù)雜度（network complexity，NC）為每個(gè)活動(dòng)的平均緊前活動(dòng)數(shù)量。

（2）資源因子（resource factor，RF）為每個(gè)活動(dòng)的資源需求量與資源總量的平均百分比。其值越大，活動(dòng)對(duì)資源的平均需求量越大，反之則越小。

（3）資源強(qiáng)度（resource strength，RS）為資源的稀缺程度。其值越大可供調(diào)配的資源總量越多，反之資源受限越嚴(yán)重。

J30和J60的參數(shù)設(shè)置為NC∈{1.5,1.8,2.1}，RF∈{0.25,0.50,0.75,1.00}和RS∈{0.2,0.5,0.7,1.0}。而J120除了RS∈{0.1,0.2,0.3,0.4,0.5}外，其余參數(shù)與其他兩個(gè)實(shí)例集相同。

為了更好與其他同類型研究進(jìn)行對(duì)比，需要測試最大調(diào)度次數(shù)Schedules為1 000、5 000和50 000時(shí)的實(shí)驗(yàn)結(jié)果（最大迭代數(shù)G=Schedules/NP）。單個(gè)實(shí)例的獨(dú)立運(yùn)行次數(shù)為10。實(shí)驗(yàn)的評(píng)估指標(biāo)是平均偏差率AD（average deviation），即算法所求最優(yōu)解與最優(yōu)下界的偏差。J30 的最優(yōu)下界為精確最優(yōu)解。J60和J120 中部分實(shí)例的精確最優(yōu)解未知，針對(duì)這兩個(gè)實(shí)例集目前有兩種評(píng)判標(biāo)準(zhǔn)：

（1）以當(dāng)前已知最優(yōu)解作為最優(yōu)下界求取平均偏差率ADBK：

（2）在國際上更為通用的以關(guān)鍵路徑值為最優(yōu)下界求取平均偏差率ADCP：

式（11）、式（12）中，P為當(dāng)前實(shí)例集包含的實(shí)例個(gè)數(shù)；Fbest,p為算法對(duì)實(shí)例p多次獨(dú)立運(yùn)行后取得的最優(yōu)解；LBp為實(shí)例p的最優(yōu)下界；下標(biāo)BK 和CP 用于區(qū)分當(dāng)前已知最優(yōu)解和關(guān)鍵路徑值。關(guān)鍵路徑值為不考慮資源約束時(shí)的項(xiàng)目最短完成時(shí)間。

4.2 參數(shù)分析

TSE-ICA中影響算法有效性的參數(shù)有：種群規(guī)模NP、帝國個(gè)數(shù)Nimp、最小同化概率UA,min、革命概率UR、最大變異概率UM和階段轉(zhuǎn)換比例系數(shù)St。因?yàn)椴捎眯∫?guī)模種群有效求解經(jīng)典RCPSP是本次研究的主要目標(biāo)之一，所以在參照大量相關(guān)文獻(xiàn)后[4,8]，將本次實(shí)驗(yàn)中的種群規(guī)模NP設(shè)為50。

本文采用Taguchi 法的實(shí)驗(yàn)設(shè)計(jì)方法（design-ofexperiment，DOE）[15]確定最佳的參數(shù)值。分別從J30、J60 和J120 中隨機(jī)選取48、48 和60 個(gè)實(shí)例計(jì)算ADBK，實(shí)驗(yàn)的最大調(diào)度次數(shù)為5 000。

表3 為各參數(shù)值對(duì)應(yīng)的等級(jí)。表4 為參數(shù)等級(jí)正交表和25種參數(shù)組合下TSE-ICA的實(shí)驗(yàn)結(jié)果。圖6是由實(shí)驗(yàn)結(jié)果得到的參數(shù)等級(jí)變化趨勢，圖中ADBK值最低的等級(jí)對(duì)應(yīng)著最佳的參數(shù)取值。根據(jù)圖6，TSE-ICA 針對(duì)不同實(shí)例集的最佳參數(shù)組合如表5 所示。表6 統(tǒng)計(jì)了面對(duì)不同實(shí)例集時(shí)各參數(shù)對(duì)TSEICA的影響程度。由表6可知，對(duì)于J30，對(duì)TSE-ICA的優(yōu)化性能影響最大的參數(shù)是Nimp，最小的是St；對(duì)于J60，UR是最有可能影響TSE-ICA 算法性能的參數(shù)，其次是UA,min，影響最小的則是St；求解J120 時(shí)，TSE-ICA 對(duì)UA,min的敏感性最高，對(duì)Nimp的敏感性最低。

表3 參數(shù)取值等級(jí)Table 3 Level of parameter values

表4 正交表和TSE-ICA求解J30、J60和J120的平均偏差率ADBKTable 4 Orthogonal table and average deviation ADBK of TSE-ICA for J30,J60 and J120

表5 最佳參數(shù)組合Table 5 The best combination of parameter values

表6 均值響應(yīng)表Table 6 Response table for means

圖6 TSE-ICA的參數(shù)等級(jí)變化趨勢Fig.6 Factor level change trend of TSE-ICA

4.3 實(shí)驗(yàn)結(jié)果

表7為TSE-ICA求解3個(gè)實(shí)例集的實(shí)驗(yàn)結(jié)果，其中CT指每個(gè)實(shí)例的平均計(jì)算時(shí)間。圖7 展示了TSE-ICA對(duì)每個(gè)實(shí)例的所求最優(yōu)解的ADBK。

表7 TSE-ICA的實(shí)驗(yàn)結(jié)果Table 7 Experimental results of TSE-ICA

圖7 TSE-ICA求解每個(gè)實(shí)例的平均偏差率ADBKFig.7 Average deviation ADBK for TSE-ICA solving each instance

如圖7（a）所示，對(duì)于J30，TSE-ICA 分別能夠在1 000、5 000 和50 000 次調(diào)度次數(shù)時(shí)求得444、473 和475個(gè)實(shí)例的理論最優(yōu)解。其中，未能求得最優(yōu)解的5個(gè)實(shí)例分別是13-6、29-1、29-5、29-8和40-1，其共同特點(diǎn)是RS=0.2。

根據(jù)圖7（b），對(duì)于J60，TSE-ICA在3種調(diào)度次數(shù)下分別有353、367 和383 個(gè)實(shí)例的計(jì)算結(jié)果與已知最優(yōu)解一致?？梢园l(fā)現(xiàn)，存在偏差的實(shí)例數(shù)量及其偏差率會(huì)隨著RF的增大而增大。對(duì)于有著最小RS和最大RF的實(shí)例，算法的偏差率最大。

面對(duì)難度最大的J120，3種調(diào)度次數(shù)下TSE-ICA能夠求得已知最優(yōu)解的實(shí)例數(shù)分別為153、173 和181。從圖7（c）中可以很明顯地看出，TSE-ICA 對(duì)RF大于0.25的實(shí)例的偏差率大幅高于RF等于0.25的實(shí)例。同時(shí)，偏差率與RS呈明顯的負(fù)相關(guān)。

總的來說，NC對(duì)本文所提算法的求解表現(xiàn)沒有顯著的影響。但是，實(shí)例的RF越高或RS越低，TSEICA越難對(duì)其求解。并且，隨著實(shí)例所含活動(dòng)數(shù)的增多，RF與RS對(duì)算法求解精度的影響越顯著。

4.4 與多種先進(jìn)算法的對(duì)比分析

實(shí)驗(yàn)結(jié)果對(duì)比共分兩部分：（1）基于實(shí)驗(yàn)所得的ADBK和CT，TSE-ICA 與3 種同類型算法、1 種GA 改進(jìn)算法和2 種DE 變種進(jìn)行數(shù)值比較和分析，以驗(yàn)證本文算法的改進(jìn)有效性和收斂效率；（2）基于國際通用標(biāo)準(zhǔn)ADCP，TSE-ICA 與11 種著名算法進(jìn)行比較，進(jìn)一步證明本文算法的優(yōu)化性能和問題適應(yīng)性。

本節(jié)列出了17 種對(duì)比算法，這些算法皆是采用或先進(jìn)、或經(jīng)典的優(yōu)化技術(shù)構(gòu)建的混合型算法。ICAS（imperialist competitive algorithm with spilt mechanism）[49]、DCCE-IICA（decimal-binary conversion and clonal evolution oriented improved imperialist competitive algorithm）[46]和ICA-DE（hybrid algorithm of differential evolution algorithm and imperialist competitive algorithm）[50]對(duì)各自應(yīng)用的組合優(yōu)化問題有著優(yōu)異表現(xiàn)，IGA（improved genetic algorithm）[26]、IDE（improved differential evolution algorithm）[51]和ADDEBS（improved differential evolution parameter control and bidirectional scheduling algorithm）[29]能夠較好地求解RCPSP 及其衍生問題。此6 種算法被用于第一部分的對(duì)比。其他11種算法皆遵循國際通用標(biāo)準(zhǔn)完成J30、J60和J120的測試實(shí)驗(yàn)，是TSE-ICA在第二部分的比較對(duì)象，這11 種算法在實(shí)驗(yàn)結(jié)果上都有著較強(qiáng)的競爭力，尤其是Search-tree+GA、ALNP 和MAOA，對(duì)J60和J120的優(yōu)化效果十分出色。

4.4.1 基于當(dāng)前已知最優(yōu)解的算法對(duì)比分析

本小節(jié)的對(duì)比算法分別是：ICAS、DCCE-IICA、ICA-DE、ADDE-BS、IGA 和IDE。表8 統(tǒng)計(jì)了TSEICA 與6 種對(duì)比算法基于當(dāng)前已知最優(yōu)解的實(shí)驗(yàn)結(jié)果；表9 為TSE-ICA 與4 種對(duì)比算法（不包括ADDEBS 和IDE）的平均計(jì)算時(shí)間。ADDE-BS 和IDE 的實(shí)驗(yàn)數(shù)據(jù)取自現(xiàn)有文獻(xiàn)。其余4 種對(duì)比算法的實(shí)驗(yàn)平臺(tái)與數(shù)據(jù)來源同本文算法一致。

表9 5種算法求解J30、J60和J120的平均計(jì)算時(shí)間Table 9 Average computational time of 5 algorithms for solving J30,J60 and J120 單位：s

如表8所示，對(duì)于J30，IDE有著一眾對(duì)比算法中最好的收斂表現(xiàn)，而TSE-ICA 與除IDE 之外的對(duì)比算法相比，有著很強(qiáng)的競爭力。并且，在4 種基于ICA 的混合型算法中，TSE-ICA 有著最好的收斂精度；對(duì)于J60和J120，TSE-ICA在最大調(diào)度次數(shù)為1 000和5 000 時(shí)的優(yōu)化性能強(qiáng)于所有對(duì)比算法，在50 000次調(diào)度時(shí)的求解精度僅次于IGA，這意味著本文算法能夠利用較少的迭代數(shù)尋得較高質(zhì)量的解決方案，但隨著迭代數(shù)的增多，TSE-ICA的收斂效益會(huì)逐漸不如IGA。

綜合表8 的總體情況進(jìn)行分析，可以發(fā)現(xiàn)4 種ICA變種算法對(duì)小規(guī)模實(shí)例集J30的整體優(yōu)化表現(xiàn)不如GA 和DE 的改進(jìn)算法，但面對(duì)更大規(guī)模的J60 和J120 時(shí)，4 種基于ICA 的變種算法與其他3 種對(duì)比算法相比有著不俗的優(yōu)化性能。而TSE-ICA 是4 種同類型對(duì)比算法中優(yōu)化精度最好的算法，這證明了本文所提改進(jìn)機(jī)制的有效性。并且，對(duì)于中大規(guī)模實(shí)例集J60和J120，TSE-ICA能夠在較少調(diào)度次數(shù)的約束下尋得相對(duì)最優(yōu)的解決方案，初步證明本文算法有著高效的迭代尋優(yōu)速率。

此外，算法運(yùn)行速率是另一項(xiàng)重要評(píng)估指標(biāo)，用于評(píng)價(jià)算法對(duì)優(yōu)化問題的適用性。正如表9所示，針對(duì)實(shí)驗(yàn)中的3個(gè)實(shí)例集，TSE-ICA的整體計(jì)算時(shí)間最短，其次是ICAS和IGA。具體來看，對(duì)于J30和J60，除最耗時(shí)的ICA-DE外，其余所有算法的平均計(jì)算時(shí)間都較為相近；而面對(duì)J120 時(shí)，TSE-ICA 在1 000 和5 000 次調(diào)度次數(shù)時(shí)的計(jì)算耗時(shí)大幅短于其他算法，在50 000次最大調(diào)度次數(shù)的計(jì)算時(shí)間也僅與第一名的ICAS 保持著很小的差距。這證明了本文所提算法有著較好的運(yùn)行速率。

為了更加確鑿地證明TSE-ICA在收斂精度上的優(yōu)勢，本小節(jié)首先采用Friedman檢驗(yàn)[52]對(duì)7種算法的優(yōu)化表現(xiàn)進(jìn)行排名。

表10 為置信度α為0.05 的Friedman 檢驗(yàn)結(jié)果?；趯?shí)驗(yàn)得到的平均偏差率數(shù)據(jù)，表中統(tǒng)計(jì)了各算法相互對(duì)比得到的秩均值。因?yàn)楸疚牡膶?shí)驗(yàn)背景是求解最小值問題，故表現(xiàn)越出色的算法秩均值越小。SR是整合3 個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果得到的秩均值，對(duì)其升序排列可得到7 種算法的優(yōu)化性能排名[53]。從表10中可以看出，對(duì)于J30，IDE和ADDE-BS這兩個(gè)DE的變種算法優(yōu)勢最大，而本文所提TSE-ICA位于第三名；對(duì)于J60和J120，TSE-ICA的秩均值最?。籗R的排名結(jié)果顯示，TSE-ICA對(duì)3個(gè)標(biāo)準(zhǔn)實(shí)例集的整體表現(xiàn)優(yōu)于所有對(duì)比算法。

表10 7種算法的Friedman檢驗(yàn)結(jié)果（α=0.05）Table 10 Results of Friedman test for 7 algorithms (α=0.05)

Friedman 檢驗(yàn)?zāi)軌蚧趯?shí)驗(yàn)結(jié)果確定多個(gè)對(duì)比算法之間是否存在顯著性差異，但忽略了對(duì)比算法兩兩之間的差異性。而post hoc Iman-Davenport檢驗(yàn)[54]能夠很好地解決該問題。首先根據(jù)式（13）計(jì)算差異臨界值CD（critical difference），然后將對(duì)比算法兩兩間的SR之差與CD進(jìn)行對(duì)比，若差值大于CD，說明二者間的性能確實(shí)存在顯著差異。

式中，qα是以((κ-1),(κ-1)(η-1))為自由度從F 分布統(tǒng)計(jì)量表得到的臨界值；κ和η分別表示算法個(gè)數(shù)和實(shí)例數(shù)。

圖8 為7 種算法的post hoc Iman-Davenport 檢驗(yàn)結(jié)果。根據(jù)式（13）計(jì)算得到CD=0.162。顯然，圖8中TSE-ICA 與所有對(duì)比算法的SR之差皆小于CD，故可得出TSE-ICA與任意一種對(duì)比算法都有著顯著的性能優(yōu)勢，證實(shí)了Friedman檢驗(yàn)得出的結(jié)果。

圖8 7種算法的post hoc Iman-Davenport檢驗(yàn)結(jié)果Fig.8 Results of post hoc Iman-Davenport test for 7 algorithms

4.4.2 基于關(guān)鍵路徑值的算法對(duì)比分析

本小節(jié)與TSE-ICA對(duì)比的算法有11種，分別是：QICA（quantum-inspired genetic algorithm）[45]、EA（FBI）（a population based stochastic algorithm with forwardbackward improvement）[55]、Search-tree+GA（Searchtrees combined with genetic algorithm）[56]、ALNP（activity-list based nested partitions algorithm）[57]、MAOA（multi-agent optimization algorithm）[58]、DSA（differential search algorithm）[59]、MJPSO（multiple justification particle swarm optimization）[60]、PSO（FBI）（pseudo particle swarm optimization with forwardbackward improvement）[61]、GRASP（SS-FBI）（greedy randomized adaptive search procedure combining scatter search and forward-backward improvement）[62]、BA（FBI）（bee algorithms with forward-backward improvement）[63]和JPSO（justification particle swarm optimization）[64]。本小節(jié)所有算法的實(shí)驗(yàn)數(shù)據(jù)皆取自已公開發(fā)表的文獻(xiàn)。

表11統(tǒng)計(jì)了12種算法基于關(guān)鍵路徑值的平均偏差率。從表11 中可以很明顯地看到：對(duì)于J30，TSEICA在調(diào)度次數(shù)較少的情況下有著最好收斂精度，但在50 000次調(diào)度時(shí)略差于MAOA、PSO（FBI）和Searchtree+GA；對(duì)于J60，本文算法的優(yōu)化表現(xiàn)并不出色；對(duì)于J120，TSE-ICA 在1 000 次調(diào)度情況下的收斂精度相對(duì)較低，但在5 000和50 000次調(diào)度時(shí)有著最低的平均偏差率。

表11 12種算法基于關(guān)鍵路徑值的平均偏差率Table 11 Average deviation of 12 algorithms based on critical-path values 單位：%

此處同樣用到Friedman 檢驗(yàn)和post hoc Iman-Davenport 檢驗(yàn)對(duì)實(shí)驗(yàn)數(shù)據(jù)作進(jìn)一步的分析，其檢驗(yàn)過程同前一小節(jié)一致。表12為本小節(jié)的Friedman檢驗(yàn)結(jié)果；圖9為post hoc Iman-Davenport檢驗(yàn)結(jié)果（根據(jù)式（13）計(jì)算得到此時(shí)CD=0.418）。

表12 12種算法的Friedman檢驗(yàn)結(jié)果（α=0.05）Table 12 Results of Friedman test for 12 algorithms (α=0.05)

圖9 12種算法的post hoc Iman-Davenport檢驗(yàn)結(jié)果Fig.9 Results of post hoc Iman-Davenport test for 12 algorithms

如表12所示，根據(jù)Friedman檢驗(yàn)結(jié)果，TSE-ICA對(duì)實(shí)例集J30和J120的優(yōu)化表現(xiàn)排在了第一位，但對(duì)J60的求解能力排在了第8名。通過對(duì)SR值排序，得出本文所提TSE-ICA在眾多優(yōu)化算法中的性能表現(xiàn)排名為第3，落后于Search-tree+GA 和MAOA。從圖9 可以看出，TSE-ICA 與ALNP 和MAOA 的SR之差小于CD，說明TSE-ICA與除ALNP和MAOA之外的其他算法之間確實(shí)存在顯著差異，可以證明Friedman檢驗(yàn)的結(jié)果存在合理性。

綜上，可以確定本文算法與國際上的知名算法相比，在小規(guī)模數(shù)據(jù)集J30和大規(guī)模數(shù)據(jù)集J120上有著出色的優(yōu)化性能和較好的適用性。對(duì)于中等規(guī)模數(shù)據(jù)集J60，TSE-ICA 雖然差于部分先進(jìn)的混合型算法，但仍具有較強(qiáng)的競爭力。

4.5 收斂速率分析

為進(jìn)一步分析本文所提TSE-ICA 的收斂速率，本文分別從3個(gè)測試集中挑選2個(gè)較難求解的實(shí)例，于圖10繪制TSE-ICA與3種ICA變種（ICAS、DCCEIICA、ICA-DE）對(duì)這些實(shí)例在5 000 次調(diào)度下的收斂曲線。J30-13-5表示J30中的13-5，余同。

圖10 4種改進(jìn)ICA對(duì)6個(gè)實(shí)例的收斂曲線Fig.10 Convergence curves of 4 improved ICA for 6 instances

如圖10（a）和圖10（b）所示，對(duì)于J30-13-5和J30-25-7，ICAS與TSE-ICA有著最快的前期收斂速率，但僅有TSE-ICA的收斂曲線能夠在中后期保持著穩(wěn)定且快速的下降速率，并在最大迭代次數(shù)結(jié)束前尋得理論最優(yōu)解。根據(jù)圖10（c）和圖10（d），TSE-ICA 對(duì)J60-13-5 有著眾算法中最快的收斂速度，但在對(duì)J60-25-7 的收斂速率上慢于DCCE-IICA。在圖10（e）和圖10（f）中，面對(duì)J120-21-4，TSE-ICA 雖有著最好的收斂精度，但在收斂速度上不如DCCE-IICA和ICA-DE；對(duì)于J120-57-3，TSE-ICA 在前期的收斂速度優(yōu)于其他算法，在中后期的收斂速率與DCCEIICA相近。

綜合圖10 中的所有信息，可以發(fā)現(xiàn)四種同類型算法都能夠在演化前期有一個(gè)較快的收斂速率，但只有TSE-ICA的收斂曲線能夠在中后期依舊保持穩(wěn)定的下降趨勢，極少發(fā)生收斂早熟的現(xiàn)象。這說明二階段演化框架及其對(duì)應(yīng)的搜索算子，能有效滿足演化種群在不同時(shí)期的搜索性能需求，幫助算法維持穩(wěn)定且高效的收斂速率。

4.6 改進(jìn)策略的有效性分析

為了進(jìn)一步驗(yàn)證組塊提取策略和相同元素保留策略的改進(jìn)有效性，本節(jié)對(duì)以下4 種算法進(jìn)行對(duì)比：（1）采用傳統(tǒng)同化算子的ICA1；（2）僅采用組塊間同化算子的ICA2；（3）僅采用保留相同元素的組塊間同化算子的ICA3；（4）采用二階段同化算子的TSEICA。除同化算子外，這四種ICA的其余部分完全一致。圖11 為4 種算法對(duì)J30-13-5、J60-25-7 和J120-57-3的收斂曲線，調(diào)度次數(shù)為5 000。從圖11中可以很清晰地得出如下結(jié)論：

圖11 4種同化算子下ICA對(duì)3個(gè)實(shí)例的收斂曲線Fig.11 Convergence curves of ICA for 3 instances with 4 different assimilation operators

（1）ICA2對(duì)3個(gè)實(shí)例的收斂精度和收斂速度明顯強(qiáng)于ICA1，證明了利用組塊提取策略改進(jìn)過的同化算子具有更好的搜索效率。

（2）ICA3對(duì)3個(gè)實(shí)例的求解速率明顯優(yōu)于其他對(duì)比算法。并且，ICA3能夠輕松求得J30-13-5的理論最優(yōu)解，對(duì)其余兩個(gè)實(shí)例的收斂精度僅弱于TSE-ICA。但是，除去難度最低的J30-13-5，ICA3對(duì)J60-25-7 和J120-57-3的收斂過程存在早熟的現(xiàn)象。這說明相同元素保留策略確實(shí)能夠?yàn)榻M塊間同化算子帶來高效的收斂性能，但僅采用該種同化算子會(huì)增加算法陷入局部最優(yōu)的風(fēng)險(xiǎn)。

（3）在搜索過程的前半段，ICA2與TSE-ICA的收斂曲線是重合的。但到了后半部分，TSE-ICA開始采用保留相同元素的組塊間同化算子后，其收斂曲線的下降速率明顯快于ICA2，且在收斂精度上超過ICA3。一方面，這進(jìn)一步印證了相同元素保留策略對(duì)收斂性能的貢獻(xiàn)；另一方面，也說明種群在第一階段對(duì)基因多樣性的積累確實(shí)有助于第二階段的收斂，驗(yàn)證了二階段演化框架的有效性。

5 結(jié)束語

本文提出了一種能夠有效求解經(jīng)典資源約束項(xiàng)目調(diào)度問題的二階段演化帝國競爭算法。該算法基于種群多樣性和收斂性能提出兩種同化算子，通過二者的交替使用實(shí)現(xiàn)算法在不同階段下的功能側(cè)重。兩種基于組塊的鄰域搜索策略用于革命機(jī)制中，加快算法收斂的同時(shí)幫助算法逃出局部最優(yōu)。改進(jìn)帝國競爭機(jī)制為算法提供自適應(yīng)的參數(shù)決策。同時(shí)，一個(gè)記憶庫不斷存儲(chǔ)迭代過程中產(chǎn)生的精英解，并利用其更新現(xiàn)有種群，保證種群的進(jìn)化效率?；跇?biāo)準(zhǔn)實(shí)例集J30、J60和J120的仿真實(shí)驗(yàn)結(jié)果，本文算法通過與17種先進(jìn)的元啟發(fā)式算法進(jìn)行實(shí)驗(yàn)結(jié)果對(duì)比，證明了本文所提改進(jìn)策略的有效性、算法良好的優(yōu)化性能和問題適用性。

下一步，至少還有兩個(gè)需要深入討論的研究方向：首先，本文所用的二階段算法演化框架是一種能夠平衡廣度探索與深度挖掘能力的改進(jìn)策略，其有望應(yīng)用于其他元啟發(fā)式算法的改進(jìn)中；其次，實(shí)際的資源約束項(xiàng)目調(diào)度問題可能存在多模式、多技能、多緩沖和不確定性強(qiáng)等特點(diǎn)，如何基于帝國競爭算法或二階段演化框架設(shè)計(jì)出有效的優(yōu)化方法，是近期需要展開的下一步工作。