请问有哪些最优化算法可以做全局优化？

Zephus · 发表于 2021-7-4 09:17

目前我只知道有模拟退火算法，不知道还有哪些算法，收敛速度如何，因为我需要解决的问题变量维度很多。

Zephus · 发表于 2021-7-4 09:18

如果不对问题结构做任何假设的话，没有任何方法可以做全局最优化，模拟退火也不能。
如果不假设结构，函数可以长成任意样子，除非能穷举遍历所有局部最小值点，否则根据局部信息是根本无法判断全局最优解在哪个方向。Nesterov甚至证明过，在一般的非凸不可导的函数优化中，在一个给定的点找一个局部下降方向都可能是NP-hard的（相对问题的维度），更别说找局部最小值甚至全局最优解。
一般来说，要保证找到全局最有值，我们需要假设函数是凸的。当然凸只是一个充分条件，并不是必要的，有很多非凸的问题也能保证优化算法收敛到全局最优（比如matrix completion问题就被证明了所有局部最优点都有相同的函数值，所以也都是全局最优点），但这个能不能保证还得看具体问题。

mastertravels77 · 发表于 2021-7-4 09:26

优化算法的有效性和效率很大程度上依赖于问题，没有一种非常通用的方法适用于所有问题，这是著名的所谓“No free lunch”理论。
具体地，你应该说说你要求解的问题的特点，才好给你建议的算法，包括：维度有多高，会超过30维吗，是连续函数吗，非线性程度怎么样，能求出梯度吗(有限差分法可以求出梯度也可以)，有约束吗，等式约束还是不等式约束，单目标还是多目标优化，连续变量优化还是组合优化。
你提到全局优化。目前，在数学上，还没有算法能证明自己的全局收敛性，只有部分方法能保证局部收敛性。在应用中，一般有两类方法，可以尽可能地找到全局近优解：一是采用进化算法，像GA，PSO，DE等等；二是采用局部优化算法(最常用的如SQP)+multistart策略。后者的效率比进化算法高，大部分全局优化问题都可以用它来解决。

c0d3n4m · 发表于 2021-7-4 09:29

实名反对一下上面的部分回答。
当前全局优化算法分为两种类，确定性算法和非确定性算法。上面这些涉及到进化算法，蚁群算法，模拟退火算法主要都是在说非确定性算法，一般只能保证找到可行解，无法保证是否是全局最优。而求解非凸全局优化的确定性算法基本上都要基于分支定界，其中可能大部分的计算都是在验证某些解不是全局最优解。
具体这些基本概念的概览请参照这个答案和里面的链接。
启发式优化算法中，如何使之避免陷入局部最优解？如果题主需要保证全局最优性，那只能考虑确定性算法，而确定性算法的求解效率基于具体的问题形式。对于某些形式的问题，现有的求解器可以快速得到给定精度的最优解。而如果题主的问题形式比较复杂，无法转化，并且更在意是否能快速找到一个可行解，就需要考虑采用非确定性算法。
现有的比较出名的求解器，比如Baron，基于分支定界，并且采用了很多启发性搜索策略提高计算效率。
https://en.m.wikipedia.org/wiki/BARON

Arzie100 · 发表于 2021-7-4 09:30

才疏学浅，强答一番，希望能探讨一下
我理解全局最优跟局部最优并不是由算法决定的，而是由问题决定的
所谓能求解的全局最优，指的其实是全局只有一个局部最优解，如果有多个局部最优解，那就涉及到比较多个局部最优的问题
如果问题是固定的，不会受时间等变量影响，多迭代几轮，应该比较有希望选出一个全局最优解
如果函数图像本身会变动，包含了不可控因素，那么求解全局最优本身是不可能的，不如将就用局部最优

Ylisar · 发表于 2021-7-4 09:31

相对传统基于梯度信息的数值优化方法，启发式算法的确有一定的全局寻优能力，比如进化计算，遗传算法，粒子群优化，各种动物园算法等等。但这些能力优点夸大的嫌疑，随便给个np-hard问题就歇菜了。最好的方法，建议针对具体问题加入先验信息，设计针对性的算法来解决。

unityloverz · 发表于 2021-7-4 09:40

可以试试麻雀搜索算法（SSA），优化效果非常的好

IT圈老男孩1 · 发表于 2021-7-4 09:45

这种大规模问题还是用确定性算法吧，进化算法不好使。GAMS中的BARON或αBB，或者免费的SCIP软件都可以。

kyuskoj · 发表于 2021-7-4 09:46

国产优化数值计算软件1stOpt里的通用全局优化算法（UGO），貌似强悍无比。

rustum · 发表于 2021-7-4 09:51

我是学水文的，在进行水文模型参数率定时，往往要考虑参数的最优性问题。其实就是手里有了实测值，希望模型最终模拟的结果尽可能地逼近实测值。这也是各类水文模型参数优选的目标函数。通常用的较多的是遗传算法、粒子群算法、模拟退火算法、蚁群算法、鱼群算法、狼群算法、免疫算法、蜘蛛群居算法以及SCEM-UA等。但其实效果都差不多，需要调整算法中的一些参数，以防止陷入局部最优。

		自动登录	找回密码
密码			立即注册