基于云计算模型的ART算法改进及其应用.doc

基于云计算模型的ART算法改进及其应用李传涛 王海英 中国地质大学（北京）地球物理与信息工程学院，北京，100083 中国地质大学（北京）数理学院，北京，100083摘要 本文基于云计算模型理论，利用正态云的多条定性关联规则生成器进行控制，改进ART算法，有效提高计算速度及解的精度。计算实例证明该改进方法的有效性，可获得满意结果。关键词 ART算法；云计算；数学模型地球物理反演问题常常归结为线性方程组的求解，尤其病态线性方程组。设线性方程组 (1)其中系数矩阵为非奇异矩阵，、为维向量。若系数矩阵和发生微小变化，引发方程组（1）的解的巨大变化，则称此方程组为病态方程组。“微小变化”系相对而言，并无数量上的标准。由于病态线性方程组的条件数较大，输入数据发生微小扰动或计算过程中的舍入误差均可能引起输入数据的很大扰动，即解具有较强的不稳定性，从而，求解病态线性方程组非常困难。病态线性方程组，尤其大规模病态线性方程组的数值求解问题一直是数值计算领域的研究热点。人们一直探寻病态线性方程组的有效方法，如条件预优法、迭代校正法、投影法、递推法、刚性常微分方程法，但是均在算法简便性、有效性并不理想。鉴于此，本文尝试ART算法求解病态线性方程组。运用ART（Algebraic Reconstruction Technique）算法进行求解，不仅节省计算机内存、运算速度快以及计算结果较准确，而且其原理简单，使用十分灵活方便，效果较好。从而，ART算法越来越受到国内外地球物理学和应用数学界的重视。一、ART算法的原理代数重建法（Algebraic Reconstruction Technique，ART）是1970年首先由Gordon、Bender和Herman 首先公开提出，主要解决图像重建问题。运用ART算法进行求解上述大型的稀疏的线性方程组，不仅节省计算机内存、运算速度快以及计算结果较准确，而且其原理简单，使用十分灵活方便，效果较好。从而，ART算法越来越受到国内外地球物理学和应用数学界的重视。ART算法最先由Housfied应用在放射性医学的断面成像中，取得巨大成功。在放射医学的断面成像中，射线源和检测器都被置于被测人体的某一个平面上（如图1所示）。图1 断面成像原理图设射线的入射强度为，出射强度为，被测区域内的衰减函数为，建立投影值等式 （1）其中射线投影值。所谓图像重建就是根据不同方向的大量投影值反演被测平面内部衰减函数的分布。Housfield将被测区域划分成若干规则小矩形块，视每个小矩形块内的函数为常数，即网格化方法。从而，由上述（1）式得 （2）其中为第条射线的投影值，为第块小矩形内的衰减值（待求），为第块小矩形对条射线投影值（线线积分）的贡献，。记，投影值向量。从而，（2）式的矩阵形式为 （3）从而，（2）式本质上为一个线性方程组。由于网格分块较细，射线较多，而且每一条射线所穿过的块数均小于，从而，上述的众多，从而，（3）式中的系数矩阵为大型的稀疏矩阵。二、 ART的基本思想及其求解步骤给定重建区域的一个初值，一般为0；再将所有投射值残差一个个沿其射线方向均匀地反投射回去，不断地对图像进行校正，直到满足所求，这就是ART算法的基本思想。求解该线性方程的ART算法步骤如下。Step1. 赋初始值，一般取零；给出收敛条件和进行循环计算次数。对全部的投影值都进行一次运算，称为一次循环计算。Step2. 对迭代次数 （1）其中；为第条射线的投影价；为第块内的衰减值（待求）；为第个像素对条射投影值（线线积分）的贡献；为阻尼因子。Step3. 收敛条件。设方差标准 ，其中。选定判定指标证书，当 时，停止迭代计算；否则，转（2）。ART算法是在的基础上算出，最终得到满意结果，故它是逐次逼近的迭代算法。当经过一个循环计算后（），称为一次全迭代。在每个迭代步的计算中，只用到了一条射线的信息，即只用稀疏矩阵的一行元素，无论其它行元素的值是否已存在均对当前迭代步没有影响，从而，对于现生成型线性方程组采用ART算法求解将大幅度节省计算机内存。 例如，对行的迭代计算，只需将算出的第行元素的参加运算；对行的迭代计算，也只需用到行元素的值。因此，在整个迭代计算中，只需对未知向量提供内存空间，而不需存入整个系数矩阵，易于计算机运行。三、云模型原理云模型（Cloud Model）是一种较新的定性定量不确定性转换模型，它将模糊数学和概率论有机结合，采用泛正态分布表示自然语言概念，较好地表现自然语言的模糊性和随机性，为不确定性问题的研究和知识的表达提供了新方法。设是一个用精确值表示的普通集合，称为论域。是上对应的定性概念，对任意，均存在一个具有稳定倾向的随机数，称为对概念的确定度或隶属度，在论域上的分布称为云模型，简称云。云模型的数字特征分别为期望、熵和超熵，它们共同反映定性概念整体上的定量特征。期望是云滴在论域空间分布上的期望值，反映相应定性概念的信息中心值，也是该概念值量化最典型的样本；熵反映定性概念的亦此亦彼性的度量，它决定在论域中可被定性概念所接受的元素个数，即模糊度，即反映模糊性和随机性，也必然揭示两者之间的相关性；超熵是熵的熵，是熵的不确定性的度量，其大小间接反映云的厚度。定性概念到论域空间的一次映射形成一个云滴，即一次具体量化，众多云滴形成云。云滴的形成过程具有不确定性，云模型给出云滴对概念的确定度。云滴越多，形成的云雾越充分，越能反映定性概念的整体特征（见图2）。图2为云模型表示“坐标轴零值附近”云模型通过两次正态随机生成云滴，奠定云推理、云聚类、云运算和云控制等基础。云模型是定性知识和定量数据的转换模型，包含两层含义，一是将定性的知识转化为定理的数据表示，即通过数字特征值生成云滴的过程，称之为正向云发生器；反之，通过定量的数据表示产生定性概念的过程，即通过云滴的分布得到云模型的数字特征的过程，称之为逆向云发生器。正态云是最常用的一种云模型，具有普遍的适用性。设是定性概念的一次随机实现，若，而且对的确定度或隶属度满足，则在论域上的分布称为正态云。将云模型的三个数字特征转换为大量均匀、微小的云滴的过程称为正向正态云发生器，实现定性概念到定量数据的映射，具有良好的概念-数据转换能力（见图3）。 图3 正向正态云发生器示意图将由大量微小、均匀的云滴组成的云状体转换为自然语言描述的概念过程称为逆向正态云发生器，具有良好的数据-概念转化能力和简单的表达形式（见图4）。 图4 逆向正态云发生器示意图对照语言原子与云的关系，运用云对象构造云模型的定性关联规则。单条定性关联规则可形式化描述为If then 其中和为语言值表示的对象。多条定性关联规则也可类似定义。显然，该推理系统均对不确定性具有良好的继承性与传递性。三、基于云模型的蚁群算法改进影响ART算法的速度和精度的关键因素在于阻尼因子，该因子对于加快、提高计算精度和压制噪声起着极其重要的作用。实践与理论证明，当时，虽然迭代式（1）收敛，但是，若阻尼因子太小，无限接近0，迭代速度加快，易产生循环，陷入局部最优解；若阻尼因子太大，无限接近2，迭代速度加慢，也易产生停滞与循环。从而，可限制在，其中、的值与算法规模、循环次数等有关。运用云模型理论， 针对阻尼因子因素进行调整，运用多定性关联规则如下。规则1 若且，则选取；规则2 若、且，则选取较大的；规则3 若且，则选取；规则3 若且，则选取. 上述关联规则可用云模型的多规则生成器完成，其中以调整前的阻尼因子为输入参数来实现多规则生成器的U条件云，而以调整后的阻尼因子云来实现多规则生成器的V条件云。从而，这种多规则生成器使得随机过程和阻尼因子的优化设置有机地结合在一起。上述规则的倾向性、云模型的随机性保证了能够获得全局最优解。 四、基于云计算模型理论的ART改进算法的应用：病态线性方程组的求解在地球物理的反演过程中，常遇到大型的稀疏的病态线性方程组的求解问题。基于云计算模型理论的ART的改进算法采用直接对该方程组进行求解而不需要先转化为正则方程；若方程组是相容的，它最终可得到精确解。举例求解如下。设由Hilbert系数矩阵构成的严重病态线性方程组 （4）其中，。显然，该方程组的精确解为 Hilbert系数矩阵构成的严重病态线性方程组(4)是一个现生成型线性方程组，其系数矩阵具有一定规律，采用ART算法进行求解不需要将其系数矩阵求出存入计算机内存里，只需在每次迭代中临时求出相应的行参加计算，这样节省内存、加快运算速度。为了方便与其它方法进行比较，选择，计算结果如下。线性方程组的解准确解1.00001.00001.00001.00001.00001.00001.00001.00001.0000列主元法0.99991.00500.90731.7059-1.72166.7819-5.85835.2553-7.5496全主元法0.99381.0800-0.22548.7184-23.503843.4828-39.513320.7425-2.7788LU分解法1.00030.99520.95631.7684-2.78869.9980-10.33618.2950-0.8889Householder法0.99831.1157-0.977015.2214-51.4975108.7700-123.3476.40-17.690SVD法0.99991.0080.9850.9951.0071.0121.0090.9990.984一般ART算法1.00200.99480.98911.00451.01511.01581.00780.9934 0.9748基于云模型的ART的改进算法1.00090.99980.99911.00011.00011.01001.00680.9989 0.9988上述表格数据表明：除了ART算法和SVD（奇异值分解）算法以外，其它方法对（4）式的求解均失效（）；与标准解进行比较，基于云计算模型的ART的改进算法解病态方程组可以得较满意结果，并且易于操作，灵活实用。致谢本文由中国国家专项项目“深部探测技术实验与集成”（SinoProbe-02)”、国家自然科学基金（40874067）、教育部高等学校博士点基金（20070491520）资助、中国地质大学（北京）研究生教改项目支持与资助。参考文献 1R. Gordon, Bender and G. T. Herman. Algebraic Reconstruction Techniques (ART) for Three-Dimensional Electronmicroscopy and X-Ray Photography, J. Theor. Biol. Vol.29, 1970. 2 R. Gordon, “A Tutorial on ART, IEEE Trans”. Nucl. Science, Vol. NS-21, 1974. 3G. T. Herman, Image reconstruction from projections: the fundamentals of computerized temography, Science press, 19854 C. Y. Ma, S. L. Yang, S. P. Li, A Regularization Method of Ill-Conditioned Linear Equations, Journal of Gansu Sciences, 2010，22(4)：33-35.5 Li Dengyi ea al. Study on the universality of the normal cloud modelJ, Engineering Science, 2004, 6(8): 28-34. The Improvement of the ART AlgorithmBased onCloud Model Chuantao LiSchool of Geophysics and Information TechnologyChina University of Geosciences (Beijing), Beijing, ChinaHaiying WangSchool of Information Engineering, China University of Geosciences (Beijing), Beijing, ChinaAbstract In this paper, we use some qualitativeassociation rule generators of the normal cloudtocontrol the proceeding, and i