協同演化算法(coevolutionary algorithms,CEA)是當前國際上計算智慧型研究的一個熱點,它運用生物協同演化的思想,是針對演化算法的不足而興起的,通過構造兩個或多個種群,建立它們之間的競爭或合作關係,多個種群通過相互作用來提高各自性能,適應複雜系統的動態演化環境,以達到種群最佳化的目的。
基本介紹
- 中文名：協同演化算法
- 外文名：coevolutionary algorithms
- 縮寫：CEA
基本信息,協同演化算法設計、實現和套用,機制設計,問題表示,遺傳操作,算法實現,
基本信息
協同演化算法(eoevolutionary algorithm,CEA)通過構造兩個或多個種群,建立它們之間的競爭或合作關係,多個種群通過相互作用來提高各自性能,適應複雜系統的動態演化環境, 以達到種群最佳化的目的.與協同演化算法相比,演化算法只採用基於個體自身適應度的演化模式,沒有考慮其演化的環境和個體之間的複雜聯繫對個體 演化的影響.它在套用中表現出了易出現未成熟收 斂並且收斂的速度較慢等缺陷.而協同演化能夠利用少數起演化導向作用的個體,減少了不必要的計算量,使收斂的速度加快.
雖然在生物系統中協同演化可以帶來很多益處是眾所周知的,但如何設計一個有效的適應性計算系統,仍然是不很清楚的.協同演化算法的研究開始於1990年Hillis的排序網路.在他的工作中,演化算法被用來設計排序網路,這個網路能夠接受任意序列的整數,通過一台比較器完成序列的排序. 這個排序網路的設計開創了具有重要意義的研究, 也是其他許多論文的研究主題.最初,Hillis利用一個傳統的遺傳算法最佳化網路設計,通過蒐集大量的隨機排序序列確定網路適應度並計算排序正確的片段.在網路演化最初階段取得了一定的進展,但隨著演化的進行演化沒有達到最佳最佳化網路便進入了停滯狀態.隨後的實驗Hillis做了些改進工作,Hillis 將一種寄生蟲和寄主協同演化的機制套用到最佳化搜尋的改進中去,成功地找到只需要61次比較的16 個元素排序網.1994年Paredis引入生命周期適應度評價(1ife-time fitness evaluation, LTFE)的方法,使CGA健壯性更好,成為一種細粒度的遺傳算法,並在分類神經網路設計、約束最佳化問題的狀態空間搜尋方面取得了一系列有意義的成功套用.
近年來,協同演化算法已在很多領域取得了一系列的成功套用,如函式最佳化、多目標最佳化、分類、圖像分割、神經網路設計和工程設計等,該領域已引起越來越多的學者們的興趣。
協同演化算法設計、實現和套用
協同演化算法與一般的演化算法的根本差別在於它的演化過程,在協同演化中,一個個體的適應度的計算是在與其他個體的互動過程中進行的,依賴於不同的問題,互動夥伴可以是同一種群的個體或者是不同種群的個體.自1990年Hillis提出基於競爭協同演化算法的排序網路以來,國際上已開展了一系列協同演化算法的研究工作.1994年Paredis提出了協同演化遺傳算法(CGA).Potter和De Jong對多個合作互動子種群的物種協同演化選擇機制進行了研究.Subbu等人提出了一種分散式協同演化算法模型並套用到最佳化問題.Ficici 基於博弈論的思想研究協同演化算法的解概念,提出了簡單協同演化算法的博弈論方法.Sim等人提出了基於博弈論的多目標協同演化算法.國內在協同演化算法方面也開展了一系列研究,取得了較好的套用效果.曹先彬等人借鑑生態學對個體生存環境和種群競爭的認識,構造了一種基於生態種群競爭模型的新的協同演化模式.2004年胡仕成等人針對次序約束和資源約束的多模式項目調度問題提出了一種病毒協同演化遺傳算法.目前對協同進化算法研究比較系統深入的團隊主要有: Brandeis大學Pollack領導的DEMO小組和George Mason大學De Jong領導的演化計算實驗室. Pollack領導的DEMO小組在協同演化算法中,利用博弈論來研究選擇方法的動態均衡和協同演化算法的解概念.De Jong領導的團隊主要針對合作協同進化模型,研究熱點主要集中在理論、實驗分析和套用等方面.
機制設計
協同演化算法具有與傳統演化算法明顯不同的特徵是多個種群同時演化,種群形成用於維持演化過程中的種群多樣性,對求解空間進行更有效的搜尋,如果這些分離的種群用一個全局適應度來衡量,
它們就傾向於收斂到合作很好的不同策略中,這是協同演化的基本機制.協同演化算法借鑑生態學的種群協同理論,套用種群間自動調節和自動適應原理來構造,根據生態學對種群相互關係的劃分.一共有4種關係:捕食者與被捕食者(predator.prey)、寄生物與寄主(host.parasite)、競爭(competitive)和互惠共生(mutualistic),這4種關係可以概括為兩種基本協同演化模型，即競爭協同和合作協同。
演化算法的最新研究表明，採用生態模型和協同演化結構是一種擴展傳統演化算法的有效方法。特別地,協同演化技術通過分而治之的策略提供一種處理大規模和複雜問題的有效方法.協同演化分為競爭協同演化和合作協同演化,前者通過演化使得個體更有競爭力,後者通過演化尋找最佳個體使得系統構造得更好.許多研究表明競爭協同導致“軍備競賽”,兩個種群通過互動提高了系統的性能和複雜程度.在一個競爭協同演化算法中,一個個體的適應度是在同其他物種的個體直接競爭中獲得的.例如,一個物種的適應度的提高隱含著另一個物種適應度的降低.這種演化壓力促使種群中產生新的有利競爭策略,從而確保種群的生存機會.在共生協同演化里,參與合作的個體同時獲得成功或同時失敗.在合作協同演化中個體的適應度依賴於一個物種與其他物種間的合作關係.合作協同演化模型最適合用於能自然分解成相互作用或相互合作的問題,每一個子模組用單獨的種群演化,問題的解由來自不同種群的個體組成,通過問題分解,搜尋空間變小,更容易維持多樣性.競爭協同演化適合於求解比較容易獲得測試例子的問題,通過問題的解和測試例子一起演化,相互促進提高各自性能和複雜性.競爭協同演化可以相互促使參與競爭的種群不斷提高適應度,達到種群最佳化的目的.在競爭協同演化中個體的適應度依賴於一個物種與其他物種間的競爭關係,競爭使得每個種群獨立演化.
問題表示
算法中種群結構是EA演化的基礎,種群中的個體一般可以是二進制編碼或是實數編碼.種群規模直接影響著EA的求解能力.所以為了獲得較好的EA性能,一般採用較大種群規模.但是種群規模增大,計算量按多項式增長,而算法的性能並不同比例增長.為了提高協同演化算法的能力,CEA一般採用多種群表示方法維持遺傳多樣性。Ficici認為CEA種群結構在算法張是非常重要的，EGT表明即使博弈過程相同，不同的種群結構導致不同的結果。KIM等人提出了一種基於聯賽競爭的協同演化算法，該算法採用基於鄰近演化、聯賽競爭和局部傑出者的組合策略。為驗證該算法的性能，對兩種不同特性的問題（排序網路和囚徒博弈問題）進行了實驗測試,實驗結果驗證了主種群和寄生種群在平衡演化中的演化效果,算法得到了高質量的解和較少的計算時間.
2001年曹先彬等人提出了基於生態種群競爭模型的協同演化算法,遺傳算法基於適應度的演化模式沒有考慮演化的外部環境和演化成分之間的關係,借鑑生態學對個體生存環境和種群競爭的認識,構造了一種基於生態種群競爭模型的新的協同演化模式.該模型的動力學特徵可以比較全面地描述個體與環境及相互之間的協同行為.新算法除了採用個體適應度控制演化的演化模式以外,還加入了一種新的演化模式,基於種群密度的演化模式.實驗結果表明,算法更易趨於全局收斂.Nicolas等人提出了一種求解演化神經網路的合作協同演化模型——COVNET.該模型基於協同演化子網路的思想對具體問題進行合作求解,從而代替全網路的演化.子網路的最佳組合一定是一個協同演化的過程.子網路的幾個子種群既相互合作協同演化又相互獨立,每個子種群的個體組合形成整體神經網路.這種方法不同於當前所流行的其他演化神經網路模型.為驗證模型性能,COVNET通過用3種真實分類問題與“適應專家混合模型”進行了對比實驗,實驗結果顯示了COVNET模型的良好泛化能力,在達到相同性能情況下產生比“適應專家混合模型”更小的網路規模.
遺傳操作
由於CEA的多種群結構,所以存在許多不同形式的變異操作和交叉操作.Potter對多個合作互動子種群的物種協同演化選擇機制進行了研究.在這個協同演化過程中,GA的多個程式並行運行,每個程式演化一個物種作為一個潛在的解,用於求解一種特殊的任務,通過組合多個程式潛在的局部解構成了一個協同演化算法的全局解.董紅斌等人提出了基於博弈論的混合變異策略協同演化規劃.在過去幾年中,演化規劃已經提出了幾種不同的變異運算元,然而,每種變異運算元只對某類問題有效,而對其他類問題則效果不佳.為了克服變異運算元的這種缺點,一種可能的方法是採用組合幾種變異運算元的協同演化方法.受演化博弈論的啟發,文獻[26]中提出了一種組合Gaussian,Cauchy,Levy和單點等多種不同變異運算元的演化規劃.在不同的搜尋階段總有不同的策略成為優勢策略,例如,當解種群遠離最佳點時大的跳步是有利的策略,Cauchy變異可以產生比Gau愛sian變異較大的跳步,因此在早期搜尋階段, Cauchy變異是比Gaussian變異更常用的變異策略. 另一方面,當解種群接近最佳點時Gaussian變異是一種更常用的提高解的精度的策略.但是,我們不清楚在什麼時間、什麼階段哪一種策略是比其他策略更常用的一種策略.為了克服這種困難,混合策略不預先確定某一階段的最優策略,而是演化某一策略的機率分布.混合策略用來保存搜尋的歷史信息,如果混合策略是固定,那么歷史信息沒有改變,如果某一策略發生了變化,就調整這種策略的機率分布.標準測試函式的實驗結果顯示,基於混合策略協同演化方法優於其他變異策略.
Ficici在協同演化算法中,利用演化博弈論來研究選擇方法的動態和均衡.用於EGT的經典選擇方法等價於演化算法中的標準適應種群選擇方法,EGT動態的主要吸引子是Nash均衡,他們研究了簡單對稱變和博弈中的多重Nash均衡.採用博弈論和動態系統的觀點研究幾種通常的選擇方法的性,這些選擇方法是比例選擇、截斷選擇(truncation)、(μ，λ)、(μ+ λ)、線性排序、Boltzmann 和錦標賽選擇.對應於比例選擇的動態行為,比較了截斷選擇、線性排序選擇、Boltzmann選擇和錦標賽選擇等的行為.除了Boltzmann選擇外,測試的每種選擇方法都沒有達到多重Nash均衡,當選擇壓力較低時,Boltzmann選擇收斂到多重Nash均衡. 協同演化算法常常用於搜尋博弈策略的解(Nash均衡),研究結果顯示,在簡單對稱變和博弈中,許多選擇方法不適合發現多重Nash均衡解.
算法實現
1997年Potter給出了一個通用合作協同演化算法框架,此算法的主要思想是以一般演化算法框架為基礎,將種群分為若干子種群,再進一步考慮子種群之間基於合作關係的協同進化.算法在每次疊代中都依次進行演化過程和協同過程,其中演化採用一般演化算法的遺傳操作方法.子種群是根據子種群間合作收益關係來產生下一代子種群.
適應度評價是影響算法運行效率的重要因素,降低群體規模或減少試例數目,都會在一定程度上影響解的質量,而CEA算法的並行實現能較好地解決這個問題.Sim等人提出了基於博弈論的多目標協同演化算法,算法中將每個函式中的不同變數組合在一起形成一個染色體種群,為兩個目標函式中的不同變數建立了兩個染色體種群,同時,將兩個目標函式的差值作為兩個新的目標函式.該方法成功達到多目標問題平衡點.
協同演化算法中一個相關問題是遺忘,一種或多種先前已經獲取的特徵在後來需要時已經丟失. Ficici介紹了一種新的協同演化存儲機制以防止演化過程中特徵丟失,這種存儲機制是基於博弈論的原理設計的,稱為“Nash存儲器”機制.這種“Nash存儲器”機制的特徵如下:1)通過搜尋形成一個特徵集合,將這個特徵集合表示為混合策略. 2)在搜尋過程中這種混合策略單調趨近Nash均衡策略,充當“棘輪”機制.3)這種存儲器自然存儲了協同演化過程中所獲得的結果.4)這種存儲器適當地處理反傳遞循環過程(以資源限制為條件).Ficiei對3種不同存儲器機制(Nash存儲器、傑出者存儲和優勝聯賽機制)進行了比較實驗,結果顯示Nash 存儲機制提高了特徵提取的能力和混合策略存儲機制的新特點:1)找到問題的近似最優解;2)逐漸提高了演化策略的競爭能力.
Subbu等人提出了一種分散式協同演化算法模型並套用到最佳化的問題.在模型中變數分布到P個結點中,每個結點中演化算法基於其初始變數集合進行局部搜尋,每個結點中第2個變數集中的變數嵌入這個階段.在結點間頻繁互動更新第2個變數集.局部搜尋和通信階段的互動導致了P個結點的合作搜尋.
