遗传算法写的这么厉害，为什么在最优化理论里面罕见有应用，还是以梯度下降为主呢？

TheLudGamer · 发表于 2021-7-14 17:22

DomDomm · 发表于 2021-7-14 17:25

遗传算法，还有粒子群算法，蚁群算法等等为代表的智能算法（也被称为进化计算），本质来说是单纯仅依靠对目标函数进行采样，然后通过一定的机制（不同的智能算法其搜索机制不一样）来达到群体的随机搜索的一类方法。
梯度类算法属于传统数学优化的范畴，主要采用目标函数梯度作为搜索方向或者根据梯度来构造搜索方向。
遗传算法的初衷：仅依靠采样目标函数的随机搜索

你回到遗传算法被发明的初衷：在于不依赖优化对象的模型，也就是说我是无需知道优化目标函数长啥样的，完全就靠采样就可以了。这么做的好处是对于黑箱一类的优化问题或者目标函数和目标函数梯度难以获得的优化问题来讲，此类算法有一定的优势。如果我比较容易能获得目标函数的梯度的话，那其实已经在很大程度上没有必要用遗传算法了。
遗传算法的优势其实也就是它的劣势，由于没有过多引入优化问题本身的信息（仅仅依靠对目标函数采样的信息）去设计算法。简单来说就是对什么问题都能用的算法，那一定对特定某一类问题效果不好。这一点非常符合 No Free Lunch theorem
相对来说梯度类算法需要知道目标函数具体表达式才行，同时还要求目标函数最起码是可微的那才有梯度吧。虽说这些条件一方面是限制了算法应用的范围，另外一方面反过来说明了梯度类算法引入了更多关于优化问题本身的信息来辅助算法搜索。
遗传算法和梯度类算法（数学优化）对比

1求解效果
对问题结构明确能够容易获得目标梯度的优化问题，有充分的关于优化问题的信息来利用的时候梯度类算法一般来说有优势，例如梯度类算法，线性规划，二次规划，凸优化等等在业界的应用都非常广泛。反之，可能使用遗传算法就会有优势。对于一些传统数学优化目前不能彻底解决的问题例如NP hard问题，遗传算法也有一定的应用前景。此时遗传算法也需要更多的利用特定问题的结构去设计特定的算法才能够提升算法的能力。
2求解速率
遗传算法的计算速度比较慢这一点也很好理解，每迭代一次都需要计算M次目标函数，M是种群规模一般是30-50左右。遗传算法的前沿的研究方向其中一个就是针对大规模优化问题的（large-scale），我也曾查阅过相关顶级期刊的论文发现进化算法里的large-scale的规模，一般决策变量几千维就是large-scale的了。对数学优化算法来讲可能根本构不成large-scale。而实际问题中经常决策变量达到几百万以上的规模，此时遗传算法的缺点就被暴露了。所以侧面反应出了遗传算法在计算速度的瓶颈限制了其在大规模优化问题上的应用。
3理论性保证
目前对于遗传算法的理论性分析还停留在一个很初级的阶段，虽然有用随机过程（马尔科夫性）的方法来证明进化算法依概率收敛到最优解，但一般而言这类理论分析停留在马尔可夫链证明的全局收敛性，当算法运行时间趋于无穷的时候，依概率1趋于全局最优。这个理论分析的结果聊胜于无吧。因为实际上在运行算法的时候没有人把运行时间设置为无穷大，而且何时停止搜索也不知道（因为缺乏最优性判定准则）。同时依概率1收敛的条件本身就非常弱，哪怕是完全随机搜索其实也都一样可以满足上面的收敛性条件。所以很多时候遗传算法说自己能收敛到全局最优也就成了一个美好的梦想。
遗传算法等进化计算方法主要适应场景

我列了一下目前以遗传算法为代表的进化算法方法主要的适用场景：
场景1: 神经网络超参数优化
场景2: 一部分结构和特性固定的组合优化问题
场景3: 一部分机理模型难以建立的黑箱优化问题
场景4: 多目标优化问题
除了以上场景你可以认为基本上就是数学优化（梯度类）算法的天下了。以上场景大致有两种情况一种是优化问题的模型是黑箱，梯度难以求得，例如场景1，场景2，场景3都属于这种情况。另外一种就是目前传统数学优化还不能很好解决的问题，例如场景 2，场景4 都属于这种情况。所以总得来说目前遗传算法为代表的进化计算方法主要还是捡数学优化的漏。一般我们会优先考虑数学优化方法，当数学优化解决不了的时候再考虑遗传算法。当一类问题采用遗传算法时基本上代表这是没有办法的办法了。
综上所述，进化算法也好，数学优化也好都只是认识问题解决问题的工具之一，工具本身并不存在绝对的优劣之分，每种工具都有其适用的场景，辨别它们的长短，找到它们合适的应用场景是我们这些用工具的人应该做的。下面是我之前创作的关于数学优化和进化计算对比的原创漫画，欢迎各位评论：

RhinoFreak · 发表于 2021-7-14 17:27

说明: 这个回答是在2018年年初的时候写的，当时这个问题下面只有一个回答说“遗传算法适合搜索空间大的问题”，所以这个回答一直针对这一点，主要从收敛速率方面讲的，其他方面只提了一下。现在这个回答排到前面了，只说收敛速率似乎不太够，在后面对优化问题的难点这个更大的问题做一点补充。
<hr/>所谓遗传算法适合搜索空间大的问题是误导性的，有必要做澄清。

遗传算法，或者更广泛的说，随机搜索算法(随机搜索算法是一大类非确定性搜索算法的统称Stochastic optimization, Stochastic Global Optimization）最主要的问题就是收敛性差，收敛速度慢。进化计算常常声称的优势就是马尔可夫链证明的全局收敛性，当算法运行时间趋于无穷的时候，以概率一趋于全局最优。即使是完全随机搜索，比如从标准正态分布产生一个点，好的话就作为均值，不做任何步长之类的参数调整，一样满足这一条件。这种理论保障这在实际中是完全没有意义的，有谁跑程序的时候把运行时间设置成无穷？

在很多问题上，这种程度的理论保障是不够的，需要更精细的收敛速率分析。具体来说就是，k次迭代之后找到的解的精度或者找到epsilon精度的解所需的迭代次数。对于收敛速率，上面那种随机算法收敛速率是sub-linear的，在普通单峰函数（如球函数）上搜索到 $\epsilon$ 精度所需的迭代次数是 $O(({1}/{\epsilon})^n)$ ，n是变量个数。这样即使是非常低的维度比如n=10，所需的时间也是不可接受的。

绝大部分算法是自适应调整的，能比上面那种要精细很多。从收敛速率方面考虑，自适应调整的随机搜索、进化计算、或者无梯度优化的收敛速率不可能超过 $O\left({1}/{n}\right)$ ，即收敛速率随着变量个数增加而下降。如果更精细一些，这个可以写成 $O(1/n\rho)$ , rho是Hessian的条件数。这对于神经网络一类的优化问题仍然是不可接受的，神经网络等问题中涉及的优化变量通常都非常大，state-of-the-art的模型则动辄达到 $10^6\sim10^8$ 的量级。无梯度优化过小的收敛速率使得在这些问题上所需的迭代次数是不可接受的。这才是这一大类算法没有被广泛应用的原因。

与此相对应的，梯度下降法的收敛速率是和维度（变量个数）无关的， dimension-free。这其实很好理解，从有限差分的角度来说，计算一次梯度需要n次有限差分进行估计，这样就退回到了无梯度的情形，收敛速率与维度成反比。这样dimension-free的算法才能用到变量个数非常多的，空间维度很高的优化问题。

Random Gradient-Free Minimization of Convex Functions

Our experiments confirm the following conclusion. If the computation of the gradient is feasible, then the cost of the iteration of random methods, and the cost of iteration of the gradients methods are the same. In this situation, the total time spent by the random methods is typically in O(n) times bigger than the time of the gradient schemes. Hence, the random gradient-free methods should be used only if creation of the code for computing the gradient is too costly or just impossible.

Linear Convergence of Comparison-based Step-size Adaptive Randomized Search via Stability of Markov Chains

Comparison based adaptive evolution strategies converge linearly. The convergence rate is inverse proportional to the dimension of search space $\lim_{t \rightarrow \infty} \frac{\|x_{t + 1}-x^* \|}{\|x_t -x^*\|} = \exp\left(- \frac{c}{n}\right)$ .

从这个角度来说，进化计算适合的实际上是搜索空间不那么大的问题。尤其是所谓的复杂优化问题，这种时候（变量个数不多）进化计算的优势在相当大程度上来自于搜索的随机性，相对于梯度每次迭代只搜索一个点来说，EAs每次迭代都会评估一整个种群的解。这是通过牺牲搜索的效率得到的（从初始化到找到一个局部极值所需的评估/迭代的步数更多了），只是变量个数不多的时候影响不大。无梯度优化在这样的问题取得了比较好的效果，如
Evolution Strategies as a Scalable Alternative to Reinforcement Learning
Path Integral Policy Improvement with Covariance Matrix Adaptation
Flexible Muscle-Based Locomotion for Bipedal Creatures
<hr/>进化计算以及很多随机优化算法领域，人们认为的优化问题的难点就是多峰问题，multimodal objective function。这种问题上很难做出什么有效的收敛速率方面的分析，使得这些领域长期就停留在“设计一个算法，跑几个函数，有的好有的不好”这样的程度。
至少在机器学习领域，高维非凸问题并没有那么多恶劣的局部极值，目标函数值很差的临界点通常是鞍点而不是局部极值，而局部极值本身的目标函数值通常和全局最优比较接近。更进一步的，由于模型参数数目极大，整个目标函数的Hessian是高度退化的，使得局部极值可能是连续存在的。
至少有相当的理由相信，局部极值并不构成高维非凸问题的主要难点。这种情况下，所说的优势还剩下多少？在神经网络上绝大部分临界点是鞍点这个结果到现在已经有很多年了，然而鞍点问题上进化算法表现如何，到现在也没有一个像样的说法。

相关问题
梯度下降法的神经网络容易收敛到局部最优，为什么应用广泛？

XGundam05 · 发表于 2021-7-14 17:32

遗传算法也是梯度下降啊，只不过这个梯度值是采样来的罢了，我想这个问题应该是问“为什么还是以反向传播为主？”吧（当然不是神经网络也可以啦，只要能显示地写出目标函数就行）。
那为什么反向传播很常用呢，因为反向传播只能用在白盒模型，你对损失函数知根知底，可以写出来，而且还可以求导，可以求梯度的解析解。甚至直接取导数为零的地方，或者是用拉格朗日乘数法都行。
但是遗传算法常用在黑箱模型，你对它一无所知，或者函数干脆就不可导，比如遗传算法的那个适应度值（类似于强化学习中的环境），写不出梯度的解析解，那咋办。这个时候就只能进行梯度估计了，没有解析解那就估计出数值解，采样越多，估计越准（误差方差越小），相当于贪心搜索。
遗传算法属于蒙特卡洛采样法，这类方法就是拿采样来求积分（数学期望），同样是蒙特卡罗采样法的还有策略梯度（Policy Gradient），零阶估计，这些都是梯度估计的方法，而且是等价的。
比如说零阶估计法，黑箱模型的损失函数写不出来怎么求导？在很多个正交的 $v$ 上采样就行，要多少？非常多，如果反向传播要训练一天，那采样1000次就得训练1000天...
$\hat{\nabla} _Xf\left( X \right) \approx \mathbb{E} _{v\sim N\left( 0,1 \right)}\left[ \frac{f\left( X+\varepsilon v \right) -f\left( X \right)}{\varepsilon}v \right] , \varepsilon >0$
总之，遗传算法当然厉害啊，但是要是目标函数是白盒的，可导的，谁还用遗传算法啊。

maltadirk · 发表于 2021-7-14 17:35

因为厉害都是吹出来的，换个模型就能发篇paper，反正别人也不会复现出来，实验结果有多垃圾只有做着自己知道。

pc8888888 · 发表于 2021-7-14 17:39

通俗点说，遗传算法、PSO为代表的一系列仿生启发算法(或者称非梯度优化)是在对目标问题内在机理了解极少情况下，以随机牺牲资源和效率进行求解。
直白的比喻，求x+1=2，你对这个问题的内在机理完全清楚可以直接写出1，当然如果你确实不会求解一元方程，也可以用启发算法在-5到5区间内搜索，至少可以逼近答案。
再回头看近几年梯度下降用的最多的神经网络，很明显我们对神经网络内在机理有一定理解，但远远达不到对1+1=2的理解程度，因此可以用随机算法求解。实际上神经网络中从头到尾都透出随机的气味，初始化，dropout........
少用非梯度优化原因1既然有一定认识，比如梯度确实对优化有益那就应该充分使用，2是时间等不起，宁肯接受差一点到解。
ps 仿生仿生仿的生物进化史就是大自然内在机理几乎无了解，以巨大的生物数量，漫长的地质年代进行的一场史诗优化游戏，效果的确不错，即便一个节肢动物的神经系统也不熟我们的state-of-the-art，不过也不是所谓的全局最优解。

HuldaGnodim · 发表于 2021-7-14 17:45

主要是因为遗传算法计算量太大，比如神经网络，10000个样本，如果用梯度下降，迭代一次只需要计算10000次，如果用遗传算法，population size是100的话，迭代一次就需要计算1000000次，是梯度下降的100倍，这还不包括选择、交叉、变异等的计算量。

Baste · 发表于 2021-7-14 17:50

用梯度下降的前提是可导吧？但遗传算法没这个限制

DomDomm · 发表于 2021-7-14 17:58

佛系玩法和常规玩法

佛系玩法让人觉得很厉害，明明看着很扯却常常能完美通关.然而佛系玩法随机性太大而且一般人去玩要花很长很长的时间才能偶然通关，对于一般人游戏体验太差
因此大家通常选择常规玩法，循规蹈矩也能通关

jquave · 发表于 2021-7-14 18:00

罕有应用？请恕不能苟同。
至少，目标函数不可微的问题不适合梯度类搜索算法；此外，多目标优化也被认为适合以遗传算法为代表的智能算法，因为批量输出pareto非劣解更有意义；最后，也是最重要的，一些优化问题的目标函数根本写不出精确的表达式，梯度类算法在面对这类被称为“黑箱优化”的问题面前也很无力。

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

遗传算法写的这么厉害，为什么在最优化理论里面罕见有应用，还是以梯度下降为主呢？

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源