蒙特卡洛算法与遗传算法的区别是什么?

蒙特卡洛算法与遗传算法的区别是什么?

应该叫蒙特卡洛方法(Monte Carlo Method)与遗传算法(Genetic Algorithm),一个是方法一个是算法,层次上有不同。两者都能解近似最优化问题,都不能保证得到最优解。

蒙特卡洛方法的思想基础是统计学里的大数定理,类似于气枪打鸟,产生大量随机状态,通过合理的状态检验,我们可以得到有效状态,包括这些有效状态的数量、内容等各种信息,利用它们得到的统计结果得到的解的方法就叫蒙特卡洛方法。这是一种模拟统计方法,如果问题可以描述成某种统计量的形式,那么就可以用蒙特卡洛方法来解决。

例如一个复杂多边形求面积,要靠计算几何去算还挺麻烦的,但是判断一个点是否在图形内却很简单。如果我们在一个可以框住这个图形的矩形范围内采用均匀分布随机放置大量的点,每个点都能判断出在内部还是外部,那么就很好办了:矩形面积很容易求,多边形面积可以表示为矩形面积*点落在多边形内的概率,只要大量重复产生随机点,检查在内在外,然后统计的过程就可以了。

甚至有比较激进的分类是认为蒙特卡洛方法就是指不确定算法,包含全部的随机化算法……

遗传算法则是在搜寻最优解(近似最优解)的过程中,因为状态空间太大(指数阶甚至无穷状态),为了快速逼近最优解而提出的算法。核心思想在于先产生一定量的随机状态,计算其优化程度(或者叫适应度),保留优质的状态,并通过不断微调较优的状态来获得新状态加入竞争。因为十分类似进化论的“适者生存”理论,所以起名遗传算法(其实应该直译叫基因算法…)核心在于优势状态有更大概率保留和产生子状态,劣势状态虽然保留概率不高但也不是不可能保留,因此可以避免陷入局部最优解,同时人为加入了基因池容量限制(资源有限),保证了运转效率。