群优化算法全局收敛性证明

㈠ 优化设计算法的收敛准则有哪些

点距准则
函数下降量准则
梯度准则

㈡ 蚁群算法的执行结果一定收敛与全局最优解吗

什么是启发式算法转自：p://blog.csdn.net/aris_zzy/archive/2006/05/27/757156.aspx引言：解决实际的问题，要建模型，在求解。求解要选择算法，只有我们对各种算法的优缺点都很熟悉后才能根据实际问题选出有效的算法。但是对各种算法都了如指掌是不现实的，但多知道一些，会使你的选择集更大，找出最好算法的概率越大。现在研一，要开题了些点文献综述，愿与大家分享。大自然是神奇的，它造就了很多巧妙的手段和运行机制。受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。现在的启发式算法也不是全部来自然的规律，也有来自人类积累的工作经验。启发式算法的发展：启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，取得了巨大的成就。40年代：由于实际需要，提出了启发式算法（快速有效）。50年代：逐步繁荣，其中 贪婪算法和局部搜索 等到人们的关注。60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规 模的问题仍然无能为力（收敛速度慢）。启发式算法的不足和如何解决方法：（水平有限 仅仅提出6点）启发式算法目前缺乏统一、完整的理论体系。很难解决！ 启发式算法的提出就是根据经验提出，没有什么坚实的理论基础。由于NP理论，启发式算法就解得全局最优性无法保证。等NP？=P有结果了再说吧，不知道这个世纪能不能行。各种启发式算法都有个自优点如何，完美结合。如果你没有实际经验，你就别去干这个，相结合就要做大量尝试，或许会有意外的收获。启发式算法中的参数对算法的效果起着至关重要的作用，如何有效设置参数。还是那句话，这是经验活但还要悟性，只有try again………..启发算法缺乏有效的迭代停止条件。还是经验，迭代次数100不行，就200，还不行就1000…………还不行估计就是算法有问题，或者你把它用错地方了………..启发式算法收敛速度的研究等。你会发现，没有完美的东西，要快你就要付出代价，就是越快你得到的解也就远差。其中（４）集中反映了超启发式算法的克服局部最优的能力。虽然人们研究对启发式算法的研究将近５０年，但它还有很多不足：1.启发式算法目前缺乏统一、完整的理论体系。2.由于NP理论，各种启发式算法都不可避免的遭遇到局部最优的问题，如何判断3.各种启发式算法都有个自优点如何，完美结合。4.启发式算法中的参数对算法的效果起着至关重要的作用，如何有效设置参数。5.启发算法缺乏有效的迭代停止条件。6.启发式算法收敛速度的研究等。70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。 由此必须引入新的搜索机制和策略……….. Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的 兴趣。80年代以后： 模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。 最近比较热或刚热过去的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms）， 拟人拟物算法，量子算法等。各个算法的思想这就不再详细给出（以后会给出一些，关注我的blog） ，为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。这里要说明的是：启发式算法得到的解只是近似最优解（近似到什么程度，只有根据具体问题才能给出）. 二十一世纪的最大的数学难题NP？=P，如果NP=P启发式算法就不在有存在的意义。 优胜劣汰是大自然的普遍规律，它主要通过选择和变异来实现。选择是优化的基本思想，变异（多样化）是随机搜索或非确定搜索的基本思想。“优胜劣汰”是算法搜索的核心，根据“优胜劣汰”策略的不同，可以获得不

㈢ 混沌优化算法可以求解全局最优解吗

非线性最优化问题的一种混合解法

摘 要：把BFGS方法与混沌优化方法相结合，基于混沌变量提出一种求解具有变量边界约束非线性最优化问题的混合优化方法。混合算法兼顾了混沌优化全局搜索能力强和BFGS方法收敛速度快的优点，成为一种求解非凸优化问题全局最优的有效方法。算例表明，当混沌搜索的次数达到一定数量时，混合优化方法可以保证算法收敛到全局最优解，且计算效率比混沌优化方法有很大提高。

关键词：混合法；BFGS方法；混沌优化方法；全局最优

1 引言
在系统工程、控制工程、统计学、反问题优化求解等领域中，很多问题是具有非凸性的。对此普通的优化技术只能求出局部最优解，因为这些确定性算法总是解得最近的一个极值点[1]，只有能够给出很好的初始点才有可能得出所需要的全局最优解。为此，实际应用中通过在多个初始点上使用传统数值优化方法来求取全局解的方法仍然被人们所采用，但是这种处理方法求得全局解的概率不高，可靠性低，建立尽可能大概率的求解全局解算法仍然是一个重要问题。近年来基于梯度法的全局最优化方法已经有所研究[2]，基于随机搜索技术的遗传算法和模拟退火算法等在全局优化问题中的应用也得到越来越大的重视[3-4]。本文则基于混沌优化和BFGS方法，提出一种求解具有简单界约束最优化问题(1)的混合算法。
混沌是存在于非线性系统中的一种较为普遍的现象。混沌运动宏观上无序无律，具有内随机性、非周期性和局部不稳定性，微观上有序有律，并不是完全的随机运动，具有无穷嵌套的自相似几何结构、存在普适性规律，并不是杂乱无章的。利用混沌变量的随机性、遍历性和规律性特点可以进行优化搜索[5]，且混沌优化方法容易跳出局部最优点。但是某些状态需要很长时间才能达到，如果最优值在这些状态时，计算时间势必很长[5]。可以说混沌优化具有全局搜索能力，其局部搜索能力稍显不足，文[5]采用二次载波技术，文[6]考虑逐渐缩小寻优变量的搜索空间都是为了弥补这一弱点。而本文则采用混沌搜索与BFGS方法进行优化求解，一方面采用混沌搜索帮助BFGS方法跳出局部最优，另一方面利用BFGS增强解附近的超线性收敛速度和搜索能力，以提高搜索最优的效率。
2 混沌－BFGS混合优化方法
2.1 BFGS方法
作为求解无约束最优化问题的拟牛顿方法类最有代表性的算法之一，BFGS方法处理凸非线性规划问题，以其完善的数学理论基础、采用不精确线性搜索时的超线性收敛性和处理实际问题有效性，受到人们的重视[7-9]。拟牛顿方法使用了二阶导数信息，但是并不直接计算函数的Hesse矩阵，而是采用一阶梯度信息来构造一系列的正定矩阵来逼近Hesse矩阵。BFGS方法求解无约束优化问题min()的主要步骤如下：
(1) 给变量赋初值x0，变量维数n和BFGS方法收敛精度ε，令B0=I（单位阵），k=0，计算在点x0的梯度g0。
(2) 取sk=-Bk-1gk，沿sk作一维搜索，确定最优步长αk，，得新点xk+1=xk+αksk，计算xk+1点的梯度gk+1。
(3) 若||gk+1||≤ε，则令，，BFGS搜索结束，转步骤3；否则执行(4)。
(4) 计算Bk+1：
(2)
(3)
(5) k=k+1，转(2)。
2.2 混沌优化方法
利用混沌搜索求解问题(1)时，先建立待求变量与混沌变量的一一对应关系，本文采用。然后,由Logistic映射式(4)产生个轨迹不同的混沌变量（）进行优化搜索，式(4)中=4。已经证明，=4是“单片”混沌，在[0,1]之间历遍。
(4)
(1)给定最大混沌变量运动次数M；给赋初值，计算和；置，。
(2) 。
(3) 。
(4) 若k<M，
若，令，；
若，和保持不变；
然后令k=k+1，，转(2)。
若k>M，则，，混沌搜索结束。
2.3 混合优化方法
混沌方法和BFGS方法混合求解连续对象的全局极小值优化问题(1)的步骤如下：
step1 设置混沌搜索的最大次数M，迭代步数iter=0，变量赋初值x0，。
step2 以为始点BFGS搜索，得当前BFGS方法最优解及=。
step3 若，取=；若，取；若，取，是相对于,较小的数。
step 4 以为始点进行混沌搜索M次，得混沌搜索后的最优解及=。
step5 若<，iter=iter+1，，转step2；否则执行step6。
step6 改变混沌搜索轨迹，再次进行混沌搜索，即给加微小扰动，执行step 4，得搜索结果和。若<，iter=iter+1，，转step2；否则计算结束，输出、。
对全局极大值问题，max ，可以转化为求解全局极小问题min 。
混合算法中混沌搜索的作用是大范围宏观搜索，使得算法具有全局寻优性能。而BFGS搜索的作用是局部地、细致地进行优化搜索，处理的是小范围搜索问题和搜索加速问题。
3 算例

图 1 函数-特性示意图 图 2 函数特性示意图
采用如下两个非常复杂的、常用于测试遗传算法性能的函数测试本文算法：

函数称为Camel 函数，该函数有6个局部极小点(1.607105, 0.568651)、(-1.607105, -0.568651)、(1.703607, -0.796084)、(-1.703607, 0.796084)、(-0.0898,0.7126)和(0.0898,-0.7126)，其中(-0.0898,0.7126)和(0.0898,-0.7126)为两个全局最小点，最小值为-1.031628。函数称为 Schaffer's函数，该函数有无数个极大值，其中只有（0，0）为全局最大点，最大值为1。此函数的最大峰值周围有一圈脊，它们的取值均为0.990283，因此很容易停留在此局部极大点。文献[10]采用该函数对该文提出的基于移动和人工选择的改进遗传算法（GAMAS）其性能进行了考察，运行50次，40％的情况下该函数的唯一全局最优点能够找到。而采用本文混合算法，由计算机内部随机函数自动随机生产100个不同的初始点，由这些初始点出发，一般混合算法迭代2－4次即能够收敛。M取不同数值时对函数、的计算结果分别如表1和表2所示，表中计算时间是指在奔腾133微机上计算时间。
由表2可见，当M=1500时，本文方法搜索到最优解的概率即达到40％，而此时计算量比文献[10]小。同样由混合算法的100个起始点，采用文献[5]的算法对函数优化计算100次，以作为收敛标准，混沌搜索50000次，计算结果为67次搜索到最优解，概率为67%，平均计算时间为1.2369s。而即使保证混合算法100次全收敛到最优解所花费的平均计算时间也只为0.2142s（表1），可见混合算法优于文献[5]的方法。
表1 M取不同数值时函数的计算结果
_____________________________________________________________________
M 搜索到全局最优点的次数 搜索到最优的概率 平均计算时间
(-0.0898,0.7126) (0.0898,-0.7126)
_____________________________________________________________________________________________
1000 44 39 83% 0.1214s
3000 53 45 98% 0.1955s
5000 53 47 100% 0.2142s
________________________________________________________________________________________________

表2 M取不同数值时函数的计算结果
___________________________________________________________
M 搜索到全局最优点的次数 搜索到最优的概率 平均计算时间
____________________________________________________________________________________
1500 40 40% 0.1406s
5000 73 73% 0.2505s
10000 88 88% 0.4197s
50000 100 100% 1.6856s
____________________________________________________________________________________

4 计算结果分析
由表1和表2可见，混合算法全局寻优能力随M的增加而增大，当M达到某一足够大的数值Mu后，搜索到全局最优的概率可以达到100％。
从理论上说，Mu趋向无穷大时，才能使混沌变量遍历所有状态，才能真正以概率1搜索到最优点。但是，本文混沌运动M次的作用是帮助BFGS方法跳出局部最优点，达到比当前局部最优函数值更小的另一局部最优附近的某一点处，并不是要混沌变量遍历所有状态。由混沌运动遍历特性可知，对于某一具体问题，Mu达到某一具体有限数值时，混沌变量的遍历性可以得到较好模拟，这一点是可以满足的，实际算例也证实了这一点。
由于函数性态、复杂性不同，对于不同函数，如这里的测试函数、，数值Mu的大小是有差别的。对于同一函数，搜索区间增大，在相同混沌运动次数下，即使始点相同，总体而言会降低其搜索到全局最优的概率,要保证算法仍然以概率1收敛到全局最优，必然引起Mu 增大。跟踪计算中间结果证实，当M足够大时，混合算法的确具有跳出局部最优点，继续向全局最优进行搜索的能力；并且混合算法的计算时间主要花费在为使混合算法具有全局搜索能力而进行混沌搜索上。
5 结语
利用混沌变量的运动特点进行优化，具有非常强的跳出局部最优解的能力，该方法与BFGS方法结合使用，在可以接受的计算量下能够计算得到问题的最优解。实际上，混沌优化可以和一般的下降类算法结合使用，并非局限于本文采用的BFGS方法。采用的Logistic映射产生混沌变量序列，只是产生混沌变量的有效方式之一。
混沌运动与随机运动是不同的。混沌是确定性系统中由于内禀随机性而产生的一种复杂的、貌似无规的运动。混沌并不是无序和紊乱，更像是没有周期的秩序。与随机运动相比较，混沌运动可以在各态历经的假设下，应用统计的数字特征来描述。并且，混沌运动不重复地经过同一状态，采用混沌变量进行优化比采用随机变量进行优化具有优势。
混沌优化与下降类方法结合使用是有潜力的一种全局优化途径，是求解具有变量界约束优化问题的可靠方法。如何进一步提高搜索效率，以及如何把混沌优化有效应用于复杂约束优化问题是值得进一步研究的课题。
本文算法全局收敛性的严格数学证明正在进行之中。
参考文献
[1]胡山鹰，陈丙珍，何小荣，沈静珠．非线性规划问题全局优化的模拟退火法[J]．清华大学学报，37(6)，1997，5-9．
[2]C A Floudas, A Aggarwal, A R Ciric． Global optimum search for nonconvex NLP and MINLP problems[J]. Comput Chem Engng． 1989， 13(10)， 1117~1132．
[3]康立山，谢云，尤矢勇等．非数值并行算法（第一册）――模拟退火算法[M]．北京：科学出版社，1998．
[4]刘勇，康立山，陈琉屏．非数值并行算法（第二册）――遗传算法[M]．北京：科学出版社，1998．
[5]李兵，蒋慰孙．混沌优化方法及其应用[J]．控制理论与应用，14(4)，1997，613-615．
[6]张彤，王宏伟，王子才．变尺度混沌优化方法及其应用[J]．控制与决策，14(3)，1999，285-287．
[7]席少霖．非线性最优化方法[M]．北京：高等教育出版社，1992．
[8]席少霖，赵凤志．最优化计算方法[M]．上海：上海科学技术出版社，1983．
[9]Press W H, Tenkolsky S A, Vetterling W T, Flannery B P．Numerical Recipes in C, The Art of Scientific Computing[M]． Second edition， Cambridge University Press， 1992．
[10]J C Ports．The development and evaluation of an improved genetic algorithm based on migration and artificial selection[J]．IEEE Trans. Syst. Man and Cybern.．1994, 24(1)，73-85．
A Hybrid Approach for Nonlinear Optimization
Abstract：Combined BFGS method with chaos optimization method, a hybrid approach was proposed to solve nonlinear optimization problems with boundary restraints of variables. The hybrid method is an effective approach to solve nonconvex optimization problems, as it given both attentions to the inherent virtue to locate global optimum of chaos optimization method and the advantage of high convergence speed of BFGS method. Numerical examples illustrate that the present method possesses both good capability to search global optima and far higher convergence speed than that of chaos optimization method.

㈣ 怎么判断粒子群优化算法有没有局部收敛

那要看你用什么软件，测试什么函数了。
基本思想就是测试的目标函数值为y值，迭代次数为x值，统计数据，绘制图像~得到的就是迭代收敛曲线图~

㈤ 请问智能优化算法以及神经网络能不能用数学理论进行证明

智能优化算法多达十几种，你说的是哪一种？而且你光说算法证明，这个算法本来就不存在证明，所谓的证明就是对算法收敛性的证明。就拿最普遍的遗传算法来说吧，这个的证明通常是用马氏链来描述，Holland本人则是通过模式方式来证明，但是证明过程被大家所 不认同。因为这种启发式随机搜索算法只能用概率来描述他的行为，那么一个依概率存在的东西，找到最优也是依概率的，所以所有的智能算法至今没有任何一个人说他的算法收敛性证明是严谨的，是经得起推敲的。所以算法的证明通常书上不说，要么就是简要说一下，因为本身意义不大，实际应用中，算法的参数都是要反复调整的。至于神经网络，你要证明神经网络的什么？BP的学习也不需要证明啊

㈥ 牛顿迭代法的全局收敛性和局部收敛性有何区别各自有什么作用要详细点的,

总的来说局部收敛性指的是初值取在根的局部时算法(一般)具有二阶收敛速度,全局收敛性是指初值在定义域内任取时算法是否收敛,若收敛其速度如何,收敛到哪个根.
具体来说
局部收敛性有如下定理
设已知 f(x) = 0 有根 a,f(x) 充分光滑(各阶导数存在且连续).
若 f'(a) != 0(单重零点),则初值取在 a 的某个邻域内时,迭代法 x[n+1] = x[n] - f(x[n])/f'(x[n]) 得到的序列 x[n] 总收敛到 a,且收敛速度至少是二阶的.
若 f'(a) == 0(多重零点),则初值取在 a 的某个邻域内时,收敛速度是一阶的.
记 g(x)=x-f(x)/f'(x),其中"某个邻域"可由 |g'(x)|

㈦ 怎么证明它的收敛性

望采纳

㈧ 遗传算法全局收敛能力和全局寻优能力一样还是不一样

收敛能力是指的从一个初始条件出发，经过一系列迭代之后，最终能否收敛到最优解；全局寻优能力实际上指算法的“搜索”能力。
一个优化收敛能力差，意味着有时候他的求解不一定收敛（正常情况下，经过一些步的迭代后，最好解会很稳定）
寻优能力差意味着在很多初始条件下，算法找不到系统最优解或近似最优解。

㈨ 怎么判断粒子群优化算法有没有局部收敛

转载请注明：来自网络知道——小七的风
首先说，标准的粒子群算法是通过控制权重系数ω的线性下降来使得种群收敛的，从收敛图上看，如果在多次迭代后（比如100次迭代后）如果最优粒子的适应度值不再变化即认为此时算法已经达到收敛。
理论上，粒子群通过自身的更新机制使得每个粒子在每次的迭代中会向该粒子的历史最优位置以及全局粒子位置的中间（或周围）位置靠近，这样虽然保证了粒子搜索的高效性（假设最优点存在于全局最优点与历史最优点的中间位置）但势必带来了粒子搜索范围的减少，所以容易出现局部收敛，并且已有相关文献证明了这不是一个全局最优的算法。
还有一种简单的做法是证伪，即不去直接证明粒子群是一个全局最优，而是试图去找到一个点，这个点的适应度值比粒子群找到的全局最优点的适应度值更好，这样就间接说明了算法没有找到全局最优点（可以采用纯随机，直到找到比粒子群提供的全局最优点好为止）

㈩ 如何提高蚁群路由算法收敛速度

蚂蚁算法是一种新型随机优化算法,能有效解决Ad Hoc网络多约束的QoS路由问题,但存在收敛速度慢和易陷入局部最优等缺点.针对于此,在借鉴精英策略的基础上提出了一种基于双向收敛蚁群算法,并将该算法应用于Ad Hoc网络的QoS路由问题中.仿真结果表明,算法可明显提高数据包的投递率,降低端到端的传输时延.
可以
针对蚁群算法(ACA)寻优性质优良,但搜索时间长、收敛速度慢、易限于局部最优解,从而使其进一步推广应用受到局限的问题,对算法的全局收敛性进行了深入的理论研究,并从改善全局收敛性的角度对算法作了一系列改进,最后对Bayes29这一典型的TSP问题进行了仿真实验。实验结果证明,改进后的蚁群算法具有很好的全局收敛性能。这为蚁群算法的进一步理论研究打下了很好的基础,对其在各优化领域中的推广应用具有重要意义。