精华内容
下载资源
问答
  • 算法收敛性分析
    万次阅读 多人点赞
    2020-11-21 15:05:52

    最近在看资料时,遇到了这样的说法“某某算法具有收敛快的优点”,于是便有点疑惑:收敛不是函数或者数列才有的概念吗?用到算法上是代表什么意思呢?遂查阅资料,将一点理解记录如下。

     

    算法收敛性

    算法的收敛性就是指某个算法能否在迭代时间趋于无穷的假设下,最终找到问题的全局最优解。这里有一点要明确:算法收敛性是迭代法中的一个概念,所以主要针对跟迭代相关的算法,如进化算法。对于能够一次求解的直接法,就不在算法收敛的讨论范围之内了。

     

    算法收敛速度

    知道了算法收敛性的含义,再来理解算法收敛速度就比较容易了。百度百科对算法收敛速度是这样解释的:

    数值分析中, 一个收敛序列向其极限逼近的速度称为收敛速度(Rate of convergence). 该概念多用于最优化算法中; 其被定义为一个迭代序列向其局部最优值逼近 (假设计算过程收敛, 并能达到最优值) 的速度, 是评价一个迭代法于该问题中发挥的性能的一个重要指针。

    说白了,算法收敛速度就是指算法需要经过多少次迭代才能得到最优解。很明显,有些算法的收敛性好,有些算法的收敛性差,所谓收敛性好就是收敛得快,快速收敛的意义就是使用较少的迭代次数便可得到相对精确的值,或者说是在允许的时间内得到满意结果。因此,能以较快速度收敛于最优解的算法,才能称得上一个好算法。

     

    最后再贴一段关于收敛性的论述来帮助理解:

    仅仅知道算法是收敛的还远远不够,收敛性的结论是建立在无穷迭代时间基础上的,而实际应用中的计算迭代时间是有限的。收敛性研究只能回答进化算法在迭代无穷次后最终会不会找到全局最优解,而不能回答算法实际究竟要花多长时间(迭代多少次)才能找到最优解,很难在实践中用于指导算法设计和改进。

     

    关于如何证明一个算法的收敛性以及对收敛速度的分析,有兴趣的可以看以下资料:

    1.https://xueshu.baidu.com/usercenter/paper/show?paperid=f70e65d2b08ddb59a2602e9ff1593033&site=xueshu_se

    2.https://kns.cnki.net/kcms/detail/detail.aspx?dbcode=CDFD&dbname=CDFD1214&filename=1013320373.nh&v=Mdg9jxBMyFAAVIXJAHoc4RLlqgHadtKNiNI9aJBOO6JygAqnN6SovcLK56hCzkrY

    3.https://blog.csdn.net/q__y__L/article/details/51834694?utm_medium=distribute.pc_relevant.none-task-blog-baidulandingword-2&spm=1001.2101.3001.4242

     

    参考资料:

    1. https://kns.cnki.net/kcms/detail/detail.aspx?dbcode=CDFD&dbname=CDFD1214&filename=1013320373.nh&v=Mdg9jxBMyFAAVIXJAHoc4RLlqgHadtKNiNI9aJBOO6JygAqnN6SovcLK56hCzkrY
    2. https://baike.baidu.com/item/%E6%94%B6%E6%95%9B%E9%80%9F%E5%BA%A6/8853577?fr=aladdin
    3. https://bbs.csdn.net/topics/360149144?utm_medium=distribute.pc_relevant.none-task-discussion_topic-BlogCommendFromBaidu-3.control&depth_1-utm_source=distribute.pc_relevant.none-task-discussion_topic-BlogCommendFromBaidu-3.control
    4. https://blog.csdn.net/q__y__L/article/details/51834694?utm_medium=distribute.pc_relevant.none-task-blog-baidulandingword-2&spm=1001.2101.3001.4242

     

    几篇有关算法收敛性的文献分享:链接:https://pan.baidu.com/s/1QkyiKEzlFF7LF9JsaQOG7w      提取码:egef 

    更多相关内容
  • 警示传播算法(WP)作为信息传播算法的基本模型,分析WP算法的收敛性对于研究其他信息传播算法的收敛性具有重要意义,分析了WP算法收敛性与结构熵之间的关系,给出WP算法收敛的判定条件。通过实验分析,该方法有效...
  • 针对从自然界中杂草的生长繁殖特性演化而来的新型智能优化算法―扩张性杂草进化算法,通过马尔可夫链,分析证明了它的全局收敛性。相比其他启发式算法,其最大优点是基于种群中优秀的个体有指导地进行搜索,且算法中子代...
  • 利用矩阵理论和线性方程组迭代收敛的一般原理, 在不附加特殊条件的情况下, 证明... 通过计算机仿真验证了收敛定理的正确和改进算法的优越, 并研究得出了 CMAC 网络各个参数对其泛化性能影响的相关结论。</p>
  • BP算法收敛性分析及改进.pdf
  • 粒子群优化算法收敛性分析.pdf
  • 虽然文化算法已被广泛应用于解决各个领域的优化问题, 但与其收敛能力相关的理论分析还比较缺乏. 为 此, 针对传统文化算法, 应用有限状态Markov 链来分析文化算法的搜索过程, 进一步使用公理化模型深入研究了种 群...
  • 大数据-算法-系数正则化在线算法收敛性分析
  • 安全技术-网络信息-前馈神经网络梯度学习算法收敛性分析.pdf
  • 本文利用最小二乘理论研究学习理论中的回归问题...其目的在于利用概率不等式与神经网络的逼近性质来分析回归学习算法的误差.结论表明,当回归函数满足一定的光滑时,得到较为紧的上界且该上界与输入空间的维数无关.
  • 动态交互作用下的粒子群优化算法收敛性分析.pdf
  • 安全技术-网络信息-高阶神经网络的梯度训练算法收敛性分析.pdf
  • 基于关系模型的进化算法收敛性分析与对比
  • 利用矩阵理论和线性方程组迭代收敛的一般原理,在不附加特殊条件的情况下,证明了CMAC算法在批量和增量两种学习方式下的收敛定理,对在关联矩阵正定条件下得出的结论进行推广和改进。在此基础上提出一种学习率自寻...
  • 带L2正则化项的神经网络逆向迭代算法收敛性分析.pdf
  • 为了研究蝙蝠算法收敛性,本文基于随机搜索算法的全局收敛性判断准则对蝙蝠算法收敛性进行了分析,并通过仿真实验进行了验证.结果表明,蝙蝠算法不完全满足随机搜索优化算法的2个全局收敛准则,无法确保全局...
  • 有关蚁群优化算法收敛性分析的研究还很少,不利于进一步改进其算法.为此, 较详细地分析了用蚁群优化算法求解TSP问题的收敛性,证明了当0</p>
  • 不适定积分方程的加速期望最大化算法收敛性分析
  • 可满足性问题中信念传播算法收敛性分析
  • 利用随机过程理论, 对人工蜂群算法收敛性进行理论分析, 给出人工蜂群算法的一些数学定义和蜜源位置 的一步转移概率, 建立人工蜂群算法的Markov 链模型, 分析此Markov 链的一些性质, 论证了人工蜂群状态序列是有...
  • 本文阐述了遗传禁忌搜索算法的混合策略,从理论上对该算法收敛性进行了证明,对时间复杂度进行了分析。应用马尔科夫链模型证明了遗传禁忌搜索算法是以概率1收敛到全局最优解的,并应用求解随机算法时间复杂度的方法,...
  • 为了提高蚁群算法的收敛速度和求解精度,根据仿生优化算法在...通过对蚁群系统马尔科夫过程进行分析,证明了该算法的全局收敛性.针对典型的TSP 问题进行仿真对比实验,验证了该算法在速度和精度方面优于传统蚁群算法.</p>
  • 使用MATLAB手打k-means聚类函数,通过矩阵运算提高运行速度,带有详细注释。 样本点归类过程提供循环方式和矩阵计算方式,后者耗时和pdist2...压缩包中附带K-means聚类实现原理介绍及收敛性分析文件(readme.pdf)。
  • 分析了粒子群优化算法收敛性,指出它在满足收敛性的前提下种群多样性趋于减小, 粒子将会因速度降低而失去继续搜索可行解的能力;提出混沌粒子群优化算法, 该算法在满足收敛性的条件下利用混沌特性提高种群的多样性和...
  • 用随机过程论中的马尔克夫链理论研究了几种遗传算法收敛性.提出了6个引理,3个定理和3个推论,证明了最优保存遗传算法和作者提出的2种新型遗传算法:模拟生物种族进化的遗传算法,带罗盘算法的GA是全局收敛的,而...
  • 梯度下降收敛性分析与证明

    千次阅读 2021-03-30 22:20:27
    性质1:若函数在定义域内满足Lipschitz连续,则有 (1-1) 二:梯度下降算法收敛性分析 在求解优化问题时,我们常用梯度下降算法对目标函数进行寻优,求得优化问题的最优解或近似最优解。而在面对不同性质的目标函数...

    一:Lipschitz连续

    定义:对于在实数集的子集的函数f:D\subseteq \mathbb{R}\rightarrow \mathbb{R},若存在常数K,使得\left | f(a)-f(b) \right |\leq K\left | a-b \right |,\forall a,b\in D,则称函数f符合利普希茨条件。

    性质1:若函数f在定义域内满足Lipschitz连续,则有

                                                         f(y)\leq f(x)+\bigtriangledown f(x)^{T}(y-x)+\frac{M}{2}\left \| y-x \right \|^{2}                                                                        (1-1)                  

    二:梯度下降算法收敛性分析

    在求解优化问题时,我们常用梯度下降算法对目标函数进行寻优,求得优化问题的最优解或近似最优解。而在面对不同性质的目标函数时,如凸函数、强凸函数和非凸函数,梯度下降算法的收敛性会发生何种变化,都是值得去思考的一个问题。

    在此,我们首先讨论第一种情况,在优化问题的目标函数为强凸函数,且满足Lipschitz连续,采用梯度下降算法进行求解的算法收敛性分析如下:

    若目标函数f为强凸函数,且在定义域内Lipschitz连续。则有:

      Lipschitz连续性质:                   f(y)\leq f(x)+\bigtriangledown f(x)^{T}(y-x)+\frac{M}{2}\left \| y-x \right \|^{2}                                                                          (2-1)

    强凸函数性质                             f(y)\geq f(x)+\bigtriangledown f(x)^{T}(y-x)+\frac{m}{2}\left \| y-x \right \|^{2}                                                                          (2-2)

    显然,结合公式(2-1)与公式(2-2),我们可得:

                                          \frac{m}{2}\left \| y-x \right \|^{2}\leq f(y)-f(x)-\bigtriangledown f(x)^{T}(y-x)\leq\frac{M}{2}\left \| y-x \right \|^{2}                                                            (2-3)

    此外,采用梯度下降的更新公式为x^{(k+1)}=x^{(k)}-\bigtriangledown f(x^{(k)})t,我们令y=x^{(k+1)},x=x^{(k)}代入公式(2-1)可得:

                                     f(x^{(k+1)})-f(x^{(k)})\leq \bigtriangledown f(x^{(k)})(x^{(k+1)}-x^{(k)})+\frac{M}{2}\left \| x^{(k+1)}-x^{(k)} \right \|^{2}

                                                                       \leq -\left \| \bigtriangledown f(x^{(k)}) \right \|^{2}t+\frac{M}{2}\left \| \bigtriangledown f(x^{(k)}) \right \|^{2}t^{2}                                                                  (2-4)

    且当t=\frac{1}{M}时,不等式右侧取极值,步长取为\left \| \bigtriangledown f(x) \right \|^{2}的上届值的倒数,即精确搜索法(采用回溯搜索法,步长0\leq t\leq \frac{1}{M})代入公式(2-4)可得:

                                                         f(x^{(k+1)})-f(x^{(k)})\leq -\frac{1}{2M}\left \| \bigtriangledown f(x^{(k)}) \right \|^{2}                                                                             (2-5)

    对于公式(2-2),我们考虑公式右侧关于y的二次函数g(y),当y=x-\frac{1}{m}\bigtriangledown f(x)时取极值,并进一步的变形可得:

                                                                     f(y)\geq f(x)-\frac{1}{2m}\left \| \bigtriangledown f(x) \right \|^{2}                                                                                     (2-6)

    y=x^{(k+1)},x=x^{(k)},代入可得:

                                                            f(x^{(k+1)})\geq f(x^{(k)})-\frac{1}{2m}\left \| \bigtriangledown f(x^{(k)}) \right \|^{2}                                                                             (2-7)

    结合公式(2-5)与公式(2-7)可得:

                                           -\frac{1}{2m}\left \| \bigtriangledown f(x^{(k)}) \right \|^{2}\leq f(x^{(k+1)})-f(x^{(k)})\leq -\frac{1}{2M}\left \| \bigtriangledown f(x^{(k)}) \right \|^{2}                                                     (2-8)

    对于不等式(2-8)右侧,我们同时减去最优值p^{*},同等变形可得:

                                                       f(x^{(k+1)})-p^{*}\leq f(x^{(k)})-p^{*}-\frac{1}{2M}\left \| \bigtriangledown f(x^{(k)}) \right \|^{2}                                                                (2-9)

    对不等式(2-8)左侧变形可得:

                                       f(x^{(k)})-p^{*}\leq \frac{1}{2m}\left \| \bigtriangledown f(x^{(k)}) \right \|^{2}\Rightarrow \left \| \bigtriangledown f(x^{(k)}) \right \|^{2}\geq 2m(f(x^{(k)})-p^{*})                                              (2-10)

    讲公式(2-10)代入公式(2-9)可得:

                                                      f(x^{(k+1)})-p^{*}\leq f(x^{(k)})-p^{*}-\frac{m}{M}(f(x^{(k)})-p^{*})

                                                      f(x^{(k+1)})-p^{*}\leq (1-\frac{m}{M})(f(x^{(k)})-p^{*})                                                                                (2-11)

    我们可以发现第k+1次与第k次更新与最优值的差值成等比关系,假设经过T次迭代,则有:

                                                     f(x^{(T)})-p^{*}\leq (1-\frac{m}{M})^{T}(f(x^{(0)})-p^{*})                                                                                  (2-12)
    显然1-\frac{m}{M}< 1,当T\rightarrow \infty时,f(x^{(T)})\rightarrow p^{*},因此算法能够收敛。此外,当f(x^{(T)})-p^{*}\leq (1-\frac{m}{M})^{T}(f(x^{(0)})-p^{*})\leq \epsilon时,有:

                                                                 (1-\frac{m}{M})^{T}(f(x^{0})-p^{*})\leq \epsilon                                                                                           

                                                  \frac{1}{(1-\frac{m}{M})^{T}}\geq \frac{f(x^{(0)})-p^{*}}{\epsilon }\Rightarrow T\geq {log_{\frac{1}{1-\frac{m}{M}}}}^{\frac{f(x^{(0)})-p^{*}}{\epsilon }}

                                                                        T\geq \frac{log^{\frac{f(x^{(o)})-p^{*}}{\epsilon }}}{log^{\frac{1}{1-\frac{m}{M}}}}                                                                                                     (2-13)

    即此时的迭代次数T=O(log\frac{1}{\epsilon }).

    此外,梯度下降的收敛性质是由目标函数决定的。当目标函数为强凸函数时,收敛速度为线性的。若是为凸函数和非凸函数,梯度下降的收敛性将变差。此外可以通过对步长的设置来加快算法的收敛。

    展开全文
  • 资源名:matlab仿真_LMS算法_RLS算法_收敛性 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换。 适合人群:新手及有一定...
  • 最优保留GA (EGA )是目前GA 收敛性研究中比较典型的一类。在已有研究成果的基础上给 出了EGA 更一般的规范化定义, 指明了 EGA 全局收敛的本质及其两种...了收敛性分析。最后提出一种变形的全局收敛的 EGA。</p>
  • 分析基于免疫响应原理的免疫进化算法流程和运行机制.根据免疫抗体群的状态转移过程,研究免疫...通过实验总结影响免疫进化算法收敛性的关键因素,为解空间较大及高维优化问题的免疫进化算法收敛性和性能分析提供可行方法.
  • 贝叶斯博弈多目标进化算法及其收敛性分析

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 54,356
精华内容 21,742
关键字:

算法收敛性分析

友情链接: 48457457.zip