化驗(yàn)室資源調(diào)度優(yōu)化的改進(jìn)型克隆選擇算法

顧偉偉, 張棟良

(上海電力大學(xué) 自動化工程學(xué)院, 上海 200090)

化驗(yàn)室調(diào)度的目的是將待化驗(yàn)的化驗(yàn)單及樣品分配到合適的設(shè)備,以此來提高共享資源的利用率,使得整個流程更加高效。化驗(yàn)室資源調(diào)度問題本質(zhì)上是一個組合優(yōu)化[1]問題,針對原先的動態(tài)規(guī)劃法[2],其處理大規(guī)模復(fù)雜優(yōu)化問題時存在不足,建模較為復(fù)雜,計(jì)算速度也較慢。目前智能算法如神經(jīng)網(wǎng)絡(luò)[3]、遺傳算法[4]、模擬退火[5]等在調(diào)度問題上的應(yīng)用越來越廣泛。近年來,研究人員提出了各種優(yōu)化算法[6-14]以解決調(diào)度問題。高陽陽等人[15]在克隆選擇算法中設(shè)計(jì)了新的移民算子進(jìn)行多種群交流,提高了搜索效率;宋丹等人[16]將克隆選擇算法與模糊非基因信息搜索策略相結(jié)合,改善了算法搜索能力及算法精度;周炳海和顧佳穎[17]在免疫克隆選擇算法中引入了新的鄰域搜索算子和種群更新算子,提高了算法的搜索效率。

傳統(tǒng)的克隆選擇算法與其他智能算法一樣,容易陷入局部最優(yōu)、早熟收斂等問題。本文在克隆選擇算法的基礎(chǔ)上,引入了多種群協(xié)同進(jìn)化的思想,以提高種群的多樣性;設(shè)計(jì)了新的克隆選擇算子,增加了個體的多樣性;提出了自適應(yīng)變異算子,能加快局部搜索速度,提升全局搜索能力。

1 化驗(yàn)室調(diào)度數(shù)學(xué)模型

化驗(yàn)室處理化驗(yàn)單的問題可表述為:有j個化驗(yàn)單(一個化驗(yàn)單可含多種樣品)在某一臺設(shè)備上化驗(yàn)檢測,已知各類樣品的化驗(yàn)時間和各樣品在各設(shè)備上化驗(yàn)檢測的次序約束,合理地安排樣品所使用的設(shè)備以及化驗(yàn)單檢測順序,可使化驗(yàn)檢測流程效率達(dá)到最優(yōu)。為建立化驗(yàn)室調(diào)度模型,作如下假設(shè)。

(1) 某一時刻在每臺設(shè)備上都只能對某個化驗(yàn)單的某個樣品進(jìn)行化驗(yàn)且是非搶占的,允許有設(shè)備空閑。

(2) 不同化驗(yàn)單的樣品可以同時在不同的設(shè)備上化驗(yàn)。

(3) 一臺設(shè)備不能同時化驗(yàn)兩個樣品。

(4) 化驗(yàn)單的優(yōu)先級是相同的。

目標(biāo)函數(shù)化驗(yàn)完成最小時間Tm為

(1)

式中:Zjt——二進(jìn)制量;

t——化驗(yàn)單化驗(yàn)完成時間。

Zjt取值為1,反之為0,其中化驗(yàn)單數(shù)量j和時間t的取值范圍j=1,2,3,…,J,t=1,2,3,…,T。

約束條件如下:

(2)tcjh≤tsj(h+1)為樣品的化驗(yàn)順序約束,表示第h個樣品的化驗(yàn)完成時間小于第h+1個樣品的化驗(yàn)開始時間。其中:tcjh為第j個化驗(yàn)單的第h個樣品的化驗(yàn)完成時間;tsjh為第j個化驗(yàn)單的第h個樣品的化驗(yàn)開始時間。

(3)tcjh≤Tm表示一個化驗(yàn)單的化驗(yàn)時間總小于整個化驗(yàn)流程所花費(fèi)的時間。

(4)tcjh=tsjh+pijh表示樣品在一臺設(shè)備上化驗(yàn)過程中不會被中斷。其中,Pijh為第j個化驗(yàn)單的第h個樣品在機(jī)器i上的化驗(yàn)時間。

2 改進(jìn)型克隆選擇算法

2.1 具體步驟和流程

免疫算法通過模擬生物免疫原理,將實(shí)際求解問題當(dāng)作抗原,結(jié)合基因進(jìn)化機(jī)理,是一種魯棒性好、搜索能力強(qiáng)的新型智能算法。它具有一般免疫系統(tǒng)的特征,采用群體搜索策略,通過迭代計(jì)算,最終以較大概率得到問題的最優(yōu)解。標(biāo)準(zhǔn)免疫算法在計(jì)算迭代過程中也容易陷入局部最優(yōu)解及早熟收斂等不足。本文在標(biāo)準(zhǔn)免疫算法的基礎(chǔ)上提出了改進(jìn)型克隆選擇算法,引入多種群協(xié)同進(jìn)化思想,提高了種群的多樣性;引入克隆選擇算子和自適應(yīng)變異算子,提高了算法的搜索效率,加快了算法的收斂速度。算法的具體步驟如下。

步驟1 識別待優(yōu)化的目標(biāo)函數(shù)。

步驟2 隨機(jī)生成初始抗體群P,初始抗體群由n個子群體Pn構(gòu)成,確定初始參數(shù)。

步驟3 計(jì)算各抗體群中抗體適應(yīng)度F及濃度C,基于親和度A排序,選擇優(yōu)質(zhì)抗體放入記憶庫中。

步驟4 計(jì)算每個抗體期望的繁殖概率Pr,根據(jù)繁殖概率對抗體進(jìn)行選擇克隆操作。

步驟5 對不同種群中的抗體進(jìn)行移民操作,前一個種群的劣質(zhì)抗體由后一個種群中的優(yōu)質(zhì)抗體取代。

步驟6 從已更新后的抗體中,將M個親和度高的解保留下來,組成記憶庫。

步驟7 終止條件判斷,滿足就結(jié)束,不滿足則跳轉(zhuǎn)到步驟3。

改進(jìn)型克隆選擇算法流程如圖1所示。

2.2 編碼及初始抗體群

以隨機(jī)的方式生成初始抗體群。初始抗體群由n個子群體構(gòu)成。在初始抗體子群中,根據(jù)化驗(yàn)設(shè)備數(shù)量、樣品數(shù)量來限制生成抗體的取值范圍。采用單層實(shí)數(shù)編碼表示各解,各抗體表示對化驗(yàn)單合理分配設(shè)備與輔助資源以及確定化驗(yàn)單樣品化驗(yàn)順序的調(diào)度方案。 設(shè)置初始參數(shù)如下:最大迭代數(shù)為Gmax,種群數(shù)為Npop,交叉概率為θc,變異概率為θm等。

圖1 改進(jìn)型克隆選擇算法

2.3 抗體評價(jià)

親和度是指分配方案與目標(biāo)函數(shù)的匹配程度,可作為評估每一個可行解的衡量指標(biāo)。親和度越大,表示抗體適應(yīng)度越高,抗體濃度越低。其中,抗體與抗原之間的匹配程度由適應(yīng)度表示,抗體與抗體間的相似程度由濃度表示。其計(jì)算公式分別為

(2)

(3)

(4)

式中:fi——抗體與抗原間的適應(yīng)度;

ti——各個抗體的完成時間;

Ci——抗體i的濃度;

N——抗體數(shù)量;

j——除了抗體i之外的抗體;

nj——抗體j的數(shù)量;

Si,j——群體中抗體i和抗體j的相似程度;

Ki,j——抗體i和抗體j中基因編碼相同的位數(shù);

L——抗體的長度。

若Ki,j/L≤0.6,則表示兩個抗體沒有相似性,取Si,j=0;反之,則表示兩個抗體具有相似性,取Si,j=1。

2.4 克隆競爭擴(kuò)增

根據(jù)親和度大小篩選出種群中的優(yōu)勢抗體,將其放入記憶庫,并對其進(jìn)行概率克隆?？贵w選擇克隆的策略主要由抗體適應(yīng)度和濃度決定。本文在此基礎(chǔ)上提出了抗體克隆選擇算子,盡可能選擇適應(yīng)度大的抗體來保證潛力較大的抗體得以繁殖,選擇濃度低的抗體來擴(kuò)大搜索空間。選擇概率公式為

(5)

式中:Pcs(i)——第i個抗體的期望選擇概率;

λ——多樣性評價(jià)指數(shù),每個子抗體群都會獲得一個隨機(jī)生成的λ,取值范圍為[0.3,0.7]。

2.5 自適應(yīng)變異

根據(jù)自適應(yīng)變異算子對克隆合并后的抗體群進(jìn)行變異操作,降低部分適應(yīng)度小于平均適應(yīng)度的抗體變異概率,提高部分適應(yīng)度高于平均水平的抗體變異概率,以此來獲得具有高潛力的優(yōu)質(zhì)抗體,從而加快算法收斂速度。

(6)

式中:P′v——變異自適應(yīng)概率;

Pv——原來的自適應(yīng)概率;

f′——進(jìn)行變異操作的抗體適應(yīng)度;

fmax——適應(yīng)度最大值;

favg——適應(yīng)度平均值。

2.6 移民操作

首先確定n(n為自然數(shù))個初始種群,通過移民算子實(shí)現(xiàn)優(yōu)質(zhì)抗體傳遞,計(jì)算每個抗體的親和度,將第n個種群的優(yōu)質(zhì)抗體替換掉第n+1個種群的劣質(zhì)抗體。

2.7 種群重組及記憶庫更新

將未進(jìn)行變異操作的原抗體與已變異的抗體合并重組得到抗體群。比較種群中兩代抗體的適應(yīng)度大小,由優(yōu)質(zhì)抗體替換掉劣質(zhì)抗體,完成記憶庫更新。

2.8 算法終止判斷

若迭代次數(shù)達(dá)到上限,則終止算法,輸出最優(yōu)解。

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

為了測試改進(jìn)型克隆選擇算法的性能,選擇3個基準(zhǔn)測試函數(shù)進(jìn)行了仿真測試。仿真實(shí)驗(yàn)在MATLAB 2017a上進(jìn)行,運(yùn)行環(huán)境為Windows 10系統(tǒng)下Intel(R) Core(TM) i5-3230M處理器,8 G內(nèi)存,2.6 GHz。最后與文獻(xiàn)[8]中的混合免疫算法和文獻(xiàn)[15]中的非支配克隆選擇算法以及標(biāo)準(zhǔn)免疫算法進(jìn)行了對比實(shí)驗(yàn)與分析。

由于尋優(yōu)結(jié)果具有一定的隨機(jī)性,也為了測試的公平和客觀,所以每種算法獨(dú)立運(yùn)行30次,并取平均值作為分析的依據(jù)。

3.1 Griewank函數(shù)

(7)

Griewank函數(shù)具有大量的局部極小值且為均勻規(guī)則分布,在點(diǎn)xi=(0,0,…,0)處取得全局最小值為零。在高維情況下全局最優(yōu)解的搜索容易陷入局部最優(yōu)中,故變異率Pm設(shè)置不能過小,否則無法保證群體的多樣性,而且會使找到峰值的概率降低。算法參數(shù)設(shè)置如下:免疫個體數(shù)目NP=100,最大免疫代數(shù)G=200,變異率Pm=0.7,激勵度系數(shù)β=1.5,相似度閾值Δ=0.2,反饋因子r=0.6。

圖2為函數(shù)F1的收斂曲線。表1為Griewank函數(shù)的仿真結(jié)果。

圖2 函數(shù)F1的收斂曲線

表1 Griewank函數(shù)的仿真結(jié)果

由圖2可以看出,改進(jìn)型克隆選擇算法的收斂速度優(yōu)于另外3種算法,收斂的最優(yōu)值也較為接近理論最優(yōu)值。結(jié)合表1數(shù)據(jù)可知,改進(jìn)型克隆選擇算法具有較高的求解精度,高維數(shù)時改進(jìn)型克隆選擇算法尋優(yōu)性能相對于標(biāo)準(zhǔn)免疫算法已有較大提升,平均質(zhì)量稍高于其他算法。

3.2 Rastrigin函數(shù)

(8)

Rastrigin函數(shù)是一個多維多峰函數(shù),在點(diǎn)xi=(0,0,…,0)處取得全局最小值為零,局部極小值比Griewank函數(shù)更為集中,通常被用來測試算法的脫困能力。激勵度系數(shù)的選取不宜過大,優(yōu)秀抗體容易被過早抑制,導(dǎo)致收斂速度過快,無法脫困。算法參數(shù)設(shè)置如下:免疫個體數(shù)目NP=100,最大免疫代數(shù)G=200,變異率Pm=0.6,激勵度系數(shù)β=0.9,相似度閾值Δ=0.25,反饋因子r=0.5。

圖3為函數(shù)F2的收斂曲線。表2為Rastrigin函數(shù)的仿真結(jié)果。

由圖3可看出,標(biāo)準(zhǔn)免疫算法在高維Rastrigin函數(shù)中易陷入局部最優(yōu)。表2仿真結(jié)果顯示,改進(jìn)型克隆選擇算法在精度上有較大提升,表現(xiàn)出較好的全局收斂能力。

圖3 函數(shù)F2收斂曲線

表2 Rastrigin函數(shù)的仿真結(jié)果

3.3 Resonbrock函數(shù)

(9)

Resonbrock函數(shù)是一個多維病態(tài)二次單峰函數(shù),在拋物線頂點(diǎn)xi=(1,1,…,1)處取得全局最小值為零,空間內(nèi)走勢平緩,收斂到全局最優(yōu)難度較大。反饋因子r取較小值時,會導(dǎo)致多種群間信息交流過于激烈,使得收斂速度過快,無法找到最優(yōu)解。算法參數(shù)設(shè)置如下:免疫個體數(shù)目NP=100,最大免疫代數(shù)G=200,變異率Pm=0.6,激勵度系數(shù)β=0.9,相似度閾值Δ=0.25,反饋因子r=0.3。

圖4為函數(shù)F3的收斂曲線。表3為Resonbrock函數(shù)的仿真結(jié)果。

圖4 函數(shù)F3的收斂曲線

表3 Resonbrock函數(shù)的仿真結(jié)果

由圖4可以看出,本文算法收斂速度優(yōu)于改進(jìn)的混合免疫算法,低于改進(jìn)型非支配克隆選擇算法,尋優(yōu)精度略高于改進(jìn)的混合免疫算法和標(biāo)準(zhǔn)免疫算法。

圖5為化驗(yàn)室高度仿真甘特圖。仿真過程中,共采用10個化驗(yàn)單,每個化驗(yàn)單有9個樣品,在化驗(yàn)室有10臺設(shè)備的情況下得到的全局最優(yōu)解。圖5中標(biāo)識83的長方形表示第8個化驗(yàn)單的第3個樣品在6#設(shè)備上化驗(yàn)。利用本文算法仿真得出的化驗(yàn)完成時間最小的最優(yōu)解為1 063 min,所有化驗(yàn)單化驗(yàn)完畢。

圖5 化驗(yàn)室調(diào)度仿真甘特圖

4種算法的仿真結(jié)果比較如表4所示。

表4 4種算法的仿真結(jié)果比較

由表4可以看出:本文算法的平均計(jì)算時間最短,為28 s,具有較高的搜索質(zhì)量;改進(jìn)型混合免疫算法的平均計(jì)算時間次之,為32 s;標(biāo)準(zhǔn)免疫算法平均計(jì)算時間最慢,為45 s。此外,本文算法的平均迭代次數(shù)為72次,改進(jìn)型混合免疫算法的平均迭代次數(shù)為101次,改進(jìn)型非支配克隆選擇算法的平均迭代次數(shù)為123次,表明本文算法的收斂速度在4種算法中具有一定優(yōu)越性,能在算法運(yùn)行的較早期收斂,證明了本文算法的可行性和可靠性。

4 結(jié) 語

針對化驗(yàn)室調(diào)度資源優(yōu)化問題,提出了一種改進(jìn)型克隆選擇算法。該算法的特點(diǎn)在于:將多種群協(xié)同進(jìn)化的思想引入免疫算法,能有效克服種群多樣性下降的問題;為了增加個體多樣性,提出了克隆選擇算子,優(yōu)先選擇親和度大、濃度低的抗體進(jìn)行克隆操作;提出了自適應(yīng)變異算子,能加快局部搜索速度,避免算法陷入局部最優(yōu)。

采用改進(jìn)型克隆選擇算法對化驗(yàn)室調(diào)度策略進(jìn)行了優(yōu)化,并在MATLAB上進(jìn)行了仿真實(shí)驗(yàn)。結(jié)果表明,與其他算法相比,本文所提算法表現(xiàn)最優(yōu),具有較高的收斂精度和良好的穩(wěn)定性,證明了算法的可行性和有效性。