魯子鵬孫鳳云蘇 昂劉 劍

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

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

用于生化檢測的微孔板上有幾十甚至幾百個(gè)微孔檢測位點(diǎn)，如圖1(a)所示。 但是在實(shí)際應(yīng)用中往往只有部分微孔是放有樣本的有效檢測位點(diǎn)，如圖1(b)所示(●為假設(shè)有效檢測位點(diǎn))。 在此情況下，如果逐一檢測每個(gè)微孔位點(diǎn)，檢測效率必然很低，浪費(fèi)大量的時(shí)間。 除此之外，過長時(shí)間的檢測過程還會導(dǎo)致檢測誤差的增大。 因?yàn)樯磻?yīng)產(chǎn)生的光學(xué)信號往往隨時(shí)間動(dòng)態(tài)衰減，檢測過程花費(fèi)的時(shí)間越多，則檢測后面有效位點(diǎn)時(shí)帶來的誤差越大。因此，根據(jù)有效檢測位點(diǎn)的位置合理規(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ī)劃。 以枚舉法為例，枚舉法的實(shí)現(xiàn)過程是將探針移動(dòng)的所有路徑找到然后比較路徑長度，選取長度最短的路徑作為最優(yōu)路徑。 整個(gè)計(jì)算過程較為繁瑣，只適合路徑數(shù)量較少的路徑選擇問題。 而蟻群算法、混沌算法等算法也因?yàn)橛?jì)算量大、過程復(fù)雜等缺點(diǎn)無法用于微孔板的最優(yōu)路徑規(guī)劃問題。

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

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

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

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

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

②無后效性分析:這七個(gè)中間過程存在遞進(jìn)關(guān)系，相互之間并不獨(dú)立，但每一個(gè)狀態(tài)的最優(yōu)解只與上一狀態(tài)的解有關(guān)，與實(shí)現(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策問題滿足動(dòng)態(tài)規(guī)劃最優(yōu)化原理，具有最優(yōu)子結(jié)構(gòu)、無后效性。 因此，可用動(dòng)態(tài)規(guī)劃法來解決問題。

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

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

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

圖3 A03→B05 代表的探針移動(dòng)路徑

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

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

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

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

②狀態(tài)決策

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)果與分析

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

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

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

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

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

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

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

圖6 探針的順序檢測軌跡

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

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

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

表2 三種檢測路線對比表

4 結(jié)束語

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