局部最优算法

❶ 怎样解决遗传算法的局部最优问题

这个看看遗传算法的专着吧。
局部收敛，就是所谓的“早熟现象”是遗传算法的一个很让人头疼的问题。对应的措施，我举个例子，可以是提高变异算子的变异概率。变异算子是跳出局部收敛的重要操作算子，当然，遗传算法有很多的改进类型。这里不多说了，我介绍本书，叫《MATLAB遗传算法工具箱及应用》，雷英杰，西安电子科技大学出版社

❷ matlab全局优化与局部优化

在实际的工作和生活过程中，优化问题无处不在，比如资源如何分配效益最高，拟合问题，最小最大值问题等等。优化问题一般分为尺核局部最优和全局最优，局部最优，就是在函数值空间的一个有限区域内寻找最小值；而全局最优，是在函数值空间整个区域寻找最小值问题。

matlab中的提供的传统优化工具箱（Optimization Tool），能实现局部最优，但要得全局最优，则要用全局最优化算法（Global Optimization Tool），主要包括：
GlobalSearch 全局搜索和 MultiStart 多起点方法产生若干起始点，然后它们用局部求解器去找到起始点吸引盆处的最优点。

ga 遗传算法用一组起始点（称为种群），通过迭代从种群中产生更好的点，只要初始种群覆盖几个盆，GA就能检查几个盆。

simulannealbnd 模拟退火完成一个随机搜索，通常，模拟退火算法接受一个点，只要这个点比前面那个好，它也偶而接受一个比较糟的点，目的是转向不同的盆。

patternsearch 模式搜索算法在接受一个点之前要看看其附近的一组点。假如附近的某些点属于不同的盆，模式搜索算法本质上时同时搜索若干个盆。

下面我就一些具体例子，来说明各种优化方法：

可以看出，初值x0不同，得到的结果侍孙截然不同，这说明这种求解器，能寻找局部最优，但不一定是全局最优，在起点为8时，取得全局最优。
我们换一种求解器：fminbound,这种求解器不需要给点初值。

因此全局最优的方法能够获取全局最优。

结果：最小二乘拟合结果误差较大

可以陵谈掘看出全局优化结果较好，误差较小。
这种算法的运行时间：Elapsed time is 6.139324 seconds.
使用并行计算的方式解决

结果：14 out of 100 local solver runs converged with a positive local solver exit flag.
Elapsed time is 4.358762 seconds.Sending a stop signal to all the labs ... stopped.可以看出，运行时间减少，提高了效率。

这种方法只能寻找局部最优。
现在用全局优化算法：

❸ 请大神解释一下在医学图像配准中，什么叫做局部优化算法，什么叫做全局优化算法

算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。
一、遗传算法的目的
典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：
考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有
bi∈{0,1}L (3-84)
给定目标函数f，有f(bi)，并且
0<f(bi)<∞
同时
f(bi)≠f(bi+1)
求满足下式
max{f(bi)|bi∈{0,1}L} (3-85)
的bi。
很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。
二、遗传算法的基本原理
长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：
1．选择(Selection)
这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproction)。
2．交叉(Crossover)
这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。
3．变异(Mutation)
这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。
遗传算法的原理可以简要给出如下：
choose an intial population
determine the fitness of each indivial
perform selection
repeat
perform crossover
perform mutation
determine the fitness of each indivial
perform selection
until some stopping criterion applies
这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。
三、遗传算法的步骤和意义
1．初始化
选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。
2．选择
根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。
给出目标函数f，则f(bi)称为个体bi的适应度。以

(3-86)
为选中bi为下一代个体的次数。
显然．从式(3—86)可知：
(1)适应度较高的个体，繁殖下一代的数目较多。
(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
3．交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。
例如有个体
S1=100101
S2=010111
选择它们的左边3位进行交叉操作，则有
S1=010101
S2=100111
一般而言，交叉幌宰P。取值为0.25—0.75。
4．变异
根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
例如有个体S＝101011。
对其的第1，4位置的基因进行变异，则有
S'=001111
单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。
5．全局最优收敛(Convergence to the global optimum)
当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
图3—7中表示了遗传算法的执行过程。

❹ 如何判断萤火虫算法陷入局部最优

FA主要是利用萤火虫发光的特点进行随机优化。利用萤火虫个体模拟解空间的可行解，目标函数值表示萤火虫的亮度，较亮的萤火虫会吸引其他个体向这个方向进行位置移动，他们之间的吸引力与距离成反比，如果某个萤火虫周围没有更亮的个体，它选择不移动或者随机变换位置。两只萤火虫之间的吸引力计算公式如下： 贝塔0是指距离为0时的吸引力值，rij表示两只萤火虫之间的欧式距离，拉姆塔一般表示对光的吸收率，通常取1. 萤火虫会飞向更亮的萤火虫位置处，其位置更新公式为：
其中阿尔法是[0,1]之间的随机数，另一个因子是服从均匀分布的随机因子。 算法流程如下 1、初始化各个参数和每只萤火虫的位置 2、计算每对萤火虫之间的吸引力，选取萤火虫移动的方向 3、更新整个种群中萤火虫的位置，更新萤火虫的最优位置 4、判断是否达到终止条件，是就结束算法，否则就返回步骤2继续进行

❺ 优化算法总结

本文介绍一下机器学习和深度学习中常用的优化算法和优化器以及一些其他我知道的优化算法,部分算法我也没有搞懂,就先记录下来以后慢慢研究吧.*_*.

1.梯度下降算法(Gradient Descent)

梯度下降法可以参考我另一篇文章 机器学习-线性回归 里的讲解,这里就不在重复叙述.这里需要强调一下,深度学习里常用的SGD,翻译过来是随机梯度下降,但是实质是mini-batch梯度下降(mini-batch-gd),或者说是两者的结合更准确一些.

SGD的优点是,算法简单,计算量小,在函数为凸函数时可以找到全局最优解.所以是最常用的优化算法.缺点是如果函数不是凸函数的话,很容易进入到局部最优解而无法跳出来.同时SGD在选择学习率上也是比较困难的.

2.牛顿法

牛顿法和拟牛顿法都是求解无约束最优化问题的常用方法,其中牛顿法是迭代算法,每一步需要求解目标函数的海森矩阵的逆矩阵,计算比较复杂.

牛顿法在求解方程根的思想:在二维情况下,迭代的寻找某一点x,寻找方法是随机一个初始点x_0,目标函数在该点x_0的切线与x坐标轴的交点就是下一个x点,也就是x_1.不断迭代寻找x.其中切线的斜率为目标函数在点x_0的导数(梯度),切必过点(x_0,f(x_0)).所以迭代的方程式如图1,为了求该方程的极值点,还需要令其导数等于0,也就是又求了一次导数,所以需要用到f(x)的二阶导数.

在最优化的问题中,牛顿法提供了一种求解的办法. 假设任务是优化一个目标函数f, 求函数ff的极大极小问题, 可以转化为求解函数f导数等于0的问题, 这样求可以把优化问题看成方程求解问题(f的导数等于0). 剩下的问题就和牛顿法求解方程根的思想很相似了.

目标函数的泰勒展开式:

化简后:

这样就得到了与图1相似的公式,这里是二维的,在多维空间上,求二阶导数就是求海森矩阵,因为是分母,所以还需要求海森矩阵的逆矩阵.

牛顿法和SGD的区别:

牛顿法是二阶求导,SGD是一阶求导,所以牛顿法要收敛的更快一些.SGD只考虑当前情况下梯度下降最快的方向,而牛顿法不仅考虑当前梯度下降最快,还有考虑下一步下降最快的方向.

牛顿法的优点是二阶求导下降速度快,但是因为是迭代算法,每一步都需要求解海森矩阵的逆矩阵,所以计算复杂.

3.拟牛顿法(没搞懂,待定)

考虑到牛顿法计算海森矩阵比较麻烦,所以它使用正定矩阵来代替海森矩阵的逆矩阵,从而简化了计算过程.

常用的拟牛顿法有DFP算法和BFGS算法.

4.共轭梯度法(Conjugate Gradient)

共轭梯度法是介于最速下降法与牛顿法之间的一个方法,它仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点,又避免了牛顿法计算海森矩阵并求逆的缺点.共轭梯度法不仅是解决大型线性方程组最有用的方法之一,也是解大型非线性最优化最有效的算法之一.

5.拉格朗日法

参考SVM里的讲解 机器学习-SVM

6.动量优化法(Momentum)

动量优化法主要是在SGD的基础上,加入了历史的梯度更新信息或者说是加入了速度更新.SGD虽然是很流行的优化算法,但是其学习过程很慢,因为总是以同样的步长沿着梯度下降的方向.所以动量是为了加速学习的方法.

其中第一行的减号部分是计算当前的梯度,第一行是根据梯度更新速度v,而α是新引进的参数,在实践中,α的一般取值为 0.5,0.9 和 0.99.和学习率 一样,α 也会随着时间不断调整.一般初始值是一个较小的值,随后会慢慢变大.

7.Nesterov加速梯度(NAG, Nesterov accelerated gradient)

NAG是在动量优化算法的基础上又进行了改进.根据下图可以看出,Nesterov 动量和标准动量之间的区别体现在梯度计算上, Nesterov 动量中,梯度计算在施加当前速度之后.因此,Nesterov 动量可以解释为往标准动量方法中添加了一个校正因子

8.AdaGrad算法

AdaGrad算法,自适应优化算法的一种,独立地适应所有模型参数的学习率,缩放每个参数反比于其所有梯度历史平均值总和的平方根.具有代价函数最大梯度的参数相应地有个快速下降的学习率,而具有小梯度的参数在学习率上有相对较小的下降.通俗一点的讲,就是根据实际情况更改学习率,比如模型快要收敛的时候,学习率步长就会小一点,防止跳出最优解.

其中g是梯度,第一行的分母是计算累计梯度的平方根, 是为了防止分母为0加上的极小常数项,α是学习率.

Adagrad的主要优点是不需要人为的调节学习率,它可以自动调节.但是依然需要设置一个初始的全局学习率.缺点是随着迭代次数增多,学习率会越来越小,最终会趋近于0.

9.RMSProp算法

RMSProp修改 AdaGrad 以在非凸设定下效果更好,改变梯度积累为指数加权的移动平均.AdaGrad旨在应用于凸问题时快速收敛.

10.AdaDelta算法

11.Adam算法

Adam是Momentum和RMSprop的结合体,也就是带动量的自适应优化算法.

12.Nadam算法

13.模拟退火算法

14.蚁群算法

15.遗传算法

动量是为了加快学习速度,而自适应是为了加快收敛速度,注意学习速度快不一定收敛速度就快,比如步长大学习速度快,但是很容易跳出极值点,在极值点附近波动,很难达到收敛.

未完待定....

参考:

《统计学习方法》  李航    着

《深度学习》  花书

❻ 优化算法笔记（二十五）飞蛾扑火算法

（以下描述，均不是学术用语，仅供大家快乐的阅读）
飞蛾扑火算法（Moth-Flame Optimization）是受飞蛾围绕火焰飞行启发而提出的算法。算法提出于2015年5月（投稿日期），虽可算作一个新算法，不过无数研究者就像飞蛾见了火一样，发表了如此之多的论文，惊了。
飞蛾扑火算法中有两种个体，飞蛾和火焰，飞蛾选择并围绕火焰以螺线方式飞行搜索，搜索完后，火焰将移动位置，以保持火焰是飞蛾和火焰群体中最优的位置。
算法的流程简单，螺线搜索在之前的鲸鱼算法中也出现过，这里会较为详细的记录记录螺线搜索的具体情况。

显然,飞蛾扑火算法中有两种角色,飞蛾与火焰。初始时飞蛾与火焰的数量均为N。为了方便查看，将飞蛾的位置表示为XM ，火焰的位置为 XF。
初始化时，会在解空间内初始化N个飞蛾与M(M=N)个火焰。在算法过程中，飞蛾将会围绕它所选择的火焰飞行，之后将这N个飞蛾与M个火焰按优劣排序，并将M个火焰移动到较优的前M个个体的位置。其中火焰的数量M会随着迭代次数的改变而不断变化，论文中阶梯递减至1。
算法的主要步骤如下：
1. 飞蛾选择火焰（将火焰分配给飞蛾）。
2. 飞蛾围绕火焰飞行。
3. 移动火焰到相应位置。
从步骤可以看出，算法中飞蛾的飞行是一种无贪心算法的操作，而火焰的移动则是一种变相的贪心操作。

初始化时，会有N个飞蛾和N个火焰（M=N）,故每只飞蛾都可以选择互不相同的火焰。随着迭代次数的递增，火焰的数量会递减。其数量根据以下公式计算得出：

其图像如下图所示：

其实就是将火焰数量M线性递减到1，由于火焰数量是正数，故图像呈阶梯状。
随着迭代次数增加，火焰数量递减，每只飞蛾无法选择互不相同的火焰，此时可以随机选择火焰或者飞蛾群体按顺序依次往后选取，类似于取模。两种方式的差别不大。

该步骤是算法的核心计算步骤。
对于飞蛾 ,它围绕火焰 飞行后到达的新位置XM_new根据以下公式计算得出：

其图像如下

而算法中的飞行轨迹应该是这样的：

取出一维看看

其中i为计算次数。

图像就是cos函数图像的变形。考虑到飞蛾与火焰之间的距离会越来越短，其飞行图像应该与上图相反，即振幅越来越小，局部搜索能力越来越强。

N只飞蛾围绕M个火焰飞行后，会到N个新位置，计算这N个新位置的适应度值，将这N个新位置与M个火焰这（N+M）个位置按优劣排序，并将其中较优的M个位置作为下一轮中火焰的位置。

其飞蛾扑火算法流程图如下：

由于飞蛾扑火算法可以说是对蚁狮算法和鲸鱼算法的结合，这里就看看算法的图像，不再做其他处理了。
适应度函数 。

实验一：

从结果看来，飞蛾扑火算法的性能稳定也优于蚁狮算法，从图像看算法收敛性不如蚁狮算法但局部搜索性能要强于蚁狮算法。
可见螺线的局部搜索能力还是强于随机游走的，不过其全局搜索要弱于随机游走。相比蚁狮算法，飞蛾扑火算法更容易陷入局部最优（其实与蚁狮差不多，只要火焰/蚁狮陷入局部最优基本完蛋，不过蚁狮数量恒定，火焰数量递减，所有火焰更容易局部最优）。

飞蛾扑火算法是根据飞蛾围绕火焰飞行的行为而提出的算法。算法的结构比较简单，与蚁狮算法类似，只是搜索步骤将随机游走替换成了螺线搜索（当然还有跟多细节上的不同，可以看看原文）。算法的局部搜索能力非常强，依靠螺线就提供了全局搜索和局部搜索能力，其全局搜索和局部搜索能力强弱由其极半径决定，算法中由b决定。不过算法缺少跳出局部最优的能力，在平滑函数中的效果非常好，在局部最优较多的函数中效果中规中矩。

参考文献
Mirjalili S . Moth-flame optimization algorithm: A novel nature-inspired heuristic paradigm[J]. Knowledge-Based Systems, 2015, 89(NOV.):228-249.. 提取码：koy9
以下指标纯属个人yy,仅供参考

目录
上一篇 优化算法笔记（二十四）帝王蝶算法
下一篇 优化算法笔记（二十六）和声搜索算法