蒙特卡洛方法

1、1 在任何一个阶段使用随机(或伪随机)生成元的方法，为纪念著名的赌城蒙特卡洛被命名为蒙特卡洛方法。蒙特卡洛方法可以解决许多难以解决的问题。 传统蒙特卡洛搜索方法又可以称为“尝试和误差”方法。它是在计算机中按一定的先验信息给出的先验限制随机地生成大量可供选择的模型，计算其理论数据值；将这些理论数据与实际观测数据进行比较，并对一些先验约束进行检验；若比较和检验符合了某些可接受的标准，则模型被接受，否则被“排斥”并“遗忘”。因此，传统蒙特卡洛搜索方法的主要步骤为：2 (1)选定待求的模型参数并建立起模型参数与观测数据之间的理论关系。 (2)根据搜索问题的实际要求，选定适当的可接受标准。 (3)在计算

2、机中按给定的先验范围随机地生成模型。 (4)用观测数据和可接受的标准来检验生成的模型舍弃“失败者”，保留“成功者”。 (5)回到第(3)步，再随机地生成新的模型，又进行检验。 (6)反复不断地重复上述步骤，直至认为满足，可以结束了为止。3 传统蒙特卡洛搜索方法之所以比穷举法现实，就在于它用随机抽样搜索代替了系统搜索。而能进行这样的代替有一定的理论依据，即概率论中的大数定理。 大数定理说明只要随机抽样的次数n相当多，结果的算术平均值与数学期望接近，而随机事件的频率在它的概率附近摆动。因此只要n足够大，可以用随机抽样搜索代替系统搜索。若要对收敛的程度进行研究，作出各种误差估计，则要用到中心极限定理

3、：4 中心极限定理表明：无论单个随机变量的分布如何，许多独立随机变量之和总是满足高斯分布的。高斯分布由给定的期望值和方差完全确定下来。由此可以判断蒙特卡洛搜索方法的误差。5 用蒙特卡洛搜索方法工作时，需要产生只有各种概率分布的随机变量。最简单相最基本的随机变量是0，1区间，均匀分布的随机变量。这些随机变量的抽样值就称为随机数。真随机数列是不可预计的，因而也不可能重复产生。这种随机数列只能用某些随机物理过程产生。但这样作存在许多困难，无法满足我们在数字计算机上进行蒙特卡洛搜索的需要。实际应用中的随机数都是在计算机中用某些计算公式产生的。这样占用内存少，速度快、又便于重复计算。但是，这样产生的随机

4、数显然不能满足随机数的要求。它由初始数值确定，且存在着周期性重复。严格说己不是随机的。因此一般称之为伪随机数。实际应用中，只要选取得好，这样的伪随机数还是可以便用的。6传统蒙特卡洛搜索方法的特点和局限 首先，传统蒙特卡洛搜索方法的特点可以总结为： (1)受问题的条件限制影响小，适应能力强。无论对于多么复杂的非线性搜索问题都可以用它们解决。多参数联合搜索与单参数搜索方法相同，仅计算工作量不同而已；非线性搜索与线性搜索均能解决，特别是当数据与模型之间的理论关系非常复杂，以至于无法用数学解析或其他方式表现出来时，用其他搜索方法往往无从下手，仅用蒙特卡洛搜索方法没有丝毫困难。因此，从某种意义上说，蒙特

5、卡洛搜索方法是一种十分普遍适用的方法。当用其他搜索方法无法解决问题时，不妨试一试蒙特卡洛搜索方法。7 (2)收敛速度与问题的维数(即搜索的模型参数个数)无关。可以看出，在一定的置信水平下，蒙特卡洛搜索方法的误差除与方差有关之外，只与试验次数有关，而与模型空间的组成无关。无论模型参数是几个，只要方差不变且试验次数n相同，则蒙特卡洛搜索方法对模型空间搜索的程度就是相同的，即误差不变。问题维数的变化只影响抽样时间的改变以及演算时间的改变，不影响问题的误差。换言之，要达到同一精度，搜索到同样程度，用蒙特卡洛搜索方法需随机选取的点数n与问题的维数无关，计算时间与维数成比例。因此，蒙特卡洛方法特别适宜于大

6、规模、多参数问题的搜索。 (3)理解容易，因而容易编制程序。而且编制出的程序结构清晰简单，占用内存单元较少，很容易实现。8 但是，传统蒙持卡洛搜索方法也有致命的弱点。其局限性影响了它的广泛应用。 (1)任何一种传统蒙持卡洛搜索方法都不能保证搜索的彻底性。在搜索过程中任何时候均可以停止按索或继续搜索。谁也不能保证此时得到的结果已经“完全”满意了。当然，这一局限性对于只欲求解的共性而言相对来说要好一些，影响要小些；而对于欲求整体极值对应的所谓“最佳”解而言却是致命的、难以解决的问题，必须另辟途径。 (2)传统蒙特卡洛搜索方法的另一个局限性是收敛速度太慢且误差不是确切的，仅具概率性质。9 随着观测资

7、料的急剧增加和观测精度的不断提高，常规蒙特卡洛搜索方法越来越显得不适应了，它们的应用受到了很大的限制，需要加以改进才能适应发展的需要。改进的主要思路是在蒙特卡洛搜索中不进行“盲目”的、完全随机的搜索，而进行在一定先验知识引导下的有“方向”的随机搜索，这就是所谓的启发式蒙特卡洛方法。根据“启发”的思想不同发展了很多种方法，如以人工智能中推理的思想进行启发的方法，以模糊数学的思想进行启发的方法等。目前，应用效果最好，在实际工作中已得到广泛应用的两种启发式蒙特卡洛搜索方法是以统计物理学为基础的模拟退火法和以生物工程为基础的遗传算法及它们的各种变种。10 LAMOST是一台横卧于南北方向的中星仪式反射

8、施密特望远镜。如图所示，它由在北端的反射施密特改正板MA、在南端的球面主镜MB和在中间的焦面构成。球面主镜及焦面固定在地基上，反射施密特改正板作为定天镜跟踪天体的运动，望远镜在天体经过中天前后时进行观测。天体的光经MA反射到MB，再经MB反射后成像在焦面上。焦面上放置的光纤，将天体的光分别传输到光谱仪的狭缝上，然后通过光谱仪后的CCD探测器同时获得大量天体的光谱。1112 相应于5度视场，直径为1.75米的焦面上放置4000根光纤。采用并行可控的光纤定位技术，可在较短的时间里将光纤按星表位置精确定位，并提供了光纤位置微调的可能。这将在光纤定位技术上突破目前世界上同时定位640根光纤的技术。 1

9、3USTC参与的部分工作1、科学目标2、观测控制 观测控制系统是根据LAMOST的巡天战略，具体安排数千万个待观测天体的观测时间，使其能分期分批地进行观测；同时在每夜的观测中根据LAMOST观测程序一步步地实施各项观测步骤，在每夜完成数次观测后，则将观测数据存储到原始数据库中，并进行备份。该系统与LAMOST的科学目标研究、巡天战略的制订密切相关，同时与望远镜控制系统和焦面仪器控制系统以及数据处理系统紧密相联 。143、数据处理 数据处理系统是对LAMOST的观测数据进行处理与分析，得到被观测天体的物理信息，由此可提供给天文学家进行科学研究。LAMOST的观测数据是在每次观测后由三十个CCD上

10、采集下来的原始数据，数据量每天近10GB，每年达数个TB。对这些数据按照一定的步骤和程序进行处理后得到每个被观测天体的一维光谱图（即流量与波长的关系），再对这些光谱进行分析和测量，得到被观测天体的各种物理信息，如类型、红移、视向速度、线强比、等值宽度等，从而可直接提供给天文学家进行大样本天文学的科学研究。15国外巡天望远镜光纤定位方式 美国思隆巡天望远镜( Sloan Digital Survey-SDSS)：打孔式光纤定位系统。每块焦面板上（Tile）根据星表数据预先打有640个位置孔，观测时将光纤插入孔中，实现观测任务。16 澳大利亚AAT望远镜(Anglo-Australian Tele

11、scopeAAT)：磁扣式光纤定位系统。光纤固定在微小的磁扣(Magnitude button)上,由机器人手臂将磁扣放置在需要观测星像对应的钢制焦面板位置上，实现观测任务。17并行可控式定位系统的提出1819并行可控式定位系统的模拟计算解决的问题1、观测完备性和光纤头利用率 与打孔式和磁扣式光纤定位相比，并行可控式系统的观测完备性和利用率是使用者关心的问题，实际计算结果如下：20完备率和利用率2122两个有用的结论1光纤头数目 观测星像的面密度=4 2重合区大小 考虑到机械干涉问题，当观测半径大于18毫米时，光纤头的利用率增加不明显。23 SDSS中为使得分配星象时效率较高，有一套完整的算法

12、来解决这个问题。 算法分为两步来实现：一确定观测效率最高的焦面板分布，使得整个天区尽可能被覆盖，由于整个天区内星象分配是不均匀的这个问题是一个“NP-complete”问题；二在焦面板中心位置固定的情况下分配目标星象给各个焦面板，使得尽可能多的星象被观测，由于各个焦面板之间存在覆盖区，这个问题并非无足轻重，但它是个多项式问题。24 多项式问题和NP-complete是计算复杂性方面的概念。P（polynomial），NP，NPcomplete，NPhard的关系如上图所示 。 输入规模增大时，多项式时间算法的基本计算总次数的增加速度相对较慢25焦面板位置给定 我们首先来考虑第二个问题，在无碰撞

13、的情况下问题等价于如右图所述的网络流问题。 从左面的source node流入网络的一个有七个对象的流。我们的目标是以尽可能小的费用使整个流流过网络到达右边的sink node。 对象必须流经弧，从一个顶点到另一顶点。每个弧有一个它所能传递的最大容量。每一个弧还有一个相关的费用，单个对象通过这条弧所必须花费的成本。 26 SDSS中解决这个问题所使用的算法是变尺度标号推进方法（Goldberg在1997年提出，the scaling push-relabel method），它可以在多项式时间内解决这个问题。它是在传统的标号推进方法的基础上进行了一些改进，从而改善了算法的运行时间而并未改变最坏

14、情况下的运行上界O（mlog（nC）。(The inner loop of the method is based on the push-relabel algorithm for the maximum flow problem.) 一般的标号推进算法是用来解决最大流问题。 它的基本思想：在残量网络中，选择活跃节点, 并把一定的流量推进到它的邻居。 这个网络在每个tile上光纤数限制的基础上表示了所有可能的光纤分配。找到最小费用方案也就是使分配给tile的对象数达到最大。 27 如果当前活跃点有多个邻居，那么首先推进到哪个邻居呢? 由于算法最后的目的是尽可能将流推进到汇(节点t)，因此算法

15、总是首先寻求把流量推进到它的邻居中距离节点t最近的节点. 距离标号表示节点与t的距离，因此算法总是将流量沿着允许弧推进。 如果当前活跃点出发没有允许弧，则增加该节点的距离标号，使得从当前活跃点出发至少含有一条允许弧。28残量网络定义6.7 对网络N=(s,t,V,A,U)中给定的s-t可行流x，网络N关于流x的残量网络N(x) = (s, t, V, A(x), U(x) ，其中A(x)，U(x)定义如下：（residual network，又常称为增量网络或辅助网络 ）其中称, uij(x)为弧(i,j)上的残留容量(residual capacity)。29活跃节点 流网络N=（s，t,

16、V，A，U）上的一个预流 x 是指从N 的弧集A到实数集合R的一个函数,使得对每个顶点 i 都满足如下条件：其中 , 称为 x 在 i 上的赢余(excess). e(i)0的节点i 称为活跃的(Active). 对预流 x ，如果存在活跃节点, 则说明该预流是不可行的。30距离标号 对于一个残量网络N（x），如果一个函数d 将节点集合V映射到非负整数集合，则称d是关于残量网络N（x）的距离函数（distance function），d（i）称为节点 i 的距离标号（distance label）。 如果距离函数d满足： （1） d（t） =0； （2）对N（x）中的任意一条弧（i，j）有d（

17、i） d（j）+1； 则称距离函数 d 关于流 x 是有效的（valid），或称距离标号（函数）d 是有效的。31 如果任意一个节点的距离标号正好等于残量网络中从该节点到汇点（节点t）的所有有向路中弧数最少的有向路所包含的弧数（当令所有弧的长度为1时, 这就是从该节点到汇点的最短路路长， 因此我们后面直接称为最短路路长），则称距离函数d关于流x是精确的（exact），或称距离标号是精确的。32允许弧 如果对N（x）中的某一条弧（i，j）有d（i）= d（j）+1，则称弧（i，j）为允许弧（Admissible Arc）。 一条s-t有向路如果完全由允许弧组成,则该有向路称为允许路（Admiss

18、ible Path）。123412345112033焦面板位置给定 有时候某一类星象更重要些我们更希望得到它的光谱，这将使得情况稍稍复杂些。在寻找无碰撞星象时，应该使得这类较高优先级的星象被选中，然后再去考虑优先级低的星象。 在有碰撞的情况下算法是分两步来完成的 ：一先用一种算法（friendsfriends grouping algorithm）来寻找无碰撞的星象集合，如右图所示，再调用前面的网络算法对未发生碰撞的星象进行分配。34焦面板位置给定 二利用剩余未分配的光纤来解决焦面板重合区域内的“碰撞”问题。 这里我们设计了另一个网络流，只考虑焦面板重合区内的星象进行再次分配以解决“碰撞”问题

19、。在两个星象发生碰撞和三个星象发生碰撞的情况下网络流的解就是我们要求的解决碰撞后的最优分配。35 即使这样仍然有得到不可行解的情况，只是很少见。一组的一部分在重合区内一部分不在，保证未发生“碰撞”的星象被分配；二组内一些星象被多个焦面板所覆盖，另一些被较少的焦面板覆盖，这时会有部分未发生“碰撞”的星象没有被分配光纤，他们的概率是极小的 。 对于更复杂的情况这个方法并不能保证得到可行的结果，此时我们随机选择一个解决方案，所幸的是这样的星象只有不到1。36优化焦面板位置 为了优化焦面板的放置位置以最大限度的观测到星象，在SDSS中是这样做的：首先给焦面板一个初始的近似平均的分布，将天空均匀覆盖，再

20、调用网络算法将焦面板打散，移动焦面板至新的位置，循环以上步骤直至令人满意的星象数被分配或者最终收敛于某一点。 调整已给定焦面板分布的方法是这样的：首先焦面板的位置已经给定了，要使尽量多的星象被分配光纤，由前面我们知道这个问题等价于一个最小费用流问题，但在这里我们允许一个星象可以被分配到一个并不覆盖它的焦面板内，只是这样做要带来额外的费用。这样做的好处是它的解决办法可以带给我们如何改进焦面板分布的一些信息。37r为焦面板半径，d为星象与焦面板中心的距离 费用函数可采用下面的形式： 如果某一个地区星象密度高，而另一个地区可观测的容量大，那么这两个区域间的焦面板就会被分配不被它们所覆盖的星象，并且是

21、朝向星象密集区的。 关于费用函数, 在另一个文献中费用函数是下面这种形式，38 Rtile为焦面板半径，r为星象与焦面板中心的距离。这个函数更一般些，因为存在A和这两个参数。A是尺度参数用来调节费用的具体数值。决定了费用函数斜率的变化情况，一般来说0.52。当12，费用函数是鼓励焦面板从原始位置作大的偏移，因为这时费用函数的斜率是增函数。对于大天区来说这种特性是很好的，通过焦面板的移动可以达到高效率的配置。当0.51，费用函数鼓励焦面板从原始位置作小的调整，因为这时费用函数的斜率是减函数。对于小天区来说这是很好的，因为大的偏移有可能导致部分天区未被覆盖。也许更一般的措施是在一定的情况下让是可变

22、的，以此来适应不同的情况。 39 星象分配完后，就要移动焦面板到新的位置，这时焦面板是一个一个移动的。在前一步里我们已经给每一个焦面板分配了星象，现在我们移动焦面板就是要使每个焦面板内所有星象的费用总和最小。假设费用总和f（x，y）是焦面板中心坐标（x，y）的函数，我们从当前焦面板中心的位置出发采用梯度法或鲍威尔直接法来移动焦面板以使f（x，y）最小。文献中讲了一种梯度法（The simple gradientdescent method）：在当前位置计算梯度，以步长（焦面板半径的16/1000）沿梯度的反方向前进直至f（x，y）不再减少。在新的当前位置再次计算梯度，平分步长重复上面的步骤直至

23、 减少至焦面板的2/1000。40算法流程 以上只是SDSS中为优化焦面板位置所采用算法的大致描述，事实上其中还加入了很多近似（heuristics）以利于算法的求解。 寻找焦面板最优位置是不断循环进行的，怎样判断它何时收敛？每个循环过后实际已被分配的星象和要达到的数目间的差如果没有减少5，那我们就认为程序“卡”住了。 此时我们采取以下步骤（称之为polishing）：焦面板半径减少2，然后继续进行直至程序再次被“卡”住。我们只在“卡”住的时候使用减小的半径。 41 如果程序至少连续两次被“卡”住，那我们就认为它收敛了。这样做的目的是因为在原始问题中一个焦面板有可能会以较少的费用分配位于它边缘的星象，这些星象将无法被正确分配。在一些轮次里减小焦面板半径将会使它们被分配到其他地方去。 为了减小网络流问题的规模，SDSS中也采用了很多近似。 首先算法在分配星象时只考虑中心距离星象在两倍半径之内的焦面板，而且最多只考虑三个这样的焦面板。 其次费用函数在使用前将被圆整以减小问题的规模。42 最后如果两个星象在同一个焦面板内且圆整的费用也相同那么它们就是同一类的，同一类的星象网络