錢乾，芮坤坤　(安徽商貿(mào)職業(yè)技術(shù)學(xué)院電子信息工程系，安徽 蕪湖 241002)

程美英　(合肥工業(yè)大學(xué)管理學(xué)院，安徽 合肥 230009；南洋理工大學(xué)計算機(jī)工程學(xué)院，新加坡 639798)

?

生物啟發(fā)式算法求解多模態(tài)優(yōu)化問題研究

錢乾，芮坤坤(安徽商貿(mào)職業(yè)技術(shù)學(xué)院電子信息工程系，安徽 蕪湖 241002)

程美英(合肥工業(yè)大學(xué)管理學(xué)院，安徽 合肥 230009；南洋理工大學(xué)計算機(jī)工程學(xué)院，新加坡 639798)

[摘要]實際生活及工程應(yīng)用中的諸多問題均可歸結(jié)為多模態(tài)優(yōu)化問題，研究多模態(tài)優(yōu)化問題的目的在于找出問題的所有全局極值解或有意義的局部極值解。從算法的“完全收斂性”出發(fā)，探討了目前生物啟發(fā)式算法(如遺傳算法、蟻群算法、螢火蟲算法、魚群算法、粒子群算法等)求解多模態(tài)優(yōu)化問題存在的問題和缺陷，并得出其在求解多模態(tài)優(yōu)化問題時必須滿足的條件：種群的多樣性及種群分布的均勻性。隨后概括并總結(jié)了目前求解多模態(tài)優(yōu)化問題而保持種群多樣性及均勻性的若干策略，著重研究了通過生物啟發(fā)式算法并結(jié)合改進(jìn)小生境技術(shù)在多模態(tài)優(yōu)化問題求解中的研究進(jìn)展，最后評述了今后一些有意義的研究方向及主要研究內(nèi)容。

[關(guān)鍵詞]多模態(tài)優(yōu)化問題; 生物啟發(fā)式算法；完全收斂性;小生境技術(shù);種群多樣性

多模態(tài)優(yōu)化問題(Multi-Modal Optimization)或多峰函數(shù)優(yōu)化問題(Multi-hump Function Optimization，MFO)[1]自提出至今，得到了眾多學(xué)者的廣泛關(guān)注。相對于解決其他形式的優(yōu)化問題，求解多模態(tài)優(yōu)化問題既要避免算法陷入局部極值解，又要讓不同的極值解在種群中都有出現(xiàn)的機(jī)會，以便找到更多的優(yōu)秀解。傳統(tǒng)的解析方法或數(shù)值優(yōu)化算法,如牛頓法、DFP變尺度法、梯度下降法、Hooke-Jeeves方法、混沌法以及改進(jìn)的Powell方法等在目標(biāo)函數(shù)較為簡單或者說較少峰值的多模態(tài)優(yōu)化問題中表現(xiàn)較好、求解精度較高，但對目標(biāo)函數(shù)有較強(qiáng)的限制性要求、依賴初始值的選擇、缺乏通用性以及求解時間難以忍受等缺陷限制了這些傳統(tǒng)算法的廣泛應(yīng)用。生物啟發(fā)式算法，如遺傳算法、蟻群算法、粒子群算法、螢火蟲算法等，因只需根據(jù)相應(yīng)的啟發(fā)式信息指導(dǎo)搜索方向，操作簡單而受到學(xué)者的廣泛研究。但易陷入局部最優(yōu)(即算法的早熟收斂)、不能搜索到所有全局最優(yōu)解(或局部最優(yōu)解)等缺陷在上述啟發(fā)式算法中依然存在。下面，筆者從多模態(tài)優(yōu)化問題的數(shù)學(xué)模型和完全收斂性入手，探討了近些年運(yùn)用生物啟發(fā)式算法求解多模態(tài)優(yōu)化問題的若干策略以及今后的一些主要研究方向。

1多模態(tài)優(yōu)化問題

問題描述如下：

其中，x∈Rn稱為時變量；S∈Rn稱為參數(shù)搜索空間；f:S→R稱為目標(biāo)函數(shù)；S={x|x∈Rn;li≤xi≤ui,i=1,2,…,n}，通常S是一個n維長方體。

定義1設(shè)x*∈S，若存在δ>0，使得當(dāng)x∈S且‖x-x*‖<δ時，總有f(x)≤f(x*)，則稱x*為f在S上的局部極值解，f(x*)稱為一個局部極值。

定義2 設(shè)存在x*∈S，使得對任意x∈S都有f(x)≤f(x*)，則稱x*為f在S上的全局極值解，f(x*)稱為一個全局極值。

定義3已知f*是f在S上的全局極值，若存在且僅存在一個x*∈S，使得f(x*)=f*，則稱函數(shù)f(x)是一個單峰值函數(shù)。

定義4已知f*是f在S上的全局極值，若存在互不相同的x1,x2,…,xm∈S，使得f(xi)均為全局極值或局部極值，則稱f(x)是一個多峰函數(shù)，也即多模態(tài)函數(shù)。

多模態(tài)優(yōu)化問題(或多模態(tài)函數(shù))是相對于單模態(tài)函數(shù)而言的，其目標(biāo)旨在求出所有全局最優(yōu)解或多個有意義的局部極值解。

2生物啟發(fā)式算法求解多模態(tài)優(yōu)化問題的完全收斂性

不同于單峰函數(shù)優(yōu)化問題中涉及的“全局收斂”的概念,多模態(tài)優(yōu)化算法的收斂性應(yīng)理解為隨著進(jìn)化代數(shù)的增大,算法最終能夠以概率1找到定義域內(nèi)所有的極值解，稱之為完全收斂(Complete Convergence)[2]。

定義5對于多峰函數(shù)f(x)，在定義域中共有m個峰，這m個峰的極值點(diǎn)分別記為φ1,φ2,…,φm，t代時的種群記為Z(t)，當(dāng)且僅當(dāng)：

(1)

則稱算法是完全收斂的。

2.1遺傳算法完全收斂性

遺傳算法(Genetic Algorithm，GA)是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法，最初由美國Michigan大學(xué)J.Holland教授于1975年首次提出，并在同年，J.Holland提出了基于小生境的遺傳算法這一思想，1987年Goldberg和Richardson基本實現(xiàn)了這一想法。文獻(xiàn)[3]以馬爾科夫鏈為分析工具，證明了基本小生境遺傳算法不能停留在完全峰值狀態(tài)中，即簡單遺傳算法不能完全收斂。

2.2蟻群算法完全收斂性

蟻群算法(Ant Colony Optimization, ACO)是一種用來在圖中尋找優(yōu)化路徑的概率型算法，由Marco Dorigo于1992年在他的博士論文中提出，其靈感來源于螞蟻尋找食物過程中發(fā)現(xiàn)最短路徑的行為。因蟻群算法主要依靠信息素吸引其他的螞蟻，隨著算法的迭代，幾乎所有的螞蟻都會聚集到同一條路徑上，這就使得ACO算法不適合求解多模態(tài)優(yōu)化問題[4]，但此部分沒有相關(guān)的理論證明。2006年熊偉清等[5]將二進(jìn)制編碼與ACO算法相結(jié)合，提出了二進(jìn)制蟻群進(jìn)化算法(BACO)，2009年嚴(yán)彬等[6]從理論上證明在BACO算法中，因螞蟻每次只需從面前的2條路徑進(jìn)行選擇，隨著迭代次數(shù)的增加，螞蟻幾乎全部集中在其中一條路徑上，即每次運(yùn)行只能保證求解到問題的一個最優(yōu)解，單一種群所對應(yīng)的單一二元網(wǎng)絡(luò)不能給出多模態(tài)優(yōu)化問題的全部最優(yōu)解。

2.3螢火蟲算法完全收斂性

螢火蟲算法(Glow warm Swarm Optimization, GSO)是由印度學(xué)者Krishnanand 和Ghose于2005年提出的一種模仿螢火蟲群發(fā)光行為的群智能算法。在螢火蟲算法中，每只螢火蟲個體有不同的搜索范圍，即決策域，每只螢火蟲個體在決策域范圍內(nèi)朝比自身亮的螢火蟲靠近，若感知范圍內(nèi)沒有比自身優(yōu)秀的個體，則停止不動，最終所有的螢火蟲個體分別聚集在不同的全局(局部)極值點(diǎn)上[7]。

上述討論的遺傳算法、蟻群算法等的主要思想都是基于全局最優(yōu)點(diǎn)和如何避免算法計算過程中種群多樣性缺失速度太快的問題，人工螢火蟲群優(yōu)化算法在同時獲得多模態(tài)函數(shù)的所有極值點(diǎn)的同時，可以不需要任何記憶，具有自由的梯度和不依賴任何全局信息等優(yōu)點(diǎn)，是研究處理多峰函數(shù)優(yōu)化問題的新方法[8]。2008年，Krishnanand和Ghose為特殊形式下的螢火蟲群算法建立了理論基礎(chǔ)，證明了每個子群的個體將分別收斂于所在子群的極值點(diǎn)，即完全收斂[9]。

此外，粒子群算法、魚群算法等其他生物啟發(fā)式算法在多模態(tài)優(yōu)化問題上均有應(yīng)用，如拉伸粒子群算法[10]、物種粒子群算法[11]、小生境粒子群算法[12]、小生境人工魚群算法[13]及基于量子理論的小生境人工魚群算法[14]等，但都沒有在理論上對這些算法求解多模態(tài)優(yōu)化問題的“完全收斂性”進(jìn)行分析，這一部分有待于后續(xù)學(xué)者的完善。

3生物啟發(fā)式算法與小生境技術(shù)相結(jié)合求解多模態(tài)優(yōu)化問題

目前的多模態(tài)優(yōu)化算法大多是基于生物啟發(fā)式算法的多模態(tài)尋優(yōu)過程。在用生物啟發(fā)式算法求解多模態(tài)優(yōu)化問題時，對群體的控制必須滿足以下2點(diǎn)：①保持種群的多樣性；②保持種群分布的均勻性。然而，絕大多數(shù)生物啟發(fā)式算法本身的特性決定了其往往將精力集中在某一最有優(yōu)勢的優(yōu)秀解上，只適用于搜索單一的全局最優(yōu)解，當(dāng)需要同時找到全局最優(yōu)解或一些有意義的次優(yōu)解時則顯得無能為力。1917年Grinnell根據(jù)生物學(xué)中特定環(huán)境的組織功能衍生出小生境(niche)[15]的概念，在自然界中往往特征、性狀相似的物種相聚在一起組成一個個小環(huán)境(子種群)，它們可以在種群內(nèi)部繁殖，但不能和種群之外的個體繁殖。小生境技術(shù)的出現(xiàn)，為生物啟發(fā)式算法求解多模態(tài)優(yōu)化問題保持種群多樣性提供了一種新穎的方法，而如何形成小生境則成為首要解決的問題。

3.1小生境的形成

在多模態(tài)優(yōu)化問題中，每一個極值解可以看作一個小生境，子群體居住在小生境中參與競爭協(xié)作，因而小生境技術(shù)能使普通的優(yōu)化算法具有發(fā)現(xiàn)多個最優(yōu)解的能力，在很多領(lǐng)域的多模態(tài)優(yōu)化問題中得到研究應(yīng)用。實現(xiàn)小生境優(yōu)化需要解決的2個重要問題是：①小生境的判斷問題，即判斷新發(fā)現(xiàn)的極值解是否與新產(chǎn)生的極值解屬于同一小生境；②小生境保持問題，即如何將一些較優(yōu)的不同小生境在后續(xù)的進(jìn)化過程中穩(wěn)定的保存下來。 縱觀小生境的各種實現(xiàn)方法，其基本思想為：將連續(xù)的、無限的搜索空間劃分為離散的、有限的小生境區(qū)域；在此基礎(chǔ)上各種各樣的小生境技術(shù)層出不窮。下面，筆者將介紹一些有代表性的小生境技術(shù)，為實際應(yīng)用提供一些有效的參考設(shè)計依據(jù)。

圖1　等區(qū)間分割小生境示意圖

1)等分區(qū)間小生境生物在進(jìn)化過程中之所以能形成千變?nèi)f化物種，主要是因為物種有分化小種群的能力，各個小種群沿著不同的方向進(jìn)化，逐漸分化成不同的物種。隔離主要是地理上的隔離，進(jìn)而產(chǎn)生生殖、生態(tài)或行為上的隔離，由于隔離后的子群體彼此獨(dú)立，因而對各子群體的控制相當(dāng)靈活。

最簡單的小生境技術(shù)是將整個搜索區(qū)間等分成幾個小的子區(qū)間(或稱小生境)，每個子區(qū)間相互隔離，獨(dú)立進(jìn)化，互不干涉(即互不交互信息)，最后綜合各子區(qū)間的所得解，即為問題的所有最優(yōu)解，如圖1所示?；趨^(qū)間分割的小生境技術(shù)又分各區(qū)間參數(shù)設(shè)置一致或不一致2種情形。

文獻(xiàn)[16]將區(qū)間分割的小生境技術(shù)引入二元蟻群算法中，根據(jù)目標(biāo)解的個數(shù)決定小生境的個數(shù)，若有m個解，則將搜索空間等分成m個子區(qū)間，每個子區(qū)間產(chǎn)生一個種群，各種群參數(shù)的設(shè)置完全一致，每個子種群并行獨(dú)立搜索。仿真實驗通過對Branin Rcos 函數(shù)(3個不同全局極小點(diǎn))、six-hump camel back 函數(shù)(2個全局極小點(diǎn))、shubert函數(shù)(18個全局極小點(diǎn))進(jìn)行測試，均能找到搜素空間的所有極值點(diǎn)。上述區(qū)間分割技術(shù)，一般來說，問題有多少個最優(yōu)解，即設(shè)置相應(yīng)數(shù)量的種群，但遺憾的是，在大多數(shù)實際問題中，事先并不知道解的數(shù)量和分布。葉青等[17]改進(jìn)了上述問題空間的劃分方法，針對一個具有n個自變量的多目標(biāo)優(yōu)化問題，將每一維自變量按其取值范圍分割為d(d≥2)份，從而將問題空間劃分成dn個子區(qū)域，d一般取值較小，以免時間代價過高。

基于區(qū)間分割的小生境技術(shù)在峰值較少的情況下基本能搜索到所有的極值解，但是事先必須知道解的大致分布和最優(yōu)解的個數(shù)，這必然導(dǎo)致區(qū)域的劃分不夠靈活。

圖2　聚類小生境示意圖

2)聚類小生境采用上述等分區(qū)間的方式形成的小生境拓?fù)浣Y(jié)構(gòu)相對比較固定，但控制不夠靈活，且初始解的分布不符合自然界“物以類聚，人以群分”的思想。隨后研究者將數(shù)據(jù)挖掘中“聚類”的思想引入種群中，通過計算個體i,j之間的距離dij(如歐式距離、海明距離等)，若dij小于某一指定半徑r，則這些個體歸屬同一類，處于同一個小生境中，最終形成一個個類似球體的超球面，如圖2所示，稱之為基于聚類分離的小生境形成技術(shù)。當(dāng)然，上述等分區(qū)間的小生境屬于基于聚類分離小生境的一種特例。

上述基于聚類的小生境空間劃分方法被引入到多種啟發(fā)式算法中，形成多個子種群(即小生境)，但是這種劃分方法面臨著一個重要的問題，即如何確定聚類的數(shù)目，而在算法的運(yùn)行過程中自動確定聚類的數(shù)目是一個很困難的問題。文獻(xiàn)[18]提出了一種基于適應(yīng)度-距離相似度模型的概念(FDPSO)，打破了傳統(tǒng)算法中只將個體之間的距離作為聚類的依據(jù)，而是將個體的適應(yīng)度和距離相似度共同作為聚類的依據(jù)，使得具有更相近的適應(yīng)度值和更近距離的2個個體屬于同一個小生境的概率更高,也就是說,如果2個個體的適應(yīng)度值相差很大,并且空間距離同樣很大,那么這2個粒子很可能屬于不同的小生境。通過對該算法的復(fù)雜度進(jìn)行分析，F(xiàn)DPSO具有更低的計算量。

3.2生物啟發(fā)式結(jié)合小生境技術(shù)求解多模態(tài)優(yōu)化問題

目前生物啟發(fā)式算法結(jié)合小生境技術(shù)求解多模態(tài)優(yōu)化問題的主要代表為基于排擠模型的小生境技術(shù)和基于適應(yīng)值共享的小生境技術(shù)以及后續(xù)學(xué)者在這2種模型上的若干改進(jìn)。

1)適應(yīng)值共享小生境技術(shù)及其改進(jìn)1987年，Goldberg 和Richardson提出了一種基于適應(yīng)值共享機(jī)制的小生境技術(shù)(SH: sharing fitness)[19],通過定義群體中個體的共享度,采用適應(yīng)值非線性標(biāo)度變換調(diào)整個體的適應(yīng)值,使得群體同時保持多個高階模式，其中小生境半徑r是影響算法搜索性能的關(guān)鍵因素，該算法為了維持大量的小生境，必須有較大的種群規(guī)模，并且其中一部分小生境可能是無用的。隨后，Petrowski等[20]提出一種特殊的適應(yīng)值共享模型——清除模型，共享半徑內(nèi)的所有個體比較適應(yīng)值，最佳的若干個體存活，其余死亡，清除模型的缺陷與上述適應(yīng)值共享模型大體一致。

1993年，Beasley基于共享的小生境技術(shù)的不足，提出了序列小生境技術(shù)(sequential niching)，依次搜索多個全局最優(yōu)解。其不足在于阻斷了不同最優(yōu)解位串之間模式信息的繼承關(guān)系,交叉操作產(chǎn)生大量無效個體浪費(fèi)計算資源,同時也存在著復(fù)雜的參數(shù)選擇問題。

多模態(tài)優(yōu)化問題一般存在多個局部極值解，局部極值解處適應(yīng)值的大小很大程度上影響了它們被算法搜索到的概率。文獻(xiàn)[21，22]通過分析基因池遺傳算法的無限種群動力系統(tǒng)，從理論上證明了雙峰函數(shù)局部極值解的適應(yīng)值差與不動點(diǎn)之間的解析關(guān)系，并對該理論進(jìn)行擴(kuò)展，提出了適于求解多模態(tài)優(yōu)化問題的兩階段遺傳算法(FAGA)：對于一般的多模態(tài)函數(shù),保持函數(shù)在某個閾值以下的各點(diǎn)的函數(shù)值不變,通過式(2)由拉伸效果的函數(shù)標(biāo)度變換增大函數(shù)值在這個閾值以上的各點(diǎn)的適值差,就可以增加那些函數(shù)在閾值以上的局部極值解(包含全局最優(yōu)解)的被搜索概率。相反，通過式(3)保持閾值以下的各點(diǎn)的函數(shù)值不變，通過有壓縮效果的函數(shù)標(biāo)度變換減小閾值以上的各點(diǎn)的適值差，減小那些閾值以上的局部極值解(含全局最優(yōu)解)的被搜索概率，相應(yīng)增加各閾值以下的局部極值解的被搜索概率。

假設(shè)變換前的原函數(shù)f(x)>0，若f(x)<0，先作如下處理：令f′(x)=f(x)+N，N?max{0-f(x)}然后對f′(x)按式(2)、式(3)進(jìn)行變換：

F1(f(x))=f(x) f(x)≤f(x')f(x)-1+T|f(x)-f(x')| f(x)>f(x'){

(2)

(3)

式中，F(xiàn)1(f(x))為具有拉伸效果的函數(shù)；F2(f(x))為具有壓縮效果的函數(shù)。

通過對文獻(xiàn)[22]中2個函數(shù)進(jìn)行測試，結(jié)果明顯優(yōu)于PSO算法及基于小生境的適應(yīng)值共享遺傳算法。

2)排擠小生境技術(shù)及其改進(jìn)1993年De Jong 提出的確定性排擠模型(deterministic crowding，DC)是一種維持群體多樣性的選擇方法[23,24]。在自然界中,當(dāng)種群中的個體大量繁殖時,為爭奪有限的生存資源,個體之間的競爭壓力加大、個體消亡的概率升高、生存率下降。在采用DC模型時,新的子代個體僅僅替代與之相似的父代個體.然而,實驗表明上述方法發(fā)現(xiàn)2個以上最優(yōu)解的可能性極小[23,24]。 為此,在原有的基本操作方式的基礎(chǔ)上,引入了概率排擠模型(PC: probabilistic crowding)[25],使之更加適合于多模態(tài)函數(shù)的求解。但是,仍然存在著已搜索到的最優(yōu)解丟失的問題,而且CF參數(shù)(排擠系數(shù))的選擇與具體問題有關(guān),很難事先確定合適的取值。

Harik借鑒聯(lián)賽選擇模型(tournament selection),提出了一種受約束的聯(lián)賽保留策略，使得群體中構(gòu)成以最優(yōu)解點(diǎn)為核心的多個超球面小生境[26],對于給定的一類多模態(tài)函數(shù)的求解表現(xiàn)出了良好的性能。但是，需要事先指定各個小生境的核心、半徑和數(shù)量,當(dāng)不知道峰值點(diǎn)和峰距時,難以給定恰當(dāng)參數(shù)。

文獻(xiàn)[28]將混沌搜索、網(wǎng)絡(luò)抑制、網(wǎng)絡(luò)補(bǔ)充等機(jī)制相結(jié)合，提出了一種解決多峰函數(shù)優(yōu)化的免疫混沌網(wǎng)絡(luò)算法。該算法對一定數(shù)量的抗體進(jìn)行混沌映射，產(chǎn)生混沌抗體群，將混沌抗體群中的抗體與父本比較，保留親和度最高的抗體組成新抗體群，新抗體群組成免疫網(wǎng)絡(luò)，通過混沌搜索不斷提高抗體親和度，當(dāng)抗體群的平均親和度無法提高時，利用抑制閾值消除相似抗體，其余保存在記憶池中。為了防止多峰函數(shù)的峰值大于預(yù)設(shè)的種群規(guī)模，需補(bǔ)充新抗體以調(diào)節(jié)種群的數(shù)量，如此循環(huán)迭代，直到整個網(wǎng)絡(luò)達(dá)到動態(tài)平衡，最后記憶池中的抗體即為多峰函數(shù)的優(yōu)化解。

文獻(xiàn)[29]提出了一種基于隔離機(jī)制的動態(tài)小生境技術(shù)。該算法將初始群體分割成幾個子群體，各子群體彼此獨(dú)立，界限分明，子群體的規(guī)模同種群個體平均適應(yīng)值相關(guān)，子群體平均適應(yīng)值越高，則群體規(guī)模越大，并通過引入子群最大允許規(guī)模Smax、子群體最小生存規(guī)模Smin、幼弱保護(hù)政策、同種互斥以及新老更替政策等來保持種群的動態(tài)多樣性。上述的這種小生境策略不僅使得子群體進(jìn)化操作具有靈活性，子群體之間的相互競爭排擠給全局搜索具有導(dǎo)向性，且妥善解決了局部搜索和全局搜索的平衡。文獻(xiàn)[6,30]分別將具有這種隔離機(jī)制的小生境技術(shù)應(yīng)用于遺傳算法、二元蟻群算法中，較好地應(yīng)用于50個城市的TSP問題、多峰函數(shù)優(yōu)化以及多重0/1背包選擇問題。

文獻(xiàn)[31]通過對克隆選擇算法中記憶算子、抑制算子、重組算子等進(jìn)行改進(jìn)，并結(jié)合小生境技術(shù)，提出了一種求解多峰函數(shù)的小生境克隆選擇算法。算法主要思想：隨機(jī)產(chǎn)生N個抗體組成初始抗體群，對每個抗體計算其抗體-抗原親和度，將抗體的親和度評價值大于記憶閾值δn的抗體通過記憶算子添加到記憶庫中(可防止在進(jìn)化過程中優(yōu)秀解被破壞)，并對其進(jìn)行抑制算子操作；應(yīng)用小生境適應(yīng)值共享函數(shù)對初始抗體群中抗體的抗體-抗原親和度進(jìn)行調(diào)整(可以保證高、低峰同時被選中)；根據(jù)調(diào)整后的抗體-抗原親和度，對每一個抗體進(jìn)行克隆擴(kuò)增和重組變異(包括抗體交換算子、抗體逆轉(zhuǎn)算子、抗體移位算子，如圖3～圖5所示)，從而形成N個子抗體群；計算克隆擴(kuò)增和重組變異后的抗體親和度，從每個子群里選出一個最優(yōu)抗體組成新的抗體群。此外，為了在整個搜索區(qū)域大幅度尋找抗體，隨機(jī)生成 個新的抗體，替換新的抗體群中Ns個具有低親和度的抗體。

圖3　抗體交換算子　　　　　　　　　　圖4　抗體逆轉(zhuǎn)算子　　　　　　　　　圖5　抗體移位算子

文獻(xiàn)[32]受免疫系統(tǒng)中的記憶細(xì)胞機(jī)制啟發(fā)，提出了免疫記憶策略。具體方法是：設(shè)計一個記憶算子，當(dāng)種群中有優(yōu)秀個體適應(yīng)值超過一定閾值(稱為記憶閾值)時，就遷移到記憶子群中；一旦個體遷移到記憶子群后，就刪除原種群中與其相同的個體，然后再檢查種群中是否還有優(yōu)秀個體，如有則繼續(xù)遷移，否則停止記憶操作。在記憶操作停止之后，檢查種群中的個體數(shù)，如果小于原種群規(guī)模，則用隨機(jī)產(chǎn)生的新個體補(bǔ)滿，記憶子群中，一旦有新的優(yōu)秀個體進(jìn)入記憶子群，立即對該個體進(jìn)行梯度進(jìn)化,如Adaptive gradient descent(自適應(yīng)梯度下降法)、Simulated Annealing(模擬退火)等，直到該個體到達(dá)所在的峰。然后，用進(jìn)化完畢的個體與臨時子群的其他個體逐一比較，去掉與之相似度大于一定閾值的個體(稱為“相似性抑制”)，從而保持種群的多樣性。

圖6　基于局部抽象凸支撐面?zhèn)€體更新過程

鄧勇軍等[33]針對小生境半徑難以確定及確定性算法復(fù)雜度高的缺陷，提出了一種提出了一種基于局部抽象凸支撐面的多模態(tài)優(yōu)化算法(LAC)。在傳統(tǒng)進(jìn)化算法的框架下, 將目標(biāo)優(yōu)化問題轉(zhuǎn)換為單位單純形約束條件下的嚴(yán)格遞增射線凸松弛問題。在更新環(huán)節(jié)利用新產(chǎn)生個體鄰域信息構(gòu)建下界低估支撐面, 通過引入主導(dǎo)個體思想, 尋找主導(dǎo)個體所屬的支撐向量, 并利用該支撐向量的下降方向指導(dǎo)新個體更加高效的替換現(xiàn)有種群個體, 并減少替換誤差, 避免出現(xiàn)早熟現(xiàn)象, 從而產(chǎn)生質(zhì)量更高的新個體。假設(shè)C是一個trail個體(見圖6)，尋找種群中離C最近的個體A，B，構(gòu)建下界支撐面，得到下界函數(shù)極值點(diǎn)D(xu,d(xu))，若C在B主導(dǎo)的支撐面上，則B為主導(dǎo)個體，且C的適應(yīng)值優(yōu)于B，C取代B，循環(huán)此過程，完成一次種群的更新過程。

由上述可知：①基于空間分離的小生境技術(shù)必須對生物啟發(fā)式算法的搜索行為施加必要的限制，通過定義搜索空間上的某種度量保持群體的多樣性，并在群體中同時保留多個高適應(yīng)值的高階模式，防止某個高適應(yīng)值的個體快速充滿整個群體，使得優(yōu)化算法可以搜索到多個全局最優(yōu)解和局部最優(yōu)解。②隔離機(jī)制的采用,使得種群中的個體被完全分隔成幾個子群體,各子群體相互獨(dú)立并行進(jìn)化,不僅妥善地解決了局部搜索能力和全局搜索能力的矛盾,而且各子群體在整個進(jìn)化過程中實際在不停的移動,最終遍歷整個搜索空間,收斂在所有全局最優(yōu)解上。

3.3小生境半徑的選擇

每個小生境由質(zhì)心θ和半徑r確定。以多峰函數(shù)為例，每一個峰所在區(qū)域是最準(zhǔn)確、最合適的小生境范圍，但是多峰函數(shù)的峰具有不同的高度、形狀和面積，采用小生境技術(shù)時半徑的設(shè)定是一個難點(diǎn)。

在種群的進(jìn)化過程中，θ和r處于不斷變化的狀態(tài)。 r較大，有利于保持種群多樣性，但進(jìn)化速度緩慢；r較小，可加快算法的收斂速度，但種群多樣性降低，算法容易陷入局部最優(yōu)。在傳統(tǒng)的小生境技術(shù)中，一般事先確定小生境半徑r，這在實際問題中往往難以準(zhǔn)確估計，并且若在進(jìn)化過程中將各小生境半徑設(shè)定統(tǒng)一值，往往會導(dǎo)致進(jìn)化效果不佳。文獻(xiàn)[34]根據(jù)種群適應(yīng)度地形信息確定θ和r；Cho等[35]提出了一種種群規(guī)模和小生境半徑r均可自動調(diào)整的小生境技術(shù)，在電機(jī)設(shè)計優(yōu)化問題中得到了較好的應(yīng)用；Dilettoso和Salerno等[36]提出了一種能夠動態(tài)識別小生境和小生境半徑技術(shù)，較好應(yīng)用于電磁轉(zhuǎn)杯設(shè)計優(yōu)化問題中。文獻(xiàn)[18]將粒子群算法中每個粒子在每一代找到與自己距離最近的粒子，并記錄下這個最近距離,然后求出這個最近距離的平均值作為小生境半徑r。

上述方法雖然能動態(tài)計算小生境半徑，但計算方法相當(dāng)復(fù)雜。文獻(xiàn)[37]將“熵”的概念引入基于共享機(jī)制的小生境中，根據(jù)當(dāng)前種群個體間的平均距離對半徑r作自適應(yīng)性調(diào)整。文獻(xiàn)[38]針對多目標(biāo)優(yōu)化問題，在Pareto邊界生成一顆最小生成樹，將最小生成樹的平均邊長作為小生境半徑。

然而，在小生境的生成過程中，存在某一個別個體，它不屬于任何一個小生境，但其本質(zhì)是單獨(dú)存在的峰值，由于個體分布的不均勻，導(dǎo)致該個體周圍缺乏鄰居而不能構(gòu)成一個單獨(dú)的小生境，并且在劃分小生境的過程中，還可能出現(xiàn)小生境半徑r的交叉。為此，文獻(xiàn)[39]引入標(biāo)記策略，只采用小生境中心點(diǎn)和附近個體的距離信息描述函數(shù)的峰值形狀，使得小生境劃分更加準(zhǔn)確,提高了小生境的劃分效率,避免出現(xiàn)了無法劃分的個體。

4生物啟發(fā)式算法求解多模態(tài)優(yōu)化問題的其他策略

多目標(biāo)優(yōu)化問題因存在多個相互沖突的目標(biāo)，故其解為一組Pareto最優(yōu)解集，因而多目標(biāo)優(yōu)化問題也可視為多模態(tài)優(yōu)化問題。文獻(xiàn)[40]通過目標(biāo)空間變換方法，采用Pareto 前端在被稱為平行格坐標(biāo)系統(tǒng)的新目標(biāo)空間中的分布熵及差熵評估種群的多樣性及進(jìn)化狀態(tài)，并以此為反饋信息來設(shè)計進(jìn)化策略,使得算法能夠兼顧近似Pareto 前端的收斂性和多樣性。同時,引入格占優(yōu)和格距離密度的概念來評估Pareto 最優(yōu)解的個體環(huán)境適應(yīng)度,以此建立外部檔案更新方法和全局最優(yōu)解選擇機(jī)制，最終形成了基于Pareto 熵的多目標(biāo)粒子群優(yōu)化算法。

文獻(xiàn)[41]在DE(差分)群體進(jìn)化算法基礎(chǔ)上，利用群體中更新個體適應(yīng)度信息構(gòu)建多模態(tài)目標(biāo)函數(shù)的廣義凸下界估計模型，并對群體進(jìn)行拓?fù)浞诸?，綜合考慮上下界偏差值提出一種表示種群擁擠程度的生境指標(biāo)，從而保證形成協(xié)同進(jìn)化的種群，進(jìn)一步采用拓?fù)鋮^(qū)域進(jìn)化樹更新策略來保證生境內(nèi)部的局部搜索能力，仿真試驗表明，該算法能夠發(fā)現(xiàn)所有的全局最優(yōu)解以及一些有意義的局部最優(yōu)解。

近年來，還有眾多學(xué)者融合多種策略求解多模態(tài)優(yōu)化問題，吳建輝等結(jié)合Powell算法、免疫算法多子種群、協(xié)同進(jìn)化、免疫優(yōu)化、自適應(yīng)雜交算子及鄰域內(nèi)非均勻變異算子及粒子群算法等眾多策略,提出了2種解決多模態(tài)優(yōu)化問題的3種新方法：合作-競爭多子種群粒子群免疫協(xié)同進(jìn)化算法(MAPCPSOI)；基于串聯(lián)混合方式的免疫云粒子群優(yōu)化算法(PPSO)；基于串聯(lián)混合方式的融合Powell搜索算法的粒子群優(yōu)化算法(IPSO-P)等等[42～47]。

5總結(jié)與展望

工程及數(shù)學(xué)上的許多優(yōu)化問題實質(zhì)上均可歸結(jié)為多模態(tài)優(yōu)化問題(或多峰優(yōu)化問題)，多模態(tài)問題進(jìn)行多次優(yōu)化技術(shù)，直到發(fā)現(xiàn)解的個數(shù)等于指定個數(shù)為止，然而多次優(yōu)化并不能保證每次都收斂在不同的最優(yōu)解上。筆者從小生境技術(shù)、種群多樣性的保持等方面對多模態(tài)優(yōu)化問題的求解策略進(jìn)行綜述，在研究過程中得出以下結(jié)論：

1)采用生物啟發(fā)式算法求解多模態(tài)優(yōu)化問題，重點(diǎn)在于保持種群的多樣性和均勻分布，因而不管是采用小生境技術(shù)，還是采取其他策略，其最終的目的都必須對種群中的個體施加必要的策略，通過定義搜索空間中的某種度量來保持群體的多樣性，并在群體中同時保留多個高適應(yīng)值的高階模式,防止某個高適應(yīng)值的個體快速充滿整個群體,使得算法可以搜索到多個全局最優(yōu)解和局部最優(yōu)解；

2)為了保證在算法迭代過程中優(yōu)秀解不被破壞，在種群迭代過程中，需要采用相應(yīng)的“記憶”機(jī)制，來保留進(jìn)化過程中找到的最優(yōu)個體；

3)不管是適應(yīng)值共享小生境技術(shù)還是排擠小生境技術(shù)，它們之間其實并沒有明顯的界限，有時候可以相互交叉使用。

在研究的過程中，筆者發(fā)現(xiàn)以下有趣且尚待解決的問題：

1)因多模態(tài)優(yōu)化問題的目的在于找出問題的所有全局最優(yōu)解或多個有意義的局部最優(yōu)解，小生境技術(shù)或多個種群的引入，實則具有隱含的并行性，如何將并行機(jī)制引入到多模態(tài)優(yōu)化問題的求解過程中，勢必能在很大程度上減少算法的運(yùn)行時間；

2)目前的算法主要側(cè)重于問題的應(yīng)用，而相應(yīng)算法的理論分析，尤其是算法的“完全收斂性”分析則研究并不多；

3)在實際應(yīng)用過程，過度地將保持種群多樣性的重任寄托在“小生境”身上，或者說小生境舊模型的改進(jìn)或新模型的提出有時仍無法保證算法同時找到全部極值解，若讓進(jìn)化算法分擔(dān)一部分保持種群多樣性的任務(wù)，保證多模態(tài)優(yōu)化算法整體運(yùn)行的有效性，也是亟待解決的問題；

4)根據(jù)協(xié)同進(jìn)化的理論，競爭和協(xié)作不僅存在于個體和個體之間，各子群體之間同樣也存在著競爭和協(xié)作的關(guān)系，這也在一定程度上保持了種群的多樣性,同時，個體的選擇行為存在個體理性，群體的選擇行為具有集體理性，如何實現(xiàn)各不同小生境之間的相互協(xié)作，實現(xiàn)信息交流，也是一個值得研究的問題；

5)目前對算法性能的測試主要是函數(shù)的應(yīng)用，如何將企業(yè)、生產(chǎn)管理中的諸多問題抽象成多模態(tài)優(yōu)化問題，以便給企業(yè)的生成管理提供多套備選方案，也是下一步準(zhǔn)備研究的議題。

[參考文獻(xiàn)]

[1]Basak A，Das S，Tan K C. Multimodal Optimization Using a Biobjective Differential Evolution Algorithm Enhanced With Mean Distance-Based Selection[J]. IEEE Transactions on Evolutionary Computation, 2013,17：666～685.

[2]楊孔雨,王秀峰.免疫記憶遺傳算法完全收斂性研究[J].計算機(jī)工程與應(yīng)用,2005,41(12):47～50.

[3]林焰,郝聚民,紀(jì)卓尚,等. 隔離小生境遺傳算法研究[J].系統(tǒng)工程學(xué)報,2000,15(1) :86～91.

[4]Meng X Y, Huang S. A new method to design section area curve of ship based on niche ACO[A].Proc of the 8th World congress on Intelligent Control and Automation[C]. 2010:3230～3235.

[5]熊偉清，魏平.二進(jìn)制蟻群進(jìn)化算法[J].自動化學(xué)報，2007，33(3)：259～264.

[6]嚴(yán)彬,熊偉清,程美英,等. 帶擁塞控制的多種群二元蟻群算法[J].控制理論與應(yīng)用,2009,26(4):387～394.

[7]倪志偉，肖宏旺，伍章俊，等. 基于改進(jìn)離散型螢火蟲群優(yōu)化算法和分形維數(shù)的屬性選擇方法[J]. 模式識別與人工智能, 2013, 26(12): 1169～1178.

[8]Krishnanand K N, Ghose D. Multimodal function optimization using a glowworm metaphor with applications to collective robotics [A].Proceedings of the Second Indian International Conference on Artificial Intelligence[C]. 2005: 328～346.

[9] Krishnanand K N, Ghose D. Theoretical foundations for rendezvous of glowworm-inspired agent swarms at multiple locations[J]. Robotics and Autonomous systems, 2008:549～569.

[10]Parsopoulos K E, Vrahatis M N.On the computation of all global minimizers through particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation, 2004,8:211～224.

[11]Li X.Adaptively choosing neighborhood bests using species in a particle swarm optimizer for multimodal function optimization[J].Proceedings of Genetic and Evolutionary Computing, 2004, 3102:105～116.

[12] Brits A, van den Bergh F.A niching particle swarm optimizer[A].Proceedings of the 4th Asia-Pacific Conference on Simulated Evolution Learning[C].2002：692～696.

[13]張梅鳳,邵誠.多峰函數(shù)優(yōu)化的生境人工魚群算法[J].控制理論與應(yīng)用, 2008,25(4):773～776.

[14]江銘炎, 袁東風(fēng). 人工魚群算法及其應(yīng)用[M].北京：科學(xué)出版社,2012.

[15]Wessing S,PreussM,Rudolph G. Niching by multiobjectivization with neighbor information: Trade-offs and benefits[A]. IEEE Congress on Evolutionary Computation (CEC), 2013: 103～110.

[16]王柳毅，熊偉清.并行二進(jìn)制蟻群算法的多峰函數(shù)優(yōu)化[J].計算機(jī)工程與應(yīng)用，2006,22(4)：42～45.

[17]葉青，熊偉清,江寶釧. 基于二元蟻群算法的多目標(biāo)訂單分配問題求解[J].計算機(jī)工程,2011,37(3):175～182.

[18]呂明偉.基于相似度模型的多模態(tài)粒子群優(yōu)化算法研究[D]. 大連:大連理工大學(xué),2013.

[19]呂佳，熊忠陽.面向多模態(tài)函數(shù)優(yōu)化的混沌免疫網(wǎng)絡(luò)算法研究[J]. 計算機(jī)應(yīng)用，2006, 26(2)：456～459.

[20]Petrowski A. A clearing Procedure as a niching method for genetic algorithms[A].Proeeedings of the IEEE Conference on Evolutionary Computation [C].1996:798～803.

[21]李航,李敏強(qiáng),寇紀(jì)松.遺傳算法求解多模態(tài)優(yōu)化問題的動力性[J].自動化學(xué)報,2008,34(2):180～187.

[22]李敏強(qiáng),寇紀(jì)松, 林丹, 等. 遺傳算法的基本理論與應(yīng)用[M]. 北京:科學(xué)出版社,2002.

[23] De Jong K A. Genetic algorithm s: A 25 year perspective[A]. In: Proceedings of the Fifth International Conference on Genetic Algorithms[C].C A: Morgan Kaufmann Publishers, 1993.

[24] Mahfoud S W. Crowding and p re-selection revisited[A]. Manner R, M anderick B (eds.).Parallel Problem Solving from Nature [C] . Berlin: Springer, 1992: 67～76.

[25] Meng S O J, Goldberg D E. Probabilistic crow ding: Deterministic crowding with probabilistic replacement[A]. Ban Z W et al. (eds.).Proceedings of th e Genetic and Evolutionary Computation Conference 1999 (GECCO-99)[C] . C A: Morgan Kaufmann, 1999:173～179.

[26]Harik G. Finding multi-modal solutions using restricted tournament selection[A].Eshelman L J. Proceedings of the sixth International conference on Genetic Algorithms (ICGA 6)[C]. CA:Morgan Kaufmann,1995:24～31.

[27]譚竹梅,余曉峰,郭觀七.排擠小生態(tài)遺傳算法的改進(jìn)方法[J].控制理論與應(yīng)用,2004,21(4):65～654.

[28]薛文濤,吳曉蓓,單梁.多峰函數(shù)優(yōu)化的免疫混沌網(wǎng)絡(luò)算法[J].系統(tǒng)仿真學(xué)報,2012,22(4):915～920.

[29]王巍,彭力. 嵌入隔離小生境技術(shù)的混沌粒子群算法[J].系統(tǒng)工程與電子技術(shù),2008,30(6):1151～1154.

[30]嚴(yán)彬. 多種群蟻群優(yōu)化算法的研究[D]. 寧波:寧波大學(xué),2009.

[31]葉文,歐陽中輝,朱愛紅,等.求解多峰函數(shù)優(yōu)化的小生境克隆選擇算法[J]. 系統(tǒng)工程與電子技術(shù),2012,32(5):1100～1104.

[32]鄭士芹,王秀峰.基于多模態(tài)函數(shù)優(yōu)化的改進(jìn)克隆選擇算法[J].計算機(jī)工程與應(yīng)用,2006,42(3): 15～20.

[33]鄧勇躍,張貴軍.基于局部抽象凸支撐面的多模態(tài)優(yōu)化算法[J].控制理論與應(yīng)用.2014,31(4):458～466.

[34]Liu C Y,Wu W H. Niche identification techniques in multimodal genetic search with sharing scheme[J]. Advances in Engineering Software,2002,33:779～791.

[35] Cho D H, Kim J K, Jung H K. Optimal design of permanent-magnet motor using autotuning niching genetic algorithm[J]. IEEE Transactions on Magnetics, 2003,39(3):1265～1268.

[36]Diletoso E, Salerno N. A self-adaptive niching genetic algorithm for multimodal optimization of electromagnetic devices[J]. IEEE Transactions on Magnetics,2006,42(4):1203～1206.

[37]鄭金華,劉磊,劉盼,等. 一種自適應(yīng)小生境分布性保持策略[J].電子學(xué)報,2012,40(11):2330～2335.

[38]梁昌勇,陸青,楊善林,等. 一種基于小生境熵的自適應(yīng)混合遺傳算法[J].中國管理科學(xué),2008,16(2):115～121.

[39]陳彥龍，張培林，李勝，等. 面向多峰函數(shù)的自適應(yīng)小生境量子進(jìn)化算法[J].系統(tǒng)工程與電子技術(shù),2014,36(2):404～408.

[40]胡旺, Gary G, 張鑫.基于Pareto熵的多目標(biāo)粒子群算法[J].軟件學(xué)報，2014,25(5)：1025～1050.

[41]張貴軍,何樣軍,郭海鋒,等. 基于廣義凸下界估計的多模態(tài)差分進(jìn)化算法[J].軟件學(xué)報,2013,24(6):1177～1195.

[42]吳建輝. 混合免疫優(yōu)化理論與算法及其應(yīng)用研究[D]. 湖南大學(xué)博士學(xué)位論文,2013.

[43]吳建輝,章兢,李仁發(fā),等.多子種群微粒群免疫算法及其在函數(shù)優(yōu)化中應(yīng)用[J].計算機(jī)研究與發(fā)展,2012,49(9):1883～1898.

[44]李敏強(qiáng),寇紀(jì)松.多模態(tài)函數(shù)優(yōu)化的協(xié)同多群體遺傳算法[J].自動化學(xué)報,2002,28(4):497～504.

[45]于歆杰,王贊基.自適應(yīng)調(diào)整峰半徑的適應(yīng)值共享遺傳算法[J].自動化學(xué)報,2002,28(5):816～820.

[46]王湘中,喻壽益.多模態(tài)函數(shù)優(yōu)化的多種群進(jìn)化策略[J].控制與決策,2006,21(3):285～288.

[47]畢曉君，王艷嬌.用于多峰函數(shù)優(yōu)化的小生境人工蜂群算法[J].系統(tǒng)工程與電子技術(shù)，2011，33(11)：2564～2567.

[編輯]張濤

[文獻(xiàn)標(biāo)志碼]A

[文章編號]1673-1409(2016)07-0040-09

[中圖分類號]O224

[作者簡介]錢乾(1983-)，男，碩士，講師，現(xiàn)主要從事群智能算法、數(shù)據(jù)挖掘方面的教學(xué)與研究工作; E-mail:sparkqq@126.com。

[基金項目]安徽省教育廳自然科學(xué)研究項目(KJ2013Z089)；安徽省教育廳自然科學(xué)研究重點(diǎn)項目(KJ2015A373)；安徽省教育廳質(zhì)量工程項目(2014zy117)。

[收稿日期]2015-10-17

[引著格式]錢乾，芮坤坤，程美英.生物啟發(fā)式算法求解多模態(tài)優(yōu)化問題研究[J].長江大學(xué)學(xué)報(自科版)，2016,13(7)：40～48.