基于數(shù)字微流控生化檢驗操作調(diào)度的混合遺傳算法研究

王 鶴

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

0 引言

微流控生物芯片（即芯片實驗室）的出現(xiàn)，推動生化分析檢測向整體微型化、集成化、自動化與便攜化方向邁出了一大步。樣品和試劑的分配、輸運、存儲、混合、分離與檢測等功能可以通過微流控生物芯片輕松地完成。試劑消耗小、成本低廉、檢測靈敏度高以及重復(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)上獨立地控制多個微液滴完成各種基本操作以實現(xiàn)相應(yīng)的生化分析檢測[3～6]。因此，數(shù)字微流控生物芯片具有可擴展、可動態(tài)重構(gòu)的系統(tǒng)架構(gòu)。然而，在許多實際應(yīng)用中，往往要求不同類型的生化檢驗操作在同一個芯片上協(xié)同運作，這在一定程度上極大地增加了芯片系統(tǒng)的復(fù)雜性。而傳統(tǒng)數(shù)字微流控生物芯片所采用的全定制設(shè)計制作技術(shù)擴展性差，而且2D電極陣列的尺寸（即資源約束）以及生化檢測試驗中各操作之間的功能依賴性（時序約束）均限制了片上并行操作的數(shù)量。以上各種問題的出現(xiàn)使得傳統(tǒng)數(shù)字微流控生物芯片的全定制設(shè)計技術(shù)已經(jīng)遠不適用于大規(guī)模的生化分析與檢測。因此，針對上述問題，參照超大規(guī)模集成電路（VSIA），在芯片系統(tǒng)中需要引入計算機輔助設(shè)計，可優(yōu)化芯片結(jié)構(gòu)，減少人為干預(yù)，提高芯片的利用率及效率[7～9]。

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

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

1 問題描述

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

圖1 多元生化檢驗有序圖模型

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

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

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

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

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

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

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

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

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

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

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

其中，Mi,j為一個二進制變量：

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

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

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

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

3 遺傳算法設(shè)計

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

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

3.1 第一層遺傳算法

1）編碼

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

第一層個體編碼為任務(wù)鏈表編碼，液滴操作任務(wù)列表U=[U0，U1，···，UK，UK+1]表示滿足時序約束的全部操作任務(wù)的一個排列次序，解碼時各操作從左向右依次進行排列。這里要保證操作任務(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ù)，其表達式參看3.2節(jié)。

3）選擇

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

4）交叉

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

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

5）變異

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

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

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

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

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

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

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

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

3.2 第二層遺傳算法

1）編碼

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

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

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

3）關(guān)鍵鏈技術(shù)對個體進化

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

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

4）變異

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

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

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

（2）計算每個個體Yi'的適應(yīng)度值，并進行評價：

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

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

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

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

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

表1 實驗數(shù)據(jù)

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

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

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

表3 生化檢驗完成時間結(jié)果對比 （單位：s）

5 結(jié)論

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