在优化问题里，强化学习相比启发式搜索算法有什么好处？

NoiseFloor · 发表于 2021-11-7 15:47

看到一些在黑盒优化的问题上（Nerual Structure Search或电路优化等）有人在强化学习这方面做了些成果，想知道相比贝叶斯优化、粒子群算法、遗传算法这样的启发式搜索算法，强化学习有什么好处？这两类算法又分别有什么优点和不足？

redhat9i · 发表于 2021-11-7 15:53

最大的好处就是神经网络的可塑性非常强，并且号称具有迁移学习能力。举一个最简单的例子，对于传统优化问题来说，无论是贝叶斯优化还是启发式算法，对于每求解一组新问题，都需要针对每个实例（例如一个TSP路径规划实例）运行一次完整的优化算法。但是实际上这些问题的最优解可能有某种强关联，对于这种情况，基于神经网络的强化学习算法一旦解决了其中某一个问题，就有可能快速求解其他问题。一个直观的理解就是Pointer Network，通过监督学习/强化学习，神经网络可以根据已经求解的TSP方案确定一个新的TSP规划问题的方案。

经典的Pointer Network架构

但是，上述情况只是理想情况，在真实的基于强化学习的优化场景中，强化学习的训练过程其实相当复杂，目前的主流算法A3C和PPO目前来看并不能高效利用搜索过程中的知识。目前来看，RL算法在调参之后可以达到近似专业求解器的效果。但是短期来看，鉴于专业求解器的可解释性和鲁棒性，基于强化学习的优化算法依然有较大的提升空间。下图是港中深的查宏远老师AAAI 2021年的RL-Based TSP Solver的最新成果，可以看到RL方法尽管已经有非常大的进展，但是相比启发式方法依然有一定程度的差距。

上面有提到，神经网络擅长学习而不擅长搜索，而传统搜索算法，例如演化算法和启发式搜索算法擅长搜索而不擅长学习。考虑到这种困境，其实一个很好的解决方案是让演化算法去搜，然后让神经网络去看着演化算法的结果学习。目前来说，优化算法和强化学习的结合已经逐渐引起了大家的注意。在目前的基于强化学习的TSP求解算法中，已经有不少的算法尝试先基于近似最优解(Oracle)进行imitation learning/supervised learning，随后再使用强化学习算法进行学习。上图所示的SL+RL就代表了这种思想，可以看到相比传统的单纯基于RL或SL的Deep Learning Solver，这种混合了启发式算法知识和强化学习策略的求解器可以取到更好的性能。可以预见，在未来，这样的模式将会被广泛推广到Bin Packing、Job Shop Scheduling等各个组合优化领域，相比与熟优熟劣的争执，这种对不同算法的结合策略显然是更有价值的。

RecursiveFrog · 发表于 2021-11-7 15:54

1，和粒子群，差分进化算法比，强化学习的优点在于充分利用了历史样本。任何优化算法都需要寻找一个下降或者以一定概率下降的方向。梯度优化算法选择负梯度，粒子群，差分进化则通过与最优解随机杂交得到高概率下降方向。以上算法，都只利用了当前最优样本来更新，而强化学习基于评价函数得到下降方向，由于评价函数是基于所有已有样本的，因此信息利用更充分。
2，在马尔科夫序列的优化上，强化学习比贝叶斯优化更强。贝叶斯优化和强化学习一样，也基于历史样本建模得到代理模型/评价函数，从而也可以充分利用已知样本。但是在马尔科夫序列的优化中，强化学习在每一个序列节点评价函数的输入是当前状态，而贝叶斯算法需要将整个已知序列作为输入，维度高，建模更难。可见，强化学习充分利用了问题本身的结构，减少了建立评价函数所需样本，效率更高。
综上，强化学习的优点在于充分利用优化问题的先验结构（马尔科夫性），以及已有的样本。所以，如果你想针对特定过程开发一种比强化学习更强的优化算法，那也一样需要充分利用问题的特殊结构，充分利用已知样本。懂了没？

super1 · 发表于 2021-11-7 15:57

两年过去了，对问题有了一些新的理解，自问自答一下吧，期望说的不到的地方有大神可以补充，学习一下~
其实正如高赞回答所说，神经网络擅长学习而不擅长搜索，而传统搜索算法擅长搜索而不擅长学习。目前根据我的实验结果，传统的优化算法诸如BO、PSO、EA要比DRL效果好的多，稳定性也高的多，无论从搜索的效果还是收敛速度上来说都是这样。比如BO只需要搜索300次，就可以到最优点；基于种群进化的算法：种群25，迭代30次，也可以到最优点。但对于DRL，迭代了1e4次，也勉强才到次优点。DRL的收敛曲线差不多是图1这样（PPO找Ackely函数的最优点([1]*n))，一个明显的趋势是，DRL后面的表现越来越稳定（当然对于其他算法来说也应该是这样）。

图1：DRL优化结果学习曲线（横坐标是迭代次数，纵坐标是此次迭代找到的值）

究其原因，个人认为大概有几点：1）DRL的探索方式很低效，只是在action上加噪声；而BO是根据采集函数进行的，基于种群的进化算法相当于变向利用了梯度信息； 2）DRL的死亡三角问题，让数据利用率本身就很低。3）个人认为DRL本身不适合做一些精细化的操作，因为这要求调整超参数让算法表现的很激进，带来的后果就是收敛速度慢，甚至无法收敛。
所以相比已有的搜索算法来说，DRL很难或者不适合部属在样本比较贵的场合下。就我看到的应用场景，都是用廉价数据去近似昂贵数据。比如Google的芯片自动化布局布线中，是用走线长度近似PPA。还有在早期的NAS中，评估结果的时候也仅对生成的神经网络训练1个epoch。

但从积极的角度来说，传统优化算法的执行是一次性的，当有一个新的任务时，需要从头执行一次，很难做到迁移学习的（也许有一些tricky的方法，比如MTBO、或者复用历史记录，但似乎不够优雅）。而神经网络的迁移学习更加灵活，利用简单的pre-train与fine-tuning，在新的相关联任务上很容易就会有效果。即便从大多数DRL应用场景来看，通常是训练一个网络在实际场景中去做应用与调度，而不是训练结束后就扔掉了。
此外，神经网络的特征提取能力，也可以帮助解决一些实际中的困难。具体来说，已有的优化算法都是直接在欧式空间上进行优化的，但这在一些应用场景中不是很明智的选择，因为有些应用场景在欧式空间里的响应很不平坦，或者有些维度有些冗余或者相关性，而传统算法都不能有效的处理这些场景。

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

在优化问题里，强化学习相比启发式搜索算法有什么好处？

本帖子中包含更多资源

本帖子中包含更多资源