电磁场逆问题的蒙特卡罗法读书报告.docx

电磁场逆问题的蒙特卡罗法读书报告1.电磁场中的逆问题概述 1.1引言电磁学中的正问题的一般提法是：已知某一空间（或介质）中的源和媒质的分布，求该空间的电磁场分布。对应逆问题的提法为：已知某一空间的电磁场分布( 有时甚至是其不完全的分布形式) ，求产生这种现象的源或媒质的分布。我们说，实际应用中，更多碰到的都是电磁逆问题的形式，而且其中大都是与电磁信号反演相关的问题，本质上也可以归结为一个统计信号处理问题或图像处理问题。但是这些问题的背景均来自电磁学，所以它们都有其自身的特殊性。1.2逆问题特点电磁场中的逆问题从应用的角度主要可以分为两大类，一类是参数识辨问题，另一类是优化设计问题，其中优化设计问题又称为综合问题。这两类逆问题的求解对象可以完全一样，但在对解的存在性和唯一性的要求上有明显的区别。在优化设计问题中是否存在满足要求的设计方案是首要问题，而参数辨识问题从物理意义上讲解总是客观存在的，但由于模型和数据的误差又使得存在性无法保证。另一方面，参数辨识问题强调的是得到与客观实际吻合的唯一解，而优化设计问题显然容许多种可行的设计方案。2.蒙特卡罗法简介2.1蒙特卡罗反演的发展在求解逆问题的任何一个阶段使用随机（或伪随机）生成元的方法称为蒙特卡罗反演方法。使用mci方法能够求解相当大规模的、多参数、任意复杂形式的完全非线性反演问题，且不做任何线性化近似。mci既可以解决线性反演问题，也能用来解决非线性反演问题，既能用来解决单参数反演问题，又能用来解决多参数反演问题；既可以用于一种数据的反演，也可以用于多种数据的联合反演；适应能力相当强，而且计算方便、灵活，概念清楚、简单。因此，mci受到人们的极大重视。keilis borok和yanovskaya第一次把mci引入到地球物理学中，在20世纪60年代后期，随着计算机能力的发展，mci在地震学的一些重要问题中变得可行起来。到了20世纪70年代，人们将注意力从mci转向了线性反演和用先验信息解决非唯一性问题。20世纪80年代人们开始致力于完全非线性反演方法研究，完全非线性反演方法不包含任何线性化处理，是解决非线性反演问题的根本方法。柯克帕特里克在1983年首先将模拟退火法用于寻求多变量函数的全局极值。蒙特卡罗法的另一种算法遗传算法，最初是由holland作为人工系统中的适应模型提出的。2.2贝叶斯推断与蒙特卡罗反演贝叶斯提出了一种把一个解的先验信息和新数据的信息结合起来的方法。在这种表述下，逆问题的所有的信息由概率项来表示。在这种表述下，逆问题的所有的信息由概率项来表示。贝叶斯推断可以合理地应用到线性或非线性逆问题中，简而言之，它是把关于解的先验信息和观测数据结合起来，得到解的后验概率密度函数，而后验概率密度函数被认为是逆问题的完全解。在贝叶斯方法中，后验概率密度函数定义在整个解空间。线性反演技术能有效地用来解决后验概率密度函数为高斯分布时的情况。3. 蒙特卡罗法3.1禁忌搜索算法3.1.1禁忌搜索算法的原理禁忌搜索算法是解决组合优化问题的一种优化方法。该算法是局部搜索算法的推广，其特点是采用禁忌技术，即用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来挑出局部最优点。在禁忌搜索算法中，首先按照随机方法产生一个初始解作为当前解，然后在当前解的领域中搜索若干个解，取其中的最优解作为新的当前解。为了避免陷入局部最优解，这种优化方法允许一定的下山操作（使解的质量变差）。另外，为了避免对已搜索过的局部最优解的重复，禁忌搜索算法使用禁忌表记录已搜索的局部最优解的历史信息，这可在一定程度上使搜索过程避开局部极值点，从而开辟新的搜索区域。3.1.2算法要素的设计1.禁忌对象的确定禁忌对象是指禁忌表中被禁的那些变化元素。由于解状态的变化可以分为解的简单变化、解向量分量的变化和目标值变化三种情况，则在确定禁忌对象时也有相对应的三种禁忌情况。一般来说，对解的简单变化进行禁忌比另两种的受禁范围要小，因此可能早能造成计算时间的增加，但其优点是提供了较大的搜索范围。根据配送车辆优化调度问题的特点，可采用对解的简单变化进行禁忌的方法。举例进行说明：当解从x变化到y时，y可能是局部最优解，为了避开局部最优解，禁忌y这一解再度出现，可采用如下禁忌规则：当y的领域中有比它更优的解时，选择更优的解；当y为其领域的局部最优解时，不再选y，而选比y稍差的解。2.禁忌长度的确定禁忌长度是指被禁对象不允许被选取的迭代步数，一般是给被禁忌对象x一个数l（称为禁忌长度），要求x在l步迭代内被禁，在禁忌表中采用tabu(x)=l记忆，每迭代一步，该指标做运算tabu(x)=l-1，直到tabu(x)=0时解禁。关于禁忌长度l的选取，可归纳为以下几种情况。（1）l为常数，可取l=10、l=n（n为领域中邻居的总个数）。这种规则容易在算法中实现。（2）llmin,lmax。此时，l是可以变化的数，其变化的依据是被禁对象的目标函数值和领域的结构。lmin、lmax是确定的数，确定的常用方法是根据问题的规模n，限定变化区间an,bn(0ab)；也可以用领域中邻居的个数n确定变化区间an,bn(0ab)。禁忌长度的选取同实际问题和算法设计者的经验有紧密联系，同时它也会影响计算的复杂性，过短会造成循环的出现，过长又会造成计算时间的增加。3.候选集合的确定候选集合由领域中的邻居组成，常规的方法是从领域中选择若干个目标函数值或评价值最佳的邻居。由于上述常规方法的计算量太大，一般不在领域的所有邻居中选择，而是在领域中的一部分邻居中选择若干个目标值或评价值最佳的解；也可以采用随机选取的方法实现部分邻居的选取。4.终止准则利用禁忌搜索算法求解无时限单向配送车辆优化调度问题时，算法的终止准则可采用迭代一定步数终止的准则、频率控制准则、目标值变化控制等准则。除以上准则外，还可以采用下述的目标值偏离程度终止准则：记一个问题目标函数值的下界为zlb，目标值为f(x)，对给定的充分小的正数e，当fx-zlbe 时，终止计算，这表示目前计算得到的解与最优解已经非常接近。3.2模拟退火算法模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据metropolis准则，粒子在温度t时趋于平衡的概率为e-e/(kt)，其中e为温度t时的内能，e为其改变量，k为boltzmann常数。用固体退火模拟组合优化问题，将内能e模拟为目标函数值f，温度t演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(cooling schedule)控制，包括控制参数的初值t及其衰减因子t、每个t值时的迭代次数l和停止条件s。模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火算法新解的产生和接受可分为如下四个步骤：第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是metropo1is准则: 若t0则接受s作为新的当前解s，否则以概率exp(-t/t)接受s作为新的当前解s。第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。模拟退火算法与初始值无关，算法求得的解与初始解状态s(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。3.3遗传算法3.3.1遗传算法基本概念遗传算法的基本思想是基于darwin进化论和mendel的遗传学说的。darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。3.3.2遗传算法的原理遗传算法ga把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。3.3.3遗传算法的步骤和意义1初始化选择一个群体，即选择一个串或个体的集合bi，i=1，2，.n。这个初始的群体也就是问题假设解的集合。一般取n30-160。通常以随机方法产生串或个体的集合bi,i1，2，.n。问题的最优解将通过这些初始假设解进化而求出。2选择根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。给出目标函数f，则f(bi)称为个体bi的适应度。以为选中bi为下一代个体的次数。显然从式(386)可知：(1)适应度较高的个体，繁殖下一代的数目较多。(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。3交叉对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率p。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。4变异根据生物遗传中基因变异的原理，以变异概率pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率pm与生物变异极小的情况一致，所以，pm的取值较小，一般取0.01-0.2。5全局最优收敛(convergence to the global optimum)当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。3.4人工神经网络3.4.1人工神经网络简介人工神经网络是以工程技术手段模拟人脑神经系统的结构和功能为特征，通过大量的非线性并行处理器来模拟人脑中众多的神经元之间的突触行为，企图在一定程度上实现人脑形象思维、分布式记忆、自学习自组织的功能。大脑是由大量的神经细胞和神经元组成的，每个神经元可以当成是一个小的信息处理单元，这些神经元按照某种方式互相连接起来构成一个复杂的大脑神经网络。人工神经网络方法企图模拟人类的形象直觉思维，通过由大量的简单模拟神经元实现一种非线性网络，用神经网络本身结构表达输入与输出关联知识的隐函数编码，并通过学习或自适应使网络利用非线性映射的思想对信息能够并行处理。3.4.2人工神经网络的特点人工神经网络从数据中挖掘知识的主要特点是：1. 在信息处理机制上，它具有大规模并行模拟处理，网络全局作用， 信息分布存储，存储区和操作区合二为一等特点。2. 神经网络可以通过训练、学习，对输入空间产生一个非线性映射； 也可以自适应地、 自组织地对输入数据产生聚类。3. 神经网络具有较强的鲁棒性和容错能力，它不仅能处理不准确、不完整、不确定信息，而且能够克服网络本身的不精确性，甚至网络具有自身修复缺陷的能力。3.4.3人工神经网络模型根据人脑神经元之间联接的多样性，模拟人脑神经网络的人工神经网络的联接也具有各式各样的结构，但它们大体可以分为两大类，即具有反馈互联的神经网络和无反馈的前向互联神经网络。1.反馈互联网络 这种网络的神经元与神经元之间通过广泛联接，传递、反馈交换信息，网络结构十分复杂，由于网络由输出端反馈到输入端，所以动态特性丰富，存在网络的全局稳定性问题。在广泛互联反馈网络中，有把输入信号分别输入到每一个神经元，每一个神经元的输出反馈到其它所有神经元的输入端，这种结构是全互联反馈网络，典型的代表网络就是hopfield 神经网络40 (hnn，hopfield neural network）。如下图所示： . . 由于该网络是全互联反馈网络，存在输出反馈，需要考虑网络的全局稳定性问题。对于非线性网络，需要定义一个动力系统的lyapunov函数，即能量函数。若能量函数是率减的且为有限值，则网络是全局稳定的。2.前向互联网络 多层感知器这种网络的神经元与神经元之间通过前向联接的，是一种典型的前馈式多层神经网络，每一层有若干个神经元，每一层内的神经元不互相联接，每一个神经元的输出联到下一层的输入。即把输入信号分别送到第一层的每一个输入节点，第一层的每一个节点的输出加权传送到第二层的神经元的输入端，从第二层开始称为隐元层，隐元层的输出通过加权送到下一层的神经元，等等，这种结构是多层网络相联接的，网络没有输出端反馈到输入端的带来的全局稳定性问题。从隐元层到输出层的神经元一般都采用非线性的输入-输出函数，由于多次非线性函数作用，因此，整个网络能够实现任意非线性映射。同样，这种网络在学习过程中，首先定义了一组输出要求的模式（一般是用一个输出神经元输出为1，其它输出为