3.3.2　Memetic算法和Memetic計算

使用智能算法在處理數據分析問題時,對于處理數據規模和維度大的數據集,計算智能算法的適應度函數會非常耗時。受數據分布的影響,有些數據集難以優化。因此如何設計性能良好、運行高效的智能算法是近年來一個重要的研究問題。Meme是道金斯在其著作《自私的基因》[32]中定義的概念,中文譯法有“覓母”“文化基因”等。一個Meme表示一個文化進化單元,其載體可以是一本書、一段音樂。Meme在個體的進化過程中能夠對個體進行局部改良。Meme和達爾文進化論中的基因是相對應的概念,生物進化可通過基因的重組和變異實現,而Meme的傳播可以改良多個個體,這個過程就形成了文化進化。而人類社會就是一個生物進化和文化進化相結合的進化系統。

Moscato[33]在研究旅行商(Travelling Sales Problem,TSP)問題時,發現遺傳算法在求解TSP問題時,難以設計有效的交叉和變異算子來產生可行解。從而導致遺傳算法在求解TSP問題時求解精度不高,求解效率低。為此,他首次在進化計算領域引入了Meme的概念,Meme表示對個體的局部改良,在算法中被表述為局部搜索算子。實驗表明,這種將遺傳算法和局部搜索相結合的方式,在TSP問題上能有效平衡勘探(exploitation)和探測(exploration),達到更好的求解效果和效率。盡管在TSP問題上效果顯著,但Memetic算法的概念提出后并沒受到廣泛認可,而被視為混合智能算法的一種表述形式。20世紀90年代,研究人員通常以設計高效的算法作為目標,一方面,粒子群算法(Particle Swarm Optimization,PSO)[34]、蟻群優化算法(Ant Colony Optimization,ACO)[35]等帶有群體智能特征的智能算法相繼被提出,同時在進化算法的改進和參數選擇等方面也積累了較多的成果。此外,對復雜連續函數優化,TSP等著名問題也歸納了大量的標準測試集,并以此作為評價算法性能的基準。而對于智能算法設計的研究,就是通過比較不同算法在這些測試集上的性能來實現的。

無免費午餐定理(No Free Lunch Theorem,NFLT)[36]的提出,改變了進化計算的研究格局。NFLT表明所有算法(包括參數化的實例)在所有問題上的性能總和是一致的,具體用公式(3?12)表達:

(3?12)

P(xm|f,A)表示算法A可以發現優化目標f最優解的概率。P(xm|f,B)表示算法B發現優化目標f最優解的概率。式(3?12)表示,任取一對算法A和?B,它們在所有問題上的性能是一致的。雖然NFLT的提出使得設計所謂“最優”算法沒有了可能性,但也揭示了對某類問題高效的算法是存在的。因此Memetic算法作為一種有效的計算范式得到重視。 Memetic算法設計呈現兩種發展趨勢。

① 針對具體某一類問題進行算法設計從而提出求解具體問題的Memetic算法。顯然這類研究方式需要對具體問題有較為深入的理解。例如Memetic算法在旅行商問題和流水車間調度問題[37]等經典問題上取得了較為成功的應用;

② 開發和設計適用于大多數問題且具有魯棒性的算法,以自適應協同進化Memetic算法(Adaptive Coevolving Memetic Algorithm)為典型代表[38],在自適應協同進化Memetic算法中,局部搜索算子的相關信息被編碼到Meme中,在算法運行過程中,這些Meme和種群一起協同進化以適應問題空間,從而保證算法的魯棒性。在涌現出各種Memetic算法的同時,對Memetic算法的理論研究也日益深入。Krasnogor將Memetic算法定義為:Memetic算法是一種特殊的進化算法,在其進化過程中,采用了局部搜索算子來改進個體。Memetic算法的通用框架如圖3?2所示。

在該Memetic算法框架中,除了必要的初始化(initialization),優化目標評價(evaluation)等基本元素以及重組(recombination)、變異(mutation)、選擇(selection)等進化計算的常用算子,也包含了對個體的局部搜索(localsearch)。例如Petalas基于PSO和隨機游走局部搜索實現了Memetic PSO算法。

根據上述定義和框架,Memetic算法具有兩個特征:①Memetic算法首先是一種基于種群(population?based)的進化算法;②Meme在Memetic算法表示局部搜索。Ong[39]則在Memetic算法和協同進化算法的基礎上,從面向問題求解的角度提出了Memetic計算的概念,將Memetic計算定義為使用Meme來求解問題的計算范式。Meme在Memetic計算中定義為編碼于“計算表示”中的信息單元,并以算子、學習策略、局部搜索等形式存在。Memetic計算通過Meme之間的互相協作交互實現。在Memetic計算中,Meme的定義由局部搜索擴展至任意搜索或學習策略,交叉、變異等算子皆可稱之為Meme。此外,Memetic計算并不要求算法是基于種群。由此Memetic計算是對Memetic算法的一種泛化。

Icca[40]指出,在Memetic計算框架下研究的算法都采用了多種Meme協同的方式實現優化,涉及較多的算子和參數設置,導致算法設計相對復雜,因此Icca將奧卡姆剃刀(Ockham??s Razor)的思想引入了Memetic計算,而Icca認為,在Memetic計算中,下述三種Meme對于設計簡單高效的算法是充分和必要的。

① 長距離探測(long distance exploration):在搜索過程中以較大的搜索步長或較大的變化概率產生新解。

② 中距離探測(middle distance exploration):在搜索過程中以適中的搜索步長或適中的變化概率產生新解。

③ 短距離探測(short distance exploration):在搜索過程中以較小的搜索步長或較小的變化概率產生新解。

本章在設計面向數據分析的智能算法時遵循了Icca的設計準則,設計選取相應的Meme,并在Memetic算法和Memetic計算的框架下,研究了不同Meme之間的協同方式,提出了兩種基于種群的Memetic算法:基于高斯變異和深度優先搜索的Memetic PSO(Gaussian Mutation and Deepest Local Search based Memetic PSO,GS?MPSO)和基于廣泛學習的Memetic PSO(Memetic Comprehensive Learning PSO,MCLPSO)。并通過復雜函數優化問題驗證了這兩種算法的性能和效率。