基于改进粒子群算法的数字微流控芯片故障检测方法及系统

摘要

本发明涉及一种基于改进粒子群算法的数字微流控芯片故障检测方法及系统，属于微数字微流控芯片故障检测领域，为了解决现有技术的数字微流控芯片故障检测方法故障定位时间较长的缺点，而提出一种基于改进粒子群算法的数字微流控芯片故障检测方法，包括：获取测试液滴的起始位置和终点位置；构建禁忌表；构建至少一个粒子群，为每个粒子群构建与其对应的位置矩阵；确定粒子群算法中每个粒子的速度向量，直至所有相邻电极均被遍历；根据公式更新粒子的位置序列；计算每个粒子的位置向量的适应度，并分别确定每个种群当前最短路径以及全局最短路径；重复上述步骤，直至达到预定的迭代次数，输出全局最短路径。本发明适用于数字微流控芯片的故障检测。

说明书

技术领域

本发明涉及一种基于改进粒子群算法的数字微流控芯片故障检测方法及系统，属于微数字微流控芯片故障检测领域。

背景技术

随着科技的发展，自动测试领域已从对模拟电路或数字电路的测试扩展到对微机电系统MEMS(Micro-Electromechanical Systems)的测试。微流控芯片又称作片上实验室(Lab-on-a-chip),可以在一块几平方厘米的芯片上完成生物实验室及常规化学检验的各种功能。具有小型化、高敏感度、低成本、集成化等特点。第一代微流控生物芯片具有永久刻蚀的微阀、微泵和微流道，至于具体操作都是基于连续的流体流动。微流体技术和制造工艺的发展推动了数字微流控芯片的产生，数字微流控芯片在二维微流控阵列上操纵离散的液滴，具有可大幅扩展的系统架构。

数字微流控芯片与连续流体控制相比，强调将液体分散化为微量的液滴来操作，单独控制每个液滴，且能耗很低，特别适用于需要高性能并且操作较复杂的生化分析。与传统模式的生化分析仪相比，数字微流控芯片具有可重复使用、尺寸小、自动化程度高、集成度高等优势。有能力精确驱动微量液体(低至微升甚至纳升级别的液体)，在芯片上完成流体的运输、存储、分离和混合等操作，以低成本完成超灵敏的生化检测，可以显著的减少测试时间及实验室空间，由于减少了人为操作过程，增加了结果的稳定性和准确性。因此在临床诊断、生物医疗、健康检查、药物诊断、空气质量的检测等方面都有广泛的应用前景，具有重要的意义。

随着数字微流控芯片的发展，为了满足越来越复杂的生化分析实验系统的要求，数字微流控芯片的规模及芯片密度迅速扩大，这样在使用过程中十分容易出现各种物理故障及生产故障，这样的故障对微流控系统而言更具有危险性，也更容易出现破坏性的故障。同时，数字微流控生物芯片常用在生物检测、临床诊断、药物研制等安全关键领域，其可靠性成为制作和设计的重要标准。为保证芯片系统的可靠性，需要进行有效并且全面的故障检测。芯片的有效性测试不仅仅存在于芯片生产完成后，进行生化检测之前，甚至在实验进行过程中都需要不断的进行测试，以保证稳定性。故障检测完成后，为了实现实验液滴行走路线的重新配置，还需要对芯片阵列进行准确的故障定位。如何对测试液滴的测试路径进行规划是节约芯片测试时间、提高芯片测试效率的核心问题。

数字微流控芯片的测试方法是使实测试滴遍历芯片的电极单元，因此实验液滴走过路径的长短直接影响测试时间的长短。为了不影响实验液滴的正常工作，数字微流控芯片阵列故障检测属于资源限制下的路径优化问题，属于NP难问题。

因此，需要一种新的数字微流控芯片的故障检测方法，使得在保证故障覆盖率的前提下，最大程度的缩短故障定位时间，提高故障检测效率，节约检测成本，保障数字微流控芯片的安全性。

发明内容

本发明的目的是为了解决现有技术的数字微流控芯片故障检测方法故障定位时间较长的缺点，而提出一种新的基于改进粒子群算法的数字微流控芯片故障检测及定位方法。

基于改进粒子群算法的数字微流控芯片故障检测方法，其特征在于，包括如下步骤：

步骤一：获取测试液滴的起始位置和终点位置；所述测试液滴用于在数字微流控芯片的相邻电极阵列间移动以判断所述相邻电极阵列间是否存在故障；每两个相邻电极阵列间的边被赋予了互不相同的编号；

步骤二：构建禁忌表，所述禁忌表用于存放液滴在当前位置不能访问的边以及已经访问过的边；

步骤三：构建至少一个粒子群，为每个粒子群构建与其对应的位置矩阵，所述位置矩阵的行数表示粒子群算法中的粒子总数；所述位置矩阵的列数表示相邻电极阵列间形成边的总数；所述位置矩阵中的元素表示特定的粒子在特定电极阵列处的速度向量；所述速度向量为下一时刻每个粒子所在的边的序号；

步骤四：确定粒子群算法中每个粒子的速度向量Speed，直至所有边均被遍历；所述速度向量Speed具体通过如下方式的随机一种确定：

A、选择随机的一个允许选择的边Speed₁；

B、选择离当前位置距离最近的一条边Speed₂；

C、选择上一次迭代得到的最短路径序列中与当前时刻的位置相邻的边Speed₃；

步骤五：根据公式更新粒子的位置序列，其中X^t＝(1,x¹,x²,...,x^t,0,...)，x^t为第t时刻粒子的位置，V^t＝(0,0,0,...,x^t+1,0,...)，x^t+1＝Speed；

步骤六：计算每个粒子的位置向量的适应度，并分别确定每个

当前最短路径Pbestⁱ以及全局最短路径Gbest；所述适应度用于表示生成的边的有序序列所对应的路径的长度；

步骤七：重复迭代步骤三至步骤六，直至达到预定的迭代次数，输出全局最短路径Gbest。

本发明的有益效果为：使用粒子群算法，在保证故障覆盖率的前提上最大程度的缩短故障定位时间，提高故障检测效率，节约检测成本，保障数字微流控芯片的安全性。同时，本发明将PSO算法和贪婪算法的思想融合，使改进粒子群算法可以解决基本粒子群求解路径优化问题时面临的困难，并且有更高的效率。对基本PSO算法中粒子的位置、速度以及操作进行了重新定义，使粒子群算法更适合于求解最短路径优化问题，更好的完成数字微流控芯片的在线故障检测。同时，本发明提出利用红外发光管和红外接收管进行故障定位的方法，能有效的发现故障点，便于后续的实验液滴路径重构问题。

附图说明

图1为本发明的基于改进粒子群算法的数字微流控芯片故障检测方法的流程图；

图2(a)为数字微流控芯片无故障单元时的测试结果；

图2(b)为数字微流控芯片有故障单元时的测试结果；

图3(a)为一个实施例中数字微流控芯片的液滴从起始点开始移动的示意图；其中两个电极的相连表示短路；箭头表示移动方向；

图3(b)为图3(a)的液滴移动到短路位置的示意图；

图4(a)为另一个实施例中数字微流控芯片的液滴从起始点开始移动的示意图；其中两个电极的相连表示短路；箭头表示移动方向；

图4(b)为图4(a)的液滴由于偏离移动方向而经过故障电极的情况；

图4(c)为图4(b)的液滴未停留在故障电极而是移动到下一电极的情况；

图5为将微流控芯片模型转换为图的示意图。

具体实施方式

本发明涉及到的基本原理如下：

数字微流控芯片驱动微流体的方式为介电润湿驱动。通过电极阵列对液滴施加电场以改变其表面张力，在疏水聚合物表面利用的液固表面张力改变来驱动液滴。为了使液滴移动，驱动电压加在相邻的电极单元上，利用介电润湿原理，使得液滴的表面上积累电量，从而在液滴表面生成覆盖相邻电极的表面张力梯度，当该张力大于上下表面与液滴之间的阻力时，便可以完成液滴移动的驱动，这是控制液滴移动的最基本方法。通过在相应的电极阵列上施加电压序列，就能够实现在芯片上实现生化检测中基本操作，如：液滴分配，运输，存储，混合和分离等。

数字微流控芯片故障类型分为两种：参数性故障和永久性故障。参数性故障主要在制作过程中产生，如尺寸参数误差引起，当电极阵列不水平，两层表面之间不平行或电极厚度不均匀时，数字液滴的驱动将受到影响，该类故障对实验结果的影响表现为产生较大偏差，使芯片的性能受到严重影响。

永久性故障由芯片电极单元之间的断路和短路造成，这些故障可能来源于制作过程中，或者是由控制电压不合适导致的电极退化引起。永久性故障会导致液滴停留在故障单元，不能依照设计路线行进，无法完成实验移动到废液池，导致生化检测的失败，在安全性要求高的领域的应用会产生重大不良影响。本发明主要考虑永久性故障的在线故障检测方法。

数字微流控芯片的永久性故障主要会造成系统的液滴无法移动，因此可以根据测试液滴移动是否正常判断是否存在故障，但是由于故障可能会在实验进行时产生，所以需要不断的对芯片进行测试才能保证芯片长期稳定工作。可以使检测液滴和实验液滴并测的在线测试方法：通过对电极施加电压从而控制测试液滴从单独的检测液体储液池出发，在不影响实验液滴的前提下遵循测试规则行走，通过遍历阵列单元最终到达测试终点。在终点端增加电容检测电路判断测试液滴到达，即完成故障测试。如图2所示：

但仅仅使液滴遍历每个电极阵列是不能完成故障检测的，由上述介绍可知，永久故障可由电极之间短路引起，测试液滴经历短路的相邻电极时会出现不同的情况，图3图4中(a)表示液滴起始位置及运动方向，实线相连表示两个电极之间短路，即驱动电压同时产生同时消失。对图3，运动方向与电极短路方向平行，液滴经过短路的两个电极时，由于左右驱动电压同时产生同时消失，液滴会停留在短路电极中间，如(b)。对图4，液滴行进方向与短路电极方向相互垂直，经过故障位置时会有(b)中所示的稍许偏离，但是仍然能经过短路电极到达下一阵列的单元，如(c)，并没有停留在故障单元。

所以，为防止出现上述情况，需要对所有阵列单元及相邻阵列单元进行测试，从而才能保证检测的有效性和芯片工作的可靠性。数字微流控芯片的在线故障检测问题转化为寻找最短的遍历所有阵列单元和相邻阵列单元的问题。

本发明使用了基本粒子群算法来解决数字微流控芯片故障检测的问题。

基本粒子群算法(Particle Swarm Optimization，PSO)原理主要模拟鸟群飞行的觅食行为，通过鸟群的集体协作达到寻优的目的。在PSO算法中，每个粒子利用自身的历史最优位置和整个粒子群的全局最优解提供的信息，在解空间内不断飞行，实现寻找最优解的目的。

设搜索空间为N维，总粒子数为Num，第i个粒子的位置为x_i＝(x_i1,x_i2,...,x_in)，第i个粒子的速度向量是V_i＝(v_i1,v_i2,...,v_in)，第i个粒子在飞行中的粒子最优位置是P_i＝(P_i1,P_i2,...,P_in)，P_s表示目前为止在整个粒子群中发现的全局最优粒子，粒子按如下方式飞行：

v_ij^t＝w×v_ij^t+c₁×r₁×[P_ij^t-x_ij^t]+c₂×r₂×[P_sj^t-x_ij^t]

x_ij^t+1＝x_ij^t+v_ij^t+1

其中，下标j表示第j维，t为飞行的次数；w为惯性权重，使粒子保持运动惯性，控制前一速度对当前速度的影响，较大的w适用于对解空间进行大规模探查，较小的w适合于进行小范围寻优；c₁,c₂为加速常数，通常在0～2间取值，c₁调节粒子飞向自身最好位置方向的步长，c₂调节粒子向全局最好位置飞行步长；r₁,r₂是[0,1]之间相互独立的随机数。粒子的位置向量中各维变化范围为[X_min,X_max]，速度变化范围为[V_min,V_max]，迭代中若位置和速度超过边界范围则取边界值。PSO算法通过粒子在解空间内不断地变化速度向量来改变位置，最终寻到最优解。

从社会学的角度来分析，速度迭代公式的第一部分是“记忆”项，是粒子之前的速度，说明粒子当前速度向量要受到上一次速度的作用；公式第二部分是“自我认知”项，是从当前点粒子位置指向粒子个体最优的一个矢量，说明粒子的运动来源于粒子之前的经验；公式的第三部分是“群认知”项，是一个从当前点指向群体最优点的矢量，反映了粒子间的信息分享和协同合作。粒子通过经验和群体最优经验来决定下一时刻的速度以及位置。也就是第一部分起到了局部搜索和平衡全局的能力，第二部分保障粒子拥有局部搜索能力，更好的探索解空间；第三部分表示了粒子间的信息分享，使粒子能探索更广阔的空间，所以粒子能有效的搜索到最优解。

具体实施方式一：本实施方式的基于改进粒子群算法的数字微流控芯片故障检测方法，如图1所示，包括如下步骤：

步骤一：获取测试液滴的起始位置和终点位置；所述测试液滴用于在数字微流控芯片的相邻电极阵列间移动以判断所述相邻电极阵列间是否存在故障；每两个相邻电极阵列间的边被赋予了互不相同的编号。

具体而言，设置起始位置和终点位置是为了对应狮子微流控芯片上存在的储液池和废液池，实验液滴需从储液池出发，遍历所有电极阵列和相邻的电极阵列后到达废液池，所以首先需确定液滴的起始位置和终点位置，缩小解空间的维数，提高测试过程的效率。同时，根据实验液滴位置确定不能访问的边和已经走过的边，存放到禁忌表中，根据实验液滴的运动，及时更新禁忌表。

本发明将芯片遍历相邻两单元问题转化为图，建立数学模型。考虑到芯片形状规则的结构特点，为了方便利用离散粒子群算法进行问题的求解，将芯片的中的物理模型利用图论中的相关概念进行等效。将每个电极单元等效为图中的点，两个竖直或水平方向相邻的电极单元等效为一条边，抽象后的图用G＝(V,E)代表，数字微流控芯片模型如图5示。

研究表明，数字微流控芯片测试问题是一种遍历电极阵列单元与其相邻阵列单元的问题。芯片的模型为非连通图，由欧拉路径理论，我们不可能找到一次并且只有一次经过每一条边的路径。假设实验液滴走过每条边的时间一定，可以将芯片在线测试问题转化为寻找遍历图中所有边的最短路径问题。由Floy算法求得两条边i,j之间的最短路径d_ij。假设测试液滴需遍历的边的总数目为n，x_ij代表需访问的边，问题的解空间为X＝(X₁,X₂,...X_k)，第i个可行解为X_i＝(x_i1,x_i2,...,x_in)，该可行解的适应度函数为

则在线测试问题可转化为求最优解z：

由步骤一可知，数字微流控芯片故障在线测试问题为访问不同点，寻找最优路径问题，类似于TSP问题。TSP问题要求每个点访问且只访问一次，而本问题不存在遍历并且只访问每条边的回路。

步骤二：构建禁忌表，所述禁忌表用于存放液滴在当前位置不能访问的边以及已经访问过的边。

具体而言，禁忌表中的不能访问的边可以包括实验液滴所在的边。实验液滴是数字微流控芯片在正常用于实验时，其上所存在的液滴。而本发明所提到的测试液滴是与实验液滴不同的、用于测试故障的另一个液滴。本发明可以在实验液滴正常进行实验的情况下进行测试，而实验表明，测试液滴和实验液滴之间要有一定的间隔距离，两液滴不能处于直接相邻或对角相邻的阵列单元，否则会导致液滴融合，所以静态约束条件为：对任意时间单位t，d_i(测试液滴)和d_j(实验液滴)需要在水平或竖直方向相距大于一个坐标单元(否则测试液滴可能会于实验液滴融合)：

|x_i^t-x_j^t|＞1且|y_i^t-y_j^t|＞1

同时，d_i在下一时间片的目标位置不能与d_j相邻，为动态约束条件，用数学公式表示为：

|x_i^t+1-x_j^t|＞1且|y_i^t+1-y_j^t|＞1

这意味着，由于实验液滴的存在，故障在线检测问题存在动态静态约束。

步骤三：构建至少一个粒子群，为每个粒子群构建与其对应的位置矩阵，所述位置矩阵的行数表示粒子群算法中的粒子总数；所述位置矩阵的列数表示相邻电极阵列间形成边的总数；所述位置矩阵中的元素表示特定的粒子在特定电极阵列处的速度向量；所述速度向量为下一时刻每个粒子所在的边的序号。

具体而言，将粒子群算法应用到故障测试问题的核心思想为：每个粒子从起始位置开始，依次按照算法流程产生下一刻所在边的位置，并形成运动序列。设定算法参数：算法最大迭代次数gen_max，速度参数rand₁、rand₂和rand₃和粒子数目a。初始化迭代次数，粒子群算法需要产生初始粒子群的位置。在本发明中，为了提高检测效率，缩短检测时间，改进粒子群算法，可以同时产生多个群体，同时进行搜索。

例如在产生两个群体A和B时，设测试液滴从边“1”开始测试，则按照总边数和粒子总数分别产生群体A和群体B粒子初始位置向量。位置矩阵用来记录每个粒子进行搜索时走过的边的顺序排列，速度向量表示下一时刻粒子的位置。粒子群规模保证了算法的有效性，粒子群规模大，更容易蕴藏最优解，寻找最优路径时迭代次数少，但每次迭代所需时间更长。

步骤四：确定粒子群算法中每个粒子的速度向量，直至所有边均被遍历；所述速度向量具体通过如下方式的随机一种确定：

A、选择随机的一个允许选择的边Speed1。

B、选择离当前位置距离最近的一条边Speed2。

C、选择上一次迭代得到的最短路径序列中与当前时刻位置相邻的Speed3。

具体而言，本发明将粒子下一时刻所处的位置，即粒子所在边的序号定义为速度向量。这里使用贪婪算法和粒子群算法相结合的方法选择粒子速度向量，此处的速度向量是由上述的A、B、C三种方法中随机选择的。可以通过调节A、B、C的概率所占比例来得到最优的参数。

下面以图5的微流控芯片为例，说明确定速度向量的方法：

设前次迭代形成的完整粒子最短最优路径为：Gbest＝(1，5，7，3，8，2，6，4，12，9，10、11)

共有3个粒子，本次路径搜索进行到第五个时刻，形成的运动序列为；

对于粒子1，随机产生没有走过的新的位置Speed₁＝8。通过图可以看出，离上一时刻所在位置“10”最近的边为“12、7、5”，这里随机选择Speed₂＝12。观察最优路径，“10”位置之后为“11”，且粒子1在本次搜寻中还没有走过“11”，则Speed₃＝11。

设3部分速度分量所占的影响分别为20％、50％、30％。则设定参数rand₁＝0.2、rand₂＝0.7、rand₃＝0.1，产生0到1之间的随机数p，若p<rand₁，选择Speed＝Speed₁为下一时刻位置；若rand₁<p<rand₂，选择Speed＝Speed₂为下一时刻位置；rand₂<p<rand₃，选择Speed＝Speed₃为下一时刻位置。

设随机数p＝0.5627，则Speed＝12，位置矩阵变为：

按照此方法，对每个粒子每一时刻的位置进行更新。

步骤五：根据公式更新粒子的位置序列，其中X^t＝(1,x¹,x²,...,x^t,0,...)，x^t为第t时刻粒子的位置，V^t＝(0,0,0,...,x^t+1,0,...)，x^t+1＝Speed。

具体而言，由上面的介绍可知，数字微流控在线测试是类TSP问题，属于离散化问题。用前述的粒子群算法求解该问题需要对基本PSO算法中粒子的位置、速度编码及操作符进行重新定义。粒子的位置是走过的边的序列，速度定义为该粒子下一时刻的位置，第t时刻某粒子的位置序列为X^t＝(1,x¹,x²,...,x^t,0,...)，V^t＝(0,0,0,...,x^t+1,0,...)，此处x^t+1＝Speed(见步骤四)，定义位置更新公式为：

即X^t+1＝(1,x¹,x²,...,x^t,x^t+1,0,...)。

步骤六：计算每个粒子的位置向量的适应度，并分别确定每个粒子群当前最短路径Pbestⁱ以及全局最短路径Gbest；适应度用于表示生成的边的有序序列所对应的路径的长度。

步骤七：重复迭代步骤三至步骤六，直至达到预定的迭代次数gen_max，输出全局最短路径Gbest。

具体实施方式二：本实施方式与具体实施方式一不同的是：

步骤四中，速度向量Speed具体通过方式A确定的比率为20％，通过方式B确定的比率为50％，通过方式C确定的比率为30％。

前面提到了可以通过调节A、B、C三种方式的比率的方式调节出最佳参数，本实施方式中提供的比率即为一组优选的比率。

其它步骤及参数与具体实施方式一相同。

具体实施方式三：本实施方式与具体实施方式一或二不同的是：

数字微流控芯片上还具有实验液滴，所述实验液滴与所述测试液滴满足如下条件：

|x_i^t-x_j^t|＞1且|y_i^t-y_j^t|＞1

|x_i^t+1-x_j^t|＞1且|y_i^t+1-y_j^t|＞1

其中，x_i^t表示测试液滴在t时刻的横坐标，y_i^t表示测试液滴在t时刻的纵坐标，x_j^t表示实验液滴在t时刻的横坐标，y_j^t表示实验液滴在t时刻的纵坐标，x_i^t+1表示测试液滴在t+1时刻的横坐标，y_i^t+1表示测试液滴在t+1时刻的纵坐标。

即前述的，为了保证实验液滴与测试液滴不融合，而需要满足的静态约束以及动态约束条件。

其它步骤及参数与具体实施方式一或二相同。

具体实施方式四：本实施方式与具体实施方式一至三之一不同的是：

步骤四的方式A中，“允许选择的边”为不在禁忌表中的任意边。这样设置的好处是，可以尽可能避免测试液滴与实验液滴的融合，减少测试失败的几率。

其它步骤及参数与具体实施方式一至三之一相同。

具体实施方式五：本实施方式提供一种基于改进粒子群算法的数字微流控芯片故障检测系统，包括：至少一个储液池，用于产生实验液滴和/或测试液滴；废液池，用于回收经过微流控芯片后的实验液滴；微流控芯片微流控芯片上与储液池连接的电极作为起始电极，与废液池连接的电极作为终点电极；主控单元，用于根据如具体实施方式一至四中任意一项所述的方法产生全局最短路径，并通过控制微流控芯片的电极控制实验液滴沿着全局最短路径移动。

本实施方式的有益效果是，提供了一种将前述的数字微流控芯片在线测试方法进行具体应用的硬件结构。

具体实施方式六：本实施方式与具体实施方式五不同的是：

微流控芯片的电极阵列为n×n个，系统还包括：

分别设置在微流控芯片的两条相邻边外侧的第一红外发光管组以及第二红外发光管组，第一红外发光管组以及第二红外发光管组均包含n个与电极对应的红外发光管；以及分别设置在微流控芯片的另外两条相邻边外侧的第一红外接收管组以及第二红外接收管组，第一红外发光管组以及第二红外发光管组均包含n个与电极对应的红外发光管，用于接收第一红外发光管组以及第二红外发光管组发射出的红外光；主控单元用于根据未接收到红外光的第二红外接收管的序号确定发生故障的电极的位置。

具体而言，数字微流控生物芯片的永久性故障主要会导致系统的液滴无法移动，因此可根据测试液滴移动预购判断是否存在故障，即测试液滴从储液池触发，在电极阵列单元移动，在终点端检测实验液滴是否到达。如果遇到故障单元，则液滴会卡在该阵列单元上，无法到达终点。因此本实施方式的有益效果在于，可以利用红外发光管和接收管对故障位置进行定位，在数字微流控芯片左端和下端安装红外发光管，右端和上端对应的电极安装红外接收管。这样可以使得故障的定位快速而又准确。

故障检测完成后，数字微流控芯片上会有实验液滴和检测液滴，实验液滴会随着实验的进行继续移动，故障位置的检测液滴则固定在该位置，使红外发光管由实验液滴的驱动电压同步触发，发出光线，接收管没有输出的则为有液滴的位置。假设芯片上共有n个液滴，则n个液滴都移动后，接收管始终没有输出的行和列即为故障位置。

其它步骤及参数与具体实施方式五相同。

本发明还可有其它多种实施例，在不背离本发明精神及其实质的情况下，本领域技术人员当可根据本发明作出各种相应的改变和变形，但这些相应的改变和变形都应属于本发明所附的权利要求的保护范围。