生化發(fā)光分析儀最優(yōu)檢測路徑的動態(tài)規(guī)劃算法研究*

魯子鵬孫鳳云蘇 昂劉 劍

(山東大學控制科學與工程學院生物醫(yī)學工程研究所，山東 濟南 250061)

生化發(fā)光分析儀是一種集成光學、電子學和生物化學等多學科門類的綜合性測量儀器[1]，其檢測結(jié)果是臨床醫(yī)生診斷疾病的重要依據(jù)。 近年來，在市場需求和科技發(fā)展的雙重驅(qū)動下，國產(chǎn)生化分析儀得到快速發(fā)展。 然而與國外進口設(shè)備相比，國產(chǎn)儀器仍普遍存在自建檢測系統(tǒng)性能難以保障，檢測精度不高，用戶體驗差等問題，其中復雜的檢測過程是造成這些缺陷的重要原因[2]。

用于生化檢測的微孔板上有幾十甚至幾百個微孔檢測位點，如圖1(a)所示。 但是在實際應(yīng)用中往往只有部分微孔是放有樣本的有效檢測位點，如圖1(b)所示(●為假設(shè)有效檢測位點)。 在此情況下，如果逐一檢測每個微孔位點，檢測效率必然很低，浪費大量的時間。 除此之外，過長時間的檢測過程還會導致檢測誤差的增大。 因為生化反應(yīng)產(chǎn)生的光學信號往往隨時間動態(tài)衰減，檢測過程花費的時間越多，則檢測后面有效位點時帶來的誤差越大。因此，根據(jù)有效檢測位點的位置合理規(guī)劃一條檢測線路對于提高生化分析儀檢測效率、減少檢測誤差具有重要意義。

圖1 生化發(fā)光分析儀96 孔微孔板和微孔板平面圖

最優(yōu)檢測線路的選擇過程就是路徑規(guī)劃求最優(yōu)解的過程，路徑規(guī)劃分為全局規(guī)劃和局部規(guī)劃[3]，本文檢測路線選擇符合全局路徑規(guī)劃適用條件。 目前常用于路徑規(guī)劃的算法有枚舉法[4]，蟻群算法[5]，混沌優(yōu)化算法[6]，F(xiàn)loyd 算法[7]，遺傳算法[8-9]等。 但這些算法并不適合生化分析儀微孔檢測的最優(yōu)路徑規(guī)劃。 以枚舉法為例，枚舉法的實現(xiàn)過程是將探針移動的所有路徑找到然后比較路徑長度，選取長度最短的路徑作為最優(yōu)路徑。 整個計算過程較為繁瑣，只適合路徑數(shù)量較少的路徑選擇問題。 而蟻群算法、混沌算法等算法也因為計算量大、過程復雜等缺點無法用于微孔板的最優(yōu)路徑規(guī)劃問題。

除了上述的幾種算法外，還有一種專門用于多階段決策問題的算法——動態(tài)規(guī)劃法[10]。 動態(tài)規(guī)劃法由美國數(shù)學家貝爾曼(Bellman R E)等人基于最優(yōu)化原理[11]提出，通過拆分問題，定義狀態(tài)之間的關(guān)系，將多階段決策轉(zhuǎn)換成一系列中間狀態(tài)的決策問題[12]。 相比于其他算法，動態(tài)規(guī)劃法的優(yōu)勢在于運算過程簡單且重復運算量少。 在求解過程中，每個中間狀態(tài)只求解一次，并且前一中間狀態(tài)的解將為下一中間狀態(tài)求解提供線索，通過求解過程的層層遞進，最終獲取系統(tǒng)最優(yōu)解。 因為動態(tài)規(guī)劃法的求解過程只依賴相鄰中間狀態(tài)的解，不必進行大量重復運算，所以得到了廣泛應(yīng)用。

本文首先對動態(tài)規(guī)劃法的兩個適用條件進行解析，然后基于微孔板的自身特性，建立適用于生化分析儀檢測過程的最優(yōu)路徑規(guī)劃數(shù)學模型，并定義了移動路徑的中間狀態(tài)以及狀態(tài)之間的增益取值的計算方式，最終利用狀態(tài)遞歸方程求得生化分析儀探針移動的最優(yōu)路徑。

1 多孔矩陣檢測路徑動態(tài)規(guī)劃適應(yīng)性解析

動態(tài)規(guī)劃法的實現(xiàn)需要兩個基本條件，本文結(jié)合圖1(b)對這兩個基本條件進行分析。

①最優(yōu)化分析:生化分析儀探針移動方向為從A 行到H 行，將包含有效檢測位點的每一行的檢測過程看作一個中間狀態(tài)。 則對圖1(b)中微孔板的總體檢測過程可以拆分為7 個狀態(tài)，為S1，S2，…，S7，分別對應(yīng)A 行，B 行，C 行，E 行，F(xiàn) 行，G 行以及H 行的檢測，如圖2 所示。 通過計算，篩選，保留可能達到總體最優(yōu)解的中間狀態(tài)解，并根據(jù)各中間狀態(tài)的關(guān)系依次獲取解，最終中間狀態(tài)得到的解就是總體最優(yōu)解。

②無后效性分析:這七個中間過程存在遞進關(guān)系，相互之間并不獨立，但每一個狀態(tài)的最優(yōu)解只與上一狀態(tài)的解有關(guān)，與實現(xiàn)上一狀態(tài)解的過程無關(guān)[13]。 具體來說，生化分析儀的探針檢測完第x行(x取值為A-H 行中任一行)的最優(yōu)路程只與檢測完x-1 行后所選擇的路徑有關(guān)，與x-1 行之前選擇的路徑無關(guān)。

通過分析可知，生化分析儀的探針最優(yōu)路徑?jīng)Q策問題滿足動態(tài)規(guī)劃最優(yōu)化原理，具有最優(yōu)子結(jié)構(gòu)、無后效性。 因此，可用動態(tài)規(guī)劃法來解決問題。

2 多孔矩陣檢測路徑動態(tài)規(guī)劃建模與求解

本文基于動態(tài)規(guī)劃法和微孔板的自身特性建立了路徑規(guī)劃模型，模型由七個中間狀態(tài)組成，每個中間狀態(tài)(如S1)下具有多個解(由●表示)，如圖2所示。 線徑則表示兩個相鄰中間狀態(tài)的轉(zhuǎn)移關(guān)系，以A03→B05 為例，表示以A03 為起點，檢測完B 行的所有有效位點后最終停在B05 位點所需要的最短路徑，A03→B05 對應(yīng)的探針移動路徑如圖3 所示。 由圖可知，該路徑長度為11。

圖2 探針檢測路徑規(guī)劃模型

圖3 A03→B05 代表的探針移動路徑

模型建立的具體過程如下。

①劃分中間狀態(tài)并求解

中間狀態(tài)的劃分是為了簡化多階段決策問題的計算過程，中間狀態(tài)的選取既要能描述過程的演變，也要滿足無后效性[14]。 每個中間狀態(tài)往往有多個解，但每個解在整體決策過程中只求一次，結(jié)果會被保存下來，需要時直接調(diào)用而不必再重新計算。 該過程可以減少重復計算，并且中間狀態(tài)越多，效果越明顯。

中間狀態(tài)的求解順序并不是唯一的，既可以將S1 當作首個中間狀態(tài)，也可以將S7 當作首個中間狀態(tài)，即順序標號和逆序標號，這兩種標號方式的結(jié)果是唯一確定的[15]，并不影響最終結(jié)果，本文選用順序標號進行標記。

②狀態(tài)決策

計算完當前中間狀態(tài)的所有解后，就要進行狀態(tài)決策，即根據(jù)當前狀態(tài)的所有解與下一狀態(tài)之間的增益選擇兩個狀態(tài)間最合適的移動路徑。 其中狀態(tài)增益是指當前狀態(tài)轉(zhuǎn)移到下一狀態(tài)所需要的距離，當前狀態(tài)下每一個解都有其對應(yīng)的狀態(tài)增益。

③建立狀態(tài)遞歸方程并求最優(yōu)解

利用中間狀態(tài)的遞歸關(guān)系，求系統(tǒng)最優(yōu)解的過程總共有七個步驟:

步驟1 考慮第一個中間過程:從START 開始，到檢測完A 行所有有效位點整個過程一共有2 個解。即探針具有兩條可選路徑，路徑長度分別為9 和6，分別對應(yīng)START→A03，START→A06 兩條路徑。

步驟2 考慮前兩個中間過程:第一階段、第二階段走完第A，B 行所有有效位點并停留在B 行任意一個有效檢測位點這整個過程一共有3 條路徑，即三個解，分別用S1，S2，S3來表示，每個解都由第一個中間過程的解以及他們對應(yīng)的狀態(tài)增益決定。

通過比較三個解的值可以發(fā)現(xiàn)，S1的值最小，所以S1為前兩個中間過程的最優(yōu)解。 對應(yīng)的探針路徑為START→A06→B02，路徑長度為15。

步驟3 考慮前三個中間過程:與步驟2 類似，求兩個解S4，S5:

通過比較兩個解的值可以發(fā)現(xiàn)，S5為前三個中間過程的最優(yōu)解，對應(yīng)的路徑為START→A06→B02→C11，路徑長度為25。

步驟4 考慮前四個中間過程:與上述步驟類似，求得兩個解S6，S7的值分別為34，35。 通過比較得出前四個中間過程的最優(yōu)解對應(yīng)的路徑為START→A06→B02→C11→E04，路徑長度為34。

步驟5 考慮前五個中間過程:與上述步驟類似，求得兩個解S8，S9的值分別為43，42，得出前五個中間狀態(tài)的最優(yōu)解對應(yīng)的路徑為START→A06→B02→C11→E04→F07，路徑長度為42。

步驟6 考慮前六個中間過程:與上述步驟類似，求得最終解S10，S11，S12的值分別為55，59，54，得出前六個中間過程的最優(yōu)解54，對應(yīng)的路徑為START→A06→B02→C11→E04→F02→G10，路徑長度為54。

步驟7 考慮前七個中間過程:與上述步驟類似，求得最終解S13，S14的值分別為62，63，得到前七個中間過程，也是整體過程的最優(yōu)解為62。

3 結(jié)果與分析

根據(jù)上述計算結(jié)果，從生化分析儀探針的起始位置開始檢測完所有有效位點并最終停留在微孔板H行有效位點所需的最短路徑長度為62，對應(yīng)的路徑有三條。 其中一條為START→A06→B05→C11→E04→F02→G10→H03，如圖4 所示。 另外，圖5 展示了生化發(fā)光分析儀微孔板的有效檢測位點的平面位置，以最優(yōu)路徑START→A06→B05→C11→E04→F02→G10→H03 對應(yīng)的探針具體行進軌跡。

圖4 最優(yōu)路徑規(guī)劃模型

圖5 探針的最優(yōu)路徑行進軌跡

為了對比說明動態(tài)規(guī)劃法對于路徑規(guī)劃問題計算量的簡化，本文將動態(tài)規(guī)劃法與枚舉法的計算量進行了對比，如表1 所示。 枚舉法需要將所有可能的線路找到并比較其長度，從而求得最短路徑[16]，在計算路徑長度的時候，勢必會重復計算各個中間過程，造成計算量的浪費。 根據(jù)比較結(jié)果，對于圖1(b)中所示的有效位點檢測路徑規(guī)劃，枚舉法需要進行2 016次加法運算，遠大于動態(tài)規(guī)劃法的32 次加法運算。由此可以看出動態(tài)規(guī)劃算法對于運算量的大幅簡化。

表1 動態(tài)規(guī)劃法與枚舉法計算量對比表

為了進一步驗證生化發(fā)光分析儀最優(yōu)檢測路徑動態(tài)規(guī)劃算法的性能，本文選取探針的順序檢測路線和“之字形”檢測路線作為對照組，分別計算他們的檢測路線所需要的路徑長度和檢測時長，并與動態(tài)規(guī)劃法的最優(yōu)路徑作對比，以此來證明動態(tài)規(guī)劃法得到最優(yōu)檢測路線對于檢測效率的提高。

探針的順序檢測路線是指探針從起點出發(fā)，對包含有效檢測位點的有效檢測行進行從A 行→H行的順序檢測，對有效檢測行內(nèi)的檢測位點進行從左到右的順序檢測，檢測路線如圖6 所示。 以前兩個有效檢測行為例進行說明:A 行中包含A03，A06這兩個有效檢測位點，B 行中包含B02，B05，B08 這三個有效檢測位點，則探針在前兩個有效檢測行的檢測軌跡為A03→A06→B02 →B05 →B08。

圖6 探針的順序檢測軌跡

探針的“之字形”檢測路線是指探針按照從A 行→H 行的順序進行檢測，對檢測行內(nèi)的有效檢測位點采用順序逆序交替的方法進行檢測，探針的具體移動軌跡如圖7 所示。 以前兩個有效檢測行為例進行說明:A 行中包含A03，A06 這兩個有效檢測位點，采用順序檢測法，檢測順序為A03→A06；B 行中包含B02，B05，B08 這三個有效檢測位點，采用逆序檢測法，檢測順序為B08→B05→B03。 所以探針在前兩個有效檢測行的檢測軌跡為A03→A06→B08→B05→B03。

圖7 探針的“之字形”檢測軌跡

表2 對比了三種探針檢測路線的路徑長度和檢測時長。 從表2 中可以清晰地看出動態(tài)規(guī)劃法的最優(yōu)路徑長度最短，為62 步；順序檢測法得出的檢測路徑最長，為81 步。 相比于順序檢測法，動態(tài)規(guī)劃法的檢測效率提高了23.46%，縮短了約18 s 的檢測時間。 相比于探針的“之字形”檢測路徑，動態(tài)規(guī)劃法的最優(yōu)路徑檢測效率提高了1.59%，縮短了約1 s的檢測時間。 從這三種探針檢測路線的對比中可以得到最優(yōu)檢測路徑的動態(tài)規(guī)劃算法能夠提高檢測效率，減小檢測時間。

表2 三種檢測路線對比表

4 結(jié)束語

動態(tài)規(guī)劃法著眼全局，在逐一得到各個階段最優(yōu)解的情況下確定全局最優(yōu)解，是一種解決復雜動態(tài)系統(tǒng)最優(yōu)控制的有效工具。 本文首先介紹動態(tài)規(guī)劃法基本思想，解析了利用其優(yōu)化多孔矩陣檢測路徑的最優(yōu)化和無后效性條件，建立多孔矩陣檢測路徑規(guī)劃數(shù)學模型，并給出了最優(yōu)路徑的詳細求解過程。 與枚舉法相比，動態(tài)規(guī)劃法在變量較多時可顯著降低計算量，通過快速篩選最優(yōu)路徑縮短檢測時間，減小信號衰減帶來的誤差，提高分析儀的檢測效率和準確性。