电磁场逆问题的蒙特卡罗法读书报告1.电磁场中的逆问题概述1.1 引言电磁学中的正问题的一般提法是：已知某一空间 （或介质） 中的源和媒质的 分布，求该空间的电磁场分布 对应逆问题的提法为： 已知某一空间的电磁场分 布( 有时甚至是其不完全的分布形式) ，求产生这种现象的源或媒质的分布我 们说，实际应用中， 更多碰到的都是电磁逆问题的形式，而且其中大都是与电磁 信号反演相关的问题， 本质上也可以归结为一个统计信号处理问题或图像处理问 题但是这些问题的背景均来自电磁学，所以它们都有其自身的特殊性1.2 逆问题特点电磁场中的逆问题从应用的角度主要可以分为两大类，一类是参数识辨问题， 另一类是优化设计问题， 其中优化设计问题又称为综合问题这两类逆问题的求 解对象可以完全一样， 但在对解的存在性和唯一性的要求上有明显的区别在优 化设计问题中是否存在满足要求的设计方案是首要问题，而参数辨识问题从物理 意义上讲解总是客观存在的，但由于模型和数据的误差又使得存在性无法保证 另一方面，参数辨识问题强调的是得到与客观实际吻合的唯一解，而优化设计问 题显然容许多种可行的设计方案2.蒙特卡罗法简介2.1 蒙特卡罗反演的发展在求解逆问题的任何一个阶段使用随机（或伪随机） 生成元的方法称为蒙特 卡罗反演方法。
使用MCI 方法能够求解相当大规模的、多参数、任意复杂形式 的完全非线性反演问题， 且不做任何线性化近似 MCI 既可以解决线性反演问题， 也能用来解决非线性反演问题， 既能用来解决单参数反演问题， 又能用来解决多 参数反演问题；既可以用于一种数据的反演，也可以用于多种数据的联合反演； 适应能力相当强，而且计算方便、灵活，概念清楚、简单因此，MCI受到人们 的极大重视 KeilisBorok和 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）l ∈ lmin,lmax此时，l 是可以变化的数，其变化的依据是被禁对象的 目标函数值和领域的结构lmin、lmax是确定的数，确定的常用方法是根据问题的规模 N，限定变化区间a N,b N (0 < ?? < ?? )；也可以用领域中邻居的个数n确定变化区间a n,b n (0 < ??< ?? )禁忌长度的选取同实际问题和算法设计者的经验有紧密联系，同时它也会影 响计算的复杂性，过短会造成循环的出现，过长又会造成计算时间的增加 3.候选集合的确定 候选集合由领域中的邻居组成， 常规的方法是从领域中选择若干个目标函数 值或评价值最佳的邻居 由于上述常规方法的计算量太大，一般不在领域的所有邻居中选择，而是在 领域中的一部分邻居中选择若干个目标值或评价值最佳的解；也可以采用随机选 取的方法实现部分邻居的选取 4.终止准则 利用禁忌搜索算法求解无时限单向配送车辆优化调度问题时，算法的终止准 则可采用迭代一定步数终止的准则、频率控制准则、 目标值变化控制等准则 除 以上准则外， 还可以采用下述的目标值偏离程度终止准则：记一个问题目标函数 值的下界为 ZLB，目标值为 f(x)，对给定的充分小的正数e，当f x - ZLB≤e时， 终止计算，这表示目前计算得到的解与最优解已经非常接近。
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 准则: 若 Δt′ <0 则接受 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这个初始的群 体也就是问题假设解的集合一般取n＝30-160。
通常以随机方法产生串或个体的集合bi,i＝1，2，...n问题的最优解将通过 这些初始假设解进化而求出 2．选择 根据适者生存原则选择下一代的个体在选择时， 以适应度为选择原则 适 应度准则体现了适者生存，不适应者淘汰的自然法则 给出目标函数 f，则 f(bi)称为个体 bi 的适应度以 为选中 bi 为下一代个体的次数 显然．从式 (3—86)可知： (1)适应度较高的个体，繁殖下一代的数目较多 (2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰 这样，就产生了对环境适应能力较强的后代对于问题求解角度来讲， 就是选择出和最优解较接近的中间解 3．交叉 对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉 概率 P在选中的位置实行交换这个过程反映了随机信息交换；目的在于产生 新的基因组合，也即产生新的个体交叉时，可实行单点交叉或多点交叉 4．变异 根据生物遗传中基因变异的原理，以变异概率 Pm 对某些个体的某些位执行 变异在变异时，对执行变异的串的对应位求反，即把1 变为 0，把 0 变为 1 变异概率 Pm与生物变异极小的情况一致， 所以， Pm的取值较小，一般取 0.01-0.2。
5．全局最优收敛 (Convergence to the global optimum)。