基于改進(jìn)自適應(yīng)遺傳算法的并行測試任務(wù)調(diào)度

姜 瑞,韓 堯,張大為

(電子科技大學(xué) 航空航天學(xué)院,成都 611731)

0 引言

隨著科學(xué)技術(shù)的不斷進(jìn)步,現(xiàn)代高精尖設(shè)備的復(fù)雜度不斷提高,這對系統(tǒng)的自動測試性能提出了新的挑戰(zhàn)[1-3]。特別是在兵器裝備領(lǐng)域,需要測試的參數(shù)龐雜且對準(zhǔn)確性與實(shí)時性有較高要求。并行測試通過調(diào)用相應(yīng)資源同時對多個任務(wù)進(jìn)行測試改善自動測試系統(tǒng)測試效率低、資源利用率低等問題[4]。并行測試需要考慮資源競爭、系統(tǒng)死鎖與餓死等問題,導(dǎo)致其任務(wù)調(diào)度方案的確定困難且優(yōu)化難度較大。

并行測試任務(wù)調(diào)度問題研究的目標(biāo)是確定最優(yōu)調(diào)度方案,如測試時間最短,執(zhí)行價值最大、負(fù)載均衡等。目前主要有2種研究方向:一是只使用智能算法,通過智能算法良好的全局優(yōu)化性能求解調(diào)度方案,比如粒子群算法[5-6]、遺傳算法[7-8]、蟻群算法[9-11]、模擬退火算法[12-13]等;二是使用Petri網(wǎng)與智能算法相結(jié)合[14-16],首先利用Petri網(wǎng)模型強(qiáng)大的建模能力對調(diào)度過程進(jìn)行建模,然后使用智能算法求解調(diào)度方案。

遺傳算法具有優(yōu)秀的全局搜索能力,強(qiáng)魯棒性,設(shè)計(jì)簡單等特點(diǎn),適用于解決并行測試任務(wù)調(diào)度這類最優(yōu)化問題。但是,傳統(tǒng)遺傳算法采用固定的交叉與變異概率,當(dāng)交叉與變異概率較小時會導(dǎo)致種群的進(jìn)化速度較低,增加迭代次數(shù),降低算法的收斂速度,影響任務(wù)調(diào)度的實(shí)時性;當(dāng)交叉與變異概率較大時會導(dǎo)致種群的進(jìn)化速度過快,容易錯過最優(yōu)解,一些優(yōu)勢個體的基因會在種群中迅速擴(kuò)散,種群多樣性喪失,容易出現(xiàn)陷入局部最優(yōu)解的情況,導(dǎo)致得到的調(diào)度方案不是最優(yōu)調(diào)度方案,達(dá)不到優(yōu)化的目的。

針對遺傳算法的改進(jìn),Srinivas等[17]首次提出了自適應(yīng)遺傳算法(adaptive genetic algorithm,AGA),該算法根據(jù)個體適應(yīng)度值調(diào)節(jié)交叉與變異概率,在一定程度上解決了遺傳算法容易陷入局部最優(yōu)解的問題,但是該算法會使適應(yīng)度值較大的優(yōu)勢個體的交叉與變異概率接近或者等于零,導(dǎo)致優(yōu)勢個體的特征不被遺傳,陷入局部最優(yōu)解。任子武等[18]提出了一種改進(jìn)的自適應(yīng)遺傳算法(improved adaptive genetic algorithm,IAGA),保證所有個體都有一個最低的交叉與變異概率,但是在算法迭代后期,個體的適應(yīng)度值與平均適應(yīng)度值相近且這些個體數(shù)量較大時,會導(dǎo)致大部分個體的交叉與變異概率較低,可能出現(xiàn)陷入局部最優(yōu)解的情況。

本文中提出了一種基于種群相異度的自適應(yīng)遺傳算法(adaptive genetic algorithm based on population diversity,AGAPD)用于求解并行測試任務(wù)調(diào)度問題,該算法根據(jù)種群相異度對遺傳算法的交叉與變異概率進(jìn)行自適應(yīng)取值,改善了遺傳算法容易陷入局部最優(yōu)解的問題,提高算法收斂速度以及搜索最優(yōu)解的成功率,使其在解決任務(wù)調(diào)度問題時可以快速、準(zhǔn)確地求出最優(yōu)調(diào)度方案。

1 并行測試任務(wù)調(diào)度問題描述

在測試過程中,規(guī)定同一資源在同一時刻下最多只能被一個測試任務(wù)占用,且資源被占用時間等于測試該任務(wù)所需時間。在上述基礎(chǔ)上對任務(wù)調(diào)度問題建立數(shù)學(xué)模型,將模型中所涉及的參數(shù)進(jìn)行如下定義:

1) 測試任務(wù)集T={t1,t2,t3,…,tm}:表示被測試的任務(wù);

2) 測試資源集R={r1,r2,r3,…,rn}:表示對測試任務(wù)集T進(jìn)行測試所需要的資源,如儀器、通道等;

3) 測試時間集τ={τ1,τ2,τ3,…,τm}:表示完成測試任務(wù)所需的時間;

4) 任務(wù)資源矩陣TRm×n:表示資源被占用的情況,若TRm×n(i,j)=1,則任務(wù)ti在測試時需要占用資源rj,否則任務(wù)ti不占用資源rj;

5) 任務(wù)約束矩陣TSm×m:表示任務(wù)執(zhí)行的先后順序,若TSm×m(i,j)=1,則任務(wù)ti需要在任務(wù)tj之前執(zhí)行,否則任務(wù)ti與任務(wù)tj無時序關(guān)系;

6) 任務(wù)調(diào)度序列Tp:表示具體的任務(wù)調(diào)度方案,Tp為n×y的矩陣,y為最大執(zhí)行步驟,若Tp(i,j)=tk(1≤k≤m),則表示資源ri在第j個步驟時被任務(wù)tk占用。

并行測試任務(wù)調(diào)度問題是在已知測試任務(wù)集T,測試資源集R,測試時間集τ以及任務(wù)資源矩陣TRm×n的情況下確定滿足任務(wù)約束矩陣TSm×m的最優(yōu)任務(wù)調(diào)度序列Tp。

2 并行測試任務(wù)調(diào)度算法設(shè)計(jì)

本文中采用遺傳算法求解并行測試任務(wù)調(diào)度問題,遺傳算法通過選擇、交叉、變異操作模擬自然界生物進(jìn)化的過程,不斷產(chǎn)生優(yōu)秀個體達(dá)到搜索最優(yōu)解的目的[19]。傳統(tǒng)遺傳算法交叉與變異概率都是采用的固定值,種群在進(jìn)化的過程中其特征會不斷變化,固定的交叉與變異概率會對算法性能造成嚴(yán)重影響,如陷入局部最優(yōu)解、降低收斂速度等。

2.1 自適應(yīng)遺傳算法的改進(jìn)

為改善遺傳算法易陷入局部最優(yōu)解、收斂速度下降等問題,提出將種群的多樣性與遺傳算法的交叉與變異概率關(guān)聯(lián)起來,并給出了描述種群多樣性的方法。種群的多樣性與遺傳算法的交叉與變異概率的具體關(guān)聯(lián)如下:

1) 當(dāng)種群的多樣性較大時,此時降低交叉與變異概率,可減小種群進(jìn)化速度,提高搜索精度;

2) 當(dāng)種群的多樣性較小時,增大交叉與變異概率,從而提高種群進(jìn)化速度,避免陷入局部最優(yōu)解。

上述改進(jìn)使得在整個迭代過程中,交叉與變異概率都有合適的取值,保證種群的多樣性,減小陷入局部最優(yōu)解的可能性。

2.1.1編碼與種群初始化

編碼方式?jīng)Q定了個體上基因的表現(xiàn)形式以及選擇、交叉、變異操作的執(zhí)行,常見的基因編碼方式有二進(jìn)制編碼、格雷碼編碼、整數(shù)編碼等。為解決任務(wù)調(diào)度問題,采用整數(shù)編碼的方式更加適用于實(shí)際情況。

在任務(wù)調(diào)度問題中,基因代表著某個具體的被測試任務(wù);由基因構(gòu)成的個體代表著調(diào)度方案;由個體組成的種群表示一個解集。

通過對基因進(jìn)行隨機(jī)排序的方式生成個體,多次生成個體直至個體數(shù)量達(dá)到種群大小,完成種群的初始化。隨機(jī)排序是為了讓個體盡可能隨機(jī),使得初始種群在整個解空間均勻分布。假設(shè)有測試任務(wù)集T={t1,t2,t3,…,t10},共10個測試任務(wù),要求t3需在t5之前執(zhí)行,編碼與種群初始化的具體步驟如下:

步驟1對每個測試任務(wù)進(jìn)行編碼,將測試任務(wù)集T編碼為{1,2,3,4,3,6,7,8,9,10},將t3與t5都編碼為“3”,在所有個體中第一個“3”代表t3,第二個“3”代表t5,保證t3在t5之前執(zhí)行。

步驟2對編碼進(jìn)行隨機(jī)排序,得到一個個體,如:{9,2,3,7,10,8,3,6,4,1}等。

步驟3重復(fù)步驟2直至個體的數(shù)量達(dá)到種群大小。

2.1.2適應(yīng)度函數(shù)設(shè)計(jì)

在遺傳算法中依靠個體的適應(yīng)度值來評價個體的優(yōu)劣,決定種群的進(jìn)化方向。適應(yīng)度函數(shù)根據(jù)具體問題的優(yōu)化方向不同而存在差異,本文中并行測試任務(wù)調(diào)度研究的目標(biāo)是確定總測試時間最短的調(diào)度方案,因此使用總測試時間作為評價個體優(yōu)劣的標(biāo)準(zhǔn)。

加速度比f是評價并行測試完成測試所需時間長短的函數(shù),其表達(dá)式為

(1)

其中:time(Tp)為Tp所表示的調(diào)度方案完成測試所需時間。采用f作為適應(yīng)度函數(shù),其值越大表示個體越優(yōu)秀。

2.1.3選擇算子

選擇操作[20]的目的是為了從種群中選擇個體進(jìn)行交叉與變異操作,采用輪盤賭算法與精英保留策略進(jìn)行選擇,確保優(yōu)勢基因能夠盡可能遺傳給子代,增加產(chǎn)生更優(yōu)秀子代的可能性。輪盤賭算法依據(jù)個體的適應(yīng)度值進(jìn)行選擇,當(dāng)個體的適應(yīng)度值越大時,其被選擇的概率就越大,使得優(yōu)秀個體的基因遺傳給子代的可能性更大。精英保留策略將一部分優(yōu)秀個體直接選中并遺傳給子代,解決使用輪盤賭算法時優(yōu)秀個體可能沒有被選擇或者被交叉與變異操作破壞的問題。

使用輪盤賭算法得到的選擇概率為

(2)

其中:pi為第i個個體被選擇的概率,fi為第i個個體的適應(yīng)度值,N為種群大小。

2.1.4交叉算子

交叉操作[21]通過交叉2個父代部分基因片段得到子代,將自身的部分特征遺傳給子代,增加種群多樣性,提高全局搜索能力。采用兩點(diǎn)交叉方式,具體步驟如下:

步驟1隨機(jī)選擇需要交叉的父代及交叉基因片段,如圖1所示,藍(lán)色與黃色部分表示對應(yīng)父代需要交叉的片段。

圖1 父代及交叉片段

步驟2交換基因片段,不需要交換的基因位置使用“X”進(jìn)行占位,如圖2所示。

圖2 交叉操作

步驟3為了防止編碼沖突,首先,在父代p1基因中刪除子代c1已填入的基因,可得到基因片段s1={3,7,10,8,4,1}。然后,將s1中的基因按順序填入子代c1中,得到新的子代c1。同理得到新的子代c2,如圖3所示。

圖3 交叉得到的子代

2.1.5變異算子

變異操作[21]通過父代改變自身的某些基因來產(chǎn)生子代,增加種群的多樣性,可在一定程度上避免局部最優(yōu)的情況。采用逆序變異方式,具體步驟如下:

步驟1隨機(jī)選擇需要變異的父代及變異基因片段,如圖4所示,藍(lán)色部分表示父代需要變異的片段。

圖4 父代及變異片段

步驟2將基因片段逆序生成子代,如圖5所示,黃色部分表示逆序之后的片段。

圖5 變異得到的子代

2.1.6自適應(yīng)交叉與變異概率

多樣性是種群的重要屬性,漢明距離是評價種群多樣性的基本方法,但對要求多種離散值的復(fù)雜組合優(yōu)化問題等無法適用[22]。個體基因間的差異性并無大小之分,使用漢明距離并不能正確反映其差異,如“1”與“2”的漢明距離是2,“1”與“3”的漢明距離是1,但實(shí)際上,基因間差異的評價值應(yīng)該相同。本文中將種群多樣性用相異度進(jìn)行表述,對基因間的差異進(jìn)行一致性處理,可以更加準(zhǔn)確的反應(yīng)個體之間的差異。定義個體之間的相異度di,j為

(3)

(4)

其中:di,j為個體xi與xj的相異度;xik、xjk分別為個體xi與xj的第k個基因。

種群整體的相異度D為

(5)

(6)

根據(jù)當(dāng)前種群的平均適應(yīng)度值,將個體分為劣勢個體和優(yōu)勢個體。對于劣勢個體,即適應(yīng)度值較小的個體,它們的基因應(yīng)該改變,讓其交叉與變異概率最大,增加在子代中產(chǎn)生更好個體的可能性。對于優(yōu)勢個體,即適應(yīng)度值較大的個體,它們擁有較好的基因,讓越好的個體的交叉與變異概率越小,增加優(yōu)秀基因保留的可能性。

定義交叉與變異概率為

(7)

(8)

其中:pc為交叉概率;pcmax為初始化最大交叉概率;pcmin為初始化最小交叉概率;D0為初始種群的相異度;f′為交叉操作中較大的父代個體適應(yīng)度值;favg為種群的平均適應(yīng)度值;pm為變異概率;pmmax為初始化最大變異概率;pmmin為初始化最小變異概率;f為變異個體的適應(yīng)度值;o為等價無窮小,防止分母為0。

根據(jù)式(7)、式(8)可繪制出自適應(yīng)交叉與變異概率的變化圖像,如圖6、圖7所示。

圖6 自適應(yīng)交叉概率

圖7 自適應(yīng)變異概率

可以看出,對于適應(yīng)度值小于平均適應(yīng)度值的個體,其交叉與變異概率采用最大值;對于適應(yīng)度值大于平均適應(yīng)度值的個體,根據(jù)其適應(yīng)度值和當(dāng)前種群相異度D與初始種群相異度D0的比值確定交叉與變異概率。

在迭代過程中,當(dāng)種群的多樣性較高時,種群相異度D與初始種群相異度D0相近,式(7)、式(8)變?yōu)?/p>

(9)

(10)

當(dāng)種群的多樣性較低,種群相異度D遠(yuǎn)小于初始種群相異度D0時,式(7)、式(8)變?yōu)?/p>

pc=pcmax

(11)

pm=pmmax

(12)

初始種群在整個解空間隨機(jī)分布,此時種群的多樣性最豐富,相異度最大。隨著迭代次數(shù)的增加,種群會向最優(yōu)解方向進(jìn)化,越來越多的個體會進(jìn)化出最優(yōu)解的特征,種群多樣性降低,相異度減小。在算法迭代前期,種群的相異度D與初始種群的相異度D0相近,交叉與變異概率接近式(9)、式(10),與IAGA算法中的交叉與變異概率相同。在迭代后期,種群通過不斷向最優(yōu)解方向進(jìn)化,種群的相異度D降低,交叉與變異概率接近式(11)、式(12),可以有效解決IAGA算法迭代后期大部分個體交叉與變異概率較低的問題。

總體來看,式(7)、式(8)會在種群多樣性較大時,減小交叉與變異概率,減緩種群進(jìn)化速度,提高局部搜索能力,避免錯過最優(yōu)解。在種群多樣性較小時,增大交叉與變異概率,加快種群進(jìn)化速度,提高全局搜索能力,減小陷入局部最優(yōu)解的可能性,由于采用了精英保留策略,此時并不會丟失當(dāng)前最優(yōu)解。這使得整個迭代過程中的交叉與變異概率都有合適的取值,保證了種群多樣性,可以解決遺傳算法容易陷入局部最優(yōu)解的問題,加快算法收斂速度。

2.2 AGAPD算法的收斂性分析

設(shè)AGAPD算法的解空間為E,第k次迭代產(chǎn)生的種群看作狀態(tài)X(k),X(k)?E。由于在整個迭代過程中選擇、交叉、變異操作都隨機(jī)的,可以將X(k)看作是一個離散隨機(jī)序列。

X(k+1)在迭代過程中僅通過對X(k)進(jìn)行選擇、交叉、變異產(chǎn)生,故對于任意的k≥0,以及y0,y1,y2,…,yk+1?E,滿足條件概率:

P{X(k+1)=yk+1|X(0)=y0,X(1)=y1,…,X(k)=yk}=

P{X(k+1)=yk+1|X(k)=yk}

(13)

因此,X(k)具有馬爾科夫性。

根據(jù)馬爾科夫鏈求解AGAPD算法的收斂性,將X(k)看作馬爾科夫鏈中的一個狀態(tài),種群的迭代過程可以看作是馬爾科夫鏈中狀態(tài)的轉(zhuǎn)移。由于AGAPD算法采用了精英保留策略,即X(k)中的優(yōu)秀個體會直接遺傳給X(k+1),當(dāng)X(k)含有最優(yōu)解時,X(k+1)一定包含有最優(yōu)解,滿足條件概率:

(14)

因此,AGAPD算法以概率1收斂于全局最優(yōu),即具有全局收斂性。

2.3 AGAPD算法流程

基于AGAPD算法的并行測試任務(wù)調(diào)度問題求解流程如圖8所示,其基本步驟如下:

圖8 改進(jìn)的遺傳算法流程圖

步驟1初始化算法參數(shù)。獲得測試任務(wù)信息:測試任務(wù)集T,測試資源集R,測試時間集τ,任務(wù)資源矩陣TRm×n以及任務(wù)約束矩陣TSm×m;設(shè)置種群大小,最大迭代次數(shù);最大交叉概率pcmax,最小交叉概率pcmin,最大變異概率pmmax,最小變異概率pmmin。

步驟2采用整數(shù)編碼的方式對測試任務(wù)進(jìn)行編碼,并以隨機(jī)排序的方式生成個體。

步驟3根據(jù)初始化得到的種群計(jì)算初始種群的相異度D0。

步驟4計(jì)算每個個體的適應(yīng)度值。

步驟5判斷是否滿足終止條件,此處終止條件為迭代次數(shù)是否達(dá)到最大迭代次數(shù),如果是則執(zhí)行步驟9,否則執(zhí)行步驟6。

步驟6使用輪盤賭算法與精英保留策略進(jìn)行選擇操作。

步驟7首先,計(jì)算當(dāng)前種群的相異度D;然后,計(jì)算種群當(dāng)前的交叉概率pc;最后,進(jìn)行交叉操作。

步驟8首先,計(jì)算當(dāng)前種群的相異度D;然后,計(jì)算種群當(dāng)前的變異概率pm;最后,進(jìn)行變異操作并執(zhí)行步驟4。

步驟9根據(jù)個體適應(yīng)度值,將適應(yīng)度值最大個體作為任務(wù)調(diào)度的結(jié)果進(jìn)行輸出。

3 實(shí)例分析

3.1 測試結(jié)果

以某無人機(jī)地面測試設(shè)備的自動測試系統(tǒng)為例,對某無人機(jī)的動力子系統(tǒng)、溫控子系統(tǒng)等5個子系統(tǒng)編寫了15個測試任務(wù),其中各子系統(tǒng)分別用s1,s2,…,s5表示,15個測試任務(wù)用t1,t2,…,t15表示,測試所涉及的資源共7種,為不同功能的板卡,為了方便描述,使用r1,r2,…,r7分別表示上述資源。采集15個測試任務(wù)時序關(guān)系以及資源占用情況如表1所示。表1中測試任務(wù)所使用的測試用例并非涉及對應(yīng)系統(tǒng)中的所有參數(shù),而是在自動測試時根據(jù)需求設(shè)計(jì)的自動測試用例。

表1 測試任務(wù)信息

將上述測試任務(wù)信息轉(zhuǎn)換為并行測試任務(wù)調(diào)度數(shù)學(xué)模型?？芍?測試任務(wù)集T={t1,t2,t3,…,t15},測試資源集R={r1,r2,r3,…,r7},測試時間集τ={2,9,4,11,2,16,19,20,12,17,12,12,18,13,13};任務(wù)約束矩陣TS15×15中,TS15×15(9,1)=1,TS15×15(6,11)=1,TS15×15(10,7)=1;任務(wù)資源矩陣TR15×7為

AGAPD算法主要參數(shù)設(shè)置如表2所示。

表2 主要參數(shù)

算法運(yùn)行得到的一種最優(yōu)調(diào)度方案的甘特圖如圖9所示,其任務(wù)調(diào)度序列Tp為

圖9 任務(wù)調(diào)度甘特圖

從上述結(jié)果可以看出,使用AGAPD算法得到的任務(wù)調(diào)度方案測試用時為72 s,與最優(yōu)調(diào)度方案用時相同,說明AGAPD算法可以解決并行測試任務(wù)調(diào)度問題。

3.2 算法對比

在參數(shù)設(shè)置相同的情況下,對AGA算法、IAGA算法、AGAPD算法從種群相異度,最大適應(yīng)度值和找到最優(yōu)解的概率3個方面進(jìn)行對比,如圖10—圖12所示。

圖10 種群相異度對比

圖10是3種算法種群相異度隨迭代次數(shù)變化的對比結(jié)果。可以看出,種群相異度在初始時達(dá)到了最大。在迭代后期,AGA算法與IAGA算法的種群相異度在較小范圍波動,種群多樣性較小;而AGAPD算法的種群相異度在較大范圍變化,種群多樣性較大。AGAPD算法在迭代的過程中保證了種群的多樣性,減小了陷入局部最優(yōu)解的可能性,說明了AGAPD算法設(shè)計(jì)的合理性。

圖11是3種算法最大適應(yīng)度值隨迭代次數(shù)變化的對比結(jié)果?？梢钥闯?AGA算法與IAGA算法都出現(xiàn)了陷入局部最優(yōu)解的情況,需要多次迭代才能跳出局部最優(yōu)解,而AGAPD算法具有更好的跳出局部最優(yōu)解的能力。

圖11 最大適應(yīng)度值對比

圖12是3種算法找到最優(yōu)解的概率隨迭代次數(shù)變化的對比結(jié)果?？梢钥闯?3種算法在迭代40次后找到最優(yōu)解的概率趨于穩(wěn)定,AGA算法穩(wěn)定在約75%,IAGA算法穩(wěn)定在約95%,AGAPD算法穩(wěn)定在約99%,AGAPD算法相比較于AGA算法提升27%,相比較于IAGA算法提升約4%。在迭代10次以前,AGAPD算法與IAGA算法相近;而在迭代10次以后,AGAPD算法優(yōu)于IAGA算法。AGAPD算法擁有更快的收斂速度以及更高的搜索準(zhǔn)確度,符合設(shè)計(jì)預(yù)期。

圖12 找到最優(yōu)解概率對比

設(shè)置最大迭代次數(shù)為50次,將3種算法分別運(yùn)行1 000次,得到的結(jié)果如表3所示?？梢钥闯?AGAPD算法僅增加了根據(jù)適應(yīng)度值求解交叉與變異概率的過程,而適應(yīng)度值的計(jì)算復(fù)雜度遠(yuǎn)小于交叉與變異操作,其時間復(fù)雜度還是依賴于迭代次數(shù)以及交叉、變異操作,與遺傳算法相同,其搜索時間并沒有增加?？傮w來看,AGAPD算法相比較于AGA算法、IAGA算法有著更好的搜索準(zhǔn)確性。

從上述結(jié)果可以看出AGAPD算法引入種群相異度自適應(yīng)調(diào)節(jié)交叉與變異概率,改善了IAGA算法后期容易陷入局部最優(yōu)解的問題,提升了算法的收斂速度,有著更好的搜索性能。

4 結(jié)論

本文中引入遺傳算法求解并行測試任務(wù)調(diào)度問題,通過對遺傳算法進(jìn)行改進(jìn)提出了AGAPD算法。該算法將種群多樣性與遺傳算法的交叉與變異概率相關(guān)聯(lián),設(shè)計(jì)了種群相異度函數(shù)描述種群的多樣性,并據(jù)此自適應(yīng)調(diào)節(jié)交叉與變異概率。通過具體實(shí)例與對比分析說明了AGAPD算法能夠有效解決并行測試任務(wù)調(diào)度問題,在迭代過程中保證了種群的多樣性,有著更好的跳出局部最優(yōu)解的能力以及更高的搜索準(zhǔn)確性,實(shí)現(xiàn)了較好的搜索性能。