文化算法

文化算法是Robert G.Reynolds於1994年提出的一種雙層進化機制，文化作為一種將人以往的經驗保存於其中的知識庫，以供後人在知識庫中學到沒有直接經歷的經驗知識。

基本介紹

• 中文名：文化算法
• 外文名：Cultural Algorithms
• 提出者：Robert G.Reynolds
• 提出時間：1994年
• 機制：雙層進化

原理簡介

文化算法正是基於此目的來模擬人類社會的演進過程而提出的。通過—個獨立於種群空間的信仰空間，來獲取和保存並加以整合解決問題的知識，使種群的進化速度超越單純依靠生物基因遺傳的進化速度，具有良好的全局最佳化性能。

詳細內容

文化算法由種群空間和信仰空間構成雙層進化機制，總體上包括三大元素：種群空間、信仰空間和通信協定。

文化算法結構圖

種群空間從微觀的角度模擬生物個體根據一定的行為準則進化的過程，信仰空間從巨觀的角度模擬文化的形成、傳遞和比較等進化過程。

種群空間和信仰空間是兩個相對獨立的進化過程，但是又相互影響相互促進，兩個空間根據通信協定相互聯繫，對進化信息進行有效提取和管理，並將其用於指導種群空間的進化。文化算法基本框架結構如右圖所示。

這個過程使得種群像人類社會推演一樣，不僅有生物特徵的進化，而且有文化信念作為指導，超越單純的生物進化，具有目的性和方向性。算法結束後，末代種群中的最優個體經過解碼，可以作為問題近似最優解。

文化算法的重要特徵是引進了信仰空間，將群體空間中的個體在進化過程中形成的個體經驗，通過接受函式傳遞到信仰空間，信仰空間將收到的個體經驗看作一個單獨的個體，根據一定的行為規則進行比較最佳化，形成知識儲備，它根據現有的經驗和新個體經驗的情況更新知識，修改群體空間中個體的進化行為規則, 以使個體空間得到更高的進化效率。

具體作用機理

1）初始化一個種群空間p，然後通過目標函式（適應度函式）對種群空間中的個體進行評價；

2）根據目標函式給定的取值範圍和初始種群中的候選解，按照信仰空間結構，生成初始信仰空間；

3）根據影響函式influence()，對種群中的每個父個體進行變異，生成相因個數的子個體；

4）對於生成的父、子共2p新中群的每個個體，從中隨機選取c個個體與其進行比較，如果該個體適應值優於與其比較的個體則稱其獲勝一次，記錄每個個體獲勝次數。選取p個具有最多勝利次數的個體作為下一代的父個體；

5）設定接收函式，更新信仰空間；

6）不滿足結束條件，則重複（3）至結束。

文化算法的特點

文化算法具有以下特點：

(1)雙重進化繼承：在種群空間和信念空間分別繼承父代的信息；

(2)種群空間的進化是由信念空間中保存的知識進行引導；

(3)支持種群空間和信念空間的層次結構；

(4)支持兩個空間的自適應進化；

(5)不同空間的進化可以按不同的速度進行；

(6)支持不同算法的混合問題求解；

(7)“文化”改變的不同模型可表達於一個模型之內。

文化算法的以上特徵決定了其可適用於：種群空間和信念空間按不同速率進化的複雜系統；需採用不同方式的知識表示的問題；結合搜尋和知識引導的混合系統；需要多種群及其互動的問題求解；支持多層次種群空間和信念空間並存的多層次結構問題等。

理論發展

Reynolds於1994年最先引入文化算法的概念，他指出任何符合文化算法要求的計算構架都能夠被用來表示種群空間，如進化規劃、進化模式、遺傳算法等；不同的符號表示方法都能被用來描述信念空間，如語義網路、邏輯、集合論等。他最初採用遺傳算法來模擬微觀進化過程，用Mitchell所描述的譯本空間(VersionSpaces)來模擬巨觀進化過程。隨後他和他的學生相繼在文化算法領域展開研究，並取得一定成果。

目前國外大部分相關文獻均來自於Reynolds和他的學生。Reynolds和Chung於1995年起利用文化算法求解全局最佳化問題，並取得較好結果。

Chung關注於解決靜態無約束實值函式最佳化，他提出了兩種知識類型：環境知識和標準知識，後來它們被認為是劃分信念空間的兩種最基本的知識類型。

Chung和Reynolds比較了兩種知識類型在引導搜尋過程中所起到的不同效果：環境知識不適用於高維問題；用標準知識同時決定搜尋步長和方向能起到不錯的效果，並指出算法的改進取決於知識類型和問題結構。Zannoni和Reya~olds於1996年將遺傳規劃嵌入文化系統框架(即C )，用於控制規划進化過程(Pm—gram Evolution Process)E引。Shinin Zhu提出模糊文化算法(Rm Fuzzy Cultural Algorithm)，其中包括模糊接受函式、模糊信念空間、模糊知識更新以及模糊影響函式。

1999年Jin和Reynolds提出了一種 維地域模式(regional schema)，稱為“知識元”(Bellef—cel1)，將其作為文化算法中的顯性機制來對非線性約束知識進行獲取、保存和整合，並在Chung的基礎上除去環境知識，加入約束知識(constraint knowledge)。

2002年David提出基於GP的雙文化算法框架。此外他們還將文化算法用於圖像分割、動態最佳化問題、數據挖掘等。當然除了Reynolds 和他的學生外，還有其他的一些學者也致力於文化算法的研究。CoeUo和Becerra在Jin和Reynolds基礎上對一些約束準則作了進一步改進，如信念空間的約束部分每代更新一次，而標準知識每k代更新一次等。

2003年他們首次提出將文化算法用於解決多目標最佳化問題。Digalakis J G和Margaritis K G提出一種多種群文化算法(a multipopulation cultural algOdthm)——並行協作文化算法(paralld c0一operating cultural algo—rithm)，並將之用於複雜組合最佳化問題，證實了種群間採用不同的進化行為，以及彼此間的信息交流、共同協作往往能起到不錯的效果1 引。N．B．HO和J．C．Tay提出了一種有效的文化算法CENACE，用於靈活作業調度問題(Flexible Job—Shop Scheduling Problem)。

他們用合成調度規則(Composite Dispatching Rules)產生初始種群，採用文化進化體系來維護各代的知識模式和資源分配，信念空間影響可行染色體表示的變異和選擇。Cruz，Pacheco等將文化算法運算元引入量子進化算法，能夠更加可靠地更新算法狀態，避免過早收斂於局部最優。同時也改進了結果，保持了算法所需要的特徵，如，魯棒性、快速收斂等l2引。Trung和Xin Yao將文化算法與疊代局部搜尋(Iterated Local Search，ILS)結合，提出了一種新的基於種群的構架CA—ILS，用於解決單目標無約束數值最佳化問題。該算法能夠有效地檢測問題的結構模式，自適應地改變全局搜尋補償和方向，從而能很快地找到下一個更優解。

套用

1.在不同的種群內可按不同的速度進行進化求解的複雜系統問題；

2.結合搜尋和知識引導的混合系統求解問題；

3.需多種群及其互動的求解問題；

4.將不同算法結合利用其各自特性進行混合求解的問題等。