㈠ 优化算法是什么
什么是智能优化算法 10分
智能优化算法是一种启发式优化算法，包括遗传算法、蚁群算法、禁忌搜索算法、模拟退火算法、粒子群算法等。·智能优化算法一般是针对具体问题设计相关的算法，理论要求弱，技术性强。一般，我们会把智能算法与最优化算法进行比较，相比之下，智能算浮速度快，应用性强。
传统优化算法和现代优化算法包括哪些.区别是什么
1. 传统优化算法一般是针对结构化的问题，有较为明确的问题和条件描述，如线性规划，二次规划，整数规划，混合规划，带约束和不带约束条件等，即有清晰的结构信息；而智能优化算法一般针对的是较为普适的问题描述，普遍比较缺乏结构信息。
2. 传统优化算法不少都属于凸优化范畴，有唯一明确的全局最优点；而智能优化算法针对的绝大多数是多极值问题，如何防止陷入局部最优而尽可能找到全局最优是采纳智能优化算法的根本原因：对于单极值问题，传统算法大部分时候已足够好，而智能算法没有任何优势；对多极值问题，智能优化算法通过其有效设计可以在跳出局部最优和收敛到一个点之间有个较好的平衡，从而实现找到全局最优点，但有的时候局部最优也是可接受的，所以传统算法也有很大应用空间和针对特殊结构的改进可能。
3. 传统优化算法一般是确定性算法，有固定的结构和参数，计算复杂度和收敛性可做理论分析；智能优化算法大多属于启发性算法，能定性分析却难定量证明，且大多数算法基于随机特性，其收敛性一般是概率意义上的，实际性能不可控，往往收敛速度也比较慢，计算复杂度较高。
最新的优化算法是什么？
这个范围太广了吧？列出来一篇文献综述都列不完
多目标优化算法的多目标是什么意思
多目标优化的本质在于，大多数情况下，某目标的改善可能引起其他目标性吵灶能的降低，同时使多个目标均达到最优是不可能的，只能在各目标之间进行协调权衡和折中处理，使所有目标函数尽可能达到最优，而且问题的最优解由数量众多，甚至无穷大的Pareto最优解组成。
编程中的优化算法问题
1. 算法优化的过程是学习思维的过程。学习数学实质上就是学习思维。也就是说数学教育的目的不仅仅是要让学生掌握数学知识（包括计算技能），更重要的要让学生学会数学地思维。算法多样化具有很大的教学价值，学生在探究算法多样化的过程中，培养了思维的灵活性，发展了学生的创造性。在认识算法多样化的教学价值的同时，我们也认识到不同算法的思维价值是不相等的。要充分体现算法多样化的教育价值，教师就应该积极引导学生优化算法，把优化算法的过程看作是又一次发展学生思维、培养学生能力的机会，把优化算法变成学生又一次主动建构的学习活动。让学生在优化算法的过程中，通过对各种算法的比较和分析，进行评价，不仅评价其正确升枝扮性——这样做对吗？而且评价其合理性——这样做有道理吗？还要评价其科学性——这样做是最好的吗？这样的优化过程，对学生思维品质的提高无疑是十分有用的，学生在讨论、交流和反思的择优过程中逐步学会“多中择优，优中择简”的数学思想方法。教师在引导学生算法优化的过程中，帮助学生梳理思维过程，总结学习方法，养成思维习惯，形成学习能力，长此以往学生的思维品质一定能得到很大的提高。2. 在算法优化的过程中培养学生算法优化搭厅的意识和习惯。意识是行动的向导，有些学生因为思维的惰性而表现出算法单一的状态。明明自己的算法很繁琐，但是却不愿动脑做深入思考，仅仅满足于能算出结果就行。要提高学生的思维水平，我们就应该有意识的激发学生思维和生活的联系，帮助他们去除学生思维的惰性，鼓励他们从多个角度去思考问题，然后择优解决；鼓励他们不能仅仅只关注于自己的算法，还要认真倾听他人的思考、汲取他人的长处；引导他们去感受各种不同方法的之间联系和合理性，引导他们去感受到数学学科本身所特有的简洁性。再算法优化的过程中就是要让学生感受计算方法提炼的过程，体会其中的数学思想方法，更在于让学生思维碰撞，并形成切合学生个人实际的计算方法，从中培养学生的数学意识，使学生能自觉地运用数学思想方法来分析事物，解决问题。这样的过程不仅是对知识技能的一种掌握和巩固，而且可以使学生的思维更开阔、更深刻。3. 算法优化是学生个体学习、体验感悟、加深理解的过程。算法多样化是每一个学生经过自己独立的思考和探索，各自提出的方法，从而在群体中出现了许多种算法。因此，算法多样化是群体学习能力的表现，是学生集体的一题多解，而不是学生个体的多种算法。而算法的优化是让学生在群体比较的过程中优化，通过交流各自得算法，学生可以互相借鉴，互相吸收，互相补充，在个体感悟的前提下实施优化。因为优化是学生对知识结构的再构建过程，是发自学生内心的行为和自主的活动。但是，在实施算法最优化教学时应给学生留下一定的探索空间，以及一个逐渐感悟的过程。让学生在探索中感悟，在比较中感悟，在选择中感悟。这样，才利于发展学生独立思考能力和创造能力。4. 优化算法也是学生后继学习的需要。小学数学是整个数学体系的基础，是一个有着严密逻辑关系的子系统。算法教学是小学数学教学的一部分，它不是一个孤立的教学点。从某一教学内容来说，也许没有哪一种算法是最好的、最优的，但从算法教学的整个系统来看，必然有一种方法是最好的、最优的，是学生后继学习所必需掌握的。在算法多样化的过程中，当学生提出各种算法后，教师要及时引导学生进行比较和分析，在比较和分析的过程中感受不同策略的特点，领悟不同方法的算理，分析不同方法的优劣，做出合理的评价，从而选择具有普遍意义的、简捷的、并有利于后继学习的最优方法。5. 优化也是数学学科发展的动力。数学是一门基础学科，是一门工具学科，它的应用十分广泛。数学之所以有如此广泛的应用......>>
现在哪些智能优化算法比较新
智能优化算法是一种启发式优化算法，包括遗传算法、蚁群算法、禁忌搜索算法、模拟退火算法、粒子群算法等。·智能优化算法一般是针对具体问题设计相关的算法，理论要求弱，技术性强。一般，我们会把智能算法与最优化算法进行比较，
最新的智能优化算法有哪些呢，论文想研究些新算法，但是不知道哪些算法...
答：蚁群其实还是算比较新的。 更新的也只是这些算法的最后改进吧。演化算法就有很多。随便搜一篇以这些为标题，看06年以来的新文章就可以了。 各个领域都有的。否则就是到极限，也就没有什么研究前景了。
算法实现函数优化是什么意思
比如给一个函数 f(x1,x2)=x1^2+x2^2，求这个函数最小数值。。。
数学上，我们一般都是求偏导，然后一堆的，但是算法上，我们只要使用梯度下降，几次迭代就可以解决问题。。。
优化算法停止条件是什么?
适应度越大，解越优。
判断是否已得到近似全局最优解的方法就是遗传算法的终止条件。 在最大迭代次数范围内可以选择下列条件之一作为终止条件:
1. 最大适应度值和平均适应度值变化不大、趋于稳定;
2. 相邻GAP代种群的距离小于可接受值，参考“蒋勇，李宏.改进NSGA-II终止判断准则[J].计算机仿真.2009. Vol.26 No.2”
智能优化算法中cell是什么意思
智能优化主要是用来求最优解的，通过多次迭代计算找出稳定的收敛的最优解或近似最优解，例如复杂的单模态或多模态函数的求最值问题。
㈡ 常用优化器算法归纳介绍
优化器是神经网络训练过程中，进行梯度下降以寻找最优解的优化方法。不同方法通过不同方式（如附加动量项，学习率自适应变化等）侧重于解决不同的问题，但最终大都是为了加快训练速度。
这里就介绍几种常见的优化器，包括其原理、数学公式、核心思想及其性能；
核心思想： 即针对每次输入的训练数据，计算输出预测与真值的Loss的梯度；
从表达式来看，网络中参数的更新，是不断向着最小化Loss函数的方向移动的：
优点:
简单易懂，即对于相应的最优解（这里认为是Loss的最小函数），每次变量更新都是沿着局部梯度下降最快的方向，从而最小化损失函数。
缺点:
不同于标准梯度下降法（Gradient Descent）一次计算所有数据样本的Loss并计算相应的梯度，批量梯度下降法（BGD, Batch Gradient Descent）每次只取一个小批次的数据及其真实标签进行训练，称这个批次为mini-batch；
优点：
缺点：
随机梯度下降法的 batch size 选择不当可能导致模型难以收敛；由于这种方法是在一次更新中，就对整个数据集计算梯度，所以计算起来非常慢，遇到很大量的数据集也会非常棘手，而且不能投入新数据实时更新模型。
我们会事先定义一个迭代次数 epoch，首先计算梯度向量 params_grad，然后沿着梯度的方向更新参数 params，learning rate 决定了我们每一步迈多大。
Batch gradient descent 对于凸函数可以收敛到全局极小值，对于非凸函数可以收敛到局部极小值。
和 BGD 的一次用所有数据计算梯度相比，SGD 每次更新时对每个样本进行梯度更新，对于很大的数据集来说，可能会有相似的样本，这样 BGD 在计算梯度时会出现冗余，而 SGD 一次只进行一次更新，就没有冗余，而且比较快，并且可以新增样本。
即训练时，每次只从一批训练样本中随机选取一个样本进行梯度下降；对随机梯度下降来说，只需要一次关注一个训练样本，一点点把参数朝着全局最小值的方向进行修改了。
整体数据集是个循环，其中对每个样本进行一次参数更新
缺点：
梯度下降速度比较慢，而且每次梯度更新时往往只专注与局部最优点，而不会恰好指向全局最优点；
单样本梯度更新时会引入许多噪声（跟训练目标无关的特征也会被归为该样本分类的特征）；
SGD 因为更新比较频繁，会造成 cost function 有严重的震荡。
BGD 可以收敛到局部极小值，当然 SGD 的震荡可能会跳到更好的局部极小值处。
当我们稍微减小 learning rate，SGD 和 BGD 的收敛性是一样的。
优点：
当处理大量数据时，比如SSD或者faster-rcnn等目标检测模型，每个样本都有大量候选框参与训练，这时使用随机梯度下降法能够加快梯度的计算。
随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况，那么可能只用其中部分的样本，就已经将 迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。缺点是SGD的噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。所以虽然训练速度快，但是准确度下降，并不是全局最优。虽然包含一定的随机性，但是从期望上来看，它是等于正确的导数的。
梯度更新规则：
MBGD 每一次利用一小批样本，即 n 个样本进行计算，这样它可以降低参数更新时的方差，收敛更稳定，另一方面可以充分地利用深度学习库中高度优化的矩阵操作来进行更有效的梯度计算。
和 SGD 的区别是每一次循环不是作用于每个样本，而是具有 n 个样本的批次。
超参数设定值: n 一般取值在 50～256
缺点：（两大缺点）
鞍点就是：一个光滑函数的鞍点邻域的曲线，曲面，或超曲面，都位于这点的切线的不同边。例如这个二维图形，像个马鞍：在x-轴方向往上曲，在y-轴方向往下曲，鞍点就是（0，0）。
为了应对上面的两点挑战就有了下面这些算法
核心思想：
不使用动量优化时，每次训练的梯度下降方向，都是按照当前批次训练数据计算的，可能并不能代表整个数据集，并且会有许多噪声，下降曲线波动较大：
添加动量项之后，能够有效减小波动，从而加快训练速度：
当我们将一个小球从山上滚下来时，没有阻力的话，它的动量会越来越大，但是如果遇到了阻力，速度就会变小。
加入的这一项，可以使得梯度方向不变的维度上速度变快，梯度方向有所改变的维度上的更新速度变慢，这样就可以加快收敛并减小震荡。
优点：
通过动量更新，参数向量会在有持续梯度的方向上增加速度；
使梯度下降时的折返情况减轻，从而加快训练速度；
缺点：
如果数据集分类复杂，会导致 和 时刻梯度 向量方向相差较大；在进行向量求和时，得到的 会非常小，反而使训练速度大大下降甚至模型难以收敛。
这种情况相当于小球从山上滚下来时是在盲目地沿着坡滚，如果它能具备一些先知，例如快要上坡时，就知道需要减速了的话，适应性会更好。
目前为止，我们可以做到，在更新梯度时顺应 loss function 的梯度来调整速度，并且对 SGD 进行加速。
核心思想：
自适应学习率优化算法针对于机器学习模型的学习率，采用不同的策略来调整训练过程中的学习率，从而大大提高训练速度。
这个算法就可以对低频的参数做较大的更新，对高频的做较小的更新，也因此，对于稀疏的数据它的表现很好，很好地提高了 SGD 的鲁棒性，例如识别 Youtube 视频里面的猫，训练 GloVe word embeddings，因为它们都是需要在低频的特征上有更大的更新。
Adagrad 的优点是减少了学习率的手动调节
式中， 表示第 个分类， 表示第 迭代同时也表示分类 累计出现的次数。 表示初始的学习率取值（一般为0.01）
AdaGrad的核心思想： 缩放每个参数反比于其所有梯度历史平均值总和的平方根。具有代价函数最大梯度的参数相应地有较大的学习率，而具有小梯度的参数又较小的学习率。
缺点：
它的缺点是分母会不断积累，这样学习率就会收缩并最终会变得非常小。
这个算法是对 Adagrad 的改进，
和 Adagrad 相比，就是分母的 换成了过去的梯度平方的衰减平均值，指数衰减平均值
这个分母相当于梯度的均方根 root mean squared (RMS)，在数据统计分析中，将所有值平方求和，求其均值，再开平方，就得到均方根值 ，所以可以用 RMS 简写：
其中 的计算公式如下， 时刻的依赖于前一时刻的平均和当前的梯度：
梯度更新规则:
此外，还将学习率 换成了 RMS[Δθ]，这样的话，我们甚至都不需要提前设定学习率了：
超参数设定值: 一般设定为 0.9
RMSprop 是 Geoff Hinton 提出的一种自适应学习率方法。
RMSprop 和 Adadelta 都是为了解决 Adagrad 学习率急剧下降问题的，
梯度更新规则:
RMSprop 与 Adadelta 的第一种形式相同：（使用的是指数加权平均，旨在消除梯度下降中的摆动，与Momentum的效果一样，某一维度的导数比较大，则指数加权平均就大，某一维度的导数比较小，则其指数加权平均就小，这样就保证了各维度导数都在一个量级，进而减少了摆动。允许使用一个更大的学习率η）
超参数设定值:
Hinton 建议设定 为 0.9, 学习率 为 0.001。
这个算法是另一种计算每个参数的自适应学习率的方法。相当于 RMSprop + Momentum
除了像 Adadelta 和 RMSprop 一样存储了过去梯度的平方 vt 的指数衰减平均值 ，也像 momentum 一样保持了过去梯度 mt 的指数衰减平均值：
如果 和 被初始化为 0 向量，那它们就会向 0 偏置，所以做了偏差校正，通过计算偏差校正后的 和 来抵消这些偏差：
梯度更新规则:
超参数设定值:
建议
示例一
示例二
示例三
上面情况都可以看出，Adagrad, Adadelta, RMSprop 几乎很快就找到了正确的方向并前进，收敛速度也相当快，而其它方法要么很慢，要么走了很多弯路才找到。
由图可知自适应学习率方法即 Adagrad, Adadelta, RMSprop, Adam 在这种情景下会更合适而且收敛性更好。
如果数据是稀疏的，就用自适用方法，即 Adagrad, Adadelta, RMSprop, Adam。
RMSprop, Adadelta, Adam 在很多情况下的效果是相似的。
Adam 就是在 RMSprop 的基础上加了 bias-correction 和 momentum，
随着梯度变的稀疏，Adam 比 RMSprop 效果会好。
整体来讲，Adam 是最好的选择。
很多论文里都会用 SGD，没有 momentum 等。SGD 虽然能达到极小值，但是比其它算法用的时间长，而且可能会被困在鞍点。
如果需要更快的收敛，或者是训练更深更复杂的神经网络，需要用一种自适应的算法。
各种优化器Optimizer原理：从SGD到AdamOptimizer
深度学习——优化器算法Optimizer详解（BGD、SGD、MBGD、Momentum、NAG、Adagrad、Adadelta、RMSprop、Adam）
㈢ 求多个矩阵联乘的最优算法!
程序功能：用分而治之算法计算两个n维矩阵相乘的结果
其中n必须是2的正整数次幂。
运行过程：首先，根据提示输入矩阵的维数n
其次，根据提示分别输入矩阵A和B
最后，显示矩阵A和矩阵B以及其相乘结果矩阵C
****************************************/
#include "stdio.h"
#define mytype int//矩阵元素的数据类型
#define myinputmode "%d"//矩阵元素的输入格式
#define myprintmode "%4d"//矩阵元素的输出格式
/*以上参数的设置可根据所计算矩阵的元素的数值类型进行相应改变
如更改为浮点型数据则可以使用下面的设置
#define mytype float
#define myinputmode "%f"
#define myprintmode "%6.2f"
*/
/////////////////////////////////////////
/****************************************
函数名：is2
参数：m为长整型整数
功能：检测m是否是2的正整数次幂
返回值：返回布尔型变量
true则表示m为2的正整数次幂
false则表示m不是2的正整数次幂
****************************************/
bool is2(long m)
{
if(m<0)return false;
if(m>=2)
{
if((m%2)==0) return is2(m/2);
else return false;
}
else
{
if(m==1)return true;
else return false;
}
return false;
}
/////////////////////////////////////////
/****************************************
函数名：inputmatrix
参数：M为指向数组的指针，用来存储输入的矩阵
m长整型，是数组M所存矩阵的维数
name字符型数组，是需要进行数据输入的矩阵的名字
功能：矩阵数据输入的函数，通过输入矩阵的每个元素将
矩阵存入数组
返回值：无
****************************************/
void inputmatrix(mytype * M,long m,char *name)
{
long i,j;
for(i=0;i<m;i++)
for(j=0;j<m;j++)
{
printf("Please input the %s(%d,%d):",name,i+1,j+1);
getchar();
scanf(myinputmode,&M[i*m+j]);
}
}
/////////////////////////////////////////
/****************************************
函数名：printmatrix
参数：M为指向数组的指针，数组中存储着矩阵
m长整型，是数组M所存矩阵的维数
name字符型数组，是需要进行数据输入的矩阵的名字
功能：矩阵数据输出显示的函数，将矩阵元素一一显示一在屏幕上
返回值：无
****************************************/
void printmatrix(mytype * M,long m,char *name)
{
long i,j;
printf("\nMatrix %s:\n",name);
for(i=0;i<m;i++)
{
for(j=0;j<m;j++)
{
printf(myprintmode,M[i*m+j]);
}
printf("\n");
}
}
/////////////////////////////////////////
/****************************************
函数名：Matrix_add_sub
参数：A，B为指向数组的指针，数组中存储着矩阵
C为指向数组的指针，用来存储运算结果
m长整型，是数组A、B、C所存矩阵的维数
add为布尔型变量，为true则C=A+B，为false则C=A-B
功能：根据add值对A、B进行加减运算并将结果存入C
返回值：无
****************************************/
void Matrix_add_sub(mytype * A,mytype * B,mytype * C,long m,bool add)
{
long i;
for(i=0;i<m*m;i++)
{
if(add)
C[i]=A[i]+B[i];
else
C[i]=A[i]-B[i];
}
}
/////////////////////////////////////////
/****************************************
函数名：GetHalfValue
参数：B为指向数组的指针，数组中存储着矩阵。其中B是指向m维矩阵中的一个元素。
A为指向数组的指针，用来接收B中的四分之一数据
m长整型，是数组B所指矩阵的维数
功能：从B所在位置向左和向右取矩阵的m/2维的子矩阵（子矩阵中包括B所指元素）并存入A
返回值：无
****************************************/
void GetHalfValue(mytype * A,mytype * B,long m)
{
long i,j;
for(i=0;i<m/2;i++)
{
for(j=0;j<m/2;j++)
{
A[i*m/2+j]=B[i*m+j];
}
}
}
/////////////////////////////////////////
/****************************************
函数名：UpdateHalfValue
参数：B为指向数组的指针，数组中存储着矩阵。其中B是指向m维矩阵中的一个元素。
A为指向数组的指针，存储着一个m/2维矩阵
m长整型，是数组B所指矩阵的维数
功能：把A矩阵所有元素存入从B所在位置向左和向右的m/2维的子矩阵（子矩阵中包括B所指元素）
返回值：无
****************************************/
void UpdateHalfValue(mytype * A,mytype * B,long m)
{
long i,j;
for(i=0;i<m/2;i++)
{
for(j=0;j<m/2;j++)
{
B[i*m+j]=A[i*m/2+j];
}
}
}
/////////////////////////////////////////
/****************************************
函数名：Matrix_multiplication
参数：A，B为指向数组的指针，数组中存储着矩阵。
C为指向数组的指针，用来存储计算结果
m长整型，是指针A、B所指矩阵的维数
功能：用分而治之算法和Strassen方法计算A与B的乘积并存入C
返回值：无
****************************************/
void Matrix_multiplication(mytype * A,mytype * B,mytype * C,long m)
{
if(m>2)//当矩阵维数大于2时
{
//将矩阵A、B分为四个小矩阵，分别为A1、A2、A3、A4、B1、B2、B3、B4
mytype *A1=new mytype[m*m/4],*A2=new mytype[m*m/4],*A3=new mytype[m*m/4],*A4=new mytype[m*m/4],*B1=new mytype[m*m/4],*B2=new mytype[m*m/4],*B3=new mytype[m*m/4],*B4=new mytype[m*m/4],*C1=new mytype[m*m/4],*C2=new mytype[m*m/4],*C3=new mytype[m*m/4],*C4=new mytype[m*m/4];
GetHalfValue(A1,&A[0],m);
GetHalfValue(A2,&A[m/2],m);
GetHalfValue(A3,&A[m*m/2],m);
GetHalfValue(A4,&A[m*m/2+m/2],m);
GetHalfValue(B1,&B[0],m);
GetHalfValue(B2,&B[m/2],m);
GetHalfValue(B3,&B[m*m/2],m);
GetHalfValue(B4,&B[m*m/2+m/2],m);
//利用Strassen方法计算D、E、F、G、H、I、J
mytype *D=new mytype[m*m/4],*E=new mytype[m*m/4],*F=new mytype[m*m/4],*G=new mytype[m*m/4],*H=new mytype[m*m/4],*I=new mytype[m*m/4],*J=new mytype[m*m/4];
mytype *temp1=new mytype[m*m/4],*temp2=new mytype[m*m/4];
//D=A1(B2-B4)
Matrix_add_sub(B2,B4,temp1,m/2,false);
Matrix_multiplication(A1,temp1,D,m/2);
//E=A4(B3-B1)
Matrix_add_sub(B3,B1,temp1,m/2,false);
Matrix_multiplication(A4,temp1,E,m/2);
//F=(A3+A4)B1
Matrix_add_sub(A3,A4,temp1,m/2,true);
Matrix_multiplication(temp1,B1,F,m/2);
//G=(A1+A2)B4
Matrix_add_sub(A1,A2,temp1,m/2,true);
Matrix_multiplication(temp1,B4,G,m/2);
//H=(A3-A1)(B1+B2)
Matrix_add_sub(A3,A1,temp1,m/2,false);
Matrix_add_sub(B1,B2,temp2,m/2,true);
Matrix_multiplication(temp1,temp2,H,m/2);
//I=(A2-A4)(B3+B4)
Matrix_add_sub(A2,A4,temp1,m/2,false);
Matrix_add_sub(B3,B4,temp2,m/2,true);
Matrix_multiplication(temp1,temp2,I,m/2);
//J=(A1+A4)(B1+B4)
Matrix_add_sub(A1,A4,temp1,m/2,true);
Matrix_add_sub(B1,B4,temp2,m/2,true);
Matrix_multiplication(temp1,temp2,J,m/2);
//利用Strassen方法计算C1、C2、C3、C4
//C1=E+I+J-G
Matrix_add_sub(E,I,temp1,m/2,true);
Matrix_add_sub(J,G,temp2,m/2,false);
Matrix_add_sub(temp1,temp2,C1,m/2,true);
//C2=D+G
Matrix_add_sub(D,G,C2,m/2,true);
//C3=E+F
Matrix_add_sub(E,F,C3,m/2,true);
//C4=D+H+J-F
Matrix_add_sub(D,H,temp1,m/2,true);
Matrix_add_sub(J,F,temp2,m/2,false);
Matrix_add_sub(temp1,temp2,C4,m/2,true);
//将计算结果存入数组C
UpdateHalfValue(C1,&C[0],m);
UpdateHalfValue(C2,&C[m/2],m);
UpdateHalfValue(C3,&C[m*m/2],m);
UpdateHalfValue(C4,&C[m*m/2+m/2],m);
//释放内存
delete[] A1,A2,A3,A4,B1,B2,B3,B4,C1,C2,C3,C4,D,E,F,G,H,I,J,temp1,temp2;
}
else
{
//当矩阵维数小于2时用Strassen方法计算矩阵乘积
mytype D,E,F,G,H,I,J;
//D=A1(B2-B4)
D=A[0]*(B[1]-B[3]);
//E=A4(B3-B1)
E=A[3]*(B[2]-B[0]);
//F=(A3+A4)B1
F=(A[2]+A[3])*B[0];
//G=(A1+A2)B4
G=(A[0]+A[1])*B[3];
//H=(A3-A1)(B1+B2)
H=(A[2]-A[0])*(B[0]+B[1]);
//I=(A2-A4)(B3+B4)
I=(A[1]-A[3])*(B[2]+B[3]);
//J=(A1+A4)(B1+B4)
J=(A[0]+A[3])*(B[0]+B[3]);
//C1=E+I+J-G
C[0]=E+I+J-G;
//C2=D+G
C[1]=D+G;
//C3=E+F
C[2]=E+F;
//C4=D+H+J-F
C[3]=D+H+J-F;
}
}
/////////////////////////////////////////
int main()
{
long n;
//提示输入n维矩阵的维数
printf("Please input the dimension of the Matrix.(n):");
//获得用户输入的n维矩阵维数
scanf("%d",&n);
while(!is2(n))//检查维数是否是2的幂，不是则要求重新输入
{
printf("Please reinput the dimension of the Matrix.(n):");
scanf("%d",&n);
}
//开辟空间存储用来存储n维矩阵元素
mytype *A=new mytype[n*n];
mytype *B=new mytype[n*n];
mytype *C=new mytype[n*n];
//输入矩阵A、B
inputmatrix(A,n,"A");
inputmatrix(B,n,"B");
if(n>1)//矩阵维数大于1则用分而治之算法计算
Matrix_multiplication(A,B,C,n);
else//矩阵维数为1则直接计算
*C=(*A)*(*B);
//输出矩阵A、B、C
printmatrix(A,n,"A");
printmatrix(B,n,"B");
printmatrix(C,n,"C");
//释放内存
delete[] A,B,C;
getchar();getchar();
return 1;
}
㈣ 优化算法总结
本文介绍一下机器学习和深度学习中常用的优化算法和优化器以及一些其他我知道的优化算法,部分算法我也没有搞懂,就先记录下来以后慢慢研究吧.*_*.
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.遗传算法
动量是为了加快学习速度,而自适应是为了加快收敛速度,注意学习速度快不一定收敛速度就快,比如步长大学习速度快,但是很容易跳出极值点,在极值点附近波动,很难达到收敛.
未完待定....
参考:
《统计学习方法》 李航 着
《深度学习》 花书
㈤ 几种常用最优化方法
学习和工作中遇到的大多问题都可以建模成一种最优化模型进行求解，比如我们现在学习的机器学习算法，大部分的机器学习算法的本质都是建立优化模型，通过最优化方法对目标函数（或损失函数）进行优化，从而训练出最好的模型。常见的优化方法(optimization)有梯度下降法、牛顿法和拟牛顿法、共轭梯度法等等。
1. 梯度下降法（Gradient Descent）
梯度下降法是最早最简单，也是最为常用的最优化方法。梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。 梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。
梯度下降 法的缺点：
（1）靠近极小值时收敛速度减慢;
（2）直线搜索时可能会产生一些问题；
（3）可能会“之字形”地下降。
在机器学习中，基于基本的梯度下降法发展了两种梯度下降方法，分别为随机梯度下降法和批量梯度下降法。
比如对一个线性回归（Linear Logistics）模型，假设下面的h(x)是要拟合的函数，J( )为损失函数， 是参数，要迭代求解的值，求解出来了那最终要拟合的函数h( )就出来了。其中m是训练集的样本个数，n是特征的个数。
1）批量梯度下降法（Batch Gradient Descent，BGD）
（1）将J( )对 求偏导，得到每个theta对应的的梯度：
(2）由于是要最小化风险函数，所以按每个参数 的梯度负方向，来更新每个 ：
（3）从上面公式可以注意到，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果m很大，那么可想而知这种方法的迭代速度会相当的慢。所以，这就引入了另外一种方法——随机梯度下降。
对于批量梯度下降法，样本个数m，x为n维向量，一次迭代需要把m个样本全部带入计算，迭代一次计算量为m*n2。
2）随机梯度下降（Stochastic Gradient Descent，SGD）
（1）上面的风险函数可以写成如下这种形式，损失函数对应的是训练集中每个样本的粒度，而上面批量梯度下降对应的是所有的训练样本：
（2）每个样本的损失函数，对 求偏导得到对应梯度，来更新 ：
（3）随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将
迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。
随机梯度下降每次迭代只使用一个样本，迭代一次计算量为n2，当样本个数m很大的时候，随机梯度下降迭代一次的速度要远高于批量梯度下降方法。 两者的关系可以这样理解：随机梯度下降方法以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。
对批量梯度下降法和随机梯度下降法的总结：
批量梯度下降---最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小，但是对于大规模样本问题效率低下。
随机梯度下降---最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向， 但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近，适用于大规模训练样本情况。
2. 牛顿法和拟牛顿法（Newton's method & Quasi-Newton Methods）
1）牛顿法（Newton's method）
牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数 f ( x )的泰勒级数的前面几项来寻找方程 f ( x ) = 0的根。牛顿法最大的特点就在于它的收敛速度很快。
具体步骤：
首先，选择一个接近函数 f ( x )零点的x0，计算相应的 f ( x 0)和切线斜率 f ' ( x 0)（这里 f ' 表示函数 f 的导数）。然后我们计算穿过点( x 0, f ( x 0))并且斜率为 f '( x 0)的直线和 x 轴的交点的 x 坐标，也就是求如下方程的解：
我们将新求得的点的 x 坐标命名为 x 1，通常 x 1会比 x 0更接近方程 f ( x ) = 0的解。因此我们现在可以利用 x 1开始下一轮迭代。迭代公式可化简为如下所示：
已经证明，如果 f '是连续的，并且待求的零点 x 是孤立的，那么在零点 x 周围存在一个区域，只要初始值 x 0位于这个邻近区域内，那么牛顿法必定收敛。 并且，如果 f ' ( x )不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。下图为一个牛顿法执行过程的例子。
由于牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。
关于牛顿法和梯度下降法的效率对比：
从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）
根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。
注：红色的牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。
牛顿法的优缺点总结：
优点：二阶收敛，收敛速度快；
缺点：牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。
2）拟牛顿法（Quasi-Newton Methods）
拟牛顿法是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。
拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。 拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。
具体步骤：
拟牛顿法的基本思想如下。首先构造目标函数在当前迭代xk的二次模型：
这里Bk是一个对称正定矩阵，于是我们取这个二次模型的最优解作为搜索方向，并且得到新的迭代点：
其中我们要求步长ak 满足Wolfe条件。这样的迭代与牛顿法类似，区别就在于用近似的Hesse矩阵Bk 代替真实的Hesse矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵Bk的更新。现在假设得到一个新的迭代xk+1，并得到一个新的二次模型：
我们尽可能地利用上一步的信息来选取Bk。具体地，我们要求
从而得到
这个公式被称为割线方程。常用的拟牛顿法有DFP算法和BFGS算法。
原文链接： [Math] 常见的几种最优化方法 - Poll的笔记 - 博客园