王 鶴

（河南工程學(xué)院，鄭州 451191）

0 引言

微流控生物芯片（即芯片實(shí)驗(yàn)室）的出現(xiàn)，推動(dòng)生化分析檢測向整體微型化、集成化、自動(dòng)化與便攜化方向邁出了一大步。樣品和試劑的分配、輸運(yùn)、存儲(chǔ)、混合、分離與檢測等功能可以通過微流控生物芯片輕松地完成。試劑消耗小、成本低廉、檢測靈敏度高以及重復(fù)使用等優(yōu)勢使其在生物醫(yī)學(xué)、分析化學(xué)、藥物診斷、食品安全以及環(huán)境監(jiān)測等領(lǐng)域都有廣泛的應(yīng)用[1,2]。

與傳統(tǒng)基于連續(xù)流的微流控生物芯片相比，數(shù)字微流控生物芯片不需要微閥、微泵等復(fù)雜的微結(jié)構(gòu)，就能在二維陣列結(jié)構(gòu)上獨(dú)立地控制多個(gè)微液滴完成各種基本操作以實(shí)現(xiàn)相應(yīng)的生化分析檢測[3～6]。因此，數(shù)字微流控生物芯片具有可擴(kuò)展、可動(dòng)態(tài)重構(gòu)的系統(tǒng)架構(gòu)。然而，在許多實(shí)際應(yīng)用中，往往要求不同類型的生化檢驗(yàn)操作在同一個(gè)芯片上協(xié)同運(yùn)作，這在一定程度上極大地增加了芯片系統(tǒng)的復(fù)雜性。而傳統(tǒng)數(shù)字微流控生物芯片所采用的全定制設(shè)計(jì)制作技術(shù)擴(kuò)展性差，而且2D電極陣列的尺寸（即資源約束）以及生化檢測試驗(yàn)中各操作之間的功能依賴性（時(shí)序約束）均限制了片上并行操作的數(shù)量。以上各種問題的出現(xiàn)使得傳統(tǒng)數(shù)字微流控生物芯片的全定制設(shè)計(jì)技術(shù)已經(jīng)遠(yuǎn)不適用于大規(guī)模的生化分析與檢測。因此，針對(duì)上述問題，參照超大規(guī)模集成電路（VSIA），在芯片系統(tǒng)中需要引入計(jì)算機(jī)輔助設(shè)計(jì)，可優(yōu)化芯片結(jié)構(gòu)，減少人為干預(yù)，提高芯片的利用率及效率[7～9]。

在生化檢驗(yàn)分析中，生物樣本對(duì)很多因素（如環(huán)境、溫度等）都非常敏感，難以在片上保持最佳的臨床（如床邊檢測）或?qū)嶒?yàn)室環(huán)境。所以，為了確保檢驗(yàn)結(jié)果的完整性，在最終獲得測定結(jié)果之前，要實(shí)現(xiàn)在滿足目標(biāo)和約束（包括資源約束和時(shí)序約束）的前提條件下，生化檢驗(yàn)中各樣本和試劑操作的并行處理達(dá)到最大化，進(jìn)而減少樣本液滴在芯片上的操作時(shí)間，以使生化檢驗(yàn)完成時(shí)間最小化。因此，要實(shí)現(xiàn)上述目標(biāo)的關(guān)鍵方法之一就是對(duì)數(shù)字微流控生物芯片進(jìn)行架構(gòu)級(jí)調(diào)度。因此，這里研究的數(shù)字微流控生化檢驗(yàn)操作的調(diào)度問題，其實(shí)就是帶有資源約束的項(xiàng)目調(diào)度問題。而以往學(xué)者對(duì)這方面的研究很多是將其按照單模式資源約束項(xiàng)目調(diào)度問題來分析處理的[7,10]。單模式資源約束項(xiàng)目調(diào)度問題是指項(xiàng)目中的每項(xiàng)任務(wù)只有一種執(zhí)行模式，具有一組任務(wù)工期和資源需求。但是，生化檢驗(yàn)中的各操作任務(wù)其實(shí)是具有多種執(zhí)行模型的，比如，可以從2×2、2×3或2×4電極陣列混合器任選其一完成一個(gè)混合操作，那么在不同的電極陣列混合器上完成同一個(gè)混合操作就需要不同的資源需求量和完成時(shí)間。因此，當(dāng)操作任務(wù)具有多種執(zhí)行模式時(shí)，合理安排各個(gè)任務(wù)的執(zhí)行模式，可大大節(jié)約資源，縮短完成時(shí)間。

本文將數(shù)字微流控生化檢驗(yàn)操作的調(diào)度問題按照多模式資源源約束項(xiàng)目調(diào)度問題來分析，提出了利用雙層混合遺傳算法（DHGA）對(duì)數(shù)字微流控生化檢驗(yàn)中液滴操作的時(shí)序調(diào)度進(jìn)行優(yōu)化。將關(guān)鍵鏈技術(shù)引入傳統(tǒng)遺傳算法中，在第一層算法確定液滴調(diào)度次序的基礎(chǔ)上，采用關(guān)鍵鏈技術(shù)與第二層遺傳算法相結(jié)合的方式，對(duì)芯片資源進(jìn)行重新優(yōu)化配置，使算法加速向最優(yōu)解收斂，以達(dá)到生化檢驗(yàn)完成時(shí)間最少的目標(biāo)。

1 問題描述

數(shù)字微流控生化檢驗(yàn)中，液滴操作步驟可以看作是一系列具有先后次序的操作，這一問題通過有向圖模型進(jìn)行描述，如圖1所示。

圖1 多元生化檢驗(yàn)有序圖模型

在上述生化檢驗(yàn)中，假設(shè)從芯片儲(chǔ)液池需要生成m種樣本液滴Si（i=1，2，…，m）和n種試劑液滴Rj（j=1，2，…，n），這里用I表示液滴生成操作。在后續(xù)操作中，為完成相應(yīng)的酶化驗(yàn)，需要將m種樣本液滴Si和n種試劑液滴Rj依次相互混合，那么樣本液滴Si有n個(gè)生成操作，m種樣本液滴就會(huì)有mn個(gè)生成操作；同理，n種試劑液滴Rj也有mn個(gè)生成操作，因此共有2mn個(gè)生成操作。液滴生成操作的時(shí)間主要由系統(tǒng)參數(shù)決定，而液體的流動(dòng)特性對(duì)其幾乎沒有影響[11]。與m種樣本液滴Si和n種試劑液滴Rj依次相互混合所對(duì)應(yīng)的有mn個(gè)操作，而且1×4、2×2、2×3或2×4等多種不同類型的電極陣列混合器（即混合操作的執(zhí)行模式）均可用于完成該操作。另外，對(duì)于各種試劑來說，在使用前往往都要用同一種液體對(duì)其進(jìn)行高度稀釋，因此，液滴混合時(shí)間主要由樣本粘度和混合器類型決定。因此，可認(rèn)為同一種樣本與不同類型的試劑在同一類型混合器上完成混合操作的時(shí)間相同。注意，通常在生化檢驗(yàn)中液滴混合操作之后往往都要進(jìn)行液滴分離操作，因此這里液滴混合操作的完成時(shí)間均已包含液滴分離操作的時(shí)間。液滴混合之后，需要對(duì)其進(jìn)行生化反應(yīng)結(jié)果的檢測，而酶測定的類型決定了光學(xué)檢測時(shí)間。因此，在數(shù)字微流控生化檢驗(yàn)液滴調(diào)度問題中共有K=4mn項(xiàng)操作任務(wù)，對(duì)各任務(wù)進(jìn)行順序編號(hào)。保證操作任務(wù)k（k=1，2，…，K）的編碼大于它所有緊前操作的編碼，并且任一操作k都必須從wj種執(zhí)行模式中選擇其一執(zhí)行，執(zhí)行過程中不允許中斷或改變執(zhí)行模式。不同的執(zhí)行模式具有不同的資源需求和操作完成時(shí)間。這里的資源需求包含可重新配置的資源需求P和不可重新配置的固定資源需求Q。

圖1是由與操作任務(wù)相對(duì)于的節(jié)點(diǎn)組成，各節(jié)點(diǎn)用vi（i=0，1，2，…，K，K+1）表示，其中設(shè)置了兩個(gè)沒有任何液滴操作的空節(jié)點(diǎn)NOP，即v0和vK+1。該有向圖模型可用G（V，E）表示，節(jié)點(diǎn)集V={vi：i=0，1，2，…，K，K+1}，邊集E={(vi，vj）：i，j=0，1，2，…，K，K+1}用來表示兩個(gè)液滴操作的前后依賴關(guān)系。為每個(gè)節(jié)點(diǎn)均設(shè)置一個(gè)權(quán)重di，表示操作vi的持續(xù)時(shí)間。相比液滴生成、混合、檢測等操作，液滴移動(dòng)操作的時(shí)間極短，可忽略不計(jì)，因此有向圖模型中兩個(gè)節(jié)點(diǎn)之間的邊權(quán)重設(shè)置為0。

2 數(shù)學(xué)模型

根據(jù)上述分析，生化檢測調(diào)度問題可以看做是0-1整數(shù)線性規(guī)劃問題，因此建立數(shù)學(xué)模型[7,12]如下所示：

設(shè)xi,j為二進(jìn)制變量，則：

其中，1≤i≤K；1≤j≤M，M表示松弛時(shí)間因子，即為所有操作時(shí)隙數(shù)量總和。由于每個(gè)檢測操作只能被調(diào)度一次，因此：

操作vi的開始時(shí)間si可以用一個(gè)變量x集{xi,1，xi,2，…，xi,m}表示。假設(shè)每個(gè)時(shí)隙長度為一個(gè)單位，那么操作vi的開始時(shí)間為：

操作vi的持續(xù)時(shí)間為di，且操作vi和vi+1之間存在依賴關(guān)系，那么：

對(duì)于數(shù)字微流控生物芯片來說，除了上述的各操作間的依賴性這個(gè)時(shí)序約束以外，還有受芯片電極陣列尺寸限制的資源約束。這里假設(shè)每種液體的儲(chǔ)液池?cái)?shù)量Nr和每種酶測定的檢測器數(shù)量Nd均設(shè)置為1，而且兩者均屬于不可重新配置的固定資源需求。于是對(duì)于m種樣本和n種試劑有：

由于受資源約束的限制，有可能出現(xiàn)具有前后次序的兩個(gè)操作無法被連續(xù)調(diào)度，這時(shí)就需要臨時(shí)存儲(chǔ)單元暫放液滴。而液滴存儲(chǔ)單元和液滴混合器都屬于可重新配置的資源需求。其中，用于液滴混合的電極數(shù)量設(shè)為Nmixer：

用于液滴臨時(shí)存儲(chǔ)的電極數(shù)量設(shè)為Nmemory：

其中，Mi,j為一個(gè)二進(jìn)制變量：

然而，數(shù)字微流控芯片尺寸大小固定，Nmixer和Nmemory之間是成反比的：

其中Ne的值取決于芯片尺寸。

因此，數(shù)字微流控生化檢驗(yàn)液滴操作調(diào)度優(yōu)化的目標(biāo)就是生化檢驗(yàn)完成時(shí)間最短：

在最大限度地利用并行性來完成生化檢測的基礎(chǔ)上，上述優(yōu)化目標(biāo)可轉(zhuǎn)化為最小化最后一個(gè)操作的完成時(shí)間Tl，則優(yōu)化目標(biāo)轉(zhuǎn)化為：

3 遺傳算法設(shè)計(jì)

數(shù)字微流控生化檢驗(yàn)液滴操作調(diào)度屬于多模式資源約束項(xiàng)目調(diào)度問題，再加上具有兩個(gè)不可重新配置的固定資源需求，因此，這是一個(gè)NP-complete問題。本文采用雙層混合遺傳算法來解決數(shù)字微流控生化檢驗(yàn)液滴操作的調(diào)度問題。

在該算法中，第一層個(gè)體編碼代表液滴操作調(diào)度次序，第二層個(gè)體編碼代表在第一層確定的操作調(diào)度次序下的各操作執(zhí)行模式。采用關(guān)鍵鏈技術(shù)對(duì)第二層個(gè)體進(jìn)行進(jìn)化，以替代第二層遺傳算法的交叉過程；在既定的操作調(diào)度次序下求解各操作的最優(yōu)執(zhí)行模式以及與其相對(duì)應(yīng)的適應(yīng)度值，并將最優(yōu)結(jié)果反饋給第一層遺傳算法，再利用第一層個(gè)體的交叉、變異，不斷迭代求出最優(yōu)解。

3.1 第一層遺傳算法

1）編碼

針對(duì)多模式資源約束項(xiàng)目調(diào)度問題，本文采用雙鏈表式編碼[13]方式，即任務(wù)鏈表和模式鏈表兩種鏈表：

第一層個(gè)體編碼為任務(wù)鏈表編碼，液滴操作任務(wù)列表U=[U0，U1，···，UK，UK+1]表示滿足時(shí)序約束的全部操作任務(wù)的一個(gè)排列次序，解碼時(shí)各操作從左向右依次進(jìn)行排列。這里要保證操作任務(wù)k（k=0，1，…，K，K+1）的編碼大于它所有緊前操作的編碼。

2）適應(yīng)度函數(shù)

這里取第二層遺傳算法的適應(yīng)度函數(shù)的最優(yōu)值作為第一層的適應(yīng)度函數(shù)，即Fu=Fl*，其中Fl表示第二層適應(yīng)度函數(shù)，其表達(dá)式參看3.2節(jié)。

3）選擇

本文采用比例選擇算子從當(dāng)前代種群中選擇出一些比較優(yōu)良的個(gè)體，并將其復(fù)制到下一代種群中。在這種方法中，每個(gè)個(gè)體的選擇概率與其適應(yīng)度大小成比例。

4）交叉

對(duì)于傳統(tǒng)的交叉算子來說，當(dāng)隨機(jī)選擇的兩條父串染色體相同時(shí)，算法會(huì)無法繼續(xù)迭代進(jìn)化，出現(xiàn)早熟收斂。為避免這一現(xiàn)象的出現(xiàn)，減弱對(duì)種群多樣性的要求，第一層任務(wù)鏈表采用改進(jìn)的交叉算子。假設(shè)隨機(jī)選取兩條父串染色體A和B，同為：（362794185），并隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)，先將交叉段|7941|倒置變?yōu)閨1497|，并將父串A的交叉倒置段|1497|移到父串B的尾部，將父串B的交叉倒置段|1497|移到父串A的首部，分別得到子串A1和B1，在此基礎(chǔ)上，消去交叉段外與初始交叉段相同的基因，最終得到兩條不同的子串A2和B2，具體如下所示：

如上分析可知，采用改進(jìn)的交叉算子，即使隨機(jī)選擇的兩條父串染色體相同，也能得到兩條不同于父串的新染色體，而且兩個(gè)子串染色體互相之間也不相同，這使得算法得以繼續(xù)迭代進(jìn)化，避免陷入局部最優(yōu)解。

5）變異

物種變異幾率很小，所以變異操作在遺傳算法中只起輔助作用。操作任務(wù)鏈表中基因變異采用插入操作法，即對(duì)每代種群按照變異概率pm=0.03選中某個(gè)任務(wù)鏈表中的某一基因，分析得出該基因的所有緊前節(jié)點(diǎn)在該操作任務(wù)鏈表中的最后位置r1以及其所有緊后節(jié)點(diǎn)在任務(wù)鏈表中的最前位置r2，之后在r1和r2之間隨機(jī)選擇一個(gè)位置r，并將該基因置于位置r上[14]。

因此，第一層遺傳算法的具體實(shí)施步驟如下：

（1）初始化兩層控制參數(shù)；

（2）隨機(jī)生成初始種群，產(chǎn)生N個(gè)個(gè)體Y1，Y2，…，YN。

（3）將每個(gè)個(gè)體Yi的值帶入第二層遺傳算法中得到對(duì)應(yīng)的最優(yōu)解Fl(Yi)*，并保存取得該最優(yōu)解的第二層個(gè)體值。

（4）采用比例選擇從當(dāng)前代種群中選擇出優(yōu)良個(gè)體，并將其復(fù)制到下一代種群中。

（5）對(duì)第一層個(gè)體進(jìn)行交叉變異，產(chǎn)生新一代個(gè)體，并計(jì)算其適應(yīng)度值。

（6）判斷新個(gè)體適應(yīng)度是否滿足終止條件。若滿足，則算法的迭代過程收斂，算法結(jié)束；否則，轉(zhuǎn)至（3）重復(fù)以上步驟。

3.2 第二層遺傳算法

1）編碼

第二層個(gè)體編碼為模式鏈表編碼，模式列表W=[W0，W1，…，WK，WK+1]表示根據(jù)任務(wù)列表中各操作對(duì)應(yīng)的執(zhí)行模式。操作vk（k=0，…，K+1）的執(zhí)行模式有{1，2，…，wk}種，在滿足資源約束的條件下，Wk∈[1，wk]隨機(jī)選取。但是，由于操作v0與操作vK+1都是空操作，既不花費(fèi)時(shí)間也不消耗資源，因此設(shè)置W0=WK+1={1}。

2）適應(yīng)度函數(shù)

數(shù)字微流控生化檢驗(yàn)液滴操作調(diào)度優(yōu)化的目標(biāo)是最小化最后一個(gè)操作的完成時(shí)間Tl，因此本層適應(yīng)度函數(shù)定為Fl=1/Tl。

3）關(guān)鍵鏈技術(shù)對(duì)個(gè)體進(jìn)化

這里對(duì)滿足資源約束的全部個(gè)體都進(jìn)行進(jìn)化，因此進(jìn)化概率設(shè)為1。如果資源需求總量不大于約束，則采用關(guān)鍵鏈技術(shù)對(duì)個(gè)體進(jìn)化；否則，調(diào)整各操作任務(wù)的執(zhí)行模型，直到滿足資源約束為止。所謂的關(guān)鍵鏈技術(shù)對(duì)個(gè)體的進(jìn)化，就是計(jì)算出所有關(guān)鍵鏈任務(wù)工作時(shí)系統(tǒng)的閑置資源，求出在滿足資源約束的情況下，可縮短數(shù)字微流控生化檢驗(yàn)完成時(shí)間的新執(zhí)行模式，替換舊模式。新的完成時(shí)間應(yīng)該滿足：

其中，tEFj表示操作i的緊后操作的緊前操作集合中各操作的最早結(jié)束時(shí)間。該公式保證了操作i在更新執(zhí)行模式之后仍然處于關(guān)鍵鏈上。然而，如果沒有任何操作的執(zhí)行模式發(fā)生變化，那么任意選擇c個(gè)操作（c為不大于4mn/3的隨機(jī)整數(shù)）對(duì)其進(jìn)行進(jìn)化：（1）當(dāng)中若有非關(guān)鍵鏈操作，則在資源消耗較少的執(zhí)行模式中隨機(jī)選取一種替換舊模式。當(dāng)不可重新配置的固定資源Q緊張時(shí)，優(yōu)先選取消耗Q較少的執(zhí)行模式；反之，優(yōu)先選取可重新配置的資源P消耗較少的執(zhí)行模式。（2）當(dāng)中若有關(guān)鍵鏈操作，則在滿足資源約束的條件下，在完成時(shí)間較少的執(zhí)行模式中隨機(jī)選取一個(gè)替換。

4）變異

若進(jìn)化過程中執(zhí)行模式發(fā)生變化的液滴操作數(shù)量為0，或者出現(xiàn)隨機(jī)概率大于變異概率，則任意選擇z個(gè)操作（z為不大于mn的隨機(jī)整數(shù)），在滿足資源約束的情況下，隨機(jī)更新它們的執(zhí)行模型。第二層變異概率隨迭代次數(shù)線性增加，有利于促進(jìn)算法朝全局最優(yōu)方向進(jìn)化。

因此，第二層遺傳算法的具體實(shí)施步驟如下：

（1）生成初始種群，產(chǎn)生N'個(gè)個(gè)體Y1'，Y2'，…，YN'。

（2）計(jì)算每個(gè)個(gè)體Yi'的適應(yīng)度值，并進(jìn)行評(píng)價(jià)：

（3）利用關(guān)鍵鏈技術(shù)對(duì)個(gè)體Yi'進(jìn)行進(jìn)化，替代交叉過程，并對(duì)其變異，計(jì)算出新個(gè)體的適應(yīng)度值。

（4）判斷新個(gè)體適應(yīng)度是否滿足終止條件。是則算法結(jié)束；否則，轉(zhuǎn)至（3）重復(fù)以上步驟。

4 仿真結(jié)果及分析

為驗(yàn)證該算法的可靠性與有效性，采用文獻(xiàn)[7]的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行仿真。表1給出了文獻(xiàn)[7]中5種多元體液的檢驗(yàn)數(shù)據(jù)，其中樣本S1：血漿，S2：血清，S3：尿液，S4：唾液；生化檢驗(yàn)A1：葡萄糖測定，A2：乳酸測定，A3：丙酮酸測定，A4：谷氨酸測定；Mi表示樣本Si與某試劑的混合操作；Di表示生化檢驗(yàn)Ai對(duì)應(yīng)的觀測操作。但是，文獻(xiàn)[7]是將生化檢驗(yàn)液滴操作調(diào)度問題按單模式資源約束項(xiàng)目調(diào)度問題來處理的，即每種液滴操作只有一種固定執(zhí)行模型；采用M-LS算法和遺傳算法（GA）兩種啟發(fā)式算法分別對(duì)上述4種測定實(shí)驗(yàn)進(jìn)行了計(jì)算。

在生化檢驗(yàn)中，同一混合操作在不同尺寸的混合陣列（即不同的執(zhí)行模式）上完成，其完成時(shí)間不同。假設(shè)多元體液檢驗(yàn)在不同混合器上完成混合操作的時(shí)間[15]如表2所示，而且文獻(xiàn)[7]中各樣本均是在1×4陣列混合器上完成混合操作的。由表2可知，通常情況下混合器尺寸越大，混合操作完成時(shí)間越短；電極單元數(shù)量相同時(shí)，線性混合器（如1×4）比多行陣列混合器（如2×2）完成混合操作的時(shí)間短。因此，混合器類型的選擇是影響數(shù)字微流控生化檢驗(yàn)完成時(shí)間的一個(gè)重要因素。當(dāng)然，液滴生成器、試劑稀釋器等也與混合器類似。

表1 實(shí)驗(yàn)數(shù)據(jù)

表2 樣本在各種混合器上完成混合操作所需時(shí)間 （單位：s）

雙層混合遺傳算法主要參數(shù)初始化如下所示：

圖3給出了雙層混合遺傳算法和文獻(xiàn)[7]使用算法之間仿真結(jié)果的對(duì)比。從結(jié)果可知，雙層混合遺傳算法從解的質(zhì)量和計(jì)算時(shí)間來看，均具有顯著優(yōu)勢，幾乎都達(dá)到了解的下限，而且計(jì)算時(shí)間較短。

表3 生化檢驗(yàn)完成時(shí)間結(jié)果對(duì)比 （單位：s）

5 結(jié)論

數(shù)字微流控生化檢驗(yàn)液滴操作調(diào)度問題屬于多模式資源約束項(xiàng)目調(diào)度問題。通過采用雙層混合遺傳算法對(duì)液滴操作的時(shí)序調(diào)度進(jìn)行優(yōu)化；將關(guān)鍵鏈技術(shù)引入遺傳算法中，在第一層算法確定液滴調(diào)度次序的基礎(chǔ)上，采用關(guān)鍵鏈技術(shù)與第二層遺傳算法結(jié)合的方式，對(duì)芯片資源進(jìn)行重新優(yōu)化配置，使算法加速向最優(yōu)解收斂。由該算法得到的解幾乎都達(dá)到了解的下限，因此縮短了生化檢驗(yàn)完成時(shí)間，同時(shí)減少了計(jì)算時(shí)間。仿真結(jié)果表明了算法的有效性和可行性，對(duì)數(shù)字微流控生化檢驗(yàn)液滴調(diào)度優(yōu)化具有一定的參考價(jià)值。