算法红点

1. a星算法找不到路径是会遍历全图么

C语言的A星叫A*算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。 如在一张dota地图上，英雄从一个地方走动到地图上另一个点，它选择最优路线的算法。

绿点是开始点，红点是目的地，黑色区域是不可通过区域。 通过A*算法，黄色线段就是找到的最优路线。

其实用漫水算法也能找这路线啊。这A星算法优点在于处理速度快，并不是像漫水一样，各个方向都在寻找。

2. 基于DEAP库的Python进化算法从入门到入土--（六）多目标遗传算法 NSGA-II

在很多实际工程问题中，我们的优化目标不止一个，而是对多个目标函数求一个综合最优解。例如在物流配送问题中，不仅要求配送路径最短，还可能需要参与运输车辆最少等。

多目标优化问题的数学模型可以表达为：

多目标优化问题通常具有如下特点：

对于多目标优化问题，传统方法是将原问题通过加权方式变换为单目标优化问题，进而求得最优解。该方法具有两大问题：

遗传算法具有多点多方向搜索的特征，在一次搜索中可以得到多个Pareto最优解，因此更适合求解多目标优化问题。

而当前用于求解多目标优化问题的遗传算法一般有两种思路：

NSGA-II(nondominated sorting genetic algorithm II)是2002年Deb教授提出的NSGA的改进型，这个算法主要解决了第一版NSGA的三个痛点：

针对这三个问题，在NSGA-II中，Deb提出了快速非支配排序算子，引入了保存精英策略，并用“拥挤距离”(crowding distance)替代了共享(sharing)。

在介绍NSGA-II的整体流程之前，我们需要先了解快速非支配排序和拥挤距离的定义。

解的支配关系与Pareto最优解

下图表示了解之间的支配和强支配关系：

下图表示了一个最小化问题解集中的Pareto最优解和Pareto弱最优解：

快速非支配排序步骤

快速非支配排序就是将解集分解为不同次序的Pareto前沿的过程。

它可以描述为：

DEAP实现

DEAP内置了实现快速非支配排序操作的函数 tools.emo.sortNondominated

tools.emo.sortNondominated(indivials, k, first_front_only=False)

参数：

返回：

拥挤距离的定义

在NSGA II中，为了衡量在同一个前沿中各个解质量的优劣，作者为每个解分配了一个拥挤距离。其背后的思想是 让求得的Pareto最优解在objective space中尽量分散 。也就有更大可能让解在Pareto最优前沿上均匀分布。

DEAP实现

DEAP中内置了计算拥挤距离的函数 tools.emo.assignCrowdingDist

tools.emo.assignCrowdingDist(indivials)

参数：

返回：

比较操作

根据快速非支配排序和拥挤距离计算的结果，对族群中的个体进行排序：

对两个解 ，

在每个迭代步的最后，将父代与子代合为一个族群，依照比较操作对合并后族群中的个体进行排序，然后从中选取数量等同于父代规模的优秀子代，这就是NSGA-II算法中的精英保存策略。

DEAP实现

DEAP内置了实现NSGA-II中的基于拥挤度的选择函数 tools.selNSGA2 用来实现精英保存策略：

tools.selNSGA2(indivials, k, nd='standard')

参数：

返回：

这里选用ZDT3函数作为测试函数，函数可表达为：

其Pareto最优解集为

这里为了方便可视化取 。

下图给出了该函数在Decision Space和Objective Space中的对应：

其pareto最优解在Objective Space中如下图红点所示：

将结果可视化：

得到：

可以看到NSGA-II算法得到的Pareto最优前沿质量很高：最优解均匀分布在不连续前沿的各个线段上；同时在最优前沿以外没有个体存在。

3. 优化算法笔记（十七）万有引力算法

（以下描述，均不是学术用语，仅供大家快乐的阅读）
万有引力算法（Gravitational Search Algorithm）是受物体之间的万有引力启发而提出的算法。算法提出于2008（2009）年，时间不长，不过相关的文章和应用已经相对较多，也有不少的优化改进方案。
万有引力算法中，每一个物体的位置代表了一个可行解，而物体的质量则反映了该位置的好坏，位置越好的物体的质量越大，反之物体的质量越小（质量由适应度值计算出，不是直接相等）。物体在解空间中的运动方式由其他物体的引力决定，质量越大的物体，在同等引力作用下的加速度较小，所以单位时间内的速度也相对较小，位移距离较短，反之加速度和速度都较大，位移距离较长。故可以简单的认为， 位置越优的个体的移动速度越慢，位置越差的个体的移动速度越快 。

万物之间皆有万有引力，不过在我们谈到万有引力之时，对象大多是天体，否则万有引力太小可以忽略不计。所有这次我们的主角就是天体了。（总不可能是苹果吧）。

每一个天体都有个属性：位置X，质量M，加速度A，以及速度V，还有适应度值F。
在D维空间内有N个天体，其位置为

，加速度

，速度

，其适应度值为

。

第i个天体的质量则是根据其适应度值计算得出：

其中M为天体的质量在群体重质量中的占比， 分别表示全局最差天体的适应度值和全局最优个体的适应度值。
可以看出，处于最优位置的天体的质量m为1，最差位置的天体的质量m为0。当最优天体和最差天体重合时，所有的天体的质量m都为1。

由万有引力计算公式和加速度公式可以计算出当前天体收到另一个天体万有引力而产生的加速度：

其中R表示第i个天体和第j个天体之间的欧式距离，aij为天体i在第d维上受到天体j的万有引力而产生的加速度,ai为第i个天体受到的其他所有天体万有引力的合力产生的加速度。G为万有引力常量，可以根据一下公式计算：

其中G0为初始值，T为最大迭代次数。

计算出了天体的加速度，则可以根据当前速度计算出下一步天体的运行速度以及天体下一步的位置。

这一步比较简单与粒子群、蝙蝠等有速度的算法一致。

可以看出万有引力算法的流程异常的简单，与经典的粒子群差不多。万有引力算法也可以看做是一个优化改进版的粒子群，不过设计比较巧妙，引入的质量、加速度等概念，但实现仍然很简单。万有引力算法的效果如何，在下一节将会进行实验测试。

适应度函数 。
实验一：

从图像中可以看出，各个天体都在不停的运动，由于没有贪心算法（优于当前值才改变位置）的加入，所以个天体有可能运动到比原先位置更差的地方，而且其收敛速度也比较快。
从结果上看，似乎还不错，受到最差值的影响均值也相对较大，算法结果的稳定性不是太好。
直觉上感觉算法有点问题。根据物理得来的直觉告诉我，这些天体会相互靠近，所以，它们不会集中到它们所构成的凸包之外， 凸实心物体的质心不会跑到该物体的外部 。做个试验验证一下，将测试函数的最优解设置到一个极端的位置。
实验二 ： 适应度函数

这次最优解位置在（90,90）处，该点有很大概率出现在初始天体所围成的凸多边形外。

从图像中可以看出，在天体们还没有到达最优位置附近（右下角的红点）时，它们已经收敛于一个点，之后则很难再次向最优解靠经。看结果可以发现几乎每一次实验的结果都不太好，算法果然有点问题，不过问题不大。
万有引力出现这种现象可能有两个原因： 1.算法收敛的太快 ，还未对全局进行充分搜索之时就收敛到了一点，收敛到一点后无法再运到。 2.算法没有跳出局部最优的策略 ，万有引力作用下的天体慢慢聚集到奇点，形成黑洞，无法从中逃离。
那接下来，对万有引力算法的改进方向也比较明确了：1.减缓其收敛速度，2增加跳出局部最优操作，使之逃离黑洞。
看看万有引力常量G的函数图像

将万有引力常量的值修改为随着迭代次数线性下降，从图像中可以看出，效果还是比较明显的，天体在不断的运动，最后才收敛、聚集于一起。从实验结果也可以看出，算法相对稳定。结合图像可以知道，改进后，算法的收敛性下降，但全局搜索能力有较大的提升，算法的结果不会很差但是精度较低。

将万有引力常量的下降趋势放缓为原来的1/4，从图像中可以看出，算法的收敛速度非常快，也得到了较好的结果，相比线性下降，算法有着更好的精度，不足之处则是没有跳出局部最优的操作，收敛过快也容易陷入局部最优。
不知道原文为什么让万有引力常量G的如此快的降到0，明明降的更慢能有更好的全局搜索能力，但精度可能较差。猜测如果精度较差则在测试函数结果和曲线上比不赢对比的其他算法，论文没法发了。其使用的测试函数的最优解大多处于解空间的中心位置附近，即很少出现最优解在天体所围成的凸多面体之外的情况，而实际问题中我们是无法预知最优解在个位置的。
接下来，将试着为万有引力算法加入一点跳出局部最优的操作。

实验四 ：改进,新增以下规则及操作
在实验二的条件下
1 . 处于最优位置的天体保持自己的位置不动.
2 . 如果某一个天体的运动后的位置优于当前全局最优个体的位置则将当前的最优个体初始化到解空间的随机位置.(将被自己干掉的大哥流放)。
3 . 如果触发了规则2，将所有的个体的以迭代次数重置为0，即计算G=G0*e^(-20t/T)中的t置为0，重新计算万有引力常量，若未触发条件2则t=t+1。

从图像上看，算法的全局搜索能力有大幅的增强，并且已经集中到了最优解的附近，而且由于加入了“流放”这一跳出局部最优的操作，可以看出，不断的有新的个体出现在距最优位置较远的位置。不过收敛速度有所下降，因此局部搜索能力有一定减弱。
看结果，好像没有实验三那么好，但与实验二相比，已经有了很大的提升，而且有了跳出局部最优的操作，结果也相对稳定。
上述的实验仅仅是对直观猜想的实现，如果想以此为改进点，还要对其进行大量的调优，相信会有不错的结果。

万有引力算法根据万有引力提出，结合了牛顿第二定律，可以说其操作步骤与真实的物理规律非常的贴切。不过就像前文说过，受物理现象启发而来的优化算法其性能是未知的，因为它们不具备智能，只有着规律，有规律就会存在弱点，就会有搜索盲区。宇宙那么大，肯定存在没有任何天体到达过的空间。
不过由于万有引力算法流程简单，理解方便，其优化方案和能改进的地方相对较多。万有引力算法的收敛速度过快，导致其全局搜索能力较弱而局部搜索能力很强，容易陷入局部最优。根据其特点，我们可以降低其收敛速度或者增加跳出局部最优操作，来平衡算法的各个性能。

参考文献
Rashedi E , Nezamabadi-Pour H , Saryazdi S . GSA: A Gravitational Search Algorithm[J]. Information Sciences, 2009, 179(13):2232-2248. 提取码：xhpa

以下指标纯属个人yy,仅供参考

目录
上一篇 优化算法笔记（十六）混合蛙跳算法
下一篇 优化算法笔记（十八）灰狼算法

优化算法matlab实现（十七）万有引力算法matlab实现