想知道优化算法是什么？
优化算法是通过改善计算方式来最小化或最大化损失函数E(x)。模型内部有些参数是用来计算测试集中目标值Y的真实值和预测值的偏差程度的，基于这些参数就形成了损失函数E(x)，比如说，权重(W)和偏差(b)就是这样的内部参数，一般用于计算输出值，在训练神经网络模型时起到主要作用。优化算法分的分类一阶优化算法是使用各参数的梯度值来最小化或最大化损失函数E(x），最常用的一阶优化算法是梯度下降。函数梯度导数dy/dx的多变量表达式，用来表示y相对于x的瞬时变化率。二阶优化算法是使用了二阶导数也叫做Hessian方法来最小化或最大化损失函数，由于二阶导数的计算成本很高，所以这种方法并没有广泛使用。
优化算法是什么呢？
优化算法是指对算法的有关性能进行优化，如时间复杂度、空间复杂度、正确性、健壮性。大数据时代到来，算法要处理数据的数量级也越来越大以及处理问题的场景千变万化。为了增强算法的处理问题的能力，对算法进行优化是必不可少的。算法优化一般是对算法结构和收敛性进行优化。同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。遗传算法遗传算法也是受自然科学的启发。这类算法的运行过程是先随机生成一组解，称之为种群。在优化过程中的每一步，算法会计算整个种群的成本函数，从而得到一个有关题解的排序，在对题解排序之后，一个新的种群----称之为下一代就被创建出来了。首先，我们将当前种群中位于最顶端的题解加入其所在的新种群中，称之为精英选拔法。新种群中的余下部分是由修改最优解后形成的全新解组成。常用的有两种修改题解的方法。其中一种称为变异，其做法是对一个既有解进行微小的、简单的、随机的改变；修改题解的另一种方法称为交叉或配对，这种方法是选取最优解种的两个解，然后将它们按某种方式进行组合。尔后，这一过程会一直重复进行，直到达到指定的迭代次数，或者连续经过数代后题解都没有改善时停止。
粒子群优化算法
姓名：杨晶晶 学号：21011210420 学院：通信工程学院
【嵌牛导读】
传统的多目标优化方法是将多目标问题通过加权求和转化为单目标问题来处理的,而粒子算法主要是解决一些多目标优化问题的（例如机械零件的多目标设计优化）,其优点是容易实现,精度高,收敛速度快。
【嵌牛鼻子】粒子群算法的概念、公式、调参以及与遗传算法的比较。
【嵌牛提问】什么是粒子群算法？它的计算流程是什么？与遗传算法相比呢？
【嵌牛正文】
1. 概念
粒子群优化算法(PSO：Particle swarm optimization) 是一种进化计算技术（evolutionary computation），源于对鸟群捕食的行为研究。
粒子群优化算法的基本思想：是通过群体中个体之间的协作和信息共享来寻找最优解。
PSO的优势：在于简单容易实现并且没有许多参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。
2. 算法
2.1 问题抽象
鸟被抽象为没有质量和体积的微粒(点)，并延伸到N维空间，粒子i在N维空间的位置表示为矢量Xi＝(x1，x2，…，xN)，飞行速度表示为矢量Vi＝(v1，v2，…，vN)。每个粒子都有一个由目标函数决定的适应值(fitness value)，并且知道自己到目前为止发现的最好位置(pbest)和现在的位置Xi。这个可以看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(gbest)(gbest是pbest中的最好值)，这个可以看作是粒子同伴的经验。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。
2.2 更新规则
PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest，gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。
公式(1)的第一部分称为【记忆项】，表示上次速度大小和方向的影响；公式(1)的第二部分称为【自身认知项】，是从当前点指向粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的部分；公式(1)的第三部分称为【群体认知项】，是一个从当前点指向种群最好点的矢量，反映了粒子间的协同合作和知识共享。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。
以上面两个公式为基础，形成了PSO的标准形式。
公式(2)和 公式(3)被视为标准PSO算法。
2.3 标准PSO算法流程
标准PSO算法的流程：
1）初始化一群微粒(群体规模为N)，包括随机位置和速度；
2）评价每个微粒的适应度；
3）对每个微粒，将其适应值与其经过的最好位置pbest作比较，如果较好，则将其作为当前的最好位置pbest；
4）对每个微粒，将其适应值与其经过的最好位置gbest作比较，如果较好，则将其作为当前的最好位置gbest；
5）根据公式(2)、(3)调整微粒速度和位置；
6）未达到结束条件则转第2）步。
迭代终止条件根据具体问题一般选为最大迭代次数Gk或(和)微粒群迄今为止搜索到的最优位置满足预定最小适应阈值。
公式(2)和(3)中pbest和gbest分别表示微粒群的局部和全局最优位置。
当C1＝0时，则粒子没有了认知能力，变为只有社会的模型(social-only)：
被称为全局PSO算法。粒子有扩展搜索空间的能力，具有较快的收敛速度，但由于缺少局部搜索，对于复杂问题
比标准PSO 更易陷入局部最优。
当C2＝0时，则粒子之间没有社会信息，模型变为只有认知(cognition-only)模型：
被称为局部PSO算法。由于个体之间没有信息的交流，整个群体相当于多个粒子进行盲目的随机搜索，收敛速度慢，因而得到最优解的可能性小。
2.4 参数分析
参数：群体规模N，惯性因子 ，学习因子c1和c2，最大速度Vmax，最大迭代次数Gk。
群体规模N：一般取20～40，对较难或特定类别的问题可以取到100～200。
最大速度Vmax：决定当前位置与最好位置之间的区域的分辨率(或精度)。如果太快，则粒子有可能越过极小点；如果太慢，则粒子不能在局部极小点之外进行足够的探索，会陷入到局部极值区域内。这种限制可以达到防止计算溢出、决定问题空间搜索的粒度的目的。
权重因子：包括惯性因子和学习因子c1和c2。使粒子保持着运动惯性，使其具有扩展搜索空间的趋势，有能力探索新的区域。c1和c2代表将每个粒子推向pbest和gbest位置的统计加速项的权值。较低的值允许粒子在被拉回之前可以在目标区域外徘徊，较高的值导致粒子突然地冲向或越过目标区域。
参数设置：
1)如果令c1＝c2＝0，粒子将一直以当前速度的飞行，直到边界。很难找到最优解。
2)如果＝0，则速度只取决于当前位置和历史最好位置，速度本身没有记忆性。假设一个粒子处在全局最好位置，它将保持静止，其他粒子则飞向它的最好位置和全局最好位置的加权中心。粒子将收缩到当前全局最好位置。在加上第一部分后，粒子有扩展搜索空间的趋势，这也使得的作用表现为针对不同的搜索问题，调整算法的全局和局部搜索能力的平衡。较大时，具有较强的全局搜索能力；较小时，具有较强的局部搜索能力。
3)通常设c1＝c2＝2。Suganthan的实验表明：c1和c2为常数时可以得到较好的解，但不一定必须等于2。Clerc引入收敛因子(constriction factor) K来保证收敛性。
通常取为4.1,则K＝0.729.实验表明，与使用惯性权重的PSO算法相比，使用收敛因子的PSO有更快的收敛速度。其实只要恰当的选取和c1、c2，两种算法是一样的。因此使用收敛因子的PSO可以看作使用惯性权重PSO的特例。
恰当的选取算法的参数值可以改善算法的性能。
3. PSO与其它算法的比较
3.1 遗传算法和PSO的比较
1)共性：
(1)都属于仿生算法。
(2)都属于全局优化方法。
(3)都属于随机搜索算法。
(4)都隐含并行性。
(5)根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等。
(6)对高维复杂问题，往往会遇到早熟收敛和收敛 性能差的缺点，都无法保证收敛到最优点。
2)差异：
(1)PSO有记忆，好的解的知识所有粒子都保 存，而GA（Genetic Algorithm），以前的知识随着种群的改变被改变。
(2)PSO中的粒子仅仅通过当前搜索到最优点进行共享信息，所以很大程度上这是一种单共享项信息机制。而GA中，染色体之间相互共享信息，使得整个种群都向最优区域移动。
(3)GA的编码技术和遗传操作比较简单，而PSO相对于GA，没有交叉和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。
(4)应用于人工神经网络(ANN)
GA可以用来研究NN的三个方面：网络连接权重、网络结构、学习算法。优势在于可处理传统方法不能处理的问题，例如不可导的节点传递函数或没有梯度信息。
GA缺点:在某些问题上性能不是特别好；网络权重的编码和遗传算子的选择有时较麻烦。
已有利用PSO来进行神经网络训练。研究表明PSO是一种很有潜力的神经网络算法。速度较快且有较好的结果。且没有遗传算法碰到的问题。
优化算法笔记（五）粒子群算法（3）
(已合并本篇内容至粒子群算法（1）)
上一节中，我们看到小鸟们聚集到一个较小的范围内后，不会再继续集中。这是怎么回事呢？
猜测：
1.与最大速度限制有关，权重w只是方便动态修改maxV。
2.与C1和C2有关，这两个权重限制了鸟儿的搜索行为。
还是上一节的实验， 。现在我们将maxV的值有5修改为50，即maxV=50，其他参数不变。参数如下
此时得到的最优位值的适应度函数值为0.25571,可以看出与maxV=5相比，结果差了很多而且小鸟们聚集的范围更大了。
现在我们设置maxV=1，再次重复上面的实验，实验结果如下：
这次最终的适应度函数值为，比之前的结果都要好0.00273。从图中我们可以看出，小鸟们在向一个点集中，但是他们飞行的速度比之前慢多了，如果问题更复杂，可能无法等到它们聚集到一个点，迭代就结束了。
为什么maxV会影响鸟群的搜索结果呢？
我们依然以maxV=50为例，不过这次为了看的更加清晰，我们的鸟群只有2只鸟，同时将帧数放慢5倍以便观察。
思路一：限制鸟的最大飞行速率,由于惯性系数W的存在，使得控制最大速率和控制惯性系数的效果是等价的，取其一即可。
方案1：使惯性系数随着迭代次数增加而降低，这里使用的是线性下降的方式，即在第1次迭代，惯性系数W=1,最后一次迭代时，惯性系数W=0，当然，也可以根据自己的意愿取其他值。
实验参数如下：
小鸟们的飞行过程如上图，可以看到效果很好，最后甚至都聚集到了一个点。再看看最终的适应度函数值8.61666413451519E-17，这已经是一个相当精确的值了，说明这是一个可行的方案，但是由于其最后种群过于集中，有陷入局部最优的风险。
方案2：给每只鸟一个随机的惯性系数，那么鸟的飞行轨迹也将不再像之前会出现周期性。每只鸟的惯性系数W为（0,2）中的随机数（保持W的期望为1）。
实验参数如下：
可以看到小鸟们并没有像上一个实验一样聚集于一个点，而是仍在一个较大的范围内进行搜索。其最终的适应度函数为0.01176，比最初的0.25571稍有提升，但并不显著。什么原因造成了这种情况呢？我想可能是由于惯性系数成了期望为1的随机数，那么小鸟的飞行轨迹的期望可能仍然是绕着一个四边形循环，只不过这个四边形相比之前的平行四边形更加复杂，所以其结果也稍有提升，当然对于概率算法，得到这样的结果可能仅仅是因为运气不好
我们看到惯性系数W值减小，小鸟们聚拢到一处的速度明显提升，那么，如果我们去掉惯性系数这个参数会怎么样呢。
方案3：取出惯性系数，即取W=0，小鸟们只向着那两个最优位置飞行。
可以看见鸟群们迅速聚集到了一个点，再看看得到的结果，最终的适应度函数值为2.9086886073362966E-30，明显优于之前的所有操作。
那么问题来了，为什么粒子群算法需要一个惯性速度，它的作用是什么呢？其实很明显，当鸟群迅速集中到了一个点之后它们就丧失了全局的搜索能力，所有的鸟会迅速向着全局最优点飞去，如果当前的全局最优解是一个局部最优点，那么鸟群将会陷入局部最优。所以，惯性系数和惯性速度的作用是给鸟群提供跳出局部最优的可能性，获得这个跳出局部最优能力的代价是它们的收敛速度减慢，且局部的搜索能力较弱（与当前的惯性速度有关）。
为了平衡局部搜索能力和跳出局部最优能力，我们可以人为的干预一下惯性系数W的大小，结合方案1和方案2，我们可以使每只鸟的惯性系数以一个随机周期，周期性下降，若小于0，则重置为初始值。
这样结合了方案1和方案2的惯性系数，也能得到不错的效果，大家可以自己一试。
思路二：改变小鸟们向群体最优飞行和向历史最优飞行的权重。
方案4：让小鸟向全局最优飞行的系数C2线性递减。
小鸟们的飞行过程与之前好像没什么变化，我甚至怀疑我做了假实验。看看最终结果，0.7267249621552874，这是到目前为止的最差结果。看来这不是一个好方案，让全局学习因子C2递减，势必会降低算法的收敛效率，而惯性系数还是那么大，小鸟们依然会围绕历史最优位置打转，毕竟这两个最优位置是有一定关联的。所以让C1线性递减的实验也不必做了，其效果应该与方案4相差不大。
看来只要是惯性系数不变怎么修改C1和C2都不会有太过明显的效果。为什么实验都是参数递减，却没有参数递增的实验呢？
1.惯性系数W必须递减，因为它会影响鸟群的搜索范围。
2.如果C1和C2递增，那么小鸟的惯性速度V势必会跟着递增，这与W递增会产生相同的效果。
上面我们通过一些实验及理论分析了粒子群算法的特点及其参数的作用。粒子群作为优化算法中模型最简单的算法，通过修改这几个简单的参数也能够改变算法的优化性能可以说是一个非常优秀的算法。
上述实验中，我们仅分析了单个参数对算法的影响，实际使用时（创新、发明、写论文时）也会同时动态改变多个参数，甚至是参数之间产生关联。
实验中，为了展现实验效果，maxV取值较大，一般取值为搜索空间范围的10%-20%，按上面（-100,100）的范围maxV应该取值为20-40，在此基础上，方案1、方案2效果应该会更好。
粒子群算法是一种概率算法，所以并不能使用一次实验结果来判断算法的性能，我们需要进行多次实验，然后看看这些实验的效果最终来判断，结果必须使用多次实验的统计数据来说明，一般我们都会重复实验30-50次，为了发论文去做实验的小伙伴们不要偷懒哦。
粒子群算法的学习目前告一段落，如果有什么新的发现，后面继续更新哦！
以下指标纯属个人yy,仅供参考
目录
上一篇 优化算法笔记（四）粒子群算法（2）
下一篇 优化算法笔记（六）遗传算法
