[發明專利]基于禁忌搜索與人工勢場法相結合的數字微流控芯片在線測試方法

有效

• 申請號: 201710184028.9
• 申請日: 2017-03-24
• 公開（公告）號: CN106934173B
• 公開（公告）日: 2020-05-12
• 發明（設計）人: 鄭文斌;鳳雷;喬家慶;于鴻杰;馮收;徐明珠;王安琪
• 申請（專利權）人: 哈爾濱工業大學
• 主分類號: G06F30/398
• 分類號: G06F30/398
• 代理公司: 哈爾濱市松花江專利商標事務所 23109
• 代理人: 楊立超

1.一種基于禁忌搜索與人工勢場法相結合的數字微流控芯片在線測試方法，所述方法用于生成測試液滴在數字微流控芯片上的移動路徑，所述移動路徑通過頂點序列表示；所述頂點用于表示數字微流控芯片上的電極；

其特征在于，所述方法包括如下步驟；

步驟一、建立數字微流控芯片在線測試的數學模型，構建禁忌表；

步驟二、構建鄰接列表；

步驟三、設置禁忌搜索算法以及人工勢場法的初始參數；

步驟四、根據人工勢場法計算從當前頂點的可選鄰域內各個頂點所受到的合力值，根據所述合力值以及禁忌表選擇下一頂點；

步驟五、更新禁忌表；

步驟六、判斷路徑是否完整，若否，則跳轉至步驟四；

步驟七、判斷迭代次數是否達到預設的值，若否，則跳轉至步驟三；若是，則輸出最優路徑。

2.根據權利要求1所述的方法，其特征在于，所述步驟一中，建立數字微流控芯片在線測試的數學模型具體為：

建立測試液滴遍歷所有頂點及其鄰域的模型，表達式為：

其中，t為時刻，j為試驗液滴所在的頂點，i為測試液滴所在的頂點，N(i)為頂點i的鄰域；V為頂點集；為用于記錄在t時刻測試液滴是否從頂點i移動到頂點j情況的值，若是，則的值為1，若否，則的值為0；

測試液滴的移動路徑滿足如下流體約束條件：

其中，MR(j,t)表示在同一時刻與位置j的液滴能夠發生融合的液滴存在的區域，記為合并區域；IR(j,t)表示下一時刻的位置將進入合并區域MR(j,t)，記為干涉區域；T_e為片上實驗所需要的時間；

所述表達式的優化目標為：

其中z表示測試的總時間，為用于記錄在t時刻測試液滴是否從頂點i移動至其鄰域N(i)中一個頂點的情況的值。

3.根據權利要求1所述的方法，其特征在于，所述步驟二中，鄰接列表的頭結點為數字微流控芯片中的一個電極；鄰接列表的表節點為m·n行4列的矩陣，用于表示與其頭結點對應的電極相鄰的四個電極的編號；其中m和n分別為數字微流控芯片上電極的行數和列數。

4.根據權利要求2所述的方法，其特征在于，所述步驟四中，下一個頂點的表達式為其中，Allowed(i)表示頂點i的鄰域內不在禁忌表中的頂點組成的集合；x為Allowed(i)中的頂點，F(x)為合力值，通過如下公式確定：

F(x)＝F_G(x)+F_O(x) x∈Allowed(i)

其中F_O(x)為人工勢場法中的斥力；F_G(x)為人工勢場法中的引力；k_o為用于表示試驗液滴間的距離對斥力大小影響的參數；k_g為用于表示圖模型中某條邊被訪問次數對引力大小的影響的參數；d(x,Tabu(t))為頂點x到禁忌區域時刻表Tabu(t)中的所有頂點的距離中最小的一個距離；R為用于記錄路徑(i,x)被訪問次數的矩陣。

5.根據權利要求4所述的方法，其特征在于，所述步驟一中：

禁忌表包含禁忌區域時刻表Tabu(t)以及禁忌搜索表Tabulist(t)；

禁忌區域時刻表Tabu(t)用于存儲試驗液滴流體約束條件限制下的禁止區域；Tabu(t)滿足Tabu(t)＝IR(j,t)∪MR(j,t)，其中j為某一時刻試驗液滴的位置所對應的頂點；

禁忌搜索表Tabulist(t)用于存儲測試液滴最近特定步數的電極區域。

6.根據權利要求5所述的方法，其特征在于，所述步驟五中，當測試液滴在當前時刻已經沒有可選擇的未走路徑，則釋放出禁忌表中禁忌步數最小的頂點作為當前選擇。

7.根據權利要求4或5所述的方法，其特征在于，所述步驟五中，更新禁忌表具體為：

禁忌區域時刻表Tabu(t)隨時刻t進行動態更新；

將禁忌搜索表Tabulist(t)表內的頂點禁忌步數減1；將此時禁忌步數為0的頂點移出該表；將測試液滴下一時刻將要選擇的頂點j加入Tabulist(t)表，并將其禁忌步數設置為k；其中k為禁忌步數的初始值，用于表示最近一個加入禁忌搜索表Tabulist(t)的頂點的禁忌步數，k隨著路徑搜索過程進行更新。