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

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

0 引言

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

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

1 相關(guān)工作

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

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

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

2 問題模型

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

2.1 員工屬性

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

2.2 任務(wù)屬性

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

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

2.3 動態(tài)事件

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

ev={el1,el2,el3}；

(1)

(2)

(3)

(4)

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

2.4 解的表征

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

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

(5)

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

(6)

(7)

(8)

(9)

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

(10)

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

(1)在tl時刻后的某個時間點t′，員工對其所有正在參與任務(wù)的貢獻度和不大于他的最大貢獻度值。

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

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

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

(11)

(12)

其中tL表示項目最后一個重調(diào)度點。

3 改進的雙歸檔進化算法

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

3.1 種群初始化策略

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

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

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

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

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

具體過程如下：

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

(13)

(14)

(15)

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

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

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

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

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

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

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

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

3.3 檔案更新策略

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

3.3.1 CA更新策略

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

(16)

(17)

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

具體過程如下：

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

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

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

3.3.2 DA更新策略

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

(18)

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

具體過程如下：

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

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

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

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

3.4 算法步驟

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

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

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

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

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

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

3.5 算法復(fù)雜度

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

3.5.1 時間復(fù)雜度

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

3.5.2 空間復(fù)雜度

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

4 實驗部分

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

4.1 實驗設(shè)置

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

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

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

4.2 實例Pareto解集比較

4.2.1 IGD分析

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

4.2.2 命中率分析

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

(19)

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

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

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

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

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

表2 實驗結(jié)果

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

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

5 結(jié)束語

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

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