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

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

?

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

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

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

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

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

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

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

問題描述如下：

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

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

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

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

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

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

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

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

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

(1)

則稱算法是完全收斂的。

2.1遺傳算法完全收斂性

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

2.2蟻群算法完全收斂性

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

2.3螢火蟲算法完全收斂性

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

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

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

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

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

3.1小生境的形成

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

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

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

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

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

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

圖2　聚類小生境示意圖

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

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

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

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

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

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

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

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

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

(2)

(3)

式中，F1(f(x))為具有拉伸效果的函數；F2(f(x))為具有壓縮效果的函數。

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

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

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

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

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

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

圖3　抗體交換算子　　　　　　　　　　圖4　抗體逆轉算子　　　　　　　　　圖5　抗體移位算子

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

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

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

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

3.3小生境半徑的選擇

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

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

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

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

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

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

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

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

5總結與展望

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

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

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

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

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

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

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

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

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

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

[參考文獻]

[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].計算機工程與應用,2005,41(12):47～50.

[3]林焰,郝聚民,紀卓尚,等. 隔離小生境遺傳算法研究[J].系統工程學報,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].自動化學報，2007，33(3)：259～264.

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

[7]倪志偉，肖宏旺，伍章俊，等. 基于改進離散型螢火蟲群優(yōu)化算法和分形維數的屬性選擇方法[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]張梅鳳,邵誠.多峰函數優(yōu)化的生境人工魚群算法[J].控制理論與應用, 2008,25(4):773～776.

[14]江銘炎, 袁東風. 人工魚群算法及其應用[M].北京：科學出版社,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]王柳毅，熊偉清.并行二進制蟻群算法的多峰函數優(yōu)化[J].計算機工程與應用，2006,22(4)：42～45.

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

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

[19]呂佳，熊忠陽.面向多模態(tài)函數優(yōu)化的混沌免疫網絡算法研究[J]. 計算機應用，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]李航,李敏強,寇紀松.遺傳算法求解多模態(tài)優(yōu)化問題的動力性[J].自動化學報,2008,34(2):180～187.

[22]李敏強,寇紀松, 林丹, 等. 遺傳算法的基本理論與應用[M]. 北京:科學出版社,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].控制理論與應用,2004,21(4):65～654.

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

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

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

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

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

[33]鄧勇躍,張貴軍.基于局部抽象凸支撐面的多模態(tài)優(yōu)化算法[J].控制理論與應用.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]鄭金華,劉磊,劉盼,等. 一種自適應小生境分布性保持策略[J].電子學報,2012,40(11):2330～2335.

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

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

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

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

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

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

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

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

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

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

[編輯]張濤

[文獻標志碼]A

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

[中圖分類號]O224

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

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

[收稿日期]2015-10-17

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