基于禁忌搜索的數字微流控生物芯片多目標綜合優化算法

王 鶴

(河南工程學院機械工程學院 河南 鄭州 451191)

0 引 言

數字微流控技術的快速發展，使得生化檢驗不再局限于只能通過傳統實驗室的方式來實現，它推動著生化檢驗向著微型化、集成化、自動化與便攜化方向發展。樣品消耗量極小、成本低、可重復使用等優點使其在諸多領域都有廣泛的應用，如生化檢驗和醫藥分析等方面[1-2]。數字微流控技術是以離散的微液滴為單元，通過某種液滴驅動方式實現對液滴的產生、輸運、合并、混合、分離、存儲和檢測等多種基本操控或處理。其中，驅動液滴完成操作的最常見方式之一就是介電濕潤技術。按既定次序對電極施加電壓，液滴在電濕潤力的作用下在電極陣列上執行上述各種操作，以完成指定的生化檢驗分析[3-4]，如圖1(a)所示。

(a)

(b)圖1 數字微流控生物芯片

最小化生化檢驗完成時間通常是生化分析的目標之一，這是由于生物樣本脆弱，容易失去活性，要想使其在芯片上長時間保持最佳的臨床或實驗室環境是相當困難的。因此，如果要保證生化檢驗分析結果的完整性，就要在一定的資源和時序約束下，盡可能地提高各樣本或/和試劑操作的并行性，減少各液滴操作在芯片上的執行時間，以最小化生化檢驗的完成時間。資源約束是指數字微流控生物芯片一旦被制造出來，其尺寸就被固定，不可改變；時序約束是指在生化檢測實驗中，各個液滴操作之間具有一定的功能依賴關系，即各操作是具有一定的先后順序的。由于數字微流控生物芯片與超大規模集成電路(VLSI)在設計方面有諸多相似之處，因此，美國杜克大學的krishnendu Chakrabarty教授等[5-8]將計算機輔助設計(Computer Aided Design，CAD)與數字微流控生物芯片系統相結合，采用自頂向下的分析算法來設計芯片，這種設計理念能夠從整體上優化芯片結構，減少人為干預，并且提高芯片利用率。

所謂的數字微流控生物芯片的自頂向下的設計理念。簡單而言，就是根據芯片使用者所提供的生化檢測過程，利用序列圖模型和某種算法對其進行架構級調度、幾何級布局以及液滴的尋址。其中：架構級調度是指資源綁定和液滴操作的調度，幾何級布局是指將與液滴操作相綁定的功能模塊(如混合器、稀釋器及存儲單元等)在芯片上進行合理的幾何位置布局，而液滴尋址是規劃液滴在各個功能模塊之間或儲液池/廢液池與功能模塊之間的移動路線。這里的“功能模塊”，其本質就是一種虛擬設備。通常每個功能模塊都是由若干個電極組成的，具有液滴混合、稀釋和存儲等功能，而且具有重構性。圖1(b)所示的混和/稀釋器就屬于一類功能模塊。當同一時間內有多個液滴在片上執行操作時，任意兩液滴之間都要保持至少一個電極的間距，這是為了避免在不同功能模塊上執行操作的液滴之間發生意外混合。因此，在功能模塊的外圍往往需要設置一個能夠完全包圍該功能模塊的隔離區，如圖1(b)所示，網格區域就是一個隔離區，由若干隔離電極組成。由此可知，功能模塊實際在芯片上占據的電極數量要比其自身所占數量大得多。

許多學者已從架構級調度、幾何級物理布局和液滴尋址等多個方面對數字微流控生物芯片展開研究，但與液滴操作相綁定的功能模塊在操作執行過程中，其位置通常是固定不變的，而本文根據實際空閑電極的數量和位置，適時改變某些功能模塊在片上的位置，以提高片上電極的利用率，并結合改進的禁忌搜索算法來實現對生物芯片的架構級調度以及幾何級布局。

1 片上生化檢驗系統建模

1.1 生化檢驗模型

數字微流控生化分析實驗可以被看作是一組具有先后次序的液滴操作，可用如圖2所示的有向無環圖進行描述。

圖2 多元生化分析實驗有序圖模型

該有向無環圖模型可表示為G(V,E)，節點集V={vi:i=0,1,2,…,18}，每個節點代表一個操作，而I和M則分別代表液滴生成操作和混合操作，其中:vj(j=1,2,…,8)對應8個樣本或試劑液滴生成操作I，vk(k=9,10,…,14)分別對應1個稀釋操作DL1和5個混合操作M，vl(l=15,16,17)則對應3個液滴檢測操作D。另外，設置了兩個沒有任何液滴操作的空節點NOP，即v0和v18。兩個液滴操作的前后依賴關系用邊集E={(vi,vj):i,j=0,1,2,…,18}來表示，即操作vj必須在vi結束之后才能開始。每個操作vi的持續時間均用各個節點的權重ωi來表示，其中兩個空操作節點的權重設置為0。系統參數決定了每個液滴生成操作的時間，而液體的流動特性對其影響可忽略不計[9]。在兩個小液滴完成混合操作形成大液滴之后，通常還要對該大液滴進行分離操作，這樣做的目的是為了確保在生化檢驗中各液滴的體積保持一致。因此液滴分離操作的時間均已包含在液滴混合操作的完成時間之內，不再另行單獨計算。與液滴生成和混合等操作相比，液滴輸運操作時間非常短，故忽略不計，因此在有向無環圖中，任意兩節點之間的邊權重均設置為0。液滴操作不同，其所對應的資源需求和完成時間也不同，而資源需求包含可重新配置的資源需求P和不可重新配置的固定資源需求Q。在所有液滴操作中，液滴生成和液滴檢測操作對應的資源需求屬于Q，而液滴輸運、合并、混合、稀釋或分離等操作所對應的資源需求則屬于P。

1.2 生物芯片系統綜合問題描述

數字微流控生物芯片的系統綜合問題非常復雜，可將其分解成四個部分來分析解決：(1) 資源綁定。在功能模塊庫中為某個液滴操作vi選取一個相應的功能模塊Mp×q，那么該操作必須在此模塊上執行。(2) 操作調度。在資源綁定和各約束(包含資源約束和時序約束)的前提下，明確各個液滴操作vi的起始時間。(3) 功能模塊的幾何布局。在芯片上為每個液滴操作vi綁定的功能模塊找到適當的物理位置。(4) 液滴尋址。規劃液滴在各個功能模塊之間或儲液池/廢液池與功能模塊之間的移動路線。根據實際情況，本文對生物芯片的系統綜合的目標有兩個，一是提高電極利用率；二是減小生化檢驗完成時間。這里，液滴尋址不作為本文研究的內容，只單從資源綁定、操作調度和功能模塊的物理布局這三個角度展開研究。

在傳統的數字微流控生物芯片的系統綜合算法中，與液滴操作相綁定的功能模塊在操作執行過程中，其位置通常是固定不變的。表1給出了液滴在不同類型功能模塊上完成操作所對應的時間[10-11]。

表1 不同混合器/稀釋器完成操作所需時間

假設液滴生成操作時間和光學檢測時間分別為2 s和20 s。另外，設定每種樣本或試劑的儲液池數量Nr=1，每種酶測定所需檢測器的數量Nd=1，兩者均屬于固定資源需求Q。在確定各模塊位置之后單獨執行液滴尋址，因此，這里并未將其列為本文研究內容。針對圖2所示的生化分析實驗，圖3給出了一個系統綜合方案，其中M2×2混合器2個，分別綁定給操作M1和M2；M2×4稀釋/混合器各1個，分別綁定給操作DL1和M4；M2×3和M1×5混合器各1個，分別綁定給操作M3和M5。根據以上資源綁定方式以及圖3所示的功能模塊布置于片上的位置，圖3(a)給出了最佳液滴操作調度方案。在該方案中，一旦將功能模塊布置在芯片的某個位置，在與該功能模塊相對應的液滴操作執行的過程中，該模塊的位置保持不變。這里，調度方案選擇用甘特圖表示，每個長方形代表一個液滴操作，其長度表示該操作的執行時間。比如，混合操作M3于t=2 s開始，t=8.1 s結束，在M2×3混合器上執行，該操作持續時間為6.1 s。受空閑電極在芯片上分布的限制，操作M4必須要在操作M3結束之后才能開始執行，而且由于要等到操作M4結束之后，與操作M3和M4所對應的液滴才能開始執行操作M5，所以操作M3完成之時即t=8.1 s時，要暫時將液滴存儲在存儲器S上直至操作M4完成，具體見圖3(c)和(d)所示。從圖3(c)可知，空閑電極的總數量大于操作M4綁定的功能模塊M2×4所需要的電極數量，但由于空閑電極的分布零散，造成無法在t=4.9 s時刻在片上布置混合器M2×4的位置，降低了電極的利用率，液滴操作的并行性被削弱，同時生化檢驗完成時間也大大增加。針對以上問題，本文利用功能模塊可動態重構的特點，適時改變功能模塊的位置，以提高電極的利用率，最小化生化檢驗完成時間。

(a) 由甘特圖表示的調度方案

(b) t=2 s

(c) t=4.9 s

(d) t=11.95 s

(e) t=14.85 s圖3 生化檢驗系統綜合實例

2 功能模塊動態移位

數字微流控生物芯片上的每個功能模塊都是一個虛擬設備，不同電極組合得電可使得該功能模塊在芯片上的位置發生變化，因此，功能模塊具備可動態重構這一特性。利用這一特點，在液滴操作執行過程中，本文適時改變某功能模塊位置，以最終達到提高片上電極的利用率和生化檢驗完成時間最小化這兩個目標。

圖4給出了基于以上思想的與圖2生化分析所對應的新的系統綜合方案。雖然圖4(b)所示的空閑電極的總數大于操作M4綁定的功能模塊M2×4所需要的電極數，但空閑電極的分布零散使得在t=4.9 s時刻無法為混合器M2×4找到合適的位置。因此，將混合操作M3綁定的功能模塊M2×2在t=4.9 s時刻，整體向左移動三個縱列的位移，即可將空閑電極聚集，隨之可將M4的功能模塊M2×4布置在芯片上，如圖4(c)所示。混合器M2×2在操作M3的執行過程中，產生這樣的位置移動，大大提高了液滴操作的并行性，使得生化分析的完成時間由38.05 s(圖3(a))減少至34.85 s(圖4(a))，減少了8.4%。當然，一旦混合器M2×2的位置發生變化，就需要對其上的液滴在新舊兩個位置之間進行了路徑規劃，但由于液滴輸運操作的時間極短，因此該液滴在混合器M2×2的兩個位置之間的移動時間可忽略不計。除此以外，圖3(d)中包含的存儲器S在圖4所示的新方案中也可省略不用，減少了功能模塊的使用數量。

(a) 由甘特圖表示的調度方案

(b) t=2 s

(c) t=4.9 s

(d) t=8.1 s圖4 改進的生化分析系統綜合方案

下面采用改進的緊急搜索算法來實現以上的數字微流控生物芯片的系統綜合以及功能模塊的動態移位。

3 改進的禁忌搜索算法實現系統綜合

禁忌搜索(Tabu search，TS)算法是一種亞啟發式的隨機搜索算法，是對局部領域搜索的一種擴展，是一種全局迭代尋優算法，是對人類記憶功能的一種模擬。TS算法的主要思想就是從一個初始可行解開始，對該解的鄰域進行搜索并優選，同時設置禁忌表，用來存儲已經搜索過的局部最優點，以便在后續搜索中有意避開(但并不是絕對禁止)禁忌表中所包含的局部最優點。也就是說，在搜索過程中，當最優候選解在禁忌表中時，則選擇未被禁忌的次優候選解來替代當前解，因此該算法是通過引入一個靈活的存儲結構和相應的禁忌準則來避免迂回搜索的。另外，當候選解優于最優解，但該最優解卻被禁忌時，利用特赦準則來赦免這些最優解，從而保證探索的多樣化以最終達到全局最優的目的[12-13]。但是通過算法的實際應用發現，初始解的好壞會對算法的搜索結果產生很大的影響，因此這里引入以長期記憶為基礎的變異因子對傳統的禁忌搜索算法進行優化，以此完成對數字微流控生物芯片的系統綜合以及功能模塊的動態移位。

在本文提出的系統綜合算法中，以有向無環圖模型G(V,E)、m×n生物芯片電極陣列、功能模塊庫L等作為算法輸入，完成資源綁定、操作調度和功能模塊的物理布局，實現提高片上電極利用率和生化檢驗完成時間最小化這兩個目標。對于由TS確定的資源綁定，我們使用列表調度來確定操作vi的調度。列表調度是以優先級列表PL為基礎，其中包含了所有已準備好被調度的操作，這樣操作的所有前驅操作均已完成。每次迭代，優先級最高的操作vi被調度，并且該操作被調度之前，其綁定的功能模塊Mp×q已被放置在芯片上，而各操作的優先級也是由TS確定的。一旦確定該操作的功能模塊Mp×q在片上的位置，列表調度就會根據Mp×q與源模塊之間的曼哈頓距離計算液滴尋址時間。TS將每個操作vi綁定到一個隨機選擇的功能模塊Mp×q，由此產生算法的初始解，并且利用關鍵路徑優先級函數給出各操作的優先級。

3.1 功能模塊動態移位算法實現

以圖3(c)為例，我們給出功能模塊動態移位算法的具體實現過程。在t=4.9 s時刻，操作DL1已結束，這時優先級列表中包含了三個已準備好被調度的操作，即M1、M2和M4，三者具有由高到低的優先級排序，而且前兩者均綁定到模塊M2×2，后者綁定到模塊M2×4。列表調度在t=4.9 s時刻首先為操作M1的功能模塊M2×2在片上找到合適的物理位置。選擇物理位置的基本原則就是盡量將功能模塊集中放置在芯片上，這樣的話，剩余空閑電極分布也會比較集中，便于并行布置其他功能模塊，提高操作的并行性。在t=4.9 s時刻，操作M3的功能模塊將空閑電極分成了四個交疊的矩形區域a1、b1、c1和d1，如圖5(a)所示。這四個區域分別用矩形的左下角坐標和右上角坐標表示，即(0,0,3,8)、(3,8,8,11)、(7,3,11,8)和(0,0,8,4)。除區域a1以外，其他三個區域均可容納下操作M1的功能模塊M2×2。假設該功能模塊被放置到區域d的左下角位置，如圖5(b)所示。之后更新空閑電極分布區域為a2、b2、c2和d2，即(0,4,3,8)、(3,8,8,11)、(7,3,11,8)和(4,0,8,4)。同樣除區域a2以外，其他三個區域均可容納下操作M2的功能模塊M2×2，但是區域d是正好能容納下M2，因此，基于為功能模塊選擇物理位置的基本原則，將M2放置在區域d，這樣不會造成剩余空閑電極分布過于分散，以增大剩余空閑電極容納下操作M4的幾率，如圖5(c)所示。但是，我們發現，即使這樣選擇M2功能模塊的物理位置，雖然剩余空閑電極總數大于操作M4的功能模塊M2×4所需要的電極數量，但是由于空閑電極分布分散，實際上是無法為操作M4的功能模塊M2×4找到合適的物理位置的。因此，本文在操作執行過程中移動某功能模塊位置，盡可能減小空閑電極的分散度。

(a) t=4.9 s時刻功能模塊初始狀態

(b) 放置M1綁定的功能模塊

(c) 放置M2綁定的功能模塊

(d) M3綁定的功能模塊動態移位

(e) 放置M4綁定的功能模塊圖5 功能模塊動態移位實現過程

這里采用貪心搜索策略來決定哪個功能模塊需要移動，而且對正在執行某一操作的功能模塊進行位置移動的話，還需要規劃其上的液滴從模塊初始位置到另一位置的移動路徑。模塊位置移動的路徑相當于其上液滴的移動路徑，路徑距離根據該模塊前后兩個位置左下角之間的曼哈頓距離計算。我們對這種情況下的液滴尋址時間設置一個約束，即一個時間步長。因此，一旦能夠容納下即將被調度的操作綁定的功能模塊或達到上述時間約束，就停止對功能模塊的動態移位。當然，如果動態移位之后發現沒有足夠的空間可以容納即將被調度的操作功能模塊，那么恢復被移動功能模塊的初始位置。在每次迭代中，貪心搜索策略選擇最佳移動，所謂的最佳移動就是在功能模塊移位之后，原來分散的兩個矩形區域之間的曼哈頓距離可以達到最小，而且通過矩形區域的合并增大相鄰空閑電極的數量。圖5(c)顯示了片上功能模塊所有可能的移動，即操作M3的模塊整體向左移動三個電極，或者分別向右或向上移動四個電極。貪心法選擇操作M3的模塊整體向左移動三個電極，也就是矩形區域a3同時向右移動三個電極，兩者交換位置，這是最佳移動，因為經過這樣的移動之后，圖5(c)中的矩形區域a3和c3之間的曼哈頓距離只有3，并且兩者合并為c4，(4,4,11,8)，包含28個相鄰的空閑電極，足以容納下操作M4的功能模塊M2×4，如圖5(d)、圖5(e)所示，算法終止。

3.2 改進的禁忌搜索算法

算法的主要思想為：依照傳統禁忌搜索算法進行搜索，獲得局部最優解，將其作為父代進行變異，得到迄今為止的最優解，并將其作為下一次迭代的初始解；如此循環迭代可實現對數字微流控生物芯片的系統綜合優化。

(1) 鄰域 緊急搜索算法是一種基于鄰域搜索技術的元啟發式算法，通過對當前解xnow進行設計轉換在其鄰域N(xnow)生成一組鄰域解，由此選出候選解x。目前廣泛使用的鄰域結構有交換和插入兩種，根據數字微流控生物芯片系統的自身特點，本文選擇交換鄰域結構，對當前解主要進行兩種移動，一是資源重新綁定，即隨機選擇液滴操作vi，解除與其當前綁定的功能模塊Mp1×q1，同時將該操作綁定到另一個功能模塊Mp2×q2；二是操作優先權的交換，即隨機選擇兩個液滴操作，交換兩者的優先權。

(2) 禁忌表 禁忌表是禁忌搜索算法的關鍵，存儲內容包括禁忌對象和禁忌長度兩項，決定了禁忌表中各對象的任期以及搜索范圍。本文使用兩個禁忌表，每種移動都對應有一個禁忌表。如果隨機選擇操作vi被資源重新綁定到功能模塊Mp2×q2，那么它們就會以(vi,Mp2×q2)的形式列入到與資源重新綁定對應的那個禁忌表中；如果隨機選擇操作vi和vj交換優先權，那么這兩個操作以(vi,vj)的形式被列入與操作優先權交換對應的禁忌表中。因此，被列入禁忌表中的解在禁忌長度內不允許被再次訪問，但為了防止算法中的所有對象都被禁忌這種情況出現，也為了避免遺失優良狀態，使用“特設準則”來加速實現全局優化。

(3) 特赦準則 所謂的特赦準則，是指如果鄰域候選解集中存在一個新解，優于當前最優解，即使這個新解是被禁忌表禁止的，算法也會選擇這個更優的新解，即這個新解被解禁。

以圖2生化分析中各操作資源重新綁定移動為例，圖6給出了禁忌搜索的三種鄰域解。液滴生成和液滴檢測操作屬于不可重新配置的固定資源需求Q，所以不在資源重新綁定的范圍內。對圖6(b)-(d)的三個鄰域解分析發現，雖然圖6(b)對應的解是被禁忌表禁止的，但這個解優于當前最優解，所以算法會解禁該解，并將其替代當前最優解。

(a) 當前最優解及禁忌表

(b) 操作M3的功能模塊由M2×2重新綁定到M2×4，這屬于禁忌，但優于當前最優解

(c) M4的功能模塊由M2×4重新綁定到M2×2，這屬于非禁忌移動，而且優于當前最優解

(d) M5的功能模塊由M1×5重新綁定到M1×4，這屬于非禁忌移動，但該解比當前最優解差圖6 禁忌搜索鄰域(資源重新綁定)

(4) 變異因子 為進一步擴大算法的搜索范圍，參考遺傳算法，將當前局部最優解作為父代進行變異。這里的變異就是將液滴操作的資源綁定和優先權分別進行交換。由于當前解在鄰域內的優先權交換就是在兩個液滴操作之間進行的，如果在變異階段仍然采取兩個操作之間交換進行變異，那么擴大搜索范圍的能力會受到影響。因此，這里我們選擇對兩個以上的液滴操作進行資源綁定和優先權進行交換來完成變異。下面以圖2所示的生化分析為例，給出變異的主要思想。就資源綁定變異來講，由于液滴生成和液滴檢測操作屬于Q，所以只有DL1、M1至M5這六個操作的資源綁定可以進行變異：

① 從上述6種液滴操作中隨機選擇3個(可依具體問題確定隨機選擇的數目)，如表2所示，隨機選擇M1、M3和M4；

表2 變異算子

② 3個液滴操作的資源綁定完全交換，生成兩個子代；

③ 在兩個子代中找出最優解，如果變異后的子代最優解優于父代，那么將該子代最優解替代當前迭代最優解，并且將其作為下一次禁忌搜索迭代中液滴操作資源綁定的初始解。

因此，改進的禁忌搜索算法實施步驟如下：

(1) 初始化各個控制參數；

(2) 隨機生成初始解，禁忌表設置為空集,并計算初始解所占用的電極數Ne以及完成生化檢驗的總時間T；

(3) 對當前解xnow進行設計轉換在其鄰域N(xnow)生成一組鄰域解，并選出候選解xi，計算該解所占用的電極數Nei以及完成生化檢驗的總時間Ti；

(4) 判斷xi是否滿足特赦準則且Nei≥Neinow且Ti≤Tinow，如果均滿足，則更新全局最優狀態，最優解x0=xi，并且更新禁忌表；

(6) 判斷是否達到設定的迭代步數，若是，則結束算法，并且輸出全局最優解,反之，將算法轉至(3)，重復上述步驟。

4 仿真結果及分析

為了驗證算法的有效性和可靠性，本文通過對人體體液體外診斷分析實驗的仿真，將其他算法與該算法進行了相應的比較。人體體液體外診斷實驗可參照文獻[14]，共有28個液滴操作，其中包含13個液滴生成操作、6個混合操作、3個稀釋操作和6個液滴檢測操作。

首先分別采用0-1整數線性規劃算法(ILP)[15-16]與本文提出的禁忌搜索算法，實驗仿真在三個不同面積的芯片上實施，兩種方法對應的計算機仿真時間以及其最優解所對應的生化分析完成時間的對比如表3所示。可以看出，利用本文提出的禁忌搜索算法在三種不同面積的芯片上均可在5 min內完成計算仿真，時間遠遠低于采用ILP算法的仿真時間。

表3 ILP與TS的比較

其次，定義去除功能模塊動態移位的禁忌搜索算法為TS*，用本文提出的改進的禁忌搜索算法TS與TS*分別在3 min和5 min仿真時限內，在三種不同面積的芯片上執行人體體液體外診斷實驗，兩種算法在每種情況下均運行50次，對比兩者的仿真結果，如表4所示。

表4 TS與TS*的比較

由表4可知，芯片尺寸越大，操作并行性越高，生化實驗完成時間越短；在一定的時間范圍內，仿真時間越長，生化實驗完成時間也越短。但是從算法50次仿真得到的最優解的平均值來看，在相同的仿真時限內，芯片尺寸越小，功能模塊的動態移位這一因素對增大電極利用率、提高液滴操作的并行處理和減小生化實驗完成時間的影響能力越高，比如，在3 min時限內，用TS在10×10、11×11和12×12芯片完成生化實驗的時間分別比TS*減少了10.58%、7.12%和4.19%。

5 結 語

本文利用功能模塊的動態重構特性，在某個操作執行的過程中，適時改變其綁定的功能模塊在片上的位置，增大液滴操作的并行處理，同時結合改進的禁忌搜索算法來實現功能模塊的動態移位以及數字微流控生化檢驗的架構級調度和幾何級布局，以達到提高電極利用率，最小化生化檢驗完成時間的目的。通過人體體液體外診斷實驗的仿真，對多個算法進行比較，仿真結果驗證了本文算法的有效性和可行性。而且該算法同樣也可用于其他生化實驗的實施，對數字微流控生化檢驗的系統綜合具有一定的參考價值。