蒙特卡洛演算法與遺傳演算法的區別是什麼?

並沒有實際應用過蒙卡演算法,遺傳演算法生掰硬套用過兩次,對這兩種演算法總是拎不清。
感覺上兩者本質上都是產生隨機數進行試驗,來獲得某種結果?
只不過遺傳演算法是在一定約束條件下採用生物學遺傳變異的方法生成隨機數,並在進程中淘汰一些值,而蒙卡則要求在約束範圍內完全隨機?
然後遺傳演算法用來求全局最優解,而蒙卡求期望或概率(還是說只要給定的目標合適,其實兩者都可以算最大值、最小值、概率、期望等)?
還是說遺傳演算法就是蒙特卡洛的一種?


應該叫蒙特卡洛方法(Monte Carlo Method)與遺傳演算法(Genetic Algorithm),一個是方法一個是演算法,層次上有不同。兩者都能解近似最優化問題,都不能保證得到最優解。

蒙特卡洛方法的思想基礎是統計學裡的大數定理,類似於氣槍打鳥,產生大量隨機狀態,通過合理的狀態檢驗,我們可以得到有效狀態,包括這些有效狀態的數量、內容等各種信息,利用它們得到的統計結果得到的解的方法就叫蒙特卡洛方法。這是一種模擬統計方法,如果問題可以描述成某種統計量的形式,那麼就可以用蒙特卡洛方法來解決。

例如一個複雜多邊形求面積,要靠計算幾何去算還挺麻煩的,但是判斷一個點是否在圖形內卻很簡單。如果我們在一個可以框住這個圖形的矩形範圍內採用均勻分布隨機放置大量的點,每個點都能判斷出在內部還是外部,那麼就很好辦了:矩形面積很容易求,多邊形面積可以表示為矩形面積*點落在多邊形內的概率,只要大量重複產生隨機點,檢查在內在外,然後統計的過程就可以了。

甚至有比較激進的分類是認為蒙特卡洛方法就是指不確定演算法,包含全部的隨機化演算法……

遺傳演算法則是在搜尋最優解(近似最優解)的過程中,因為狀態空間太大(指數階甚至無窮狀態),為了快速逼近最優解而提出的演算法。核心思想在於先產生一定量的隨機狀態,計算其優化程度(或者叫適應度),保留優質的狀態,並通過不斷微調較優的狀態來獲得新狀態加入競爭。因為十分類似進化論的「適者生存」理論,所以起名遺傳演算法(其實應該直譯叫基因演算法…)核心在於優勢狀態有更大概率保留和產生子狀態,劣勢狀態雖然保留概率不高但也不是不可能保留,因此可以避免陷入局部最優解,同時人為加入了基因池容量限制(資源有限),保證了運轉效率。


狹義地理解,區別大概在於目的性。蒙特卡洛目的強調根據目標distribution取樣,而遺傳演算法目的更多在於根據某個penalty函數求得最優。

但是廣義來講,前者是包含後者的。genetic演算法最早的嚴格數學模型大概要從Feynman-Kac模型開始算起,在蒙特卡洛世界,對應的演算法其實就是大名鼎鼎的particle filter或者說是sequential monte carlo.

目的雖然不同,但是共享一套架構和語言。

希望有幫助


推薦閱讀:

輪盤賭算?
誰能通俗的講解一下NSGA-II多目標遺傳演算法?
遺傳演算法相關參數設置?
工程上,實用價值最高的智能優化演算法有哪些?

TAG:演算法 | 遺傳演算法 |