MREIT中的微分进化单纯形混合算法

荆会敏，闫丹丹

中国计量大学信息工程学院，浙江杭州 310018； *通讯作者 闫丹丹 dandanyan@cjlu.edu.cn

基于微分进化（Differential evolution，DE）算法的磁共振电阻抗（magnetic resonance electrical impedance tomography，MREIT）图像重建存在着后期寻优效率不高、“早熟”收敛等问题。为解决这一问题，本研究在肺部MREIT图像重建仿真实验中尝试将实现简单、计算量小、局部搜索能力强的单纯形法和具有二次变异的修改的微分进化算法相结合，组成新的混合算法，以提高图像重建算法的收敛速度和精度。

1 原理与方法

1.1 数学模型 给定物体内电导率的分布与边界条件，求物体内磁感应强度分布和电压分布称为MREIT的正问题。正问题的数学模型描述为公式（1）、（2）[1]：

其中，V(r)为导体内电势分布；σ(r)为导体内的电导率；Ω为所要成像的物体；n为方向向量。由电势分布V(r)利用公式（3）、（4）可得电场强度E和电流密度J：

导体内的磁感应强度分布可通过毕奥萨伐尔定理求得公式（5）：

其中，r和r′分别为Ω内的测量点矢量和源点矢量；μ0为真空磁导率；B(r)为测量点的磁感应强度；J(r′)为产生磁感应强度点的电流密度分布；V′为导体体积。

MREIT的逆问题为给定物体内电流密度分布或磁感应强度分布，求解物体内电阻率分布。经过有限元法后，MREIT的逆问题可转换为如下求解目标函数最小值的问题，根据算法的特点，目标函数可以设定为公式（6）：

其中，(·)T表示转置；表示测量得到的磁感应强度； Bz表示计算得到的磁感应强度。

MREIT的研究主要分为以上2个部分，即正问题求解和逆问题重构。目前常用的求解方式均采取有限元分析求解正问题，采用迭代方法求解逆问题。

微分进化算法作为一种典型的迭代方法求解逆问题的基本思路是在全局范围内直接搜索目标函数的最优解。算法首先在一定范围内生成一定数量的随机变量作为初始种群，然后通过特定的规则方法对种群个体进行变异、交叉和选择，保留目标函数评价值较低的个体到下一代种群，使所有种群个体向着最优值移动，最终达到最优值或最优值附近。

1.2 修改的微分进化算法 基本微分进化算法是一种全局启发式的种群进化算法。该算法实现简单、性能稳定、需要调整的参数较少，在多种应用中均表现出良好的性能[2]。

根据基本DE的原理，随着迭代次数的增加，优质个体会被保留，种群会朝向一个方向移动，个体之间的差异会逐渐减小，可能导致种群个体发生“聚集”，陷入局部最小点，从而可能出现“早熟“现象。本文采用一种修改的DE算法，引入二次变异算子，在种群可能出现聚集早熟现象时使种群内部分个体发生二次变异以提升种群多样性，缓解聚集早熟问题。为了描述种群的状态信息，首先给出以下目标函数方差的定义[3]。

其中，f 为归一化因子，用来限制 δ2的大小，本文中f取值为：

目标函数方差 δ2反映出种群中个体的聚集程度。δ2较小时，表明种群个体目标函数评价接近，其他个体聚集在最优个体的周围，种群多样性较低，不利于算法的全局寻优。因此，本文中改进的DE算法将在δ2低于某一设定的阈值时对最优个体及部分其他个体进行二次变异。本研究采用随机扰动的方式进行二次变异：

其中，d 表示个体的第d 维取值，α取[0,1]区间之间的随机值。

1.3 改进的单纯形法（simplex method，SM） SM由Spendley等于1962年提出的一种求解函数最小化问题的优化方法。此后，Nelder和Mead于1965年在前者的基础上提出了一种不需要对目标函数求导数，根据函数值即可完成优化过程的非线性单纯形搜索方法（Nelder-mead，NM）[4]。该方法广泛用于多维非线性无约束优化问题。本文采用的单纯性法即为后者这种无约束优化问题搜索方法。随后，Nelder又提出“改进的单纯形法”，在基本单纯形搜索方法的基础上添加了“扩张”和“压缩”2个步骤，进一步提升了单纯形搜索方法的搜索性能。

NM的基本思想是首先按某种规则产生一个初始的单纯形，然后从这个初始单纯形开始，按照一定的移动准则不断产生新的单纯形，使得单纯形不断向最优值移动直至到达最优值。单纯形法计算量小，收敛速度快，不要求目标函数可导，局部搜索能力强。然而，NM对初始参数比较敏感，容易陷入局部最小点，是一种典型的局部搜索方法。

1.4 微分进化单纯形混合算法（DE-NM）和步骤 为使DE算法在后期具有更高的搜索效率和寻优精度，引入NM到DE算法中组成一种混合优化算法。混合算法的基本思想是在一定范围内产生一个具有NP个个体，每个个体为一个D维向量的初始种群，从初始种群开始，进行变异、交叉、选择等一系列操作，并计算目标函数方差，判断是否进行二次变异，然后选择种群中前 D+1个最优个体组成初始单纯形，利用NM进行局部寻优，达到一定条件后返回的个体加入下一代种群中，直到目标函数低于一定阈值或达到最大进化代数时终止。

DE-NM 的具体步骤如下：①种群初始化。在一定范围内随机产生一个具有NP个个体，每个个体为一个D维向量的初始种群xi,G,i=1,2…NP，其中i表示种群个体编号，G表示种群进化代数。②计算每个个体的目标函数值，求出最优目标函数以及最优个体，判断最优目标函数是否满足精度要求或是否达到最大进化代数。若是则退出循环；反之，进行下一步。③变异和交叉操作。对第G代种群中的每个目标向量xi,G,一种常见的基本变异策略方程为：

其中，r1≠r2≠r3≠i，r1，r2，r3∈[1，NP]，F 称作缩放因子，一定程度上决定了种群的进化方向。交叉是将公式（10）得到的变异向量 vi,G+1和当前目标向量xi,G按某种准则得到实验向量ui,G+1，交叉操作方程见公式（11）：

其中，i=1，2，…，NP，j=1，2，…，D，randb(j)是（0，1）之间的随机数，rnbr(i)是[1，D]之间的随机整数，CR是交叉因子。④按公式（7）计算目标函数方差 δ2。⑤若 δ2

其中f(·)表示其目标函数值。⑧继续执行步骤2，直至达到结束条件，算法终止，仿真模型建立。本节将通过MATLAB和ANSYS 10.0等软件对上面提出的混合算法进行验证分析。使用有限元法对肺部进行建模（图1）。其中二维肺部仿真模型由966个单元，1993个节点构成，三维肺部仿真模型由16 004个单元，21 672个节点构成。为简化计算，假设肺部仿真模型为各向同性均质导体，依据先验知识，癌变组织的电导率相较正常组织高1.12～2.00倍。本文采用电导率比值肌肉∶肺部∶病变=1∶6.73∶10[5-8]。病变组织设定于右肺。

图1 肺部模型剖分图

2 结果

在利用DE-NM混合算法进行MREIT图像重建的仿真实验中，将肺部仿真模型的肌肉、肺部、病变组织的上限设定为[1.10，7.40，11.00]，下限设定为[0.9，6.06，9.00]。种群规模NP=30，个体维度D=3，比例因子 F=0.8，交叉因子 Cr=0.9，最大进化代数g=100，阈值VTR（value to reach）为10-6。为了定量评价重建质量，在仿真实验中引入误差总和（total error，TE）准则，定义为公式（13）：

其中，Est代表重构电阻率值，True代表真实电阻率值，m为电阻率值分布的自由度。

使用新的DE-NM混合算法在二维和三维肺部仿真模型进行 MREIT图像重建仿真，结果见图2。其中外部蓝色部分表示肌肉组织，中间绿色部分表示健康肺部组织，内部黄色部分表示病变组织。二维或三维肺部仿真模型实验中，DE-NM 混合算法均可对阻抗图进行有效重建。

图2 阻抗图像重建结果。A、B分别为二维DE-NM重建图、二维DE重建图，C、D分别为三维DE-NM重建图、三维DE重建图

仿真实验的评价进化过程见图3。其中横坐标为评价次数，纵坐标为目标函数值。为便于直观分析，对纵坐标进行对数转换。图中蓝色线代表基本的 DE算法，红色线代表DE-NM算法，由图3可见DE算法在前期具有较好的收敛性能，但由于局部搜索能力差的缺点，后期收敛性能下降，曲线趋于平缓。在引入单纯形搜索方法的DE-NM后大幅度提高了局部搜索性能，使得收敛速度与精度均优于基本的DE算法。

图3 DE-NM算法与DE算法的比较结果。A、B分别为二维肺部模型、三维肺部模型

表1和表2为经过100次试验后DE-NM算法与 DE算法分别在二维和三维上的重建结果。值得注意的是，基于 DE算法的图像重建算法每次进化均需对种群全体成员进行目标函数评价，这一过程占据了大量的时间，尤其是在计算复杂度更高的三维模型中，算法的计算时间较长。从表中可见，改进的算法较基本 DE算法的评价次数大大降低，且误差总和也明显降低，表明基于 DE-NM 的重建算法的重建效率及重建精度均优于基于 DE算法的重建算法。

表1 二维电阻率重建结果

表2 三维电阻率重建结果

3 讨论

MREIT是由电阻抗成像（electrical impedance tomography，EIT）技术与电流密度成像（current density imaging，CDI）技术相结合的新一代成像技术。它可以穿透低电导生物的表层组织获得更多组织内部的信息，通过重建算法重构内部阻抗获得高分辨率的重构图像。MREIT依据生物组织的电导率在发生器质病变之前就有较大变化的原理，可以在心脑血管疾病、恶性肿瘤、癫痫等疾病的早期或潜伏期及时发现病变部位，进而提高治疗成功率[9-10]。

MREIT电阻抗成像问题可以概括为以下2个部分：正问题和逆问题。正问题是根据电磁关系求出生物导体内的磁感应强度；逆问题则利用正问题提供的磁感应强度和测量的磁感应强度通过重建算法重构生物导体内的阻抗分布[11-12]。近年，一些智能寻优算法逐渐引起图像重建算法研究者们的注意，如模拟退火算法、粒子群算法、遗传算法等。这些智能寻优算法和传统的算法相比，对函数是否连续无直接要求，计算简单易于实现、收敛速度快，多基于智能寻优算法的图像重建算法而被提出[13-15]。在这些智能寻优算法中，微分进化算法作为一种计算复杂度低且易于实现的全局寻优算法，仅2项参数需要调整，在电阻抗图像重建中广泛应用[16]。然而，微分进化算法也存在一些自身固有的缺点。随着迭代次数的增加，寻优效率开始下降，收敛较慢，后期搜索精度不高，还可能出现“早熟”收敛的问题。鉴于目前基于微分进化算法的MREIT图像重建算法的缺点，本文将单纯形法和具有二次变异的修改的微分进化算法进行结合，发挥各自算法的优点，肺部仿真实验结果显示新提出的算法提高了图像重建的收敛速度和精度。

总之，本文提出了一种新的用于MREIT图像重建的微分进化单纯形混合算法。由于传统DE算法每次均需对所有种群个体进行目标函数评价，又存在后期搜索效率不高、可能发生种群聚集现象等缺点，导致DE算法应用于MREIT图像重建时存在计算时间较长的问题。为加快算法的收敛速度同时获得高精度的重建图像，本研究通过引入单纯形寻优方法到修改的DE算法中，保证了DE算法种群多样性的同时，加快了算法的后期搜索速度和搜索精度。仿真结果表明，改进算法能够获得较为清晰的电阻抗重建图像，且能对病变组织进行准确定位。同时，与基本DE算法相比，改进算法的图像重建误差和收敛速度均有明显的提升，有效提高了算法的整体性能，为MREIT临床研究提供了一定的参考。本文中讨论的混合算法仅在肺部仿真模型上进行了验证试验，现实中的情况更为复杂，下一步的工作若能在真实肺部模型上验证算法的有效性将具有重要的实际意义。