现在模拟退火算法、粒子群优化算法、遗传算法和蚁群优化算法现在用的还多吗？

Baste · 发表于 2021-7-4 06:04

现在优化一般不都是用牛顿法和梯度下降法吗？那上面那些算法还有什么用途吗？他们都各有什么特点？优缺点？

JoshWindsor · 发表于 2021-7-4 06:07

研究这两类算法完全是两拨人，一个是进化计算的领域，一个是数学优化领域，这两个领域都是解优化问题的，但是思路上有着本质的不同。所以经常会出现以下情景
领域之间的互相鄙视在学术界也是司空见惯，所以我们这里尽量不带有偏见的去分析一下两类方法的适用场景和优缺点对比（如有偏颇，欢迎指正）。
宏观的来说目前数学优化的应用场景要稍微广一些，所以我这里只列举出进化计算方法（模拟退火算法、粒子群优化算法、遗传算法和蚁群优化算法等）的主要适用场景。进化计算目前应用比较多的场景我个人的感觉有以下五个方面（除去这五个方面传统数学优化会应用的比较多一些）：
1 神经网络超参数优化

神经网络超参数优化一直是一个经久不衰的话题，例如神经网络的训练算法的学习率，神经网络每层多少个隐含层节点，这些参数都属于超参数。超参数无疑对神经网络的效果有着极大的影响，传统的基于梯度的算法无法做超参数优化，因为根本无梯度可以求。所以目前主流的超参数优化方法有网格搜索，贝叶斯优化和进化计算。这可说进化计算在超参数优化的问题上的效果还是不错的，相关的paper也很多。当然这里这里提到的神经网络也可以扩展到广义的机器学习模型。
2 神经网络结构优化

神经网络结构优化，这个肯定是属于组合优化的问题，这类问题一般是NP-hard的（很难很难求解到精确解）。同样这类问题也是无梯度可求，基于梯度的方法不适用。所有多半是靠进化计算来做了。更多关于神经网络结构优化可参考深度学习如何优化神经网络结构|架构？
3 一部分结构和特性固定的组合优化问题

进化计算在一部分组合优化问题和整数规划问题上表现比较好，甚至能够比肩传统的数学优化算法或者击败传统的数学优化算法。例如针对传统的VRP问题（车辆路径规划问题），在精巧的设计变异，交叉算子的情况下，遗传算法能够取得不错的效果。
4 一部分机理模型难以建立的黑箱优化问题

有一部分优化问题由于其本身机理难以描述清楚或者其机理并不是一个解析解表达式的情况下，数学优化算法往往不适用，此时就是进化计算比较适合的情况了。举例来说就是我以前研究过带有偏微分方程的约束的优化问题，很多非线性的偏微分方程没有解析解，因此整个偏微分方程就是一个黑箱一样的东西，给一个输入能到达输出，但是就是无法知道输入和输出的函数表达式，因此也就无法求导数了。例如飞机动力学模型的设计，汽车动力学模型的设计都是依赖于流体的偏微分方程，这种动力学优化问题一般来说也很难用数学优化方法去解。据我所知进化计算在这方面应用会比较多一些。
5 多目标优化问题

传统的数学优化算法还没法直接去处理多目标优化问题，都是将多目标转化为单目标之后处理。而进化计算的最大的优势是可以直接处理多目标优化问题。至于为啥直接处理多目标优化问题比较好，可以参考：多目标优化的意义是什么
进化算法VS数学优化（以下的讨论均基于单目标优化问题）

1求解效果

进化算法只需计算目标函数的值即可，对优化问题本身的性质要求是非常低的，不会像数学优化算法往往依赖于一大堆的条件，例如是否为凸优化，目标函数是否可微，目标函数导数是否Lipschitz continuity等等。例如上面提到的汽车动力学模型的设计是带有流体偏微分方程约束的，此时你根本就不知道那个目标函数凸不凸，可导不可导。这一点是进化算法相对数学优化算法来说最大的一个优势，实际上同时也是进化算法一个劣势，因为不依赖问题的性质（problem-independent）对所有问题都好使往往意味着没有充分的利用不同问题的特性去进一步加速和优化算法（这里很具有哲学辩证思想的是有优点往往就会派生出缺点）。这样看来数学优化算法的条条框框实际上是划定了，数学优化算法的适用范围，出了这个范围好使不好使不知道，但是在这个范围内数学优化就能给出一个基本的理论保证。基于一些特定的组合优化的结构去设计的进化计算方法已经实际上引入了更多的关于问题本身的信息了。这也就是在一些组合优化问题上，进化计算能够比肩传统数学优化的原因。
结论：对问题结构确定的优化问题，有充分的关于优化问题的信息来利用的时候数学优化一般来说有优势，例如线性规划，二次规划，凸优化等等。反之，可能使用进化算法就会有优势。对于一些数学优化目前不能彻底解决的问题例如NP hard问题，进化算法也有很大的应用前景。更多的利用特定问题的结构去设计特定的进化计算算法必然能够提升进化计算的能力。
2求解速率

进化算法的计算速度比较慢一直是大家的共识，这一点也很好理解，每迭代一次都需要计算M次目标函数，M是种群规模一般是30-50左右。进化算法的前沿的研究方向其中一个就是针对大规模优化问题的（large-scale）, 我也曾查阅过相关顶级期刊的论文发现进化算法里的large-scale的规模，一般决策变量几千维就是large-scale的了。对数学优化算法来讲可能根本构不成large-scale。而实际问题中经常决策变量达到几百万以上的规模，此时进化计算的缺点就被暴露了。所以侧面反应出了进化算法在计算速度的瓶颈限制了其在大规模优化问题上的应用。
值得一提的是近几年来随着深度学习的崛起，人们对计算力的要求越来越高，基于GPU的并行计算和分布式计算的架构被广泛的应用到人工智能的各个领域。由于进化算法本身天生具有良好的并行特性，基于GPU并行计算的进化算法是否能够在一定程度上解决进化算法速度慢的问题绝对是一个值得研究的topic。
3理论性保障：

目前对于进化算法的理论性分析还停留在一个很初级的阶段，虽然有用动力学模型（微分方程）和随机过程的方法来证明进化算法的收敛性，但一般而言这类理论分析的假设条件过于强了，此类研究工作更多的倾向于是探索性的阶段，基本上很难真正的从理论上指导算法的设计。个人希望能够有更先进的数学工具来帮助进化算法完善理论分析方面的不足吧。与之相对的数学优化在算法收敛性分析，算法复杂度分析上已经比较完备了，并且其理论在一定程度上能够指导算法的设计。
综上所述，进化算法也好，数学优化也好都只是认识问题解决问题的工具之一，工具本身并不存在绝对的优劣之分，每种工具都有其适用的场景，辨别它们的长短，找到它们合适的应用场景是我们这些用工具的人应该做的。
更多关于进化计算和数学优化的内容可以参考
文雨之：【学界】数据+进化算法=数据驱动进化优化？进化计算PK 数学优化

Baste · 发表于 2021-7-4 06:15

每一种算法的应用条件不一样。

很多算法在特别条件是已知中效果最好的，并不存在什么通用算法。

没有垃圾算法，只有不懂得使用的人。

当年神经网络也是垃圾算法，主要是不知道怎么用。
现在计算机中的垃圾算法，可能那天量子计算机普及了，在那种运行环境上可能是很好的算法。
有了电视，收音机并没有被淘汰。
有了核武器，但手枪并没有被淘汰。
各种算法就像数学公式一样，是一种思想，一种工具。像孙子兵法36计一样，真正能灵活运用的很少，每种算法都是一种策略，一种工具，看你怎么用。
你可能看不上的算法，如遗传算法，别人早用于生产系统了。

签单吧：泛海在线携手天云大数据打造智能投顾平台 - 天云大数据

无限量地生产稳健的量化交易策略：Trading System Lab (TSL)

APSchmidt · 发表于 2021-7-4 06:23

应用场景还是很多的，分两部分来说：
我研究生的课题就是和进化算法相关的，进化算法最主要的一个应用之一就包括高维数据最优值求解，包括经典的旅行商问题，路径规划问题等，这些都是可以通过进化算法来解决
神经网络参数的优化

如提问者所说，经典的BP神经网络是通过梯度下降来进行优化的，但是优化的结果取决于初始权重的设定、以及learning rate等参数的设定，所以训练的结果会存在不确定性，以及陷入局部最优，这个时候其实可以使用进化算法对参数进行调整，包括一开始的初始参数优化，或者可以通过模拟退火算法，神经网络的训练跳出局部最优的解空间。
神经网络结构的优化

最高票也提到了，当我们设计神经网络的模型的时候，通常会依据经验去确定其神经网络的结构，而没有更好的办法，是我们最终沦陷为调参boy。对于简单的神经网络而言，其结构的选择已经会对神经网络的训练结果会造成很大的影响了，更不要说深度神经网络，RNN、GAN等，而这种如果要人工调的话，真的就够呛了。这个时候进化算法就C为出道，他会在神经网络训练的过程中调整他的结构，并且不断的做出优化。综合上述两个优化方向，我们就可以对网络的参数和结构进行优化，这就变成了一个多目标问题。
超启发进化算法

现在各种不同的进化算法已经有很多了，基本把所有的动物都命名了一边，但是我觉得很多算法他其实都是有类似的思想的，而不同的算法适用于不同的问题和数据集，所以我觉得之后的趋势就是算法之前的融合。不去考虑用什么算法去解决什么问题，而是让算法在训练过程中评估需要用到什么方法，然后自行调用组合
工业生产

其实我这个了解的不多，就拿我遇到的事情来说吧。需要处理资源调配、车辆调配的一些问题，当然在主流业务上都有专门的运筹优化工程师在做相关优化，但是很多业务上都是简单粗暴的调配的，所需要的代价可想而知。在公司今年的目标里会有很多类似的优化节约成本的目标，其实我觉得如果真的掌握了一些经典的进化算法，在合适的问题上加以应用，会有意想不到的收获。所以现在挺关注启发式算法在实际问题中的应用的。
写在后面

脑子一热，噼里啪啦一通乱写，照道理应该要提供相关的引用证明的（一点也不严谨，但是谁让我懒）。应该也有写的不对的地方吧，如有问题望指正，多谢

RecursiveFrog · 发表于 2021-7-4 06:31

并不能因为一个算法现在不火就认为已经被淘汰。神经网络就是很好的例子。
derivative free 算法的优势在于不需要知道derivative 信息。所以这一类算法几乎是通用算法，能在任何问题上用。但通用方法一般效率上比不过specified的算法效率高。
虽然我一直做derivative based 算法，但从原理上来讲我更欣赏这些derivative free的算法。因为它们师法自然。看起来自然界采用derivative based 算法的情况非常少，这其中的原因还不明确。

zifa2003293 · 发表于 2021-7-4 06:36

用来凑成中国本科生数学建模竞赛文章

TheLudGamer · 发表于 2021-7-4 06:43

别的不清楚，这些heuristic算法在EDA领域的应用相当多。很多应用场景比如logic synthesis, floorplanning, placement的优化都不是梯度下降能解决的

JamesB · 发表于 2021-7-4 06:45

以我的个人体验，不成熟不客观的回答是：我认为这些算法是论文导向的。

DomDomm · 发表于 2021-7-4 06:50

这两种算法优化的适用问题完全不同啊。
传统优化（gradient-based）算法是在你问题目标函数连续的情况下才可以使用，gradient嘛，不连续根本微不了。对于离散问题和非凸问题，传统优化的大家会想办法找等价问题、松弛约束、尝试凸化什么的，再去解。
然鹅，找不到等价怎么办？不能松弛（松弛后效果不好）怎么办？再或者依然算不出来怎么办？
这个时候就上演化算法了（EA）。
EA适用于解决各种组合优化问题。在我看来，其本质其实是一种聪明的穷举。问题都已经恶劣成那样了（比如混合整数规划什么的），有一种有剪枝效果的穷举方法，这不挺好？然后比如多目标优化问题，MOEA/D（多目标演化算法）效果就很好啊，这时候你用gradient-based的方法解都没法解。
再细一点，在传统工业界里，比如造个高铁车头，飞机翅膀，大型工业零部件，找到这些组件的最优形状就往往是多目标优化问题。EA在这些行业里非常经常使用。

FeastSC · 发表于 2021-7-4 06:55

就我了解的牛顿法和遗传算法说一下，牛顿法适用于目的明确，然后无限逼近求近似最优解这种问题。遗传算法适合于只有个判断标准但没有明确目标的这种问题。
举个例子:
.你随便拽根头发，请问它的直径是多少毫米: 这个可以用牛顿法
.如果全球球员任我挑选，如何组建出能赢下一届世界杯的足球队: 这个问题只有每场比赛结果这个评判标准出来了，才能迭代出最优组合，这个就适合用遗传算法

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

现在模拟退火算法、粒子群优化算法、遗传算法和蚁群优化算法现在用的还多吗？

本帖子中包含更多资源

本帖子中包含更多资源