MREIT中的微分進(jìn)化單純形混合算法

荊會(huì)敏，閆丹丹

中國計(jì)量大學(xué)信息工程學(xué)院，浙江杭州 310018； *通訊作者 閆丹丹 dandanyan@cjlu.edu.cn

基于微分進(jìn)化（Differential evolution，DE）算法的磁共振電阻抗（magnetic resonance electrical impedance tomography，MREIT）圖像重建存在著后期尋優(yōu)效率不高、“早熟”收斂等問題。為解決這一問題，本研究在肺部MREIT圖像重建仿真實(shí)驗(yàn)中嘗試將實(shí)現(xiàn)簡單、計(jì)算量小、局部搜索能力強(qiáng)的單純形法和具有二次變異的修改的微分進(jìn)化算法相結(jié)合，組成新的混合算法，以提高圖像重建算法的收斂速度和精度。

1 原理與方法

1.1 數(shù)學(xué)模型 給定物體內(nèi)電導(dǎo)率的分布與邊界條件，求物體內(nèi)磁感應(yīng)強(qiáng)度分布和電壓分布稱為MREIT的正問題。正問題的數(shù)學(xué)模型描述為公式（1）、（2）[1]：

其中，V(r)為導(dǎo)體內(nèi)電勢分布；σ(r)為導(dǎo)體內(nèi)的電導(dǎo)率；Ω為所要成像的物體；n為方向向量。由電勢分布V(r)利用公式（3）、（4）可得電場強(qiáng)度E和電流密度J：

導(dǎo)體內(nèi)的磁感應(yīng)強(qiáng)度分布可通過畢奧薩伐爾定理求得公式（5）：

其中，r和r′分別為Ω內(nèi)的測量點(diǎn)矢量和源點(diǎn)矢量；μ0為真空磁導(dǎo)率；B(r)為測量點(diǎn)的磁感應(yīng)強(qiáng)度；J(r′)為產(chǎn)生磁感應(yīng)強(qiáng)度點(diǎn)的電流密度分布；V′為導(dǎo)體體積。

MREIT的逆問題為給定物體內(nèi)電流密度分布或磁感應(yīng)強(qiáng)度分布，求解物體內(nèi)電阻率分布。經(jīng)過有限元法后，MREIT的逆問題可轉(zhuǎn)換為如下求解目標(biāo)函數(shù)最小值的問題，根據(jù)算法的特點(diǎn)，目標(biāo)函數(shù)可以設(shè)定為公式（6）：

其中，(·)T表示轉(zhuǎn)置；表示測量得到的磁感應(yīng)強(qiáng)度； Bz表示計(jì)算得到的磁感應(yīng)強(qiáng)度。

MREIT的研究主要分為以上2個(gè)部分，即正問題求解和逆問題重構(gòu)。目前常用的求解方式均采取有限元分析求解正問題，采用迭代方法求解逆問題。

微分進(jìn)化算法作為一種典型的迭代方法求解逆問題的基本思路是在全局范圍內(nèi)直接搜索目標(biāo)函數(shù)的最優(yōu)解。算法首先在一定范圍內(nèi)生成一定數(shù)量的隨機(jī)變量作為初始種群，然后通過特定的規(guī)則方法對(duì)種群個(gè)體進(jìn)行變異、交叉和選擇，保留目標(biāo)函數(shù)評(píng)價(jià)值較低的個(gè)體到下一代種群，使所有種群個(gè)體向著最優(yōu)值移動(dòng)，最終達(dá)到最優(yōu)值或最優(yōu)值附近。

1.2 修改的微分進(jìn)化算法 基本微分進(jìn)化算法是一種全局啟發(fā)式的種群進(jìn)化算法。該算法實(shí)現(xiàn)簡單、性能穩(wěn)定、需要調(diào)整的參數(shù)較少，在多種應(yīng)用中均表現(xiàn)出良好的性能[2]。

根據(jù)基本DE的原理，隨著迭代次數(shù)的增加，優(yōu)質(zhì)個(gè)體會(huì)被保留，種群會(huì)朝向一個(gè)方向移動(dòng)，個(gè)體之間的差異會(huì)逐漸減小，可能導(dǎo)致種群個(gè)體發(fā)生“聚集”，陷入局部最小點(diǎn)，從而可能出現(xiàn)“早熟“現(xiàn)象。本文采用一種修改的DE算法，引入二次變異算子，在種群可能出現(xiàn)聚集早熟現(xiàn)象時(shí)使種群內(nèi)部分個(gè)體發(fā)生二次變異以提升種群多樣性，緩解聚集早熟問題。為了描述種群的狀態(tài)信息，首先給出以下目標(biāo)函數(shù)方差的定義[3]。

其中，f 為歸一化因子，用來限制 δ2的大小，本文中f取值為：

目標(biāo)函數(shù)方差 δ2反映出種群中個(gè)體的聚集程度。δ2較小時(shí)，表明種群個(gè)體目標(biāo)函數(shù)評(píng)價(jià)接近，其他個(gè)體聚集在最優(yōu)個(gè)體的周圍，種群多樣性較低，不利于算法的全局尋優(yōu)。因此，本文中改進(jìn)的DE算法將在δ2低于某一設(shè)定的閾值時(shí)對(duì)最優(yōu)個(gè)體及部分其他個(gè)體進(jìn)行二次變異。本研究采用隨機(jī)擾動(dòng)的方式進(jìn)行二次變異：

其中，d 表示個(gè)體的第d 維取值，α取[0,1]區(qū)間之間的隨機(jī)值。

1.3 改進(jìn)的單純形法（simplex method，SM） SM由Spendley等于1962年提出的一種求解函數(shù)最小化問題的優(yōu)化方法。此后，Nelder和Mead于1965年在前者的基礎(chǔ)上提出了一種不需要對(duì)目標(biāo)函數(shù)求導(dǎo)數(shù)，根據(jù)函數(shù)值即可完成優(yōu)化過程的非線性單純形搜索方法（Nelder-mead，NM）[4]。該方法廣泛用于多維非線性無約束優(yōu)化問題。本文采用的單純性法即為后者這種無約束優(yōu)化問題搜索方法。隨后，Nelder又提出“改進(jìn)的單純形法”，在基本單純形搜索方法的基礎(chǔ)上添加了“擴(kuò)張”和“壓縮”2個(gè)步驟，進(jìn)一步提升了單純形搜索方法的搜索性能。

NM的基本思想是首先按某種規(guī)則產(chǎn)生一個(gè)初始的單純形，然后從這個(gè)初始單純形開始，按照一定的移動(dòng)準(zhǔn)則不斷產(chǎn)生新的單純形，使得單純形不斷向最優(yōu)值移動(dòng)直至到達(dá)最優(yōu)值。單純形法計(jì)算量小，收斂速度快，不要求目標(biāo)函數(shù)可導(dǎo)，局部搜索能力強(qiáng)。然而，NM對(duì)初始參數(shù)比較敏感，容易陷入局部最小點(diǎn)，是一種典型的局部搜索方法。

1.4 微分進(jìn)化單純形混合算法（DE-NM）和步驟 為使DE算法在后期具有更高的搜索效率和尋優(yōu)精度，引入NM到DE算法中組成一種混合優(yōu)化算法?；旌纤惴ǖ幕舅枷胧窃谝欢ǚ秶鷥?nèi)產(chǎn)生一個(gè)具有NP個(gè)個(gè)體，每個(gè)個(gè)體為一個(gè)D維向量的初始種群，從初始種群開始，進(jìn)行變異、交叉、選擇等一系列操作，并計(jì)算目標(biāo)函數(shù)方差，判斷是否進(jìn)行二次變異，然后選擇種群中前 D+1個(gè)最優(yōu)個(gè)體組成初始單純形，利用NM進(jìn)行局部尋優(yōu)，達(dá)到一定條件后返回的個(gè)體加入下一代種群中，直到目標(biāo)函數(shù)低于一定閾值或達(dá)到最大進(jìn)化代數(shù)時(shí)終止。

DE-NM 的具體步驟如下：①種群初始化。在一定范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)具有NP個(gè)個(gè)體，每個(gè)個(gè)體為一個(gè)D維向量的初始種群xi,G,i=1,2…NP，其中i表示種群個(gè)體編號(hào)，G表示種群進(jìn)化代數(shù)。②計(jì)算每個(gè)個(gè)體的目標(biāo)函數(shù)值，求出最優(yōu)目標(biāo)函數(shù)以及最優(yōu)個(gè)體，判斷最優(yōu)目標(biāo)函數(shù)是否滿足精度要求或是否達(dá)到最大進(jìn)化代數(shù)。若是則退出循環(huán)；反之，進(jìn)行下一步。③變異和交叉操作。對(duì)第G代種群中的每個(gè)目標(biāo)向量xi,G,一種常見的基本變異策略方程為：

其中，r1≠r2≠r3≠i，r1，r2，r3∈[1，NP]，F(xiàn) 稱作縮放因子，一定程度上決定了種群的進(jìn)化方向。交叉是將公式（10）得到的變異向量 vi,G+1和當(dāng)前目標(biāo)向量xi,G按某種準(zhǔn)則得到實(shí)驗(yàn)向量ui,G+1，交叉操作方程見公式（11）：

其中，i=1，2，…，NP，j=1，2，…，D，randb(j)是（0，1）之間的隨機(jī)數(shù)，rnbr(i)是[1，D]之間的隨機(jī)整數(shù)，CR是交叉因子。④按公式（7）計(jì)算目標(biāo)函數(shù)方差 δ2。⑤若 δ2

其中f(·)表示其目標(biāo)函數(shù)值。⑧繼續(xù)執(zhí)行步驟2，直至達(dá)到結(jié)束條件，算法終止，仿真模型建立。本節(jié)將通過MATLAB和ANSYS 10.0等軟件對(duì)上面提出的混合算法進(jìn)行驗(yàn)證分析。使用有限元法對(duì)肺部進(jìn)行建模（圖1）。其中二維肺部仿真模型由966個(gè)單元，1993個(gè)節(jié)點(diǎn)構(gòu)成，三維肺部仿真模型由16 004個(gè)單元，21 672個(gè)節(jié)點(diǎn)構(gòu)成。為簡化計(jì)算，假設(shè)肺部仿真模型為各向同性均質(zhì)導(dǎo)體，依據(jù)先驗(yàn)知識(shí)，癌變組織的電導(dǎo)率相較正常組織高1.12～2.00倍。本文采用電導(dǎo)率比值肌肉∶肺部∶病變=1∶6.73∶10[5-8]。病變組織設(shè)定于右肺。

圖1 肺部模型剖分圖

2 結(jié)果

在利用DE-NM混合算法進(jìn)行MREIT圖像重建的仿真實(shí)驗(yàn)中，將肺部仿真模型的肌肉、肺部、病變組織的上限設(shè)定為[1.10，7.40，11.00]，下限設(shè)定為[0.9，6.06，9.00]。種群規(guī)模NP=30，個(gè)體維度D=3，比例因子 F=0.8，交叉因子 Cr=0.9，最大進(jìn)化代數(shù)g=100，閾值VTR（value to reach）為10-6。為了定量評(píng)價(jià)重建質(zhì)量，在仿真實(shí)驗(yàn)中引入誤差總和（total error，TE）準(zhǔn)則，定義為公式（13）：

其中，Est代表重構(gòu)電阻率值，True代表真實(shí)電阻率值，m為電阻率值分布的自由度。

使用新的DE-NM混合算法在二維和三維肺部仿真模型進(jìn)行 MREIT圖像重建仿真，結(jié)果見圖2。其中外部藍(lán)色部分表示肌肉組織，中間綠色部分表示健康肺部組織，內(nèi)部黃色部分表示病變組織。二維或三維肺部仿真模型實(shí)驗(yàn)中，DE-NM 混合算法均可對(duì)阻抗圖進(jìn)行有效重建。

圖2 阻抗圖像重建結(jié)果。A、B分別為二維DE-NM重建圖、二維DE重建圖，C、D分別為三維DE-NM重建圖、三維DE重建圖

仿真實(shí)驗(yàn)的評(píng)價(jià)進(jìn)化過程見圖3。其中橫坐標(biāo)為評(píng)價(jià)次數(shù)，縱坐標(biāo)為目標(biāo)函數(shù)值。為便于直觀分析，對(duì)縱坐標(biāo)進(jìn)行對(duì)數(shù)轉(zhuǎn)換。圖中藍(lán)色線代表基本的 DE算法，紅色線代表DE-NM算法，由圖3可見DE算法在前期具有較好的收斂性能，但由于局部搜索能力差的缺點(diǎn)，后期收斂性能下降，曲線趨于平緩。在引入單純形搜索方法的DE-NM后大幅度提高了局部搜索性能，使得收斂速度與精度均優(yōu)于基本的DE算法。

圖3 DE-NM算法與DE算法的比較結(jié)果。A、B分別為二維肺部模型、三維肺部模型

表1和表2為經(jīng)過100次試驗(yàn)后DE-NM算法與 DE算法分別在二維和三維上的重建結(jié)果。值得注意的是，基于 DE算法的圖像重建算法每次進(jìn)化均需對(duì)種群全體成員進(jìn)行目標(biāo)函數(shù)評(píng)價(jià)，這一過程占據(jù)了大量的時(shí)間，尤其是在計(jì)算復(fù)雜度更高的三維模型中，算法的計(jì)算時(shí)間較長。從表中可見，改進(jìn)的算法較基本 DE算法的評(píng)價(jià)次數(shù)大大降低，且誤差總和也明顯降低，表明基于 DE-NM 的重建算法的重建效率及重建精度均優(yōu)于基于 DE算法的重建算法。

表1 二維電阻率重建結(jié)果

表2 三維電阻率重建結(jié)果

3 討論

MREIT是由電阻抗成像（electrical impedance tomography，EIT）技術(shù)與電流密度成像（current density imaging，CDI）技術(shù)相結(jié)合的新一代成像技術(shù)。它可以穿透低電導(dǎo)生物的表層組織獲得更多組織內(nèi)部的信息，通過重建算法重構(gòu)內(nèi)部阻抗獲得高分辨率的重構(gòu)圖像。MREIT依據(jù)生物組織的電導(dǎo)率在發(fā)生器質(zhì)病變之前就有較大變化的原理，可以在心腦血管疾病、惡性腫瘤、癲癇等疾病的早期或潛伏期及時(shí)發(fā)現(xiàn)病變部位，進(jìn)而提高治療成功率[9-10]。

MREIT電阻抗成像問題可以概括為以下2個(gè)部分：正問題和逆問題。正問題是根據(jù)電磁關(guān)系求出生物導(dǎo)體內(nèi)的磁感應(yīng)強(qiáng)度；逆問題則利用正問題提供的磁感應(yīng)強(qiáng)度和測量的磁感應(yīng)強(qiáng)度通過重建算法重構(gòu)生物導(dǎo)體內(nèi)的阻抗分布[11-12]。近年，一些智能尋優(yōu)算法逐漸引起圖像重建算法研究者們的注意，如模擬退火算法、粒子群算法、遺傳算法等。這些智能尋優(yōu)算法和傳統(tǒng)的算法相比，對(duì)函數(shù)是否連續(xù)無直接要求，計(jì)算簡單易于實(shí)現(xiàn)、收斂速度快，多基于智能尋優(yōu)算法的圖像重建算法而被提出[13-15]。在這些智能尋優(yōu)算法中，微分進(jìn)化算法作為一種計(jì)算復(fù)雜度低且易于實(shí)現(xiàn)的全局尋優(yōu)算法，僅2項(xiàng)參數(shù)需要調(diào)整，在電阻抗圖像重建中廣泛應(yīng)用[16]。然而，微分進(jìn)化算法也存在一些自身固有的缺點(diǎn)。隨著迭代次數(shù)的增加，尋優(yōu)效率開始下降，收斂較慢，后期搜索精度不高，還可能出現(xiàn)“早熟”收斂的問題。鑒于目前基于微分進(jìn)化算法的MREIT圖像重建算法的缺點(diǎn)，本文將單純形法和具有二次變異的修改的微分進(jìn)化算法進(jìn)行結(jié)合，發(fā)揮各自算法的優(yōu)點(diǎn)，肺部仿真實(shí)驗(yàn)結(jié)果顯示新提出的算法提高了圖像重建的收斂速度和精度。

總之，本文提出了一種新的用于MREIT圖像重建的微分進(jìn)化單純形混合算法。由于傳統(tǒng)DE算法每次均需對(duì)所有種群個(gè)體進(jìn)行目標(biāo)函數(shù)評(píng)價(jià)，又存在后期搜索效率不高、可能發(fā)生種群聚集現(xiàn)象等缺點(diǎn)，導(dǎo)致DE算法應(yīng)用于MREIT圖像重建時(shí)存在計(jì)算時(shí)間較長的問題。為加快算法的收斂速度同時(shí)獲得高精度的重建圖像，本研究通過引入單純形尋優(yōu)方法到修改的DE算法中，保證了DE算法種群多樣性的同時(shí)，加快了算法的后期搜索速度和搜索精度。仿真結(jié)果表明，改進(jìn)算法能夠獲得較為清晰的電阻抗重建圖像，且能對(duì)病變組織進(jìn)行準(zhǔn)確定位。同時(shí)，與基本DE算法相比，改進(jìn)算法的圖像重建誤差和收斂速度均有明顯的提升，有效提高了算法的整體性能，為MREIT臨床研究提供了一定的參考。本文中討論的混合算法僅在肺部仿真模型上進(jìn)行了驗(yàn)證試驗(yàn)，現(xiàn)實(shí)中的情況更為復(fù)雜，下一步的工作若能在真實(shí)肺部模型上驗(yàn)證算法的有效性將具有重要的實(shí)際意義。