基于改進(jìn)雙歸檔進(jìn)化算法的多目標(biāo)動(dòng)態(tài)軟件項(xiàng)目調(diào)度

陳志遠(yuǎn)，伍章俊+，童珊珊，劉 曉

(1.合肥工業(yè)大學(xué) 管理學(xué)院，安徽 合肥 230009；2.合肥工業(yè)大學(xué) 過程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230009；3.迪肯大學(xué) 信息技術(shù)學(xué)院，澳大利亞 吉朗 VIC 3126)

0 引言

隨著互聯(lián)網(wǎng)應(yīng)用和軟件產(chǎn)業(yè)的快速發(fā)展，軟件公司面臨競(jìng)爭(zhēng)激烈的市場(chǎng)環(huán)境。軟件項(xiàng)目過程管理從軟件項(xiàng)目計(jì)劃、需求、設(shè)計(jì)、編碼、測(cè)試和運(yùn)行維護(hù)的整個(gè)生命周期出發(fā)，以提高業(yè)務(wù)過程的績(jī)效為主要目標(biāo)持續(xù)改進(jìn)過程，最終實(shí)現(xiàn)降低項(xiàng)目成本和縮短項(xiàng)目工期等目標(biāo)。其中，合理的資源調(diào)度能夠保證項(xiàng)目生產(chǎn)經(jīng)營(yíng)活動(dòng)順暢運(yùn)行，取得最佳的經(jīng)濟(jì)效益，是軟件項(xiàng)目過程管理的關(guān)鍵步驟。為了贏得市場(chǎng)并滿足預(yù)算、截止日期等要求，需要采用高效的軟件項(xiàng)目調(diào)度方案[1-2]。軟件項(xiàng)目調(diào)度(Software Project Scheduling Problem，SPSP)是一種將具有特定技能的員工有效地分配到需要完成的任務(wù)的資源約束調(diào)度問題[3-4]。其中，每個(gè)任務(wù)都有相應(yīng)的任務(wù)工作量和完成任務(wù)所需的技能，并且必須根據(jù)任務(wù)優(yōu)先級(jí)圖確定的任務(wù)間優(yōu)先級(jí)關(guān)系執(zhí)行。員工有薪水、個(gè)人技能和最大貢獻(xiàn)度值等屬性，并且能夠同時(shí)參與多項(xiàng)任務(wù)。SPSP確定每項(xiàng)任務(wù)分配給哪些員工和何時(shí)執(zhí)行，其目的是在滿足任務(wù)技能的限制和不過度工作等約束條件的前提下，實(shí)現(xiàn)縮短項(xiàng)目工期和減少項(xiàng)目成本等目標(biāo)[5-6]。

在軟件項(xiàng)目調(diào)度的研究中，通常假設(shè)每個(gè)任務(wù)所需的工作量是已知、固定的，同時(shí)在項(xiàng)目生命周期中沒有干擾任務(wù)執(zhí)行的動(dòng)態(tài)事件。但在現(xiàn)實(shí)軟件項(xiàng)目實(shí)施的過程中，工作環(huán)境會(huì)因?yàn)樾氯蝿?wù)的突然加入和某個(gè)員工的離開等不可預(yù)測(cè)事件的發(fā)生而動(dòng)態(tài)變化。此外，軟件項(xiàng)目活動(dòng)通常會(huì)有相當(dāng)大的不確定性，如，客戶需求的變化、任務(wù)工作量估計(jì)方法的固有誤差所帶來的任務(wù)工作量估計(jì)的不準(zhǔn)確、項(xiàng)目開始時(shí)未考慮的可預(yù)測(cè)及不可預(yù)測(cè)風(fēng)險(xiǎn)、事先無法預(yù)見的技術(shù)困難和人員流動(dòng)[7-8]。若將SPSP作為靜態(tài)問題處理而沒有考慮問題中包含的動(dòng)態(tài)性，容易導(dǎo)致獲得的最優(yōu)解存在巨大偏差。針對(duì)軟件項(xiàng)目的不確定性和不可預(yù)測(cè)動(dòng)態(tài)事件的發(fā)生，本文構(gòu)建了多目標(biāo)動(dòng)態(tài)軟件項(xiàng)目調(diào)度問題模型(Multi-Objective Dynamic Software Project Scheduling Problem, MODSPSP)并采用主動(dòng)重調(diào)度的方法來處理該問題。其中，針對(duì)任務(wù)工作量估計(jì)的不確定性引入魯棒性目標(biāo)；為了減少動(dòng)態(tài)事件發(fā)生對(duì)項(xiàng)目效率的影響，引入穩(wěn)定性目標(biāo)，故本文同時(shí)考慮持續(xù)時(shí)間、成本、調(diào)度的魯棒性和穩(wěn)定性4個(gè)目標(biāo)。

1 相關(guān)工作

隨著基于搜索的軟件工程的發(fā)展[9]，學(xué)者們將SPSP作為一個(gè)基于搜索的優(yōu)化問題。文獻(xiàn)[4]構(gòu)建了基于任務(wù)的問題模型，并采用遺傳算法求解最優(yōu)調(diào)度；文獻(xiàn)[5]采用了相同的問題模型，并對(duì)影響遺傳算法求解的重要問題特征進(jìn)行了系統(tǒng)的經(jīng)驗(yàn)研究；文獻(xiàn)[6]通過運(yùn)行時(shí)理論證明分析了進(jìn)化算法的設(shè)計(jì)選擇是如何影響求解性能的；文獻(xiàn)[10]將任務(wù)持續(xù)時(shí)間劃分成離散時(shí)間單位，通過迭代的方式將員工分配到離散時(shí)間單位的任務(wù)中，從而可以考慮更多的如員工的離開、學(xué)習(xí)和培訓(xùn)等人為因素，但頻繁的調(diào)度會(huì)導(dǎo)致系統(tǒng)的不穩(wěn)定性；文獻(xiàn)[11]構(gòu)建了基于事件的模型，并采用蟻群算法求解最優(yōu)調(diào)度。上述文獻(xiàn)均將軟件項(xiàng)目調(diào)度問題考慮為靜態(tài)問題。

到目前為止，研究涉及不確定項(xiàng)目環(huán)境下的動(dòng)態(tài)軟件項(xiàng)目調(diào)度的文獻(xiàn)比較有限。文獻(xiàn)[12]采用主動(dòng)調(diào)度的方法解決軟件項(xiàng)目調(diào)度中的不確定性；文獻(xiàn)[13]通過動(dòng)態(tài)資源重調(diào)度來處理軟件項(xiàng)目中的動(dòng)態(tài)事件；文獻(xiàn)[14]引入軟件項(xiàng)目中的不確定性和動(dòng)態(tài)事件，構(gòu)建了多目標(biāo)動(dòng)態(tài)軟件項(xiàng)目調(diào)度問題的數(shù)學(xué)模型MODSPSP，采用基于ε-占優(yōu)的主動(dòng)重調(diào)度方法來求解該問題，利用檔案存儲(chǔ)非支配解使得算法的多樣性得到提升；文獻(xiàn)[15]針對(duì)MODSPSP提出一種基于Q-learning的主動(dòng)重調(diào)度方法，并運(yùn)用Q-learning結(jié)合雙檔案平衡算法的收斂性和多樣性，使得算法性能得到提升，但也導(dǎo)致過多的計(jì)算量；雙歸檔進(jìn)化算法[16]通過收斂性檔案(Convergence Archives，CA)和多樣性檔案(Diversity Archives，DA)來平衡算法的收斂性和多樣性，以較低的復(fù)雜度獲得了不錯(cuò)的算法性能，但在處理較多目標(biāo)數(shù)的優(yōu)化問題時(shí)，雙歸檔算法容易陷入局部?jī)?yōu)化，據(jù)此文獻(xiàn)[17]提出更適于較多目標(biāo)優(yōu)化問題的改進(jìn)雙檔案進(jìn)化算法Two-Arch2，但由于在檔案維護(hù)方案中缺乏對(duì)邊界解的保護(hù)，在處理MODSPSP時(shí)，存在獲得的非支配解擴(kuò)展性差和命中率低的問題。

針對(duì)上述問題，本文提出一種改進(jìn)的雙檔案進(jìn)化算法(Improved Two-Archive evolutionary Algorithm, ITAA)以主動(dòng)重調(diào)度的方法來處理MODSPSP。在算法搜索過程中，首先，采用佳點(diǎn)集和啟發(fā)式策略進(jìn)行種群初始化；其次，利用評(píng)價(jià)函數(shù)自適應(yīng)地對(duì)兩種交叉和變異方法進(jìn)行概率選擇；最后，對(duì)收斂性檔案和多樣性檔案分別采用質(zhì)量指標(biāo)和動(dòng)態(tài)擁擠度距離進(jìn)行更新。綜上所述，ITAA以較低的算法復(fù)雜度，很好地平衡了算法的收斂性和多樣性，并在處理MODSPSP時(shí)，可以獲得質(zhì)量更高的Pareto解集。

2 問題模型

針對(duì)軟件項(xiàng)目調(diào)度問題的動(dòng)態(tài)性，本文設(shè)計(jì)了一個(gè)動(dòng)態(tài)多目標(biāo)軟件項(xiàng)目調(diào)度模型，具體描述如下：

2.1 員工屬性

假設(shè)項(xiàng)目有M個(gè)員工參與，項(xiàng)目完成需要S個(gè)技能數(shù)。記tl(l=1,2,3,…)為重調(diào)度點(diǎn)，其中重調(diào)度點(diǎn)包括初始點(diǎn)t0。每名員工ei具有屬性的描述如下：

2.2 任務(wù)屬性

假設(shè)在項(xiàng)目初始階段有N0個(gè)任務(wù)。隨著項(xiàng)目的進(jìn)行，新任務(wù)會(huì)逐個(gè)加入。本文假設(shè)在tl時(shí)刻有Nnew(tl)個(gè)新任務(wù)加入，即在tl時(shí)刻項(xiàng)目中已經(jīng)有共計(jì)N0+Nnew(tl)個(gè)任務(wù)需要考慮。每個(gè)任務(wù)Wj具有以下屬性：

TPG表示任務(wù)優(yōu)先級(jí)關(guān)系的有向圖；

2.3 動(dòng)態(tài)事件

本文主要針對(duì)軟件項(xiàng)目實(shí)施過程中經(jīng)常出現(xiàn)的不確定性和動(dòng)態(tài)事件，包括新任務(wù)的加入、員工的離開和回歸及任務(wù)工作量的不確定性，分別用el1，el2和el3表示動(dòng)態(tài)事件的類型、發(fā)生事件和其他的額外信息。具體描述如下：

ev={el1,el2,el3}；

(1)

(2)

(3)

(4)

假設(shè)所有動(dòng)態(tài)事件發(fā)生的概率服從泊松分布，同類型動(dòng)態(tài)事件間的發(fā)生時(shí)間服從指數(shù)分布。

2.4 解的表征

2.5 優(yōu)化目標(biāo)及約束

在每個(gè)重調(diào)度點(diǎn)tl(tl>t0)，需要考慮的優(yōu)化變量包括：一系列可被調(diào)用的員工e_ava_set(tl)、一系列可被調(diào)度的任務(wù)W_ava_set(tl)，以其相應(yīng)的剩余工作量和在tl時(shí)刻更新了的任務(wù)優(yōu)先級(jí)圖(Work Precedence Graph,WPG)。在重調(diào)度點(diǎn)tl，多目標(biāo)動(dòng)態(tài)軟件項(xiàng)目調(diào)度問題可以定義如下：

(5)

其中目標(biāo)函數(shù)[Td,Tc,Tr,Ts]對(duì)應(yīng)軟件項(xiàng)目的持續(xù)時(shí)間、項(xiàng)目成本、調(diào)度的魯棒性和穩(wěn)定性。

(6)

(7)

(8)

(9)

通過計(jì)算相鄰兩個(gè)重調(diào)度點(diǎn)間的偏差和來表示項(xiàng)目的穩(wěn)定性，目的是避免員工在不同調(diào)度點(diǎn)間被頻繁地調(diào)來調(diào)去。其中權(quán)重ωij的取值如下：

(10)

同時(shí)調(diào)度解還需要滿足如下約束條件：

(1)在tl時(shí)刻后的某個(gè)時(shí)間點(diǎn)t′，員工對(duì)其所有正在參與任務(wù)的貢獻(xiàn)度和不大于他的最大貢獻(xiàn)度值。

(2)所有參與分配任務(wù)的員工應(yīng)具有完成任務(wù)所需的所有技能數(shù)。

(3)分配到每項(xiàng)任務(wù)Wj中的員工不能大于該項(xiàng)任務(wù)的最大人手?jǐn)?shù)目限制。

在每個(gè)重調(diào)度點(diǎn)tl，軟件項(xiàng)目經(jīng)理可以通過相應(yīng)的決策方法選出一個(gè)非支配解作為調(diào)度方案實(shí)施[7]。據(jù)此，相應(yīng)的軟件項(xiàng)目總持續(xù)時(shí)間Fd和總成本Fc計(jì)算公式如下：

(11)

(12)

其中tL表示項(xiàng)目最后一個(gè)重調(diào)度點(diǎn)。

3 改進(jìn)的雙歸檔進(jìn)化算法

ITAA首先運(yùn)用種群初始化策略，獲得豐富多樣性和良好收斂性的初始種群；然后引入自適應(yīng)的子代生成策略，更優(yōu)地搜索解空間；最后結(jié)合質(zhì)量指標(biāo)Iε+[18]和動(dòng)態(tài)擁擠度距離[19]進(jìn)行檔案更新，以較低的復(fù)雜度很好地實(shí)現(xiàn)算法收斂性與多樣性的平衡?；镜碾p歸檔進(jìn)化算法見文獻(xiàn)[16-17]。

3.1 種群初始化策略

在雙歸檔進(jìn)化算法中，采用隨機(jī)方法進(jìn)行種群初始化，生成的種群往往分布不均勻，使得算法容易陷入局部最優(yōu)。針對(duì)該問題，本文引入佳點(diǎn)集理論[20]構(gòu)造搜索解空間的佳點(diǎn)，并將其作為初始種群。圖1為采用佳點(diǎn)集方法和隨機(jī)方法生成的規(guī)模為100的二維初始種群分布對(duì)比圖。由圖1可知，在相同的取點(diǎn)個(gè)數(shù)下，采用佳點(diǎn)集方法較隨機(jī)方法生成的初始種群分布更加均勻，多樣性更加豐富。

均勻分布的初始種群豐富了算法的多樣性，為遍歷解空間中的各種情況打下了基礎(chǔ)。為了進(jìn)一步提升算法處理MODSPSP的效率，本文針對(duì)MODSPSP的動(dòng)態(tài)特性和不同重調(diào)度點(diǎn)的歷史信息引入啟發(fā)式策略[15]。在每個(gè)調(diào)度點(diǎn)上，上一個(gè)調(diào)度留下的信息被視為可以利用的歷史信息；上一個(gè)重調(diào)度點(diǎn)，員工和任務(wù)間的貢獻(xiàn)度值分配方案被稱為歷史解決方案。首先，從新任務(wù)的加入、員工的離開和回歸這3種不同類型的動(dòng)態(tài)事件出發(fā)設(shè)計(jì)解的修復(fù)機(jī)制，針對(duì)上述情況下員工可能出現(xiàn)的加班問題，采用規(guī)范化進(jìn)行處理。然后，利用上一個(gè)重調(diào)度點(diǎn)生成的非支配解集中的歷史信息進(jìn)行種群初始化。

3.2 自適應(yīng)子代生成策略

在進(jìn)化算法尋優(yōu)過程中，如何協(xié)調(diào)算法的全局搜索和局部搜索是提升算法搜索效率的關(guān)鍵。單一的交叉、變異方法選擇和固定的交叉、變異概率往往只能使得某一方面的搜索能力得到強(qiáng)調(diào)，而不能起到協(xié)調(diào)作用。針對(duì)該問題，本文綜合考慮了MODSPSP的具體特點(diǎn)和種群的進(jìn)化過程提出一種自適應(yīng)的子代生成策略。

首先，通過結(jié)合兩種不同搜索能力的交叉、變異方法，引入的交叉方法包括具有較優(yōu)全局搜索能力的二項(xiàng)式交叉操作[21]和具有很強(qiáng)局部搜索能力的模擬二進(jìn)制交叉[22]；變異方法包括DE/rand/1變異策略和DE/best/1變異策略[23]。其次，利用評(píng)價(jià)函數(shù)比較兩種交叉方法產(chǎn)生后代與父代的優(yōu)劣關(guān)系，賦予表現(xiàn)更優(yōu)的交叉方法更大的交叉概率。在算法迭代初期，代表全局搜索能力的交叉方法通過大而廣的搜索獲得大量更優(yōu)的子代，由此被賦予更大的交叉概率，進(jìn)一步增強(qiáng)了算法在迭代初期的全局搜索能力。在算法迭代后期，代表局部搜索能力的交叉方法通過精而細(xì)的搜索容易獲得更優(yōu)的子代，由此被賦予更大的交叉概率，使得算法在迭代后期的局部搜索能力得到進(jìn)一步加強(qiáng)。

具體過程如下：

第i種交叉操作過后，比較第j個(gè)父代(Parentj)和它產(chǎn)生的后代(Offspringj)的優(yōu)劣性，并由此給出相應(yīng)的評(píng)價(jià)函數(shù)F(Crossi)：

(13)

(14)

(15)

其中：Pci表示第i種交叉操作交叉前的概率，Aft(Pci)表示第i種交叉操作交叉后的概率。

具體事例如表1所示?？梢钥闯?，本文提出的策略可以賦予表現(xiàn)更優(yōu)的交叉操作更大的交叉概率。

表1 自適應(yīng)交叉操作實(shí)例

同理，變異操作也采用與上述交叉操作同樣的自適應(yīng)方法。

自適應(yīng)子代生成策略具體過程如下：

步驟1交叉操作。從CA(tl)中隨機(jī)選出兩個(gè)體x1和x2，比較兩個(gè)個(gè)體的占優(yōu)關(guān)系，若x1?x2則選擇x1作為父代個(gè)體，同理從DA(tl)選出另外一個(gè)父代個(gè)體，進(jìn)行交叉操作獲得子代個(gè)體加入D1(tl)，直到|D1(tl)|=2×npop。

步驟2變異操作。從CA(tl)中隨機(jī)選出一個(gè)個(gè)體進(jìn)行變異操作，將獲得的子代個(gè)體加入D2(tl)，直到|D(tl)|=npop。

步驟3D(tl)=D1(tl)∪D2(tl)，輸出D(tl)。

3.3 檔案更新策略

在雙歸檔進(jìn)化算法中，采用基于Pareto占優(yōu)關(guān)系的檔案更新策略，豐富了算法的多樣性，但在處理MODSPSP時(shí)，無法提供足夠的選擇壓力，直接影響了算法收斂。另外，固定的總檔案規(guī)模容易造成算法的多樣性缺失，因?yàn)楫?dāng)CA中的解均來自問題的Pareto前沿而CA的個(gè)體數(shù)已經(jīng)達(dá)到檔案的總規(guī)模時(shí)，會(huì)導(dǎo)致檔案DA中個(gè)體的缺失，直接影響算法的多樣性。針對(duì)這些問題，本文對(duì)檔案CA和DA分別采用固定的檔案規(guī)模nCA和nDA，引入具有良好收斂表現(xiàn)的質(zhì)量指標(biāo)Iε+對(duì)檔案CA進(jìn)行更新，在Pareto占優(yōu)關(guān)系的基礎(chǔ)上引入動(dòng)態(tài)擁擠度距離對(duì)檔案DA進(jìn)行更新。

3.3.1 CA更新策略

質(zhì)量指標(biāo)Iε+的計(jì)算公式如下：

(16)

(17)

其中:x1,x2表示解向量，m表示目標(biāo)，F(xiàn)(x)表示對(duì)應(yīng)個(gè)體的收斂性適應(yīng)度值。

具體過程如下：

步驟1將CA和子代種群Q組合成混合種群Hc。

步驟2找出混合種群Hc中的非重復(fù)解記為CA(tl)。

步驟5若|CA(tl)|>nCA依然成立，返回步驟3；否則更新結(jié)束。

3.3.2 DA更新策略

在處理MODSPSP時(shí)，保留所有Pareto最優(yōu)解不僅沒有實(shí)際意義且計(jì)算量巨大，軟件項(xiàng)目經(jīng)理需要的是一系列均勻分布的Pareto最優(yōu)解。針對(duì)該問題，引入合理的多樣性維護(hù)方法是關(guān)鍵。擁擠度距離排序法作為一種常見的多樣性維護(hù)方法[24]，能在保證對(duì)問題Pareto前沿良好覆蓋的情況下，剔除集中在密集區(qū)域的解個(gè)體。計(jì)算方法如下：

(18)

其中：Li表示xi的擁擠度距離，xi-1和xi+1是距離xi最近的兩個(gè)點(diǎn)，fk(xi-1)和fk(xi+1)為對(duì)應(yīng)的目標(biāo)函數(shù)值。但這種方法可能會(huì)在同一時(shí)間刪除密集區(qū)域的大量個(gè)體，影響解的均勻分布。針對(duì)該問題，本文引入動(dòng)態(tài)擁擠度距離，在二維解空間兩種方法得到的Pareto最優(yōu)解分布對(duì)比如圖2所示。顯然，采用動(dòng)態(tài)擁擠距離對(duì)檔案進(jìn)行更新，得到的解分布更加均勻。

具體過程如下：

步驟1將DA和子代種群Q組合成混合種群Hd。

步驟2將混合種群Hd中的非支配解記為DA(tl)。

步驟3若|DA(tl)|>nDA，初始化DA(tl)中個(gè)體的擁擠度距離，將邊界解個(gè)體初始化一個(gè)極大值，保證所有的邊界解在下一次迭代中可用。

步驟6若|DA(tl)|>nDA依然成立，返回步驟4；否則更新結(jié)束。

3.4 算法步驟

步驟1主動(dòng)調(diào)度。在軟件項(xiàng)目初始階段取l=0，利用ITAA自動(dòng)生成一系列優(yōu)化目標(biāo)為項(xiàng)目持續(xù)時(shí)間、項(xiàng)目成本、調(diào)度的魯棒性和穩(wěn)定性的非支配解，并從中選擇一個(gè)解作為調(diào)度方案實(shí)施。

步驟2重調(diào)度。當(dāng)動(dòng)態(tài)事件發(fā)生，l=l+1，在每個(gè)重調(diào)度點(diǎn)有如下子步驟：

(1)初始化。對(duì)檔案CA和DA運(yùn)用3.1節(jié)種群初始化策略初始化相應(yīng)種群規(guī)模的檔案?jìng)€(gè)體，根據(jù)正態(tài)分布隨機(jī)取樣任務(wù)工作量θq,q=1,2,…,Q，初始化最大目標(biāo)向量評(píng)估數(shù)NumEvl，賦值ct=0。

(2)生成子代。根據(jù)正態(tài)分布隨機(jī)取樣一系列任務(wù)工作量θ′q，q=1,2,…,Q，根據(jù)3.2節(jié)提出的自適應(yīng)子代生成策略生成子代D(tl)，ct=ct+|D(tl)|。

(3)檔案更新。對(duì)于加入的子代個(gè)體D(tl)根據(jù)3.3節(jié)提出的檔案更新策略進(jìn)行更新，以維持CA和DA所具有固定種群規(guī)模nCA和nDA。

(4)直到ct=NumEvl，輸出表示優(yōu)化目標(biāo)為項(xiàng)目持續(xù)時(shí)間、項(xiàng)目成本、調(diào)度的魯棒性和穩(wěn)定性的非支配解集DA，并從中選擇一個(gè)解作為調(diào)度方案實(shí)施，直到軟件項(xiàng)目中的任務(wù)全部完成。

3.5 算法復(fù)雜度

設(shè)雙歸檔進(jìn)化算法的種群規(guī)模為N，針對(duì)目標(biāo)數(shù)M的優(yōu)化問題，算法復(fù)雜度分析如下：

3.5.1 時(shí)間復(fù)雜度

初始化種群，包括兩檔案2N個(gè)體，復(fù)雜度是Ο(2N)；自適應(yīng)的子代生成策略，包括生成3N子代，并在生成過程引入評(píng)價(jià)函數(shù)，復(fù)雜度最多為Ο(9N2)；檔案更新策略，包括檔案CA中個(gè)體適應(yīng)度的計(jì)算，并在最差適應(yīng)度解剔除后剩余個(gè)體適應(yīng)度的重新計(jì)算，復(fù)雜度最多為Ο(MN2)，檔案DA中個(gè)體適應(yīng)度的計(jì)算，并在最差適應(yīng)度解剔除后相鄰個(gè)體適應(yīng)度的重新計(jì)算，復(fù)雜度最多為Ο(MN2)。通過上述分析，ITAA整體時(shí)間復(fù)雜度為Ο(MN2)。

3.5.2 空間復(fù)雜度

存儲(chǔ)檔案CA和DA中個(gè)體的每個(gè)參數(shù)所需的空間均為N；存儲(chǔ)每個(gè)個(gè)體所需的空間為M，則存儲(chǔ)2N個(gè)體所需空間為2MN；子代生成過程中利用評(píng)價(jià)函數(shù)調(diào)整交叉、變異概率所需空間為3N；其他參數(shù)所需空間均為常數(shù)。經(jīng)過上述分析，算法搜索過程的空間復(fù)雜度為Ο(MN)。

4 實(shí)驗(yàn)部分

本文所有程序代碼均采用Java語言和Eclipse軟件編寫，使用的PC機(jī)配置如下，操作系統(tǒng)：64位Windows 10，處理器：Intel(R)Core(TM) i7-7700 CPU 3.60 GHz，內(nèi)存：16 G。

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

為了分析改進(jìn)策略的有效性，設(shè)置如下對(duì)比算法：基本雙歸檔算法Two-Arch[16]，在基本算法中加入種群初始化策略TA-PIS，再加入自適應(yīng)子代生成策略TA-PIS-AOG。在實(shí)例選擇上，本文針對(duì)文獻(xiàn)[15]中的21個(gè)實(shí)例進(jìn)行求解，考慮了任務(wù)工作量的不確定性和3種不同類型的動(dòng)態(tài)事件(包括新任務(wù)的加入、員工的離開和回歸)，同時(shí)還將任務(wù)的最大完成人數(shù)、員工的技能等級(jí)、員工兼職、加班考慮在內(nèi)。實(shí)例包含不同的員工數(shù)、任務(wù)數(shù)和員工掌握的技能數(shù)，初始的任務(wù)數(shù)為10,20,30，10個(gè)新任務(wù)逐個(gè)加入到項(xiàng)目中，員工數(shù)為5,10,15，員工掌握的技能數(shù)為4～5和6～7。記18個(gè)MODSPSP實(shí)例為s#1_d#2_E#3_SK#4～#5，s#1表示初始任務(wù)數(shù)，d#2表示加入的動(dòng)態(tài)任務(wù)數(shù)，E#3表示員工數(shù)，SK#4～#5表示每個(gè)員工具有4～5技能，3個(gè)現(xiàn)實(shí)實(shí)例記為r1、r2和r3。

根據(jù)2.5節(jié)的描述可知，當(dāng)算法在不同的重調(diào)度點(diǎn)都能有良好且穩(wěn)定的表現(xiàn)時(shí)，即可獲得更優(yōu)的項(xiàng)目總持續(xù)時(shí)間和成本。因此，本文的實(shí)驗(yàn)將從整體和不同重調(diào)度點(diǎn)的Pareto解集兩方面進(jìn)行設(shè)計(jì)。

具體的參數(shù)設(shè)置如下，ITAA的種群規(guī)模npop=100，CA和DA的固定個(gè)體數(shù)nCA=nDA=100，任務(wù)工作量不確定性抽樣數(shù)q=30，初始交叉概率：多項(xiàng)式交叉和模擬二進(jìn)制交叉的交叉概率取0.45；初始變異概率：DE/rand/1和DE/best/1的變異概率取0.05，最大目標(biāo)向量評(píng)估次數(shù)NumEvl=16 000。20%的初始化種群個(gè)體來自啟發(fā)式策略，剩余的80%個(gè)體采用佳點(diǎn)集方法生成。為了保證對(duì)比實(shí)驗(yàn)的公平性，對(duì)比算法具有相同的參數(shù)設(shè)置。本文采用文獻(xiàn)[15]的中決策過程在每個(gè)重調(diào)度點(diǎn)選出一個(gè)調(diào)度方案實(shí)施，以保證在每個(gè)重調(diào)度點(diǎn)算法能在同一環(huán)境下比較。

4.2 實(shí)例Pareto解集比較

4.2.1 IGD分析

如表2所示，ITAA在所有的現(xiàn)實(shí)實(shí)例中都表現(xiàn)最優(yōu)。18個(gè)MODSPSP實(shí)例中，與Two-Arch算法相比，ITAA在16個(gè)實(shí)例上顯著優(yōu)，2例相似。與TA-PIS算法相比，ITAA在14個(gè)實(shí)例上顯著優(yōu)，2例相似，2例較差。與TA-PIS-AOG算法相比，ITAA在8個(gè)實(shí)例上顯著優(yōu)，9例相似，僅有1例較差。而且在17個(gè)實(shí)例中有最優(yōu)的平均值，綜合表明ITAA有著明顯優(yōu)于其他3種算法的性能表現(xiàn)。

4.2.2 命中率分析

命中率(Hitrate)指的是程序找到可行方案解的次數(shù)(FRuns)與程序運(yùn)行的總次數(shù)(Runs)間的比值，即

(19)

將算法在21個(gè)實(shí)例上的命中率實(shí)驗(yàn)結(jié)果記錄于表2。如表2所示，Two-Arch算法的總體命中率偏低，有的實(shí)例甚至為0。當(dāng)對(duì)Two-Arch算法采用種群初始化策略后，在所有實(shí)例上的命中率都達(dá)到了100%。在此基礎(chǔ)上，先后采用自適應(yīng)子代生成策略和檔案更新策略，命中率依然維持在100%，說明改進(jìn)策略對(duì)算法命中率提高的有效性和穩(wěn)定性。

4.3 重調(diào)度點(diǎn)Pareto解集比較

為了證實(shí)算法在不同重調(diào)度點(diǎn)都能生成一個(gè)具有好的收斂性且均勻廣泛分布的Pareto解集。本文針對(duì)3個(gè)不同實(shí)例從最優(yōu)值、平均值和最差值出發(fā)繪制圖3所示曲線圖；隨機(jī)選擇實(shí)例sT20_d10_E15_SK6～7，tl=16.8，員工e2返回，項(xiàng)目中還有9個(gè)任務(wù)需要完成，繪制圖4所示平面圖。

4.3.1 重調(diào)度點(diǎn)IGD分析

如圖3所示，ITAA在大多數(shù)的重調(diào)度點(diǎn)都表現(xiàn)最優(yōu)且表現(xiàn)穩(wěn)定，說明ITAA在不同重調(diào)度點(diǎn)具有穩(wěn)定的良好表現(xiàn)。對(duì)比Two-Arch算法，隨著改進(jìn)策略的加入，算法的收斂性和多樣性表現(xiàn)呈漸進(jìn)式增長(zhǎng)且逐漸趨于穩(wěn)定，更加說明了改進(jìn)策略的有效性。

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

4.3.2 重調(diào)度點(diǎn)解的分布

由于MODSPSP的4個(gè)目標(biāo)具有不同的規(guī)模，利用對(duì)比算法所有運(yùn)行過程中記錄的最大、最小目標(biāo)值對(duì)Pareto解集中的目標(biāo)值進(jìn)行了歸一化，得到圖4所示的平行坐標(biāo)圖。如圖4所示，ITAA生成的非支配解集在目標(biāo)空間中有著良好的分布?？梢钥闯?，Pareto解集不是在一個(gè)有限的區(qū)域內(nèi)，而是分布在一個(gè)較大的范圍內(nèi)。這一結(jié)果表明了ITAA在重調(diào)度點(diǎn)tl能生成一個(gè)具有好的收斂性且均勻廣泛分布的Pareto解集。

5 結(jié)束語

本文針對(duì)雙歸檔進(jìn)化算法在處理多目標(biāo)動(dòng)態(tài)軟件項(xiàng)目調(diào)度時(shí)，算法的收斂性、多樣性和復(fù)雜度難以平衡和命中率低的問題，提出一種改進(jìn)的雙歸檔進(jìn)化算法來求解該問題。首先，采用佳點(diǎn)集方法和啟發(fā)式策略進(jìn)行種群初始化；然后，利用評(píng)價(jià)函數(shù)自適應(yīng)地對(duì)兩種代表不同搜索能力的交叉、變異方法進(jìn)行概率調(diào)整；最后，引入質(zhì)量指標(biāo)Iε+和動(dòng)態(tài)擁擠度距離分別對(duì)收斂性檔案和多樣性檔案進(jìn)行更新。

員工作為軟件項(xiàng)目調(diào)度需要考慮的唯一資源，在未來工作中將引入更多的員工屬性，使得問題模型更具現(xiàn)實(shí)意義。