montecarlo - 比较蒙特卡罗方法和进化算法

Question

蒙特卡洛方法和进化算法之间有什么关系？从表面上看，它们似乎是用于解决复杂问题的不相关的模拟方法。哪种问题最适合？他们能解决同样的问题吗？两者之间有什么关系（如果有的话）？

Answer 1

根据我的经验，“蒙特卡洛”是一个严重超载的术语。人们似乎将它用于任何使用随机数生成器的技术（全局优化、场景分析（Google“Excel Monte Carlo 模拟”）、随机积分（每个人用来演示 MC的 Pi 计算）。我相信，因为你提到您的问题中的进化算法，您正在谈论用于数学优化的蒙特卡洛技术：您有某种具有多个输入参数的适应度函数，并且您希望最小化（或最大化）该函数。

如果您的函数表现良好（无论您从哪个输入开始，您都会达到一个单一的全局最小值），那么您最好使用确定的最小化技术，例如共轭梯度法。许多机器学习分类技术涉及寻找参数，以最小化超平面相对于训练集的最小二乘误差。在这种情况下，被最小化的函数是 n 维空间中的一个平滑、行为良好的抛物面。计算坡度并滚下坡。十分简单。

但是，如果您的输入参数是离散的（或者如果您的适应度函数具有不连续性），则不再可能准确计算梯度。如果您的适应度函数是使用一个或多个变量的表格数据计算的（如果变量 X 小于 0.5，则使用此表，否则使用该表），则可能会发生这种情况。或者，您可能有一个从 NASA 获得的程序，该程序由 20 个模块组成，这些模块由您作为批处理作业运行的不同团队编写。你向它提供输入，它会吐出一个数字（想想黑盒子）。根据您开始时的输入参数，您可能会以错误的最小值结束。全局优化技术试图解决这些类型的问题。

进化算法形成了一类全局优化技术。全局优化技术通常涉及某种“爬山”（接受具有更高（更差）适应度函数的配置）。这种爬山通常涉及一些随机性/随机性/蒙特卡洛性。一般来说，这些技术更有可能在早期接受不太理想的配置，并且随着优化的进行，它们不太可能接受劣质的配置。

进化算法松散地基于进化类比。模拟退火基于金属退火的类比。粒子群技术也受到生物系统的启发。在所有情况下，您都应该将结果与配置的简单随机（又名“蒙特卡罗”）抽样进行比较……这通常会产生等效的结果。

我的建议是开始使用确定性的基于梯度的技术，因为它们通常需要比随机/蒙特卡罗技术少得多的函数评估。当你听到蹄声时，你会想到马而不是斑马。从几个不同的起点运行优化，除非您正在处理一个特别讨厌的问题，否则您最终应该得到大致相同的最小值。如果没有，那么您可能有斑马，应该考虑使用全局优化方法。

Answer 2

好吧，我认为蒙特卡洛方法是这些使用随机数来解决优化问题的方法的总称。通过这种方式，即使进化算法使用随机数（事实上也确实如此），它们也是蒙特卡洛方法的一种。

其他蒙特卡洛方法有：metropolis、wang-landau、parallel tempering等

OTOH，进化方法使用从自然界借来的“技术”，例如突变、交叉等。