⑴ 能不能简单的给我解释一下蒙特卡罗算法
以概率和统计的理论、方法为基础的一种计算方法，将所求解的问题同一定的概率模型相联系，用电子计算机实现统计模拟或抽样，以获得问题的近似解，故又称统计模拟法或统计试验法。
蒙特卡罗是摩纳哥的一个城市，以赌博闻名于世界。蒙特卡罗法借用这一城市的名称是为了象征性地表明该方法的概率统计的特点。
蒙特卡罗法作为一种计算方法，是由S.M.乌拉姆和J.冯·诺伊曼在20世纪40年代中叶为研制核武器的需要而首先提出来的。在此之前，该方法的基本思想实际上早已被统计学家所采用了。例如，早在17世纪，人们就知道了依频数来决定概率的方法。
20世纪40年代中叶，出现了电子计算机，使得用数学方法模拟大量的试验成为可能。另外，随着科学技术的不断发展，出现了越来越多的复杂而困难的问题，用通常的解析方法或数值方法都很难加以解决。蒙特卡罗法就是在这些情况下，作为一种可行的而且是不可缺少的计算方法被提出和迅速发展起来的。
基本原理 考虑一个射击运动员的射击成绩 G。令x表示弹着点到靶心的距离，g(x)表示得分，而�0�6(x)表示该运动员的弹着点的分布密度，则
。
另一方面，如果该运动员进行了实弹射击，弹着点依次为X1，X2，…，XN，则平均得分为
。
很明显，弿N是G 的一个近似估计。蒙特卡罗法正是用弿N作为G 的近似估计。
假设 x不是一维空间的点，而是一个S 维空间的点(x1，x2，…，xs)，则上述积分变为
。
蒙特卡罗法计算此积分是用
作为G 的近似估计，式中(X1n，X2n，…，Xsn)是由�0�6(x1，x2，…，xs)中抽取的第n 个样本点。同上述一维积分比较，相同点是，都以某随机变量的N 个独立抽样值的算术平均作为近似估计；不同点仅仅是，决定随机量的样本点不同，一个是一维空间的点，另一个是S 维空间的点。由上式可见， 决定近似估计 弿N好坏的仅仅是随机变量g(x)或g(x1，x2，…，xs)的分布情况，而与它们是由怎样的样本点对应过来的无关。换言之，如果随机变量g(x)和g(x1，x2，…，xs)具有相同分布，在不计抽样，不计计算g(x)和g(x1，x2，…，xs)的差别的情况下，S维情况与一维情况无任何差异。这是其他计算方法所不具有的、一个非常重要的性质。
蒙特卡罗法解题的一般过程是，首先构成一个概率空间；然后在该概率空间中确定一个随机变量g(x)，其数学期望
正好等于所要求的值G，其中F(x)为x的分布函数；最后，以所确定的随机变量的简单子样的算术平均值
作为G 的近似估计。由于其他原因，如确定数学期望为G 的随机变量g(x)有困难，或为其他目的，蒙特卡罗法有时也用G 的渐近无偏估计代替一般过程中的无偏估计弿N来作为G 的近似估计。
收敛性、误差和费用 蒙特卡罗法的近似估计弿N依概率1收敛于G的充分必要条件是随机变量g(x)满足
。
如果随机变量g(x)满足条件
，
式中1≤r<2，则
，
亦即弿N依概率1收敛于G 的速度为。总之，蒙特卡罗法的收敛性取决于所确定的随机变量是否绝对可积，而蒙特卡罗法的收敛速度取决于该随机变量是几次绝对可积的。
根据中心极限定理，只要随机变量g(x)具有有限的异于零的方差σ2，当N 足够大时便有蒙特卡罗法的误差公式如下：
，
式中1-α为置信水平，x由置信水平所惟一确定。根据上述误差公式，为满足问题的误差和置信水平的要求，子样容量N必须大于(x/ε)2σ2，其中ε表示误差。进一步假设每观察一个样本所需要的费用是C，则蒙特卡罗法的费用是。这一结果表明，在相同误差和置信水平要求下，一个蒙特卡罗法的优劣完全取决于σ2C 的值的大小，它的值越小相应的方法越好，或者说，蒙特卡罗法的效率与σ2C 成反比。
提高效率的方法
降低方差技巧 降低方差是提高蒙特卡罗法效率的重要途径之一。考虑二重积分
，
式中�0�6(x，y)为x和y的分布密度函数，g(x，y)的方差存在。蒙特卡罗法计算Eg的一般技巧是用g=g(x， y)作为所确定的随机变量，其中x和y服从分布�0�6(x，y)。降低方差的具体办法有：
① 统计估计技巧用�0�6(x) 和�0�6x(y)分别表示分布�0�6(x，y)的边缘分布和条件分布。计算Eg的统计估计技巧是用y的统计估计量
作为所确定的随机变量，其中x服从分布�0�6(x)。g的方差恰好为两个方差的和，它们分别是对随机变量x和随机变量y采用抽样办法而产生的。gSE的方差正好等于前者，因此gSE的方差一定比g的方差小。统计估计技巧的一般原理是，对于问题中所出现的诸随机变量，能够确定其相应的统计估计量的，就不要再对它们采用随机抽样的办法。
② 重要抽样技巧引入任意分布密度函数�0�6*(x，y)，则
的数学期望同样为Eg，其中x和y服从分布�0�6*(x，y)。当�0�6*(x，y)～|g(x，y)|�0�6(x，y)时，gIS的方差达到最小。在g(x，y)≥0时，方差等于零，gIS实际上变成了与其中出现的随机变量无关的常数。重要抽样技巧的一般原理是，尽量使所确定的随机变量与问题中所出现的随机变量关系不大。
③ 相关抽样技巧考虑一个新的、积分值已知的二重积分
，
可得知
的数学期望同样为Eg，式中x和y服从分布�0�6(x，y)，α为任意常数。当为随机变量g(x，y)和g*(x，y)的均方差σg、λg*之比时，gCS的方差达到最小。此时的方差等于g 的方差 1-ρ2倍，ρ为随机变量g(x，y)和g*(x，y)的相关系数。当ρ=1时，方差变为零。相关抽样技巧的一般原理是，寻找一个数学期望已知的且与原确定的随机变量正相关的随机变量，使相应的相关系数尽量接近1，然后用这两个随机变量的线性组合作为蒙特卡罗法最终所确定的随机变量。
降低方差的技巧还有对偶变数技巧、系统抽样技巧和分层抽样技巧等。对偶变数技巧的一般原理是，除了原确定的随机变量外，寻找另一个（或多个）具有相同数学期望的随机变量，使得它们之间尽量是对偶负相关的，然后用它们的线性组合作为蒙特卡罗法最终所确定的随机变量。系统抽样技巧的一般原理是，对问题中所出现的某些随机变量按相应分布所确定的比例进行抽样，而不是进行随机抽样。分层抽样技巧的一般原理是，对问题中所出现的某些随机变量进行分层，尽量使所确定的随机变量在各层中相对平稳，各层间的抽样按相应分布所确定的比例进行。
其他途径 为了提高蒙特卡罗法的效率，除了简单地降低方差外，还有为降低费用设计的分裂和轮盘赌技巧，为逐步降低方差而设计的多极抽样技巧，为改善收敛速度而设计的拟蒙特卡罗法，为计算条件期望而设计的条件蒙特卡罗法等等。分裂和轮盘赌技巧的一般原理是，将x的积分区域分为重要和非重要两部分，对于抽样确定的X，当它属于重要区域时，对相应的Y 进行多次抽样；当它属于非重要区域时，只有在赌获胜时才对相应的Y 进行抽样。多级抽样技巧的一般原理是，在进行某一级抽样计算的同时，根据它所提供的抽样观察值，设计更好的抽样技巧，用新设计的抽样技巧进行新的一级的抽样计算，依次类推，最后用各级的结果的线性组合作为蒙特卡罗法的近似估计。拟蒙特卡罗法与一般蒙特卡罗法的最大区别是，前者不像后者那样要求子样 g(X1)，g(X2)，…，g(Xn)是相互独立的。用一致分布点列替代由随机数组成的点列的所谓数论方法，实际上就是一种拟蒙特卡罗法。条件蒙特卡罗法的一般原理是，首先将条件期望问题转化成为非条件期望问题，然后用解非条件期望的一般方法来解决条件期望计算问题。由于条件蒙特卡罗法中引进了任意分布密度函数，因此，可以选取合适的分布密度函数来实现进一步降低方差的目的。
优缺点 蒙特卡罗法的最大优点是，在方差存在的情况下，问题的维数不影响它的收敛速度，而只影响它的方差；问题几何形状的复杂性对它的影响不大；它不象其他数值方法那样对问题一定要进行离散化处理，而是常可以进行连续处理；它的程序结构简单，所需计算机存贮单元比其他数值方法少，这对于高维问题差别尤其显着。蒙特卡罗法的最大缺点是，对于维数少的问题它不如其他数值方法好；它的误差是概率误差，而不是一般意义下的误差。
应用 随着电子计算机的迅速发展和科学技术问题日趋复杂，蒙特卡罗法的应用越来越广泛，已经渗透到科学技术的各个领域。
在一些典型数学问题方面的应用主要有：多重积分计算、线性代数方程组求解、矩阵求逆、常微分方程边值问题求解、偏微分方程求解、非齐次线性积分方程求解、本征值计算和最优化计算等等。其中的多重积分计算、非齐次线性积分方程求解和齐次线性积分方程本征值计算等，不仅非常有代表性，而且有很大的实用价值，对于高维问题常比其他数值方法好。
在一些实际问题方面的应用主要有，屏蔽计算、核临界安全计算、反应堆物理计算、微扰计算、实验核物理计算、高能物理计算、核物理计算、统计物理计算、真空技术、公用事业、信息论、系统模拟、可靠性计算和计算机科学等等。其中的屏蔽计算、核临界安全计算、微扰计算、实验核物理计算和统计物理计算等，不仅非常有代表性，而且应用得很广泛，按蒙特卡罗法解决这些问题的能力讲，已经超过了其他计算方法的水平。
⑵ 优化算法笔记（一）优化算法的介绍
（以下描述，均不是学术用语，仅供大家快乐的阅读）
我们常见常用的算法有排序算法,字符串遍历算法,寻路算法等。这些算法都是为了解决特定的问题而被提出。
算法本质是一种按照固定步骤执行的过程。
优化算法也是这样一种过程，是一种根据概率按照固定步骤寻求问题的最优解的过程。与常见的排序算法、寻路算法不同的是，优化算法不具备等幂性，是一种 概率算法 。算法不断的 迭代 执行同一步骤直到结束，其流程如下图。
等幂性即 对于同样的输入，输出是相同的 。
比如图1，对于给定的鱼和给定的熊掌，我们在相同的条件下一定可以知道它们谁更重，当然，相同的条件是指鱼和熊掌处于相同的重力作用下，且不用考虑水分流失的影响。在这些给定的条件下，我们（无论是谁）都将得出相同的结论，鱼更重或者熊掌更重。我们可以认为，秤是一个等幂性的算法（工具）。
现在把问题变一变，问鱼与熊掌你更爱哪个，那么现在，这个问题，每个人的答案可能不会一样，鱼与熊掌各有所爱。说明喜爱这个算法不是一个等幂性算法。当然你可能会问，哪个更重，和更喜欢哪个这两个问题一个是客观问题，一个是主观问题，主观问题没有确切的答案的。当我们处理主观问题时，也会将其转换成客观问题，比如给喜欢鱼和喜欢熊掌的程度打个分，再去寻求答案，毕竟计算机没有感情，只认0和1（量子计算机我不认识你）。
说完了等幂性，再来说什么是概率算法。简单来说就是看脸、看人品、看运气的算法。
有一场考试，考试的内容全部取自课本，同时老师根据自己的经验给同学们划了重点，但是因为试卷并不是该老师所出，也会有考试内容不在重点之内，老师估计试卷中至少80%内容都在重点中。学霸和学渣参加了考试，学霸为了考满分所以无视重点，学渣为了pass，因此只看了重点。这样做的结果一定是score(学霸)>=score(学渣)。
当重点跟上图一样的时候，所有的内容都是重点的时候，学霸和学渣的学习策略变成了相同的策略，则score(学霸)=score(学渣)。但同时，学渣也要付出跟学霸相同的努力去学习这些内容，学渣心里苦啊。
当课本如下图时
学霸？学霸人呢，哪去了快来学习啊，不是说学习一时爽，一直学习一直爽吗，快来啊，还等什么。
这时，如果重点内容远少于书本内容时，学渣的学习策略有了优势——花费的时间和精力较少。但是同时，学渣的分数也是一个未知数，可能得到80分也可能拿到100分，分数完全取决于重点内容与题目的契合度，契合度越高，分数越高。对学渣来说，自己具体能考多少分无法由自己决定，但是好在能够知道大概的分数范围。
学霸的学习策略是一种遍历性算法，他会遍历、通读全部内容，以保证满分。
学渣的学习策略则是一种概率算法，他只会遍历、学习重点内容，但至于这些重点是不是真重点他也不知道。
与遍历算法相比，概率算法的结果具有不确定性，可能很好，也可能很差，但是会消耗更少的资源，比如时间（人生），空间（记忆）。概率算法的最大优点就是 花费较少的代价来获取最高的收益 ，在现实中体现于节省时间，使用很少的时间得到一个不与最优解相差较多的结果。
“庄子：吾生也有涯，而知也无涯；以有涯随无涯，殆矣。”的意思是：人生是有限的，但知识是无限的（没有边界的），用有限的人生追求无限的知识，是必然失败的。
生活中概率算法（思想）的应用其实比较广泛，只是我们很少去注意罢了。关于概率算法还衍生出了一些有趣的理论，比如墨菲定律和幸存者偏差，此处不再详述。
上面说到，优化算法就是不停的执行同样的策略、步骤直到结束。为什么要这样呢？因为优化算法是一种概率算法，执行一次操作就得到最优结果几乎是不可能的，重复多次取得最优的概率也会增大。
栗子又来了，要从1-10这10个数中取出一个大于9的数，只取1次，达到要求的概率为10%，取2次，达到要求的概率为19%。
可以看出取到第10次时，达到要求的概率几乎65%，取到100次时，达到要求的概率能接近100%。优化算法就是这样简单粗暴的来求解问题的吗？非也，这并不是一个恰当的例子，因为每次取数的操作之间是相互独立的，第2次取数的结果不受第1次取数结果的影响，假设前99次都没达到要求，那么再取一次达到要求的概率跟取一次达到要求的概率相同。
优化算法中，后一次的计算会依赖前一次的结果，以保证后一次的结果不会差于前一次的结果。这就不得不谈到马尔可夫链了。
由铁组成的链叫做铁链，同理可得，马尔可夫链就是马尔可夫组成的链。
言归正传, 马尔可夫链（Markov Chain, MC） ,描述的是 状态转移的过程中,当前状态转移的概率只取决于上一步的状态,与其他步的状态无关 。简单来说就是当前的结果只受上一步的结果的影响。每当我看到马尔可夫链时，我都会陷入沉思，生活中、或者历史中有太多太多与马尔可夫链相似的东西。西欧封建等级制度中“附庸的附庸不是我的附庸”与“昨天的努力决定今天的生活，今天的努力决定明天的生活”，你的下一份工作的工资大多由你当前的工资决定，这些都与马尔可夫链有异曲同工之处。
还是从1-10这10个数中取出一个大于9的数的这个例子。基于马尔可夫链的概率算法在取数时需要使当前取的数不小于上一次取的数。比如上次取到了3，那么下次只能在3-10这几个数中取，这样一来，达到目标的概率应该会显着提升。还是用数据说话。
取1次达到要求的概率仍然是
取2次内达到要求的概率为
取3次内达到要求的概率为
取4次内……太麻烦了算了不算了
可以看出基于马尔可夫链来取数时，3次内能达到要求的概率与不用马尔可夫链时取6次的概率相当。说明基于马尔可夫链的概率算法求解效率明显高于随机概率算法。那为什么不将所有的算法都基于马尔可夫链呢？原因一，其实现方式不是那么简单，例子中我们规定了取数的规则是复合马尔可夫链的，而在其他问题中我们需要建立适当的复合马尔科夫链的模型才能使用。原因二，并不是所有的问题都符合马尔科夫链条件，比如原子内电子出现的位置，女朋友为什么会生（lou）气，彩票号码的规律等，建立模型必须与问题有相似之处才能较好的解决问题。
介绍完了优化算法，再来讨论讨论优化算法的使用场景。
前面说了优化算法是一种概率算法，无法保证一定能得到最优解，故如果要求结果必须是确定、稳定的值，则无法使用优化算法求解。
例1，求城市a与城市b间的最短路线。如果结果用来修建高速、高铁，那么其结果必定是唯一确定的值，因为修路寸土寸金，必须选取最优解使花费最少。但如果结果是用来赶路，那么即使没有选到最优的路线，我们可能也不会有太大的损失。
例2，求城市a与城市b间的最短路线，即使有两条路径，路径1和路径2，它们从a到b的距离相同，我们也可以得出这两条路径均为满足条件的解。现在将问题改一下，求城市a到城市b耗时最少的线路。现在我们无法马上得出确切的答案，因为最短的线路可能并不是最快的路线，还需要考虑到天气，交通路况等因素，该问题的结果是一个动态的结果，不同的时间不同的天气我们很可能得出不同的结果。
现实生产、生活中，也有不少的场景使用的优化算法。例如我们的使用的美图软件，停车场车牌识别，人脸识别等，其底层参数可能使用了优化算法来加速参数计算，其参数的细微差别对结果的影响不太大，需要较快的得出误差范围内的参数即可；电商的推荐系统等也使用了优化算法来加速参数的训练和收敛，我们会发现每次刷新时，推给我们的商品都有几个会发生变化，而且随着我们对商品的浏览，系统推给我们的商品也会发生变化，其结果是动态变化的；打车软件的订单系统，会根据司机和客人的位置，区域等来派发司机给客人，不同的区域，不同的路况，派发的司机也是动态变化的。
综上我们可以大致总结一下推荐、不推荐使用优化算法的场景的特点。
前面说过，优化算法处理的问题都是客观的问题，如果遇到主观的问题，比如“我孰与城北徐公美”，我们需要将这个问题进行量化而转换成客观的问题，如身高——“修八尺有余”，“外貌——形貌昳丽”，自信度——“明日徐公来，孰视之，自以为不如；窥镜而自视，又弗如远甚”，转化成客观问题后我们可以得到各个解的分数，通过比较分数，我们就能知道如何取舍如何优化。这个转化过程叫做问题的建模过程，建立的问题模型实际上是一个函数，这个函数对优化算法来说是一个黑盒函数，即不需要知道其内部实现只需要给出输入，得到输出。
在优化算法中这个黑盒函数叫做 适应度函数 ， 优化算法的求解过程就是寻找适应度函数最优解的过程 ，使用优化算法时我们最大的挑战就是如何将抽象的问题建立成具体的模型，一旦合适的模型建立完成，我们就可以愉快的使用优化算法来求解问题啦。（“合适”二字谈何容易）
优化算法的大致介绍到此结束，后面我们会依次介绍常见、经典的优化算法，并探究其参数对算法性能的影响。
——2019.06.20
[目录]
[下一篇 优化算法笔记（二）优化算法的分类]
⑶ 优化算法
SGD算法中的一个关键参数是学习率。之前，我们介绍的SGD使用固定的学习率。在实践中，有必要随着时间的推移逐渐降低学习率，因此我们将第 k 步迭代的学习率记作 ϵ k 。
这是因为SGD中梯度估计引入的噪声源（m 个训练样本的随机采样）并不会在极小点处消失。相比之下，当我们使用批量梯度下降到达极小点时，整个代价函数的真实梯度会变得很小，之后为 0，因此批量梯度下降可以使用固定的学习率。保证SGD收敛的一个充分条件是
若 ϵ 0 太大，学习曲线将会剧烈振荡，代价函数值通常会明显增加。温和的振荡是良好的，容易在训练随机代价函数（例如使用Dropout的代价函数）时出现。如果学习率太小，那么学习过程会很缓慢。如果初始学习率太低，那么学习可能会卡在一个相当高的代价值。通常，就总训练时间和最终代价值而言，最优初始学习率会高于大约迭代 100 次左右后达到最佳效果的学习率。因此，通常最好是检测最早的几轮迭代，选择一个比在效果上表现最佳的学习率更大的学习率，但又不能太大导致严重的震荡。
虽然随机梯度下降仍然是非常受欢迎的优化方法，但其学习过程有时会很慢。动量方法 (Polyak, 1964) 旨在加速学习，特别是处理高曲率、小但一致的梯度，或是带噪声的梯度。动量算法积累了之前梯度指数级衰减的移动平均，并且继续沿该方向移动。动量的效果如图8.5所示
受 Nesterov 加速梯度算法 (Nesterov, 1983, 2004) 启发，提出了动量算法的一个变种。这种情况的更新规则如下：
其中参数 α 和 ϵ 发挥了和标准动量方法中类似的作用。Nesterov 动量和标准动量之间的区别体现在梯度计算上。Nesterov 动量中，梯度计算在施加当前速度之后。因此，Nesterov 动量可以解释为往标准动量方法中添加了一个校正因子。完整的Nesterov动量算法如算法3.2所示
初始点能够决定算法是否收敛，有些初始点十分不稳定，使得该算法会遭遇数值困难，并完全失败。当学习收敛时，初始点可以决定学习收敛得多快，以及是否收敛到一个代价高或低的点。此外，差不多代价的点可以具有区别极大的泛化误差，初始点也可以影响泛化。
也许完全确知的唯一特性是初始参数需要在不同单元间 ‘‘破坏对称性’’。如果具有相同激活函数的两个隐藏单元连接到相同的输入，那么这些单元必须具有不同的初始参数。如果它们具有相同的初始参数，然后应用到确定性损失和模型的确定性学习算法将一直以相同的方式更新这两个单元。即使模型或训练算法能够使用随机性为不同的单元计算不同的更新（例如使用Dropout的训练），通常来说，最好还是初始化每个单元使其和其他单元计算不同的函数。这或许有助于确保没有输入模式
丢失在前向传播的零空间中，没有梯度模式丢失在反向传播的零空间中。每个单元计算不同函数的目标促使了参数的随机初始化。我们可以明确地搜索一大组彼此互不相同的基函数，但这经常会导致明显的计算代价。例如，如果我们有和输出一样多的输入，我们可以使用 Gram-Schmidt 正交化于初始的权重矩阵，保证每个单元计算彼此非常不同的函数。在高维空间上使用高熵分布来随机初始化，计算代价小并且不太可能分配单元计算彼此相同的函数。
通常情况下，我们可以为每个单元的偏置设置启发式挑选的常数，仅随机初始化权重。额外的参数（例如用于编码预测条件方差的参数）通常和偏置一样设置为启发式选择的常数。
我们几乎总是初始化模型的权重为高斯或均匀分布中随机抽取的值。高斯或均匀分布的选择似乎不会有很大的差别，但也没有被详尽地研究。然而，初始分布的大小确实对优化过程的结果和网络泛化能力都有很大的影响。
更大的初始权重具有更强的破坏对称性的作用，有助于避免冗余的单元。它们也有助于避免在每层线性成分的前向或反向传播中丢失信号——矩阵中更大的值在矩阵乘法中有更大的输出。如果初始权重太大，那么会在前向传播或反向传播中产生爆炸的值。在循环网络中，很大的权重也可能导致混沌（chaos）（对于输入中很小的扰动非常敏感，导致确定性前向传播过程表现随机）。在一定程度上，梯度爆炸问题可以通过梯度截断来缓解（执行梯度下降步骤之前设置梯度的阈值）。较大的权
重也会产生使得激活函数饱和的值，导致饱和单元的梯度完全丢失。这些竞争因素决定了权重的理想初始大小。
也有助于避免在每层线性成分的前向或反向传播中丢失信号——矩阵中更大的值在矩阵乘法中有更大的输出。如果初始权重太大，那么会在前向传播或反向传播中产生爆炸的值。在循环网络中，很大的权重也可能导致混沌（chaos）（对于输入中很小的扰动非常敏感，导致确定性前向传播过程表现随机）。在一定程度上，梯度爆炸问题可以通过梯度截断来缓解（执行梯度下降步骤之前设置梯度的阈值）。较大的权重也会产生使得激活函数饱和的值，导致饱和单元的梯度完全丢失。这些竞争因素决定了权重的理想初始大小。
有些启发式方法可用于选择权重的初始大小。一种初始化 m 个输入和 n 输出的全连接层的权重的启发式方法是从分布 U(−1/√ m ,
1/√ m ) 中采样权重，而 Glorot and Bengio 建议使用标准初始化
后一种启发式方法初始化所有的层，折衷于使其具有相同激活方差和使其具有相同梯度方差之间。这假设网络是不含非线性的链式矩阵乘法，据此推导得出。现实的神经网络显然会违反这个假设，但很多设计于线性模型的策略在其非线性对应中的效果也不错。
数值范围准则的一个缺点是，设置所有的初始权重具有相同的标准差，例如1/√ m ，会使得层很大时每个单一权重会变得极其小。Martens (2010) 提出了一种被称为稀疏初始化（sparse initialization）的替代方案，每个单元初始化为恰好有 k 个非零权重。这个想法保持该单元输入的总数量独立于输入数目 m，而不使单一权重元素的大小随 m 缩小。稀疏初始化有助于实现单元之间在初始化时更具多样性。但是，获得较大取值的权重也同时被加了很强的先验。因为梯度下降需要很长时间缩小 ‘‘不正确’’ 的大值，这个初始化方案可能会导致某些单元出问题，例如maxout单元有几个过滤器，互相之间必须仔细调整。
Delta-bar-delta 算法 (Jacobs, 1988) 是一个早期的在训练时适应模型参数各自学习率的启发式方法。该方法基于一个很简单的想法，如果损失对于某个给定模型参数的偏导保持相同的符号，那么学习率应该增加。如果对于该参数的偏导变化了符号，那么学习率应减小。当然，这种方法只能应用于全批量优化中。
AdaGrad 算法，如算法8.4所示，独立地适应所有模型参数的学习率，缩放每个参数反比于其所有梯度历史平方值总和的平方根 (Duchi et al., 2011)。具有损失最大偏导的参数相应地有一个快速下降的学习率，而具有小偏导的参数在学习率上有相对较小的下降。净效果是在参数空间中更为平缓的倾斜方向会取得更大的进步。
在凸优化背景中，AdaGrad 算法具有一些令人满意的理论性质。然而，经验上已经发现，对于训练深度神经网络模型而言，从训练开始时积累梯度平方会导致有效学习率过早和过量的减小。AdaGrad在某些深度学习模型上效果不错，但不是全部。
RMSProp 算法 (Hinton, 2012) 修改 AdaGrad 以在非凸设定下效果更好，改变梯度积累为指数加权的移动平均。AdaGrad旨在应用于凸问题时快速收敛。当应用于非凸函数训练神经网络时，学习轨迹可能穿过了很多不同的结构，最终到达一个局部是凸碗的区域。AdaGrad 根据平方梯度的整个历史收缩学习率，可能使得学习率在达到这样的凸结构前就变得太小了。RMSProp 使用指数衰减平均以丢弃遥远过去的历史，使其能够在找到凸碗状结构后快速收敛，它就像一个初始化于该碗状结构的 AdaGrad 算法实例。
RMSProp 的标准形式如算法8.5所示，结合 Nesterov 动量的形式如算法8.6所示。相比于 AdaGrad，使用移动平均引入了一个新的超参数ρ，用来控制移动平均的长度范围。经验上，RMSProp 已被证明是一种有效且实用的深度神经网络优化算法。目前它是深度学习从业者经常采用的优化方法之一。
Adam (Kingma and Ba, 2014) 是另一种学习率自适应的优化算法，最好被看作结合 RMSProp 和具有一些重要区别的动量的变种。首先，在 Adam 中，动量直接并入了梯度一阶矩（指数加权）的估计。将动量加入 RMSProp 最直观的方法是将动量应用于缩放后的梯度。结合缩放的动量使用没有明确的理论动机。其次，Adam 包括偏置修正，修正从原点初始化的一阶矩（动量项）和（非中心的）二阶矩的估计（算法8.7）。RMSProp 也采用了（非中心的）二阶矩估计，然而缺失了修正因子。因此，不像 Adam，RMSProp 二阶矩估计可能在训练初期有很高的偏置。Adam 通常被认为对超参数的选择相当鲁棒，尽管学习率有时需要从建议的默认修改。
目前，最流行并且使用很高的优化算法包括 SGD、具动量的 SGD、RMSProp、具动量的 RMSProp、AdaDelta 和 Adam。
⑷ 优化算法笔记（十二）烟花算法
（以下描述，均不是学术用语，仅供大家快乐的阅读）
烟花算法（Firework Algorithm,FWA）是一种受烟花爆炸产生火星，并继续分裂爆炸这一过程启发而得出的算法。算法的思想简单，但具体实现复杂。算法提出时间并不长，但是已经有了不少的改进研究和较为全面的应用。
烟花算法中，每一个烟花的位置都代表了一个可行解。烟花的爆炸产生的火星有两种，正常的火星与特别的火星。每个火星都会爆炸产生数个正常火星，某些火星有一定的概率产生一个特别的火星。正常的火星根据当前火星的振幅随机均匀分布在该火星的周围，而特别的火星将在当前火星附近以正态分布方式产生。每次迭代产生的火星数量多于每一代应有的火星数，算法将参照火星位置的优劣，随机留下指定数量的火星，已保持火星数目的稳定。
烟花算法的主角毫无疑问就是烟花了。
式（1）为适应度值越小越优的情况，而式（2）则是适应度值越大越优的情况。 为一个极小的值，以保证分母不为0。
每个火星产生的正常火星数量也由其适应度值来决定。
其中 表示第i个火星将要产生的正常火星数， 是产生正常火星的总数为一个常数，从式（3）,（4）可以看出适应度值越好的火星能够产生更多的正常火星，反之，火星适应度越差，能够产生的火星数越少。
由于式（3），（4）计算出的值为小数，烟花算法中使用式（5）将其转化为整数。
从式（3）和式（4）中可以看出，在每一代中将会产生出 个正常火星。产生的正常火星的位置与当前火星的振幅有关，可以从式（1），（2）看出，适应度越优的火星的振幅越小，那么它产生的正常火星将在它自己周围，而适应度越差的火星的振幅越大，它产生的正常火星将会出现在离自己较远的位置。
当前火星每次爆炸会从D维搜索空间内随机选择z维进行更新从而产生新的火星。正常火星的位置由如下公式产生。
其中z为取值1-D的均匀随机正整数，rand(-1,1)表示-1到1内的均匀随机数。从式(6)中可以看出，正常火星的位置与其振幅有直接关系，振幅越大产生的新火星距当前火星的距离约远。
每次迭代过程中，会产生m个特别的火星，即在这N个火星中随机选择m个火星，每个火星产生一个特别的火星。特别的火星的由下面的公式产生：
由上面的过程可知，在每一代中，有N个火星，将会产生出 个正常火星以及m个特别的火星。但是每一代中只能从这 个火星中选择N个火星保留至下一代。
每次会先从 个火星中选择最优的火星保留至下一代，然后再从中选择N-1个火星。选择某个火星的概率如下：
其中R(X)表示该火星距其他所有火星的距离之和，即距其它火星越远的火星，被选择保留至下一代的概率较大。
个火星，而且
,所有烟花算法每次迭代的计算复杂度要大于其他算法，这简直就是一个作弊行为。别的算法每次只搜索了N个位置，而烟花算法却搜索了 个位置。与其他优化算法对比时，其他算法的种群数量应该取 ，否则这将是一场不公正的对决。
适应度函数还是这个简单的小白鼠
实验一 ：标准烟花算法
以上数据来自原论文，现在看一看实验的图像以及实验结果。
从图像可以看出每次只选择保留了5个火星，它们的收敛速度很慢，实验结束时距离目标点还有一段距离。
看看实验结果
从实验结果可以看出，算法的性能很不稳定，而造成这一点的原因很可能是其收敛速度较慢，算法仍在收敛过程中，所以结果看上去很差。将最大迭代次数修改为100代，重新试验，其结果如下：
结果好了一些但还是难以接受，为什么烟花算法的结果不理想呢？
原因可能是保留机制（2.3节）的问题，烟花算法中保留火星的概率是根据该火星与其他火星的距离和，距离群体越大的个体被保留下的概率越大。这样做有什么好处呢？好处是火星相对分散，这是一个对抗局部最优的策略，但是，距离群体较远的个体是一个较差的个体的概率非常大，坏处就是，集中于当前最优位置的火星被保留的概率较小，算法的局部搜索能力将较弱。
实验二 . 随机选择的方式保留火星
为了加快烟花算法的收敛速度，增强局部搜索能力，我移除了标准烟花算法的选择过程，使用随机选择的方式保留火星，当然，最优个体依然会被保留至下一代。其他参数保持不变。
可以看出这次的图像相比实验一收敛速度快了不少，在迭代结束时已经相对在一个较小的区域。这次的结果也明显优于实验一。将选择过程改为随机选择后，由于较优的火星产生的较多且分布在自己周围，因此选择到这些较优的火星的概率也相对较大，算法的收敛速度相对较快。与此同时，算法跳出局部最优的能力比修改前要弱。
对于较简单的问题来说当然是随机选择收敛较快结果较好，而复杂的问题则需要更强的跳出局部最优能力。问题的关键仍然是，我们无法在一开始就知道问题的复杂程度。
实验三 .增加火星的种群数量，减少每代产生的正常火星总数
为什么要减少产生的正常火星数，这样算法搜索的次数减少了，效果不会更差吗？其实与直觉相反，减少正常火星总数，增加火星总群数，实际上是让较优的火星产生的正常火星被保留下来的概率变大了，这样也可以解决实验一中的问题，加快算法的收敛速度。
从图像中可以看出，算法在50代之前已经收敛，但是之后只在小范围内进行搜索。实验图像与之前的描述相符，收敛速度加快但是跳出局部最优能力减弱。看看实验结果，实验结果好了不少且结果更加稳定。
其实实验二与实验三，使用了不同的策略，但都达到了同样的目的——保留更多的优质火星到下一代，它们促进了局部搜索但是挤占了较劣火星的位置，削弱了种群的多样性。
每代留下的火星多了，图像看上去是不是更像烟花？
烟花算法的探究远不止如此，几年前作为一个较新的算法来学习时却已经有了大量的论文和书籍，可见大家对烟花算法已经有了较为深入的研究，而我能做的只是应用算法解决问题以及稍作改进让算法与问题的适应性更高。
烟花算法产生正常火星的过程为算法提供了搜索能力，产生特殊火星的过程和选择过程为算法提供了跳出局部最优的能力。但是个人认为选择过程与其他过程的适应性不是很好。标准的选择过程会丢失掉许多较优的个体，使之前产生的正常火星得到的成果没有保留。
烟花算法其实还有比较多的改进点，对算法产生最大的参数应该就是正常火星的总数以及振幅了。简单粗暴的改进：在每一代可以对这两个参数进行变化或者随机化，让算法的搜索能力与跳出局部最优能力在整个流程中动态变化，以均衡两种能力。
以下指标纯属个人yy,仅供参考
参考文献
Tan Y , Zhu Y . Fireworks Algorithm for Optimization[C]// Advances in Swarm Intelligence, First International Conference, ICSI 2010, Beijing, China, June 12-15, 2010, Proceedings, Part I. Springer-Verlag, 2010. 提取码：yaj0
目录
上一篇 优化算法笔记（十一）群搜索算法
下一篇 优化算法笔记（十三）鲸鱼算法
优化算法matlab实现（十二）烟花算法matlab实现
⑸ 优化算法笔记（七）差分进化算法
（以下描述，均不是学术用语，仅供大家快乐的阅读）
差分进化算法（Differential Evolution Algorithm，DE）是一种基于群体的进化算法，它模拟了群体中的个体的合作与竞争的过程。算法原理简单，控制参数少，只有交叉概率和缩放比例因子，鲁棒性强，易于实现。
差分进化算法中，每一个个体的基因表示待求问题的一个候选解。每次迭代将先进行变异操作，选择一个或多个个体的基因作为基，然后选择不同的个体的差分来构成差分基因，最后将作为基的基因与差分基因相加来得出新的个体。交叉操作将新的个体将于父代的对应个体交叉，然后进行选择操作，比较交叉后的个体与父代的对应个体，选择较优的个体保留至下一代。在迭代完成之后将选择种群中最优个体的基因作为解。
差分进化算法可以算是我所使用过的优化算法中大魔王级别的算法，虽然它每个方面都没有强到离谱，但是综合起来的效果好于大多数算法。它就像一个每个科目都能考到90分（百分制）的学生，虽然没门课都不是最优秀的，但是论综合，论总分，它有极大的概率是第一名。
在我研究优化算法的小路上，我的目标就是找到一个能打败大魔王或是能在大多数方面压制魔王的算法。
这次的主角就选魔王军吧（或者蚁王军，为了与蚁群算法区别还是叫魔王军吧），个体则称之为魔王兵。
魔王兵的能力取决于它们的基因，它们可以根据环境或者需要改变自己的基因使得自己更加强大，更方便的处理问题，问题的维度与基因维度相同。
表示第i个魔王兵在进化了第t次后的基因，该个体有D位基因。
与遗传算法同为进化算法的差分进化算法，它们的操作（算子）也都非常相似的，都是交叉，变异和选择，流程也几乎一样（遗传算法先交叉后变异，差分进化算法先变异后交叉）。
说到差分进化算法中的变异，我就想到一句论语 “三人行，必有我师焉。择其善者而从之，其不善者而改之。” ，其实这句论语已经向我们说明了差分进化算法的整个流程：
“三人行，必有我师焉”——变异，交叉。
“择其善者而从之，其不善者而改之”——选择。
差分进化算法中，当一个魔王兵变异时，它会先找来3个小伙伴，当然是随机找来3个小伙伴，避免同化。在一个小伙伴的基因上加上另外两个小伙伴基因之差作为自己的目标基因。其变异公式如下：
表示第i个魔王兵找到了编号为r1、r2和r3的三个魔王兵，当然了i、r1、r2、r3为互不相同的整数，F为缩放比例因子，通常 ，一般取F=0.5。 为第i个魔王兵交叉后的目标基因图纸，不过这是个半成品，再经过交叉后，目标基因图纸才算完成。
其实现在我们已经有了5个基因图纸了 ，接下来将进行交叉操作。由于变异操作，差分进化算法的种群中个体数至少为4，即魔王军中至少有4个小兵。
交叉操作中，魔王兵i会将目标基因图纸 进行加工得到 ，加工过程如下：
其中 。 为交叉概率，其值越大，发生交叉的概率越大，一般取 。 为{1,2,…,D}中的随机整数，其作用是保证交叉操作中至少有一维基因来自变异操作产生的基因，不能让交叉操作的努力白费。
从公式上可以看出交叉操作实际上是从变异操作得出的基因图纸上选择至少一位基因来替换自己的等位基因，得到最终的基因图纸。
选择操作相对简单，魔王兵i拿到了最终的基因图纸 ，大喊一声，进化吧，魔王兵i的基因改变了。它拿出了能力测量器fitness function,如果发现自己变强了，那么就将基因 保留到下一代，否则它选择放弃进化，让自己还原成 。
实验又来啦，还是那个实验 ，简单、易算、好画图。
实验1 ：参数如下
图中可以看出在第20代时，群体已经非常集中了，在来看看最终得出的结果。
这结果真是好到令人发指，恶魔在心中低语“把其他的优化算法都丢掉吧”。不过别往心里去，任何算法都有优缺点，天下没有免费的午餐，要想获得某种能力必须付出至少相应的代价。
实验2：
将交叉率CR设为0,即每次交叉只选择保留一位变异基因。
看看了看图，感觉跟实验1中相比没有什么变化，那我们再来看看结果。
结果总体来说比实验1好了一个数量级。为什么呢？个人感觉应该是每次只改变一位基因的局部搜索能力比改变多位基因更强。下面我们将交叉率CR设为1来看看是否是这样。
实验3：
将交叉率CR设为1,即每次交叉只选择保留一位原有基因。
实验3的图与实验1和实验2相比好像也没什么差别,只是收敛速度好像快了那么一点点。再来看看结果。
发现结果比实验2的结果还要好？那说明了实验2我得出的结论是可能是错误的，交叉率在该问题上对差分进化算法的影响不大，它们结果的差异可能只是运气的差异，毕竟是概率算法。
实验4：
将变异放缩因子设为0，即变异只与一个个体有关。
收敛速度依然很快，不过怎么感觉结果不对，而且个体收敛的路径好像遗传算法，当F=0，时，差分进化算法退化为了没有变异、选择操作的遗传算法，结果一定不会太好。
果然如此。下面我们再看看F=2时的实验。
实验5：
将变异放缩因子设为2。
实验5的图可以明显看出，群体的收敛速度要慢了许多，到第50代时，种群还未完全收敛于一点，那么在50代时其结果也不会很好，毕竟算法还未收敛就停止进化了。
结果不算很好但也算相对稳定。
通过上面5个实验，我们大致了解了差分进化算法的两个参数的作用。
交叉率CR，影响基因取自变异基因的比例，由于至少要保留一位自己的基因和变异的基因导致CR在该问题上对算法性能的影响不大（这个问题比较简单，维度较低，影响不大）。
变异放缩因子F，影响群体的收敛速度，F越大收敛速度越慢，F绝对值越小收敛速度越快，当F=0是群体之间只会交换基因，不会变异基因。
差分进化算法大魔王已经如此强大了，那么还有什么可以改进的呢？当然有下面一一道来。
方案1 .将3人行修改为5人行，以及推广到2n+1人行。
实验6：
将3人行修改为5人行，变异公式如下：
五人行的实验图看起来好像与之前并没有太大的变化，我们再来看看结果。
结果没有明显提升，反而感觉比之前的结果差了。反思一下五人行的优缺点，优点，取值范围更大，缺点，情况太多，减慢搜索速度。
可以看出算法的收敛速度比之前的变慢了一点，再看看结果。
比之前差。
差分进化算法的学习在此也告一段落。差分进化算法很强大，也很简单、简洁，算法的描述都充满了美感，不愧是大魔王。不过这里并不是结束，这只是个开始，终将找到打败大魔王的方法，让新的魔王诞生。
由于差分进化算法足够强，而文中实验的问题较为简单导致算法的改进甚至越改越差（其实我也不知道改的如何，需要大量实验验证）。在遥远的将来，也会有更加复杂的问题来检验魔王的能力，总之，后会无期。
以下指标纯属个人yy,仅供参考
目录
上一篇 优化算法笔记（六）遗传算法
下一篇 优化算法笔记（八）人工蜂群算法
优化算法matlab实现（七）差分进化算法matlab实现
⑹ 优化算法笔记（十四）水波算法
（以下描述，均不是学术用语，仅供大家快乐的阅读）
水波算法（Water wave optimization）是根据水波理论提出的优化算法。什么是水波理论？简单来说就是水波的宽度越小，其频率越高，频率与水波宽度的平方根成反比（具体细节我也不懂，物理方面的）。水波算法也算是一种受物理现象（理论）启发而提出的算法，提出时间并不长，还有大量的研究和应用可以深入进行。
在水波算法中，水波有三种形式来对空间进行搜索。1.传播，2.折射，3.碎浪。传播即水波向周围扩散开来，折射是水波的高度趋近与0时改变了传播的方向（我是真的理解不能，光可以折射，水也能折射的咯？），碎浪即水波的高度较高时，水波破碎形成浪花。可以看出水波的传播是贯穿整个算法流程的，而折射只会发生在水波高度减少至0时，碎浪则发生在水波过高时。
（强行解释最为致命，作者开心就好）。
将每一个水波想象成一个独立的个体，那么每个水波将拥有3个属性：位置X，波长 以及波高h。
在每一次迭代过程中，每个水波都会通过传播的形式来对空间进行搜索同时水波的高度h会减少1。其位置更新公式如下：
其中 为该水波的波长， 为当前搜索空间的上下界。 的值会随着迭代的进行而改变：
其中 为波长的衰减系数， 为一个较小的数以保证分母不为0。
每次传播后，如果当前的水波优于传播前的水波，则传播到该位置，否则波浪的高度h会减少1，即：
上式中适应度函数值越大，表明位置越优。
在一个水波进行传播之后，该水波有可能进行折射。每次传播，水波的高度h会减少1，当h减少到0时，该水波将发生折射，同时其高度和波长也会改变，折射及高度波长改变公式如下：
折射后的位置正态分布在以当前水波和最优水波中点为均值，当前水波与最优水波距离为方差的位置。
在折射后水波的高度将会重新初始化为最大高度：
折射后， 会重新计算该水波的波长 ：
在水波进行传播之后，到达了一个优于当前最优水波的位置，则该水波将会进行碎浪，并将当前最优水波传播到碎浪产生的位置。
碎浪位置的产生公式如下：
k为一个随机数，每次碎浪将会随机选择k个维度来进行改变。 为一个常数。如果碎浪得到的结果优于当前最优水波，则改变当前最优水波到碎浪的位置。
是不是感觉流程图有点复杂，其实算法没有那么复杂，整个过程一共只有三个操作，一个水波在一代中最多只会执行两种方式。每个水波可能的搜索方式有三种：1.传播，2.先传播后碎浪，3.先传播后折射。
适应度函数
由于水波算法收敛较慢，所以最大迭代次数使用100。
实验一 ：
从图像中可以看出，个体在向着中心不断的收敛，其收敛速度不算很快。其结果也相对稳定。
从图像可以推测出，水波算法的核心参数其实是水波的最大高度，水波的最大高度决定了算法的收敛速度和精度，就像人工蜂群算法中的蜜源最大开采次数一样。若一个个体连续多代没有找到优于当前的位置，它将改变自己的策略。
从算法的具体实现可以看出，传播是一个在自身周围的全局搜索的过程，折射则属于一个大概率局部搜索，小概率跳出局部最优的操作，而碎浪则是进一步的局部搜索。那么水波的最大高度越高，则水波算法的全局搜索能力越强，但收敛速度越慢，反正，算法的收敛速度越快。
实验二 ：减少算法的水波最大高度至5
从图像可以看出算法的收敛速度明显比实验一要快，在第30代时已经快收敛于一个点了。从结果来看，实验二的结果也优于实验一，由于水波的最大高度较小，算法进行碎浪和折射的次数增加了，即算法的局部搜索能力增强了。
同样之前的算法中也提到过多次，收敛速度越快，群体越容易聚集到同一个区域，算法也越容易陷入局部最优，而适应度函数对优化算法来说是一个黑盒函数，无法得知其复杂程度。所以对于实验所使用的较为简单的测试函数，水波的最大高度越小，结果的精度越高，而面对未知的问题时，应该选取较大的水波高度以避免陷入局部最优。同样物极必反，水波的最大高度过大可能会使算法的局部搜索较弱，我们可以选取一个动态的水波最大高度。
实验三 ：水波最大高度随迭代次数增加由12递减至2
看图像和结果感觉和实验一差别不大，唯一的区别就是最优值要好于实验一。在这个简单的测试函数中无法表现出其应有的特点，由于算法后期群体已经较为集中，也无法明显的看出算法的收敛速度是否随着迭代次数增加而加快。
水波算法也是一个新兴算法，算法的流程较为复杂且可修改参数较多。算法的流程和思想与蜂群算法有点类似，但水波算法更为复杂。水波算法的三个搜索策略，传播是一个全局搜索行为，也有一定的跳出局部最优能力；折射则是一个局部搜索过程，由于正态分布的原因，有较小的概率产生跳出局部最优的操作；碎浪则是一个更进一步的局部搜索，只在最优位置附近搜索。
其搜索策略使算法在整个流程中都拥有全局搜索和局部搜索能力，全局搜索与局部搜索之间的平衡由水波的最大高度决定，最大高度约大，全局搜索能力越强，收敛速度越慢，反之，局部搜索能力越强，收敛速度越快。
以下指标纯属个人yy,仅供参考
参考文献
Zheng, Yu-Jun. Water wave optimization: A new nature-inspired metaheuristic[J]. Computers & Operations Research, 2015, 55:1-11. 提取码：fo70
目录
上一篇 优化算法笔记（十三）鲸鱼算法
下一篇 优化算法笔记（十五）蝙蝠算法
优化算法matlab实现（十四）水波算法matlab实现
⑺ PSO优化方向
1. PSO收敛快，特别是在算法的早期，但存在着精度较低，易发散等缺点。加速系数、最大速度等参数太大，粒子可能错过最优解--------------->不收敛； 收敛的情况下，由于所有粒子都向最优的方向飞去，所有粒子趋向同一化（失去多样性）--------->使得 后期收敛速度明显变慢，搜索能力变弱 ，同时算法收敛到一定精度时，无法继续优化。
2. 缺乏数学理论支持，PSO算法本质上是一种随机搜索算法，因此可靠性上让人存疑；
3. 寻找一种好的拓扑结构，加强PSO算法的泛化能力；
4. 平衡全局搜索和局部搜索能力；
（1）粒子群初始化：粒子群初始化对算法性能有一定的影响，分为粒子位置初始化和速度初始化。
粒子群 位置 初始化的理想效果：初始种群尽可能 均匀覆盖整个 搜索空间。
一、不推荐的初始化 ：a. 均匀分布随机数
缺点：1. 对搜索空间的覆盖不够好；
2. 当维度D增大时候，所有的粒子都倾向于靠近搜索空间的边缘：
b. 伪随机数初始化：造成粒子在参数空间的不均匀分布和聚集效应；
二、推荐的初始化 ：a. 基于centroidal voronoi tessellations (CVTs)的种群初始化方法（这东西是啥没搞懂）；
b. 采用正交设计方法对种群进行初始化；
c. 类随机采样方法中的sobol序列：使得粒子群在参数空间更加均匀；
d. Hammersley方法：感觉这个类似于类随机采样方法（具体我也没搞清楚）；
e. 将粒子建立为带电（positive charged）的模型，通过建立一个平衡方程，求解该方程的最小解获得粒子初始化位置；
f. 设置偏向的随机分布（推荐） ：即：我们通过对评价函数等一系列先验信息进行分析，得出最优解的可能存在空间范围，然后在这些范围内，着重撒点。就算再不济，也可以根据评价函数遵循Nearer is Better class（最优解更加可能在搜索空间的中心位置准则），在搜索空间的中心位置着重撒点。比如：
粒子群 速度 初始化：主要有如下五种方式：（根据实验表明，One-rand的效果最好。喂！！！这里One-rand的表达式是不是写错了啊？）
（2）领域拓扑：粒子的拓扑，决定了粒子所接受到的信息来源。
一、全局模型gbest：最早的粒子群优化版本是全局PSO，使用全局拓扑结构，社会 只能 通过种群中， 最优的那个粒子 ，对每个粒子施加影响。
1. 优点：具有较快的收敛速度。
2. 缺点：粒子间的交流不够充分，但更容易陷入局部极值。
二、局部模型lbest：采用每个粒子仅在一定的邻域内进行信息交换，，粒子之间的交流相对比较缓慢。
1. 优点：粒子更容易搜索问题空间中的不同地区。
2. 缺点：信息传递缓慢，设计相对复杂。
3. 分类：被动模型：微观领域、宏观领域、维度划分；主动模型。
（1）微观邻域：细分到每个粒子。空间邻域(spatial neighborhood)、性能空间(performance space)邻域、社会关系邻域(sociometric neighborhood)。
a. 空间邻域：直接在搜索空间按粒子间的距离(如欧式距离)进行划分。在搜索初始阶段，将邻域定义为每个粒子自身；随着迭代次数的增加，将邻域范围逐渐扩展到整个种群。
b. 性能空间领域：根据性能指标(如适应度、目标函数值)划分的邻域，如：适应度距离比值(fitness-distance-ratio)来选择粒子的相邻粒子。
c. 社会关系邻域： 按粒子存储阵列的索引编号进行划分，主要有：环形拓扑(ring or circle topology)、轮形拓扑(wheel topology)或星形拓扑(star topology)、塔形拓扑(pyramid topology)、冯－诺以曼拓扑(Von Neumann topology)以及随机拓扑(random topology)等。（随机拓扑往往对大多数问题能表现出较好的性能，其次是冯－诺以曼拓扑。）
（2）宏观邻域：对群体进行划分。比如：使用簇分析将整个粒子群划分为多个簇，然后用簇中心代替带收缩因子PSO中的粒子历史最佳位置或群体历史最佳位置；根据粒子相似性动态地将粒子群体按种类划分为多个子种群，再以每个子种群的最佳个体作为每个粒子的邻域最佳位置；划分一个主群体，多个仆群体，仆群体进行独立的搜索，主群体在仆群体提供的最佳位置基础上开展搜索；每间隔一定代数将整个群体随机地重新划分；每个粒子除了自身和邻域最佳历史位置外，还学习邻域内其他粒子的 成功经验（只学好的，不学坏的） 等等；
（3）维度划分：想法源自于：搜索空间维数较高时往往容易遭受“维数灾”的困扰。假设粒子群的整体维度为D，则可以将D划分成不同的部分，比如划分成k份，使用不同的群体，分别优化不同的维度。
（4）主动模型：主动改变粒子邻域空间，避免碰撞和拥挤。比如：将粒子分为带电粒子和自然粒子，带电粒子接近会产生排斥；为每个粒子引入与邻近粒子距离成反比的自组织危险度，距离越近危险度越高，当危险度达到一定阈值，对粒子进行重新初始化，或者弹开；为粒子赋一个半径，以检测两个粒子是否会发生碰撞，并且采取碰撞-弹开方式将其分离。
（3）参数选择：三种参数：惯性权重或收敛因子、最大速度、两个加速因子。
一、惯性权重：
a. 惯性权重大：加强PSO 全局 搜索能力；惯性权重小：加强PSO 局部 搜索能力；
b. 矛盾点：初始惯性权重大，局部搜索能力差，可能错过最优点；后期，惯性权重小，全局搜索能力不行，导致整个粒子群就陷入局部最优解。
c. 优化方向：在适当的时候降低权重w，平衡全局和局部搜索能力；
d. 优化建议：w随着更新代数的增加从0.9线性递减到0.4；
二、压缩因子：
a. 优势：惯性常数方法通常采用惯性权值随更新代数增加而递减的策略，算法后期由于惯性权值过小，会失去探索新区域的能力，而收缩因子方法则不存在此不足
b. 优化建议：通常φ取4.1，χ得0.729。
三、最大速度的选择：为了抑制粒子更新的无规律的跳动，速度往往被限制在[-Vm,Vm]
a. Vm增大，有利于全局 探索（exploration） ，但可能越过全局最优解；Vm减小，有利于局部 开发（exploitation） ，但可能陷入局部最优；
b. 优化建议：一般设定为问题空间的10%~20%；或者动态调整Vm，比如：根据群体最佳适应和最差适应来进行调整；
四、两个加速常数：加速常数C1和C2分别用于控制粒子指向自身或邻域最佳位置的运动。
a. C1增大，粒子全局搜索能力好；C2增大，粒子向着最优靠拢局部能力好，但粒子会过早收敛；
b. 优化建议：C1 = C2 = 2.0，并且C1+C2 <= 4.0;或者根据自适应调整，比如随着迭代次数增加，减小C1增大C2；
（4）混合法：PSO与其他方法结合。
这点我觉得，主要根据个人的学习积累来操作。考虑方向：增加粒子群的局部搜索能力。
⑻ 有人知道影响自适应LMS算法收敛性、收敛速度、失调量的因素么
一种具有双瞬变因子的LMS自适应滤波算法�
曾召华 刘贵忠 马社祥
（西安交通大学信息与通信工程研究所 西安710049）
【摘要】 作者在文献〔4〕中提出了一种改进的瞬变步长SPLMS自适应滤波算法。本文在SPLMS算法的基础上，进一步提出一种基于瞬变步长、瞬变平滑因子的双瞬变SPLMS算法—DSPLMS算法。该算法除具有常规LMS算法简单的优点外，还具有更高的起始收敛速率、更小的权失调噪声和更大的抑噪能力。文中重点讨论瞬变步长、瞬变平滑因子的变化特性。计算机仿真结果支持了理论分析。
【关键词】 自适应滤波器，失调噪声，收敛速度，最小均方误差，瞬变因子
1 引言
自适应滤波器及其相应算法是多年来人们广泛研究的课题。基于Widrow－Hoff标准的LMS算法和其相应的自适应滤波器以其算法和结构简单，便于实时信号处理等优点，在不同领域得到了最为广泛的应用。而为克服常规的固定步长LMS或牛顿LMS（Newton LMS，即NLMS）自适应算法在收敛速率、跟踪速率与权失调噪声之间要求上存在的较大矛盾，人们发展了各种各样的改进型LMS算法，如基于瞬变步长LMS自适应滤波算法〔1～6〕、基于正交变换（DCT、FFT、小波变换、子带滤波）的新型LMS均衡算法〔7～8〕。基于模糊判断的自适应LMS系统识别和基于最小四次均方误差的LMS自适应平稳收敛算法〔9～10〕。在所有改进型LMS算法中，瞬变步长LMS自适应滤波算法是研究最为广泛的一类LMS自适应滤波算法。本文算法也是基于瞬变因子的一种改进LMS自适应滤波算法。
2 SPLMS算法分析及问题的提出
在文献〔4〕中，作者对上述方案进行了大量的计算机仿真和理论分析，结果表明：（1）上述诸种算法的收敛速率与系统输入信噪比SNR直接相关，信噪比SNR越高，它们的收敛速率普遍提高；随着信噪比SNR的降低，它们的收敛速率减慢，甚至出现发散现象，因此它们必须在弱干扰下完成规一化起动，即在起始过程中噪声要相当小，否则效果不佳。（2）在上述所有算法中，由于采用瞬时平方误差性能函数e2k来代替均方误差性能函数，所以其算法的权值收敛过程表现为加权矢量的平均值变化规律和由于噪声引起的随机起伏项的叠加。因此，噪声方差越大，则随机起伏项越大，表现为权值振动也就越大。（3）为了追求更快的收敛性，往往增大μ和M，但滤波器阶数越高，步长因子μ和输入功率越大，就便得失调系数也越大。在有限次数起动迭代过程中，也就很难收敛到较稳态值，所以必须寻求更佳的瞬态步长算法。
文献〔4〕在准最小均方（Pseudo－LMS，即PLMS）误差算法基础上通过采用滑动时间窗，减少PLMS算法起动过程的计算量；同时在权值迭代中加一平滑迭代而使PLMS算法具备全局较强的抗噪性能，较快速收敛性能而提出了SPLMS算法，即：
其中rk为M阶滤波器输入信号的功率估值；Wk为滤波器的第k步M维最优权矢量估值；Xk是滤波器输入信号的M维输入数据矢量；dk为希望输出；μk为滤波器第k步瞬态步长。切换条件中，阈值μ类似于LMS算法的步长因子μL，满足：
μL＜μ＜1／trR，R＝E〔XkXTk〕（7）
为待定的算法常数，是μk变化的动态平衡点。而α是一常数为平滑因子，它决定上一次的权值变化对本次权值更新的影响程度。k0是采用式（2）规一化启动后，算法收敛到较稳态时的步数。式（4）是μk下降的递推算法，式（5）是μk上升的平滑递推算法。λ为上升的速度因子，满足0＜λ＜1。在实际应用中，考虑到学习过程的启动速度，一般取较大的λ值，即：
0．9＜λ＜1，k0＝25～35，｜α｜＜0．3（8）
SPLMS算法的实质是：在开始k0步中，采用启动速度较快的MLMS（Mend LMS）算法收敛到相对较稳态的状态；然后在k≥k0＋1过程中，采用瞬态步长μk来训练算法。而μk根据不同的切换条件将围绕μ作升降变化，其迭代计算主要表现为不降即升的动态过程。α主要根据经验来取值，输入数据的非平稳性越大，噪声方差越大时，增大α可明显抑制振动，从而加速收敛过程；在噪声小时减小α。
但SPLMS算法也有一明显不足，即α主要根据经验来取值，没有理论上的确切依据。α取值不当，反而容易造成算法收敛性能更差，甚至发散的现象。从理论上分析，α与瞬态步长μk和输出误差ek（文中定义为：ek＝dk－WTk Xk）应有一定关系。在算法启动阶段，ek较大，为追求启动速度而常取较大步长μk，但μk越大，权失调系数也就越大，有时反而起不到应有的作用，这时就应相应增加α值来平滑权失调噪声；在算法渐趋稳定，步长μk渐趋于常数，ek渐趋于0，此时α也应渐趋于0。综合起来就是：α应随步长μk和误差ek瞬时变化而变化，也应是一瞬变因子。本文重点就是寻求瞬变因子αk的数学表达式以满足上述分析的要求。
3 改进的双瞬变因子SPLMS算法——DSPLMS算法
3．1 μk的变化特性
从式（4）和式（5）可以看出，在k≥k0＋1过程中，μk根据不同的切换条件将围绕μ作升降变化，μk的迭 代计算主要表现为不降即升的动态过程。对于式（5），设k≥kr时，μk＜μ，则在k≥kr＞k0＋1的上升过程中：
即上升速度按指数衰减，使趋于平衡点μ的上升速度迅速减小。其变化过程类似于一电阻电容串联电路上电容的充电过程。对式（4），由于μk＝μk－1／（1＋Rk），Rk＞0，即使很小的Rk经过一步迭代就足以使μk＜μ，再次切换到上升过程。当rk较大时，下降形成的负脉冲也较大。
综上所述，在k≥k0＋1的收敛过程中，μk的时变特性等价于幅值极不对称的随机正负尖脉冲序列组成的瞬态分量和直流分量μ的线性叠加。瞬态分量的负脉冲强度与rk瞬值对应，有利于抑制局部自激或短暂发散，减小权矢量噪声，提高稳定度。在rk较小、算法渐趋于稳定时，瞬变分量趋于0，μk～μ。
3．2 αk的变化特性
定义：ΔWk＝Wk＋1－Wk为自适应滤波器的权系数增量；ξ为均方误差性能函数，ξ＝E〔ek〕2，ek＝dk－WTk Xk为输出误差，则SPLMS算法的权系数更新公式由式（1）可重写为：
Wk＋1＝Wk－μk�＾Wξk＋αΔWk－1（10）
其中�Wξ为ξ的梯度函数，＾W为�Wξ的第k步估计。由式（10）的系数更新公式，我们可写出均方误差性能函数的表达式：
式中上标T表示矢量的转置。若用一矢量�＾Wζk＋1去左乘式（10），则可得到：
＾Wξk＋1Wk＋1＝�＾Wζk＋1Wk－μk�＾Wζk＋1�＾Wζk＋�＾Wζk＋1αΔWk－1（13）
利用式（12）的结论，可将式（13）化简为：
�＾TWζk＋1ΔWk＝0（14）
由于参量μk和α均为实的标量因子，故式（14）又可写成：
（μk�＾TWζk＋1）（αΔWk）＝0（15）
式（15）清楚地表明：在SPLMS算法中，自适应滤波器的权系数在迭代过程中，其均方误差性能函数的梯度估值与权系数增量始终存在一个正交关系。ΔWk－1对ΔWk的调节作用是在当前梯度估值方向上，给出与梯度估值方向正交矢量，并以这两个矢量所构成的合矢量来改变权系数空间的权重。
对于FIR结构的LMS自适应系统而言，其均方误差性能函数在平稳输入时为一个二次型函数，在收敛点附近仍可视为一个二次型函数，故有：
ξ（Wk＋1）＝WTk RWk－2WTk P＋C（16）
式中R＝E〔XTk Xk〕为输入信号的自相关矩阵，P＝E〔dkXk〕为所需信号与输入信号的互相关矢量，C＝E〔d2k〕，则由式（16）可得：
将式（17）代入式（18），则式（18）可变形为：
式（19）就是本文给出的瞬变平滑因子αk的数学表达式。显然，它满足前面分析时所提出的要求，且在算法达到稳态收敛时，满足：
limk→∞αk＝0（20）
3．3 改进的双瞬变SPLMS算法——DSPLMS算法
用式（19）中αk的表达式替换式（1）中的α，就得到本文提出的具有双瞬变因子的LMS算法——DSPLMS算法，即
Wk＋1＝Wk＋2μk（dk－WTk Xk）Xk＋αk（Wk－Wk－1）（21）
μk＝λ／（1＋2λrk），0≤k≤k0（22）
由式（19）、（20）可知，αk是一个与μk成正比且具有衰减性的瞬变因子，从而使本文提出的DSPLMS算法比SPLMS算法更能快速稳定收敛；与常规LMS算法相比，其性能有极大的提高，为实时信号处理提供了一个较好的算法。
4 计算机仿真
仿真实验的结构如图1所示，其中dk为随机输入信号，nk为高斯白噪声，ek为输出误差，xk为自适应滤波器的输入，yk为滤波器输出，此时xk＝dk＋nk。
在图2中，dk是均值为0、方差为1的高斯白噪声；nk是与dk不相关的均值为0、方差为1的高斯白噪声；滤波器参数：M＝32，λ＝0．9，μL＝0．005，μ＝0．01，α＝0．1。在图3中，nk为均值为0、方差为0．1的高斯白噪声，其它参数同图2。图2、3为分别采用LMS、SPLMS和DSPLMS算法进行滤波的学习曲线比较图。
从图2（强干扰启动）和图3（较弱干扰启动）中可以看出：在强干扰下，DSPL MS 具有比SPLMS好、比LMS好得多的启动速度和收敛速度；而在弱干扰下，DSPLMS仍具有比SPLMS快、比LMS快得多的启动速度。从图中同时还可看出：DSPLMS与SPLM S具有几乎相同的收敛速度，它们的收敛速度比LMS快得多。
5 结语
加进瞬变平滑项的规一化起动，使DSPLMS具有更高的起始收敛速度、更小的权失调噪声和更大的抑噪能力；在平稳连接之后的稳态过程中，该算法趋于步长为μ的LMS算法性能，但由于瞬变分量负脉冲的作用，在相近的权失调量下可按式（7）取较大的μ值，增强算法对时变参数过程的跟踪处理能力；输入数据的非平稳性越大，噪声方差越大时，加进的瞬变平滑项使权失调噪声减小，从而使本文提出的DSPLMS算法比SPLMS算法更能快速稳定地收敛；与常规LMS算法相比，其性能有极大的提高，可以明显抑制振动，从而加速收敛过程。
网址：http://www.bjx.com.cn/files/WX/XDLD/2000-1/14.htm