基于演化路径优先级的数字微流控芯片液滴路径规划算法研究

AN EVOLUTIONARY ALGORITHM FOR DROPLET ROUTING IN DIGITAL MICROFLUIDIC BIOCHIPS

吴贻能

11849331

硕士

计算机技术

袁博

2020-05-30

2020-07-08

哈尔滨工业大学

深圳

数字微流控芯片是一种新兴的微流控技术，具有微型化、自动化、低成本和高效率的特点，能有效加快生化检测和分析的进行。因此，该技术在临床诊断、环境监测和药物制备等领域具有重要的应用价值。液滴路径规划是数字微流控芯片高级综合的核心步骤之一，旨在规划一组液滴的移动路径，要求液滴能够正确执行生化检测和分析的反应流程。在液滴的移动过程中，规划算法要避免液滴之间可能发生的意外混合，同时要满足时间约束。通常将最小化最晚到达终点的液滴的完成时间和最小化液滴移动过程中电极使用数量作为液滴路径规划问题的优化目标。 为了有效解决液滴路径规划问题，本文先对问题进行建模，明确输入输出、约束条件和优化目标。针对四种不同的液滴意外混合场景，本文采用四种不同的方法避免液滴之间的意外混合。进一步，本文提出了一种基于演化路径优先级的液滴路径规划算法，算法包含演化算法部分和路径搜索算法部分。演化算法以路径优先级作为个体编码，用于搜索最优的液滴路径规划顺序。路径搜索算法是在给定路径优先级条件下，获取所有液滴的移动路径。路径搜索算法分为两个步骤，第一个步骤在忽略时序的情况下，在Dijkstra算法中引入代价函数，使液滴有倾向性地选择移动的网格，依次获得每个液滴的移动路径；第二个步骤考虑时序，将所有的液滴路径综合在一起，使液滴沿着路径同时移动。本文的实验分为两个部分，第一部分是单目标实验，把最小化液滴移动的完成时间作为优化目标；第二部分是多目标实验，把同时最小化液滴移动的完成时间和电极使用数量作为优化目标。本文提出的算法在三组测试集上做测试，包括一组真实的生化反应任务。实验结果表明，在只考虑完成时间的情况下，相比基准算法，本文提出的算法在测试集一和测试集二上获得更短的完成时间，在测试集三上获得更短的平均完成时间；在同时考虑完成时间和电极使用数量的情况下，相比基准算法，本文提出的算法在三个测试集上面能够取得更短的完成时间和平均完成时间，电极使用数量有所增加。为了验证算法的正确性和液滴路径的合法性，本文设计了一个验证工具，将液滴的移动过程可视化，同时向使用者报告液滴之间是否出现冲突。此外，该工具也提供了一个以本文算法为核心的液滴路径规划求解器，使用者可以自定义测试样例、参数以及选择不同的优化目标。

Digital microfluidic biochip, as an innovative microfluidic technology, has the characteristics of miniaturization, automation, low cost and high efficiency, which make the biochemical detection and analysis more efficient. It has great application value in the fields of clinical diagnostics, environmental monitoring, and drug preparation. The droplet routing is an important design stage in the advanced synthesis of digital microfluidic biochip. It determines the routing paths for droplets and requires droplets to correctly perform the reaction process. During the movement of droplets, the routing algorithm should avoid possible accidental mixing between droplets, while satisfying the time constraint. Routing algorithms usually take minimizing the latest arrival time of a droplet and minimizing the number of cells used in the droplet movement process as the optimization objectives.In order to effectively solve droplet routing problem, we formulate the problem and clarify the input and output, the constraints and the optimization objectives. For four different mixing scenarios, we use four different methods to avoid possible accidental mixing. Further, we propose a droplet routing algorithm based on the evolutionary path priority, which includes an evolutionary algorithm and a path search algorithm. The evolutionary algorithm uses path priority as individual code to search for the optimal routing order. The path search algorithm is to obtain routing paths of all droplets under a given path priority. The path search algorithm is divided into two steps. The first step ignores the time sequence and makes droplets move one by one. At the same time, a cost function is introduced into the Dijkstra algorithm, so that the droplets tend to select better cells for moving; the second step considers time sequence, synthesizing all droplet paths together, so that the droplets can move at the same time while meeting constraints. The experiment includes two parts. The first part is single-objective experiment, and it takes minimizing the latest arrival time of a droplet as the optimization objective. The second part is multi-objective experiment which takes minimizing the latest arrival time of a droplet and the number of cells used as the optimization objectives. The proposed algorithm is tested on three benchmark suites, including a set of real assays. The experimental results show that in the case of only considering the completion time, compared with the baseline algorithms, the proposed algorithm achieves shorter completion time on the Benchmark Suite I and the Benchmark Suite II, and shorter average completion time on the Benchmark Suite III. In the case of considering two objectives, compared with the baseline algorithms, the proposed algorithm achieves shorter completion time and average completion time on three benchmark suites, and increases the number of cells used.In order to verify the correctness of routing algorithm and the legitimacy of droplet paths, we designed a tool to visualize the droplet's movement, and report conflicts between droplets. In addition, this tool provides a droplet routing solver based on our algorithm which allows users to customize test samples, parameters and select different optimization objectives.

数字微流控芯片 液滴路径规划 Dijkstra 算法 演化算法 液滴路径验证与可视化

digital microfluidic biochip droplet routing Dijkstra algorithm evolutionary algorithm droplet path verification and visualization

中文

联合培养

南方科技大学

吴贻能. 基于演化路径优先级的数字微流控芯片液滴路径规划算法研究[D]. 深圳. 哈尔滨工业大学,2020.