3.3.2　Memetic算法和Memetic計(jì)算

使用智能算法在處理數(shù)據(jù)分析問(wèn)題時(shí),對(duì)于處理數(shù)據(jù)規(guī)模和維度大的數(shù)據(jù)集,計(jì)算智能算法的適應(yīng)度函數(shù)會(huì)非常耗時(shí)。受數(shù)據(jù)分布的影響,有些數(shù)據(jù)集難以?xún)?yōu)化。因此如何設(shè)計(jì)性能良好、運(yùn)行高效的智能算法是近年來(lái)一個(gè)重要的研究問(wèn)題。Meme是道金斯在其著作《自私的基因》[32]中定義的概念,中文譯法有“覓母”“文化基因”等。一個(gè)Meme表示一個(gè)文化進(jìn)化單元,其載體可以是一本書(shū)、一段音樂(lè)。Meme在個(gè)體的進(jìn)化過(guò)程中能夠?qū)€(gè)體進(jìn)行局部改良。Meme和達(dá)爾文進(jìn)化論中的基因是相對(duì)應(yīng)的概念,生物進(jìn)化可通過(guò)基因的重組和變異實(shí)現(xiàn),而Meme的傳播可以改良多個(gè)個(gè)體,這個(gè)過(guò)程就形成了文化進(jìn)化。而人類(lèi)社會(huì)就是一個(gè)生物進(jìn)化和文化進(jìn)化相結(jié)合的進(jìn)化系統(tǒng)。

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

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

(3?12)

P(xm|f,A)表示算法A可以發(fā)現(xiàn)優(yōu)化目標(biāo)f最優(yōu)解的概率。P(xm|f,B)表示算法B發(fā)現(xiàn)優(yōu)化目標(biāo)f最優(yōu)解的概率。式(3?12)表示,任取一對(duì)算法A和?B,它們?cè)谒袉?wèn)題上的性能是一致的。雖然NFLT的提出使得設(shè)計(jì)所謂“最優(yōu)”算法沒(méi)有了可能性,但也揭示了對(duì)某類(lèi)問(wèn)題高效的算法是存在的。因此Memetic算法作為一種有效的計(jì)算范式得到重視。 Memetic算法設(shè)計(jì)呈現(xiàn)兩種發(fā)展趨勢(shì)。

① 針對(duì)具體某一類(lèi)問(wèn)題進(jìn)行算法設(shè)計(jì)從而提出求解具體問(wèn)題的Memetic算法。顯然這類(lèi)研究方式需要對(duì)具體問(wèn)題有較為深入的理解。例如Memetic算法在旅行商問(wèn)題和流水車(chē)間調(diào)度問(wèn)題[37]等經(jīng)典問(wèn)題上取得了較為成功的應(yīng)用;

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

在該Memetic算法框架中,除了必要的初始化(initialization),優(yōu)化目標(biāo)評(píng)價(jià)(evaluation)等基本元素以及重組(recombination)、變異(mutation)、選擇(selection)等進(jìn)化計(jì)算的常用算子,也包含了對(duì)個(gè)體的局部搜索(localsearch)。例如Petalas基于PSO和隨機(jī)游走局部搜索實(shí)現(xiàn)了Memetic PSO算法。

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

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

① 長(zhǎng)距離探測(cè)(long distance exploration):在搜索過(guò)程中以較大的搜索步長(zhǎng)或較大的變化概率產(chǎn)生新解。

② 中距離探測(cè)(middle distance exploration):在搜索過(guò)程中以適中的搜索步長(zhǎng)或適中的變化概率產(chǎn)生新解。

③ 短距離探測(cè)(short distance exploration):在搜索過(guò)程中以較小的搜索步長(zhǎng)或較小的變化概率產(chǎn)生新解。

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