基于禁忌搜索的數(shù)字微流控生物芯片多目標(biāo)綜合優(yōu)化算法

王 鶴

(河南工程學(xué)院機(jī)械工程學(xué)院 河南 鄭州 451191)

0 引 言

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

(a)

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

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

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

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

1 片上生化檢驗(yàn)系統(tǒng)建模

1.1 生化檢驗(yàn)?zāi)Ｐ?/h3>

數(shù)字微流控生化分析實(shí)驗(yàn)可以被看作是一組具有先后次序的液滴操作，可用如圖2所示的有向無環(huán)圖進(jìn)行描述。

圖2 多元生化分析實(shí)驗(yàn)有序圖模型

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

1.2 生物芯片系統(tǒng)綜合問題描述

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

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

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

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

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

(b) t=2 s

(c) t=4.9 s

(d) t=11.95 s

(e) t=14.85 s圖3 生化檢驗(yàn)系統(tǒng)綜合實(shí)例

2 功能模塊動(dòng)態(tài)移位

數(shù)字微流控生物芯片上的每個(gè)功能模塊都是一個(gè)虛擬設(shè)備，不同電極組合得電可使得該功能模塊在芯片上的位置發(fā)生變化，因此，功能模塊具備可動(dòng)態(tài)重構(gòu)這一特性。利用這一特點(diǎn)，在液滴操作執(zhí)行過程中，本文適時(shí)改變某功能模塊位置，以最終達(dá)到提高片上電極的利用率和生化檢驗(yàn)完成時(shí)間最小化這兩個(gè)目標(biāo)。

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

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

(b) t=2 s

(c) t=4.9 s

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

下面采用改進(jìn)的緊急搜索算法來實(shí)現(xiàn)以上的數(shù)字微流控生物芯片的系統(tǒng)綜合以及功能模塊的動(dòng)態(tài)移位。

3 改進(jìn)的禁忌搜索算法實(shí)現(xiàn)系統(tǒng)綜合

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

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

3.1 功能模塊動(dòng)態(tài)移位算法實(shí)現(xiàn)

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

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

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

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

(d) M3綁定的功能模塊動(dòng)態(tài)移位

(e) 放置M4綁定的功能模塊圖5 功能模塊動(dòng)態(tài)移位實(shí)現(xiàn)過程

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

3.2 改進(jìn)的禁忌搜索算法

算法的主要思想為：依照傳統(tǒng)禁忌搜索算法進(jìn)行搜索，獲得局部最優(yōu)解，將其作為父代進(jìn)行變異，得到迄今為止的最優(yōu)解，并將其作為下一次迭代的初始解；如此循環(huán)迭代可實(shí)現(xiàn)對(duì)數(shù)字微流控生物芯片的系統(tǒng)綜合優(yōu)化。

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

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

(3) 特赦準(zhǔn)則 所謂的特赦準(zhǔn)則，是指如果鄰域候選解集中存在一個(gè)新解，優(yōu)于當(dāng)前最優(yōu)解，即使這個(gè)新解是被禁忌表禁止的，算法也會(huì)選擇這個(gè)更優(yōu)的新解，即這個(gè)新解被解禁。

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

(a) 當(dāng)前最優(yōu)解及禁忌表

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

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

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

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

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

表2 變異算子

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

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

因此，改進(jìn)的禁忌搜索算法實(shí)施步驟如下：

(1) 初始化各個(gè)控制參數(shù)；

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

(3) 對(duì)當(dāng)前解xnow進(jìn)行設(shè)計(jì)轉(zhuǎn)換在其鄰域N(xnow)生成一組鄰域解，并選出候選解xi，計(jì)算該解所占用的電極數(shù)Nei以及完成生化檢驗(yàn)的總時(shí)間Ti；

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

(6) 判斷是否達(dá)到設(shè)定的迭代步數(shù)，若是，則結(jié)束算法，并且輸出全局最優(yōu)解,反之，將算法轉(zhuǎn)至(3)，重復(fù)上述步驟。

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

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

首先分別采用0-1整數(shù)線性規(guī)劃算法(ILP)[15-16]與本文提出的禁忌搜索算法，實(shí)驗(yàn)仿真在三個(gè)不同面積的芯片上實(shí)施，兩種方法對(duì)應(yīng)的計(jì)算機(jī)仿真時(shí)間以及其最優(yōu)解所對(duì)應(yīng)的生化分析完成時(shí)間的對(duì)比如表3所示?？梢钥闯?，利用本文提出的禁忌搜索算法在三種不同面積的芯片上均可在5 min內(nèi)完成計(jì)算仿真，時(shí)間遠(yuǎn)遠(yuǎn)低于采用ILP算法的仿真時(shí)間。

表3 ILP與TS的比較

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

表4 TS與TS*的比較

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

5 結(jié) 語

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