文化基因算法（Memetic Algorithm, MA）是Pablo Moscato 提出的建立在模擬文化進化基礎上的最佳化算法,它實質上是一種基於種群的全局搜尋和基於個體的局部啟發式搜尋的結合體。
基本介紹
- 中文名：文化基因算法
- 外文名：memetic algorithm
- 提出者：Pablo Moscato
- 基礎：模擬文化進化
- 屬性：最佳化算法
- 提出時間：1989年
文化基因算法,文化基因由來,文化基因涉及學科,
文化基因算法
文化基因算法（Memetic Algorithm, MA）是Pablo Moscato 提出的建立在模擬文化進化基礎上的最佳化算法,它實質上是一種基於種群的全局搜尋和基於個體的局部啟發式搜尋的結合體。文化基因算法的概念被提出後,已被越來越多的研究人員接受和採納。本文主要介紹了文化基因算法的起源、實現過程,以及在各類最佳化問題中的套用情況。
文化基因由來
Pablo Moscato於1989年首次提出memetic algorithm的 概念 。 Memetic一詞由meme而來,其諧音譯法很多,根據道金斯提出的本意,應理解為“文化基因” ,因此我們將Memetic algorithm稱為文化基因算法。
Pablo Moscato認為,在遺傳算法（GA）中,變異操作可以看作是含有一定噪聲的爬山搜尋,實際上模擬遺傳編碼和自然選擇的過程不應包含變異操作,因為在文化進化的過程中,在眾多的隨機變化步驟中得到一個正確的可提高整體性能的一步進展是非常困難的,只有此領域的擁有足夠的專業知識的精通者們,才有可能創造新的進展,但是這樣的事情發生的頻率是很低的。 因此,文化基因的傳播過程應是嚴格複製的,若要發生變異,那么每一步的變異都需要有大量的專業知識支撐,而所有的變異都應帶來進展而不是混亂,這就是為什麼我們觀察到的文化進化速度要比生物進化速度快得多的原因。 對應於模擬生物進化過程的遺傳算法,Moscato提出了模擬文化進化過程的文化基因算法,文化基因算法用局部啟發式搜尋來模擬由大量專業知識支撐的變異過程,因此說,文化基因算法是一種基於種群的全局搜尋和基於個體的局部啟發式搜尋的結合體。
文化基因算法的這種全局搜尋和局部搜尋的結合機制使其搜尋效率在某些問題領域比傳統遺傳算法快幾個數量級,可套用於廣泛的問題領域並得到滿意的結果。 很多人將文化基因算法看作混合遺傳算法、 遺傳局部搜尋或是拉馬克式進化算法,實際上,文化基因算法提出的是一種框架、 是一個概念,在這個框架下,採用不同的搜尋策略可以構成不同的文化基因算法,如全局搜尋策略可以採用遺傳算法、 進化策略、 進化規劃等,局部搜尋策略可以採用爬山搜尋、模擬退火、貪婪算法、禁忌搜尋、導引式局部搜尋等。
文化基因涉及學科
在遺傳算法中,我們通常對個體（Individual） 進行選擇、 交叉、 變異操作,通過對一代一代個體的適應性進化得到問題的最優解。 在文化基因算法中,用了智慧型體 （agent,實際上agent在此譯為“代表”更加恰當）的概念,遺傳操作的對象並不是種群空間中的普通個體,而是各局部區域推選出的優秀代表,遺傳操作的結果是選出那些適應性強的優秀代表,同時也產生一些交叉作用後新的個體,這些新個體可能屬於一些新的區域,在下一代的局部搜尋中它們會被附近的優秀個體取代,然後再進行進一步的全局進化。 這種局部與全局的混合搜尋機制顯然要比單純在普通個體間搜尋的進化效率高得多。
