生化发光分析仪最优检测路径的动态规划算法研究*

鲁子鹏孙凤云苏 昂刘 剑

(山东大学控制科学与工程学院生物医学工程研究所，山东 济南 250061)

生化发光分析仪是一种集成光学、电子学和生物化学等多学科门类的综合性测量仪器[1]，其检测结果是临床医生诊断疾病的重要依据。 近年来，在市场需求和科技发展的双重驱动下，国产生化分析仪得到快速发展。 然而与国外进口设备相比，国产仪器仍普遍存在自建检测系统性能难以保障，检测精度不高，用户体验差等问题，其中复杂的检测过程是造成这些缺陷的重要原因[2]。

用于生化检测的微孔板上有几十甚至几百个微孔检测位点，如图1(a)所示。 但是在实际应用中往往只有部分微孔是放有样本的有效检测位点，如图1(b)所示(●为假设有效检测位点)。 在此情况下，如果逐一检测每个微孔位点，检测效率必然很低，浪费大量的时间。 除此之外，过长时间的检测过程还会导致检测误差的增大。 因为生化反应产生的光学信号往往随时间动态衰减，检测过程花费的时间越多，则检测后面有效位点时带来的误差越大。因此，根据有效检测位点的位置合理规划一条检测线路对于提高生化分析仪检测效率、减少检测误差具有重要意义。

图1 生化发光分析仪96 孔微孔板和微孔板平面图

最优检测线路的选择过程就是路径规划求最优解的过程，路径规划分为全局规划和局部规划[3]，本文检测路线选择符合全局路径规划适用条件。 目前常用于路径规划的算法有枚举法[4]，蚁群算法[5]，混沌优化算法[6]，Floyd 算法[7]，遗传算法[8-9]等。 但这些算法并不适合生化分析仪微孔检测的最优路径规划。 以枚举法为例，枚举法的实现过程是将探针移动的所有路径找到然后比较路径长度，选取长度最短的路径作为最优路径。 整个计算过程较为繁琐，只适合路径数量较少的路径选择问题。 而蚁群算法、混沌算法等算法也因为计算量大、过程复杂等缺点无法用于微孔板的最优路径规划问题。

除了上述的几种算法外，还有一种专门用于多阶段决策问题的算法——动态规划法[10]。 动态规划法由美国数学家贝尔曼(Bellman R E)等人基于最优化原理[11]提出，通过拆分问题，定义状态之间的关系，将多阶段决策转换成一系列中间状态的决策问题[12]。 相比于其他算法，动态规划法的优势在于运算过程简单且重复运算量少。 在求解过程中，每个中间状态只求解一次，并且前一中间状态的解将为下一中间状态求解提供线索，通过求解过程的层层递进，最终获取系统最优解。 因为动态规划法的求解过程只依赖相邻中间状态的解，不必进行大量重复运算，所以得到了广泛应用。

本文首先对动态规划法的两个适用条件进行解析，然后基于微孔板的自身特性，建立适用于生化分析仪检测过程的最优路径规划数学模型，并定义了移动路径的中间状态以及状态之间的增益取值的计算方式，最终利用状态递归方程求得生化分析仪探针移动的最优路径。

1 多孔矩阵检测路径动态规划适应性解析

动态规划法的实现需要两个基本条件，本文结合图1(b)对这两个基本条件进行分析。

①最优化分析:生化分析仪探针移动方向为从A 行到H 行，将包含有效检测位点的每一行的检测过程看作一个中间状态。 则对图1(b)中微孔板的总体检测过程可以拆分为7 个状态，为S1，S2，…，S7，分别对应A 行，B 行，C 行，E 行，F 行，G 行以及H 行的检测，如图2 所示。 通过计算，筛选，保留可能达到总体最优解的中间状态解，并根据各中间状态的关系依次获取解，最终中间状态得到的解就是总体最优解。

②无后效性分析:这七个中间过程存在递进关系，相互之间并不独立，但每一个状态的最优解只与上一状态的解有关，与实现上一状态解的过程无关[13]。 具体来说，生化分析仪的探针检测完第x行(x取值为A-H 行中任一行)的最优路程只与检测完x-1 行后所选择的路径有关，与x-1 行之前选择的路径无关。

通过分析可知，生化分析仪的探针最优路径决策问题满足动态规划最优化原理，具有最优子结构、无后效性。 因此，可用动态规划法来解决问题。

2 多孔矩阵检测路径动态规划建模与求解

本文基于动态规划法和微孔板的自身特性建立了路径规划模型，模型由七个中间状态组成，每个中间状态(如S1)下具有多个解(由●表示)，如图2所示。 线径则表示两个相邻中间状态的转移关系，以A03→B05 为例，表示以A03 为起点，检测完B 行的所有有效位点后最终停在B05 位点所需要的最短路径，A03→B05 对应的探针移动路径如图3 所示。 由图可知，该路径长度为11。

图2 探针检测路径规划模型

图3 A03→B05 代表的探针移动路径

模型建立的具体过程如下。

①划分中间状态并求解

中间状态的划分是为了简化多阶段决策问题的计算过程，中间状态的选取既要能描述过程的演变，也要满足无后效性[14]。 每个中间状态往往有多个解，但每个解在整体决策过程中只求一次，结果会被保存下来，需要时直接调用而不必再重新计算。 该过程可以减少重复计算，并且中间状态越多，效果越明显。

中间状态的求解顺序并不是唯一的，既可以将S1 当作首个中间状态，也可以将S7 当作首个中间状态，即顺序标号和逆序标号，这两种标号方式的结果是唯一确定的[15]，并不影响最终结果，本文选用顺序标号进行标记。

②状态决策

计算完当前中间状态的所有解后，就要进行状态决策，即根据当前状态的所有解与下一状态之间的增益选择两个状态间最合适的移动路径。 其中状态增益是指当前状态转移到下一状态所需要的距离，当前状态下每一个解都有其对应的状态增益。

③建立状态递归方程并求最优解

利用中间状态的递归关系，求系统最优解的过程总共有七个步骤:

步骤1 考虑第一个中间过程:从START 开始，到检测完A 行所有有效位点整个过程一共有2 个解。即探针具有两条可选路径，路径长度分别为9 和6，分别对应START→A03，START→A06 两条路径。

步骤2 考虑前两个中间过程:第一阶段、第二阶段走完第A，B 行所有有效位点并停留在B 行任意一个有效检测位点这整个过程一共有3 条路径，即三个解，分别用S1，S2，S3来表示，每个解都由第一个中间过程的解以及他们对应的状态增益决定。

通过比较三个解的值可以发现，S1的值最小，所以S1为前两个中间过程的最优解。 对应的探针路径为START→A06→B02，路径长度为15。

步骤3 考虑前三个中间过程:与步骤2 类似，求两个解S4，S5:

通过比较两个解的值可以发现，S5为前三个中间过程的最优解，对应的路径为START→A06→B02→C11，路径长度为25。

步骤4 考虑前四个中间过程:与上述步骤类似，求得两个解S6，S7的值分别为34，35。 通过比较得出前四个中间过程的最优解对应的路径为START→A06→B02→C11→E04，路径长度为34。

步骤5 考虑前五个中间过程:与上述步骤类似，求得两个解S8，S9的值分别为43，42，得出前五个中间状态的最优解对应的路径为START→A06→B02→C11→E04→F07，路径长度为42。

步骤6 考虑前六个中间过程:与上述步骤类似，求得最终解S10，S11，S12的值分别为55，59，54，得出前六个中间过程的最优解54，对应的路径为START→A06→B02→C11→E04→F02→G10，路径长度为54。

步骤7 考虑前七个中间过程:与上述步骤类似，求得最终解S13，S14的值分别为62，63，得到前七个中间过程，也是整体过程的最优解为62。

3 结果与分析

根据上述计算结果，从生化分析仪探针的起始位置开始检测完所有有效位点并最终停留在微孔板H行有效位点所需的最短路径长度为62，对应的路径有三条。 其中一条为START→A06→B05→C11→E04→F02→G10→H03，如图4 所示。 另外，图5 展示了生化发光分析仪微孔板的有效检测位点的平面位置，以最优路径START→A06→B05→C11→E04→F02→G10→H03 对应的探针具体行进轨迹。

图4 最优路径规划模型

图5 探针的最优路径行进轨迹

为了对比说明动态规划法对于路径规划问题计算量的简化，本文将动态规划法与枚举法的计算量进行了对比，如表1 所示。 枚举法需要将所有可能的线路找到并比较其长度，从而求得最短路径[16]，在计算路径长度的时候，势必会重复计算各个中间过程，造成计算量的浪费。 根据比较结果，对于图1(b)中所示的有效位点检测路径规划，枚举法需要进行2 016次加法运算，远大于动态规划法的32 次加法运算。由此可以看出动态规划算法对于运算量的大幅简化。

表1 动态规划法与枚举法计算量对比表

为了进一步验证生化发光分析仪最优检测路径动态规划算法的性能，本文选取探针的顺序检测路线和“之字形”检测路线作为对照组，分别计算他们的检测路线所需要的路径长度和检测时长，并与动态规划法的最优路径作对比，以此来证明动态规划法得到最优检测路线对于检测效率的提高。

探针的顺序检测路线是指探针从起点出发，对包含有效检测位点的有效检测行进行从A 行→H行的顺序检测，对有效检测行内的检测位点进行从左到右的顺序检测，检测路线如图6 所示。 以前两个有效检测行为例进行说明:A 行中包含A03，A06这两个有效检测位点，B 行中包含B02，B05，B08 这三个有效检测位点，则探针在前两个有效检测行的检测轨迹为A03→A06→B02 →B05 →B08。

图6 探针的顺序检测轨迹

探针的“之字形”检测路线是指探针按照从A 行→H 行的顺序进行检测，对检测行内的有效检测位点采用顺序逆序交替的方法进行检测，探针的具体移动轨迹如图7 所示。 以前两个有效检测行为例进行说明:A 行中包含A03，A06 这两个有效检测位点，采用顺序检测法，检测顺序为A03→A06；B 行中包含B02，B05，B08 这三个有效检测位点，采用逆序检测法，检测顺序为B08→B05→B03。 所以探针在前两个有效检测行的检测轨迹为A03→A06→B08→B05→B03。

图7 探针的“之字形”检测轨迹

表2 对比了三种探针检测路线的路径长度和检测时长。 从表2 中可以清晰地看出动态规划法的最优路径长度最短，为62 步；顺序检测法得出的检测路径最长，为81 步。 相比于顺序检测法，动态规划法的检测效率提高了23.46%，缩短了约18 s 的检测时间。 相比于探针的“之字形”检测路径，动态规划法的最优路径检测效率提高了1.59%，缩短了约1 s的检测时间。 从这三种探针检测路线的对比中可以得到最优检测路径的动态规划算法能够提高检测效率，减小检测时间。

表2 三种检测路线对比表

4 结束语

动态规划法着眼全局，在逐一得到各个阶段最优解的情况下确定全局最优解，是一种解决复杂动态系统最优控制的有效工具。 本文首先介绍动态规划法基本思想，解析了利用其优化多孔矩阵检测路径的最优化和无后效性条件，建立多孔矩阵检测路径规划数学模型，并给出了最优路径的详细求解过程。 与枚举法相比，动态规划法在变量较多时可显著降低计算量，通过快速筛选最优路径缩短检测时间，减小信号衰减带来的误差，提高分析仪的检测效率和准确性。