基于數字微流控生化檢驗操作調度的混合遺傳算法研究

王 鶴

（河南工程學院，鄭州 451191）

0 引言

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

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

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

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

1 問題描述

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

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

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

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

2 數學模型

根據上述分析，生化檢測調度問題可以看做是0-1整數線性規劃問題，因此建立數學模型[7,12]如下所示：

設xi,j為二進制變量，則：

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

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

操作vi的持續時間為di，且操作vi和vi+1之間存在依賴關系，那么：

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

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

用于液滴臨時存儲的電極數量設為Nmemory：

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

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

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

因此，數字微流控生化檢驗液滴操作調度優化的目標就是生化檢驗完成時間最短：

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

3 遺傳算法設計

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

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

3.1 第一層遺傳算法

1）編碼

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

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

2）適應度函數

這里取第二層遺傳算法的適應度函數的最優值作為第一層的適應度函數，即Fu=Fl*，其中Fl表示第二層適應度函數，其表達式參看3.2節。

3）選擇

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

4）交叉

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

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

5）變異

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

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

（1）初始化兩層控制參數；

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

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

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

（5）對第一層個體進行交叉變異，產生新一代個體，并計算其適應度值。

（6）判斷新個體適應度是否滿足終止條件。若滿足，則算法的迭代過程收斂，算法結束；否則，轉至（3）重復以上步驟。

3.2 第二層遺傳算法

1）編碼

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

2）適應度函數

數字微流控生化檢驗液滴操作調度優化的目標是最小化最后一個操作的完成時間Tl，因此本層適應度函數定為Fl=1/Tl。

3）關鍵鏈技術對個體進化

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

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

4）變異

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

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

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

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

（3）利用關鍵鏈技術對個體Yi'進行進化，替代交叉過程，并對其變異，計算出新個體的適應度值。

（4）判斷新個體適應度是否滿足終止條件。是則算法結束；否則，轉至（3）重復以上步驟。

4 仿真結果及分析

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

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

表1 實驗數據

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

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

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

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

5 結論

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