基于適應(yīng)度地形分析的進(jìn)化計算研究綜述

李亞欣，梁 靜，岳彩通，李 珂

(鄭州大學(xué) 電氣工程學(xué)院，河南 鄭州 450001)

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)成為研究熱點。具有多模態(tài)、含約束、多目標(biāo)等性質(zhì)的復(fù)雜優(yōu)化問題因其具有更高的理論和實際應(yīng)用價值被人們持續(xù)研究。為了解決這些優(yōu)化問題，早先搜索策略的設(shè)計通常需要依賴算法設(shè)計者的經(jīng)驗、待優(yōu)化問題的先驗知識或調(diào)參確定。雖然研究人員設(shè)計了多種基準(zhǔn)測試函數(shù)集以盡可能涵蓋優(yōu)化問題的更多屬性，但是并沒有從根本上解決這個問題。根據(jù)“無免費(fèi)午餐”定理[1]，一種算法不可能在所有問題上都表現(xiàn)優(yōu)異，不同的算法可能在不同類型的問題上有特定優(yōu)勢。因此，需發(fā)展基于學(xué)習(xí)的方法來自適應(yīng)地根據(jù)優(yōu)化問題的多方面需求和性質(zhì)指導(dǎo)算法選擇和種群進(jìn)化。

問題的適應(yīng)度空間地形能直接反映問題的特性，因此提取地形信息有助于問題的特性分析。適應(yīng)度地形的概念源于理論生物學(xué)[2]，它是指一個三元組L=(S,V,F)，其中S是所有解的集合，V：S→2s是一個特定的鄰域函數(shù)，對于每一個s∈S，V(s)是其鄰域解集，F(xiàn)：S→R是適應(yīng)度方程。適應(yīng)度地形的作用是與優(yōu)化問題的真實地形對比，以便我們了解算法的工作原理，更好地解決實際問題[3]。適應(yīng)度地形分析(fitness landscape analysis，F(xiàn)LA)是指數(shù)據(jù)驅(qū)動技術(shù)的集合，用于提取與適應(yīng)度地形特性有關(guān)的描述性或數(shù)值度量[4]。因此，F(xiàn)LA的目的是獲得有關(guān)給定優(yōu)化問題的知識，并深入了解對于算法性能至關(guān)重要的優(yōu)化問題的特征[5]。

進(jìn)化計算(evolutionary computing，EC)通過模擬自然界生物進(jìn)化機(jī)制，在一些可行解組成的種群中，通過迭代進(jìn)化尋求最優(yōu)解。EC技術(shù)因其強(qiáng)大的全局搜索能力和并行計算能力備受關(guān)注，最近更是廣泛應(yīng)用于適應(yīng)度地形的研究。然而，現(xiàn)有文獻(xiàn)對近些年EC在適應(yīng)度地形上的研究缺乏全面而系統(tǒng)的討論?；诖耍疚膶C在適應(yīng)度地形分析方面的相關(guān)文獻(xiàn)進(jìn)行分析和總結(jié)，為相關(guān)研究人員提供參考。

1 進(jìn)化計算

1.1 進(jìn)化計算的主要特點和分類

進(jìn)化計算是模擬生物進(jìn)化理論而形成的一種全局優(yōu)化自適應(yīng)概率搜索的算法理論，它是計算智能的子域之一，是一類具有啟發(fā)式或隨機(jī)優(yōu)化特點的求解器。它受生物進(jìn)化中適者生存、優(yōu)勝劣汰自然選擇機(jī)制和遺傳信息傳遞規(guī)律的啟發(fā)，通過程序迭代模擬這一過程，在一些可能的解組成的種群中，通過自然演化尋求最優(yōu)解[6]。進(jìn)化計算一般包括種群初始化、個體適應(yīng)度值評價、種群繁殖與進(jìn)化等，其基本的計算流程框架如圖1所示。

圖1 進(jìn)化計算的基本流程框架

與普通搜索算法一樣，進(jìn)化計算也是一種迭代算法。不同的是，在最優(yōu)解的搜索過程中，普通搜索算法是從某一個單一的初始點開始搜索，而進(jìn)化計算是從原問題的一組解出發(fā)改進(jìn)到另一組更好的解，再對這組改進(jìn)的解進(jìn)一步改進(jìn)。而且，進(jìn)化計算還適用于沒有解析目標(biāo)函數(shù)和無法得到目標(biāo)函數(shù)梯度信息的優(yōu)化問題，以及在解決同時有整數(shù)和連續(xù)變量的混合優(yōu)化問題方面具有顯著優(yōu)勢。

進(jìn)化算法是一種理想的全局搜索方法，它有以下幾個特點：(1)有指導(dǎo)搜索，搜索中利用個體目標(biāo)函數(shù)值的信息，而不必用目標(biāo)函數(shù)的導(dǎo)數(shù)信息或與具體問題有關(guān)的特殊知識來指導(dǎo)種群進(jìn)化；(2)自適應(yīng)搜索，通過進(jìn)化算子進(jìn)化操作來改進(jìn)群體性能；(3)漸進(jìn)式尋優(yōu)，逐代進(jìn)化；(4)并行式搜索，對每一代群體中的個體同時進(jìn)行搜索，也適合于并行計算；(5)黑箱式結(jié)構(gòu)，只需要研究輸入和輸出而不需考慮過程；(6)全局最優(yōu)解，在整個搜索區(qū)域的各個部分同時進(jìn)行搜索行為；(7)魯棒性強(qiáng)，處理不確定性有優(yōu)勢，因為進(jìn)化算子中多包含隨機(jī)因素，與確定性算法相比，其具有較好的魯棒性。

常用的進(jìn)化計算方法主要包含以下幾種：(1)遺傳算法[7](genetic algorithm, GA)。GA是一種自適應(yīng)優(yōu)化概率搜索算法,它通過借助遺傳學(xué)原理，經(jīng)過自然選擇、遺傳、變異等作用機(jī)制進(jìn)而篩選出具有適應(yīng)性更高的個體；(2)遺傳規(guī)劃[8-9](genetic programming, GP)。GP是一種用于求解最優(yōu)解結(jié)構(gòu)的優(yōu)化算法，而這種解的結(jié)構(gòu)一般用樹狀圖來表示；(3)進(jìn)化規(guī)劃[10](evolution programming, EP)。EP是一種模擬生物進(jìn)化過程與機(jī)制求解問題的自適應(yīng)進(jìn)化算法,它通過繁殖、變異、競爭、選擇4種操作來產(chǎn)生新一代種群；(4)進(jìn)化策略[10](evolution strategies, ES)。ES是一種模擬自然進(jìn)化原理以求解參數(shù)優(yōu)化問題的優(yōu)化算法,它利用遺傳信息每一代的傳承變異，通過適者生存的理論，保存適應(yīng)性強(qiáng)的個體，得到最優(yōu)解；(5)粒子群算法[11](particle swarm optimization, PSO)。PSO算法是受鳥類群體覓食行為的啟發(fā)而提出的一種仿生優(yōu)化算法,它利用種群粒子間合作與競爭來指導(dǎo)優(yōu)化搜索[11]；(6)差分進(jìn)化算法[12](differential evolution, DE)。DE算法是一種具有保優(yōu)思想的貪婪遺傳算法，它通過隨機(jī)生成初始種群，利用變異與交叉操作來選擇最佳個體進(jìn)行繁殖；(7)蟻群算法[13](ant colony optimization algorithm, ACO)。ACO算法是受螞蟻覓食行為的啟發(fā)而提出的一種啟發(fā)式搜索算法,它模擬螞蟻尋找食物的規(guī)律，在運(yùn)動過程中以信息素為牽引，控制螞蟻尋找最優(yōu)路徑。

1.2 進(jìn)化計算的理論基礎(chǔ)研究

一般來說，進(jìn)化算法的求解包括以下幾個步驟：給定一組初始解，評價當(dāng)前這組解的性能；從當(dāng)前這組解中選擇一定數(shù)量的解作為迭代后的解的基礎(chǔ)；再對其進(jìn)行操作，得到迭代后的解；若這些解滿足進(jìn)化要求則停止，否則將這些迭代后的解作為當(dāng)前解重新操作。目前，有關(guān)進(jìn)化計算的理論基礎(chǔ)研究主要包括以下幾個方面：

第一，進(jìn)化計算在算法的復(fù)雜度、收斂性和收斂速度分析等方面的數(shù)學(xué)建模和理論研究。例如，Huang等[14]針對連續(xù)型進(jìn)化算法，提出了一種基于平均增益模型的時間復(fù)雜度上界的估算方法，建立了理論基礎(chǔ)與實際應(yīng)用的溝通橋梁。覃俊等[15]基于有限馬爾可夫鏈理論，提出了一種多目標(biāo)進(jìn)化算法(multi-objective evolutionary algorithm，MOEA)的收斂性分析框架。案例研究的結(jié)果表明，搜索算子和選擇算子不僅對提高M(jìn)OEA的效率有重要作用，而且對算法的收斂性也有很大的影響。Zhang等[16]進(jìn)行有關(guān)算法行為和收斂性的理論分析，并證明稀疏性促進(jìn)算法如何快速逼近一個局部最小值。Wu等[17]利用離散時間動態(tài)系統(tǒng)理論對粒子群算法進(jìn)行了收斂性分析和參數(shù)選擇，該研究為一般性隨機(jī)算法的參數(shù)選擇提供了定性指導(dǎo)。

第二，從理論和實際效果兩方面比較進(jìn)化算法與其他優(yōu)化方法的不同。例如，Del等[18]結(jié)合穩(wěn)態(tài)和經(jīng)濟(jì)標(biāo)準(zhǔn)，將增強(qiáng)型粒子群算法(enhanced particle swarm optimization algorithm，enhanced-PSO)的性能與經(jīng)典優(yōu)化方法進(jìn)行了比較以說明進(jìn)化算法的有效性。Piotrowsk等[19]將多種進(jìn)化算法訓(xùn)練注入噪聲的多層感知器神經(jīng)網(wǎng)絡(luò)，用于估計河流中的縱向彌散系數(shù)。實驗結(jié)果顯示，與之前最常用的基于梯度的優(yōu)化方法相比，進(jìn)化算法不僅能夠應(yīng)對不可微問題，并且能快速收斂到局部最優(yōu)。另外，Zhang等[20]也充分利用進(jìn)化算法的全局搜索特性和反向傳播算法的局部搜索功能，提出了一種三層前饋神經(jīng)網(wǎng)絡(luò)的兩階段訓(xùn)練算法。通過對比傳統(tǒng)的剪枝優(yōu)化等方法，該算法可以以較低的計算成本獲得更好的泛化能力。

第三，從生物進(jìn)化或自然界各種現(xiàn)象中獲得新啟發(fā)，提出新方法，或?qū)ΜF(xiàn)有的進(jìn)化計算方法進(jìn)行改進(jìn)。例如，Schaffer[21]首次提出多目標(biāo)遺傳算法，隨后多種多目標(biāo)遺傳算法NSGA[22]、NSGAII[23]等被相繼提出。自從多目標(biāo)粒子群優(yōu)化算法被首次提出后[24]，后期也出現(xiàn)了多種多目標(biāo)粒子群優(yōu)化算法，代表性算法包括NSPSO[25]、MOCLPSO[26]、MO_ring_PSO_SCD[27]等。此外，針對多模態(tài)多目標(biāo)優(yōu)化問題需要優(yōu)化算法來定位多個帕累托解集的情況，Liang等[28]提出了一種基于聚類技術(shù)和精英選擇機(jī)制的差分進(jìn)化算法來獲得決策空間和目標(biāo)空間中均勻分布的解集。針對全局解決方案不可行的問題，Yue等[29]提出了一種利用小生境方法的多模態(tài)多目標(biāo)遺傳算法來查找全局和局部帕累托解，使種群可以在局部范圍內(nèi)快速進(jìn)化。

第四，研究如何通過學(xué)習(xí)提高進(jìn)化算法自適應(yīng)求解能力。例如，Peng等[30]提出了基于種群的算法組合方案(population-based algorithm portfolios，PAP)，通過將總種群劃分為多個子種群以及為每種算法分配一個子種群，多個種群之間信息交互來實現(xiàn)時間預(yù)算的分配，并在文獻(xiàn)[31]中進(jìn)行了相關(guān)拓展與改進(jìn)。為了實現(xiàn)利用合適的策略和控制參數(shù)來解決不同類型優(yōu)化問題或適應(yīng)不同演化階段的目標(biāo)，F(xiàn)an等[32]提出了一種基于知識的策略自適應(yīng)和控制參數(shù)的環(huán)境優(yōu)化算法。該算法利用學(xué)習(xí)遺忘機(jī)制實現(xiàn)了對變異和交叉策略的自適應(yīng)調(diào)整，在所有比較算法中具有很強(qiáng)的競爭性。針對多目標(biāo)問題搜索空間中搜索冗余的情況，Huang等[33]提出了一種結(jié)合適應(yīng)度地形崎嶇度和強(qiáng)化學(xué)習(xí)策略的多目標(biāo)差分進(jìn)化算法。實驗結(jié)果表明，該算法可以緩解搜索冗余和搜索空間映射不平衡的問題，有效提高了算法在優(yōu)化過程中的收斂性。另外，盡管目前已經(jīng)提出了多種DE算法來解決各種優(yōu)化問題，但是并沒有發(fā)現(xiàn)任何一種DE算法在多種類型的問題上都表現(xiàn)最佳。于是，Shao等[34]提出了一種基于適應(yīng)度模態(tài)檢測(landscape modal detection, LMD)技術(shù)的自適應(yīng)地形模態(tài)檢測(DE-LMD)算法。針對不同地形的問題，采用了包含DE/current-to-best/1和鄰域引導(dǎo)變異的混合變異策略。實驗結(jié)果表明，該算法在不同類型的優(yōu)化問題上都具有良好的性能。

通過大量的文獻(xiàn)調(diào)研發(fā)現(xiàn)：國內(nèi)外將進(jìn)化算法用于研究優(yōu)化問題本身特性的研究相對較少，而將適應(yīng)度地形應(yīng)用于進(jìn)化算法受到了大量學(xué)者的廣泛關(guān)注。圖2給出了Engineering Village數(shù)據(jù)庫中2000—2020年適應(yīng)度地形相關(guān)文章數(shù)的變化趨勢及相關(guān)文章中中國占世界文章數(shù)目的比例。由圖可見，相關(guān)文章數(shù)總體趨勢逐漸增長，2008—2015年整體有所下降，但2016年開始回升并達(dá)到歷史最高，可見適應(yīng)度地形分析目前是研究的熱點。

圖2 2000—2020年基于適應(yīng)度地形分析的進(jìn)化計算研究的相關(guān)文章數(shù)目趨勢圖

2 適應(yīng)度地形分析

2.1 適應(yīng)度地形的定義

令X為適應(yīng)度函數(shù)f的候選解，使得Y=f(X)。候選解的子集為輸入樣本x，其成本值為輸出樣本y。對于未知特性的優(yōu)化問題，只能通過對決策空間進(jìn)行采樣獲取問題的特征信息。搜索算法保持了候選解與計算代價關(guān)系的簡化模型，該模型假定問題具有可利用的結(jié)構(gòu)，因此進(jìn)化算法可以通過在運(yùn)行期間收集信息來推斷有關(guān)問題結(jié)構(gòu)的詳細(xì)信息，這種結(jié)構(gòu)被稱為函數(shù)的適應(yīng)度地形[35]。

圖3顯示了一個維數(shù)為2的函數(shù)適應(yīng)度地形圖，其中圖3a說明該地形是由山脊、山谷、高原和盆地組成的三維表面。局部和全局最優(yōu)值均位于此曲面的最低點[36];圖3b顯示了適應(yīng)度地形的等高線圖,顏色條顯示的是高度值。在這種情況下，搜索算法的目標(biāo)是找到最優(yōu)解，并在表面更新模型時存儲有關(guān)表面結(jié)構(gòu)的信息，而這種利用模型推斷適應(yīng)度地形情況的方式直接影響算法的搜索性能。

圖3 D=2的函數(shù)適應(yīng)度地形圖

2.2 適應(yīng)度地形的基本特性

2.2.1 模態(tài)性與平滑度 可以使用全局最優(yōu)個數(shù)xg和局部最優(yōu)個數(shù)xl來描述適應(yīng)度地形的某些特征。單模態(tài)函數(shù)被定義為|xg|=|xl|=1的地形(如圖4a)，而多模態(tài)函數(shù)可定義為|xg|=|xl|>1的地形(如圖4b)。

與模態(tài)性緊密相關(guān)的特性是平滑度[37]，它是根據(jù)在鄰域范圍內(nèi)代價函數(shù)適應(yīng)度值變化的幅度，將適應(yīng)度地形正式分為崎嶇、平滑或中立。崎嶇的地形[38]是指在一定的鄰域范圍內(nèi)候選解的適應(yīng)度值有很大的波動，呈現(xiàn)多個局部最優(yōu)值，以及地形呈現(xiàn)陡峭的上升和下降(如圖4c)。中性的地形[39]具有較大的平坦區(qū)域，其中輸入變量的變化無法產(chǎn)生輸出的顯著變化(如圖4d)。由于崎嶇和中性地形的特性，因此很難斷定地形的某些區(qū)域是否值得探索。全局結(jié)構(gòu)是指由聚類的局部最優(yōu)值xl組成的整體盆地形狀，可用于指導(dǎo)對全局最優(yōu)點xg的搜索。如果該結(jié)構(gòu)是平滑的(如圖4e)，則將為算法提供潛在的可利用信息。如果這種模式是崎嶇的或不存在的，那么找到一個全局最優(yōu)值是具有挑戰(zhàn)性的或者是找不到的。另外，也有可能發(fā)現(xiàn)表現(xiàn)出欺騙性的問題，即全局結(jié)構(gòu)和梯度信息使算法偏離最優(yōu)值(如圖4f)，從而使優(yōu)化算法的效率不如隨機(jī)搜索或窮盡枚舉[40-41]。

圖4 描述特定地形特征的6個一維函數(shù)適應(yīng)度地形圖

2.2.2 吸引盆地 除了局部最優(yōu)個體的數(shù)目外，盆地大小的分布和深度是確定地形難度更為重要的因素[42-43]。其中，具有相對較小吸引力盆地的局部最優(yōu)區(qū)域被稱為孤立的地形。盆地的大小和深度不僅會增加分析優(yōu)化算法適應(yīng)度地形的復(fù)雜度，而且會對種群個體的更新產(chǎn)生重要影響。Whitley等[44]研究了模態(tài)性對遺傳算法性能的影響，發(fā)現(xiàn)盡管局部最優(yōu)值的數(shù)目并不總是會影響遺傳算法的行為，但高度合適的局部最優(yōu)值(尤其是具有大吸引力的盆地)確實為遺傳算法搜索帶來了問題。另外，Kinnear等[45]也發(fā)現(xiàn)，在使用遺傳規(guī)劃算法解決問題時，地形盆地的深度與一系列問題的難度呈現(xiàn)良好的相關(guān)性。

2.2.3 對稱性 適應(yīng)度函數(shù)或地形中的對稱性會產(chǎn)生多個具有相同適應(yīng)度值的點，因此有多種方式能將搜索空間劃分為較大的等價類。例如，如果適應(yīng)度地形相對于其中一個軸對稱，則稱為軸向偏置。如果在設(shè)定距離值上，某些點與最佳點的適應(yīng)度值相同，則無論點的方向如何，適應(yīng)度地形都相對于最佳點對稱。對稱性對算法搜索的性能存在相互矛盾的研究結(jié)果:Whitley等[46]在研究中發(fā)現(xiàn)函數(shù)對稱性的存在會導(dǎo)致某些遺傳算法的失??；Naudts等[47]的研究也表明，對稱性的存在會對簡單遺傳算法的收斂能力產(chǎn)生負(fù)面影響，這可能是由于兩個互不相同的良好(對稱)解相互交叉導(dǎo)致了不好(不對稱)的子代。但是，其他研究表明，遺傳算法確實在具有軸向偏差的適應(yīng)度地形上表現(xiàn)出更好的性能[48]，并且對于此類問題，坐標(biāo)系的旋轉(zhuǎn)會導(dǎo)致嚴(yán)重的算法性能損失[49]。

2.2.4 進(jìn)化性/搜索性 進(jìn)化性可粗略地定義為進(jìn)化能力[50]。Altenberg[51]將進(jìn)化能力描述為種群產(chǎn)生比其父代更好的子代的能力。盡管可進(jìn)化性的概念與算法種群進(jìn)化的能力有關(guān)，但就特定的搜索算子或策略而言，它也可被視為適應(yīng)度地形的特征。本文將這種可進(jìn)化性定義為給定搜索過程中采樣點向適應(yīng)度更好的地形中某個位置移動的能力，即可搜索性。該定義擴(kuò)大了可進(jìn)化性的范圍，超出了基于進(jìn)化算法的范圍，以涵蓋任何搜索過程?？伤阉餍允菃栴}的特征，僅對特定搜索策略有意義。另外，對某一種算法而言，具有高搜索性的問題，相對于另一種算法可能表現(xiàn)出低搜索性。近年來，關(guān)注于可搜索性的適應(yīng)度地形分析技術(shù)包括適應(yīng)度進(jìn)化描述[52]、適應(yīng)度云[53-54]、適應(yīng)度概率云[53,55]、負(fù)斜率系數(shù)[54]、累計逃逸概率[55]等。

2.2.5 上位性 在遺傳學(xué)中，上位性是指染色體中基因之間表達(dá)的依賴性程度。如果基因獨(dú)立地影響染色體的整體適應(yīng)性，那么該系統(tǒng)的上位性就很低。如果基因的適應(yīng)性貢獻(xiàn)取決于其他基因的值，則該系統(tǒng)就具有較高的上位性。通常，對于優(yōu)化問題，此特性可以稱為變量之間的相互依存度(也可稱為非線性可分離性)。當(dāng)優(yōu)化問題中的變量相互依賴時，這意味著不可能做到通過調(diào)整一個獨(dú)立于其他變量的變量來找到最優(yōu)值[48]。例如，如果適應(yīng)度函數(shù)的數(shù)學(xué)表達(dá)式中不同變量可以通過加法分開，則可以認(rèn)為變量是獨(dú)立地對適應(yīng)度值做貢獻(xiàn)。但是，如果在函數(shù)表達(dá)式中是通過乘法將不同的變量組合在一起時，這些變量就必須配合才能有助于提高適應(yīng)度；如果任一變量的值較低，那么即使另一個變量的值較高，乘積也可能比較低。研究表明，對遺傳算法而言，線性可分離函數(shù)比非線性可分離函數(shù)更容易求解[47]。

2.3 基于適應(yīng)度地形分析的進(jìn)化計算研究

2.3.1 地形特征的設(shè)計與改進(jìn) 盡管許多適應(yīng)度地形分析技術(shù)最初被定義為精確測度，但實際上它們被用作近似度量[3]。由于我們的目標(biāo)不是將技術(shù)劃分為各種類別，而是為了了解實際使用的技術(shù)，因此為了更具描述性地區(qū)分特征，表1對代表性適應(yīng)度地形技術(shù)進(jìn)行了描述和說明。其中，與模態(tài)性和全局結(jié)構(gòu)相關(guān)的技術(shù)包括適應(yīng)度距離相關(guān)[6,56]、色散度量[57]；與崎嶇性和中立性相關(guān)的技術(shù)包括自相關(guān)函數(shù)[58]、相關(guān)長度[59]、隨機(jī)游走[60]、熵測度[61-62]、盆地規(guī)模比[63]等。近年來，關(guān)注可搜索性的適應(yīng)度地形分析技術(shù)包括適應(yīng)度進(jìn)化描述[52]、適應(yīng)度云[53-54]、適應(yīng)度概率云[53,55]、負(fù)斜率系數(shù)[54]、累計逃逸概率[55]等。并且，量化上位性與欺騙性的技術(shù)有按位上位性[64]、上位性差異[65]和信息地形[40-41]等。

表1 代表性適應(yīng)度地形分析技術(shù)

在進(jìn)化計算領(lǐng)域，許多研究人員基于這些代表性的適應(yīng)度地形特征，進(jìn)行了針對性的改進(jìn)。例如，Lunacek等[66]研究了色散度量的性質(zhì)。為了改善色散度量的缺陷，作者對3個基本方法提出了3個獨(dú)立的修改，分別是色散邊界的標(biāo)準(zhǔn)化、分?jǐn)?shù)p的LP范數(shù)和固定步長的隨機(jī)游走。實驗結(jié)果表明，這些改進(jìn)可以促進(jìn)收斂并增加問題的可分離性。此外，Ochoa等[67]提出了一種將組合優(yōu)化問題的基本地形特征壓縮為局部最優(yōu)網(wǎng)絡(luò)圖形的技術(shù)，而這種基于圖的模型可用于表征地形結(jié)構(gòu)和局部最優(yōu)值的分布。Vanneschi等[68]也指出負(fù)斜率系數(shù)原始定義的限制，于是為負(fù)斜率系數(shù)提供了一個新的相關(guān)定義和提出了一種劃分適應(yīng)度云的新方法，并從經(jīng)驗上證明了此新定義作為問題硬度度量的適用性。

2.3.2 利用地形特征對優(yōu)化問題分類 適應(yīng)度地形分析是一個涵蓋理論和實踐技術(shù)的術(shù)語，用于分析與問題難度相關(guān)的特征，不同的搜索運(yùn)算符如何影響適應(yīng)度地形拓?fù)涞?。利用地形特征對?yōu)化問題分類可以幫助選擇適合于解決待優(yōu)化問題的良好算法。近年來，針對優(yōu)化問題的分類，學(xué)者們做了許多工作。Cicirello等[70]研究了可用于排列的距離度量，并使用主成分分析對現(xiàn)有特征分類，從而識別與優(yōu)化問題最相關(guān)的搜索算子。Kerschke等[71]通過引入檢測優(yōu)化問題漏斗結(jié)構(gòu)的特征，將其與現(xiàn)有相關(guān)特征組合在一起，以便于對有關(guān)漏斗屬性的優(yōu)化問題進(jìn)行分類，并在文獻(xiàn)[72]中進(jìn)行了拓展和改進(jìn)。Merz等[73]對二次分配問題的多個實例進(jìn)行了適應(yīng)度地形分析，并根據(jù)問題實例的硬度特征對優(yōu)化問題的實例進(jìn)行分類?；诖耍梢哉业街亟M和/或變異操作算子的有利選擇以更好地解決待優(yōu)化問題。

2.3.3 利用地形特征指導(dǎo)算法設(shè)計 隨著進(jìn)化算法的不斷發(fā)展，適應(yīng)度地形可以在適應(yīng)度方面提供更豐富的特征信息，從而更好地指導(dǎo)研究人員設(shè)計有效算法。這些地形特征分別從不同角度反映了優(yōu)化問題最優(yōu)解的分布、數(shù)量以及全局拓?fù)?。例如，對于每種算法僅適用于某個適應(yīng)度地形的情況，Li等[74]提出了一種新的自反饋差分進(jìn)化算法，通過提取各代種群中局部適應(yīng)度地形特征，并結(jié)合各個局部適應(yīng)度地形中單峰和多峰的概率分布，選擇最優(yōu)的變異策略以此來自適應(yīng)地解決某些類型的優(yōu)化問題。Sallam等[75]在差分進(jìn)化算法選擇機(jī)制的設(shè)計中也使用了優(yōu)化問題的地形信息，針對組合約束優(yōu)化問題，提出了一個具有適應(yīng)距離相關(guān)性的多算子DE框架，該框架用于在進(jìn)化過程中動態(tài)地將更多權(quán)重分配給性能最佳的DE算子。實驗結(jié)果表明，與現(xiàn)有算法相比，該算法能夠產(chǎn)生高質(zhì)量的解決方案。另外，Kuk等[76]提出了將適應(yīng)度地形分析技術(shù)和自適應(yīng)算子選擇機(jī)制相結(jié)合的多目標(biāo)算法框架，該方案擴(kuò)展了適應(yīng)度地形分析收集的可搜索性和多模態(tài)信息，是將適應(yīng)度地形應(yīng)用于多模態(tài)多目標(biāo)問題的初步研究。

2.3.4 利用地形特征評估算法相對性能 群集智能的研究重點主要在算法方面，目前對于優(yōu)化問題以及與問題相關(guān)的算法行為的研究相對較少。并且，當(dāng)文獻(xiàn)中提出新算法或現(xiàn)有算法的變體時，很少討論或分析算法弱點以及算法失敗的原因。適應(yīng)度地形分析是一種可用于分析優(yōu)化問題的方法，根據(jù)適應(yīng)度地形特征來表征問題，可以研究問題類型與算法性能之間的聯(lián)系。例如，了解和研究算法性能的邊界對于良好的實踐研究至關(guān)重要，并且可以提供對算法優(yōu)缺點更為準(zhǔn)確、更強(qiáng)大的描述。于是，Smith等[77]設(shè)計了一種能夠評估各種優(yōu)化算法相對能力的新方法，即將一組不同實例表示為高維特征空間中的點，而且，投影到低維空間以可視化。定義了評估算法好壞的性能指標(biāo)，并提出了一種用于測量算法占用空間大小的方法。另外，Malan等[78]研究了多種地形特征用來分析算法進(jìn)化過程，并表明最初針對離散優(yōu)化問題提出的許多現(xiàn)有的適應(yīng)度地形分析技術(shù)同樣適用于某些連續(xù)優(yōu)化問題。實驗表明，沒有任何一種度量能夠單獨(dú)用作PSO算法的預(yù)測指標(biāo)，但是可以結(jié)合多種適應(yīng)度地形特征來預(yù)測PSO算法的失敗。Tavares等[79]也研究了啟發(fā)式算子和遺傳算子之間的相互作用如何影響解決多維背包問題的進(jìn)化算法的搜索性能，并且對啟發(fā)式算法和局部搜索技術(shù)如何提高進(jìn)化算法的性能進(jìn)行了對比分析。

續(xù)表1

2.3.5 利用地形特征指導(dǎo)算法選擇 近年來，不同類型的進(jìn)化算法層出不窮，并且在不同類型優(yōu)化問題上的表現(xiàn)截然不同。因此，工程師們很難選擇合適的方法來有效地解決目標(biāo)問題[80]。對于待優(yōu)化問題來說，最直接的一種方法是分別執(zhí)行所有可能的算法，然后選擇表現(xiàn)最佳的算法。盡管這對于某些實際應(yīng)用而言是一種合理的離線優(yōu)化方法，但是為每個待研究問題找到最佳參數(shù)的代價十分昂貴。在這種情況下，算法推薦系統(tǒng)應(yīng)運(yùn)而生。Kerschke等[81]構(gòu)建了一組具有代表性的高性能互補(bǔ)求解器，并提出了一種算法選擇模型。與單個最佳求解器相比，該算法選擇模型僅需要不到一半的資源就可以解決給定的問題。除此之外，Abell等[82]也基于公認(rèn)屬性及適應(yīng)度地形特征提出了一個算法選擇模型，并將BBOB問題集用于特定實例的算法配置模型中。實驗證明，該模型能夠在特征計算過程中為未知實例選擇最快的求解器。另外，Bisichl等[83]將算法選擇任務(wù)視為基于探索性景觀分析的成本敏感的分類任務(wù)，通過對可行集上的函數(shù)進(jìn)行系統(tǒng)采樣獲得的低級特征來預(yù)測給定組合中性能良好的算法。

3 問題與展望

3.1 問題

雖然進(jìn)化計算在適應(yīng)度地形特征分析方面取得了很多成果，但是由于待優(yōu)化問題的復(fù)雜性，目前現(xiàn)有的算法及方法在實例生成問題、高維問題、特征提取、算法配置、知識運(yùn)用等方面仍存在不足，距離廣泛的工業(yè)應(yīng)用存在明顯的差距，尚有許多研究工作有待深入開展。

3.1.1 演化生成問題及實例 與可以自動綜合數(shù)據(jù)集的組合優(yōu)化問題不同[84-85]，連續(xù)優(yōu)化問題通常由難以任意生成的復(fù)雜函數(shù)表示，這些函數(shù)的適應(yīng)度值易于獲得并且可以直接反映問題的特征。由于實驗中缺少現(xiàn)實世界中的連續(xù)優(yōu)化問題，因此為了提供一種更系統(tǒng)的方法來對基于采樣的優(yōu)化啟發(fā)式方法進(jìn)行測試，研究者們將多種基準(zhǔn)測試函數(shù)集合在一起，例如，BBOB問題集[86]、COCO問題集[87]、WFG問題集[88]、CEC競賽問題集[89-90]等。但是，對于算法推薦與分類任務(wù)來說，這些函數(shù)集不足以評估元啟發(fā)式方法的性能，因此難以基于如此少量的樣本來訓(xùn)練有效的分類器。更重要的是，現(xiàn)有的基準(zhǔn)測試問題由數(shù)量有限的映射函數(shù)組成，這些函數(shù)無法為不同的元啟發(fā)法提供足夠多樣的困難度，從而產(chǎn)生效果不均衡的數(shù)據(jù)集，這對推薦模型的訓(xùn)練有害。

3.1.2 適應(yīng)度地形特征的維數(shù)災(zāi)難 形式上，函數(shù)f的適應(yīng)度可表示為一個三元數(shù)組L= (X,f,d)，其中X是適應(yīng)度函數(shù)f的候選解集，d是用于量化候選解之間相似度的距離度量。在連續(xù)優(yōu)化問題中，d通常是歐氏距離。這些元素構(gòu)成一個鄰域結(jié)構(gòu)Nr(x)∈X，其定義如下:

Xi∈Nr(x)?d(x,xi)≤r,

(1)

其中r是以xi為中心的超球面半徑。實驗研究表明，Nr的值與搜索算法的性能相關(guān)。此外，隨著維數(shù)D的增加，X的大小和Nr的體積也會增加，從而導(dǎo)致算法性能下降，這被稱為維數(shù)災(zāi)難。

由于連續(xù)優(yōu)化問題中函數(shù)的復(fù)雜性，大多數(shù)現(xiàn)有方法將它們視為黑盒問題并提取特征以表示適應(yīng)度地形特性。具體來說，許多決策向量是通過在問題的決策空間中進(jìn)行抽樣，并計算其目標(biāo)值，然后基于這些目標(biāo)值來計算各種特征。人們認(rèn)為算法的性能高度依賴于問題的情況[91]，因此這些與情況有關(guān)的特征可以在算法性能和問題難度之間架起橋梁。這個想法簡單明了且合理，但是它遭受了維數(shù)詛咒，由于實際問題僅允許進(jìn)行少量函數(shù)評估，因此對于復(fù)雜問題，計算的地形表征很可能不準(zhǔn)確。

3.1.3 特征提取方法與算法配置 隨著引入的復(fù)雜優(yōu)化算法的數(shù)量增加，從給定的算法組合中為待優(yōu)化問題選擇最佳算法已成為巨大的挑戰(zhàn)。事實上，沒有一個萬能的進(jìn)化算法適用于所有任務(wù)，為不同任務(wù)選擇最佳算法往往需要經(jīng)歷漫長而令人沮喪的練習(xí)[92]?；谶m應(yīng)度地形的特征提取方法為此打開了一個新思路。例如，Sallam等[93]設(shè)計了一種基于適應(yīng)度地形的自適應(yīng)算子選擇的DE算法，該算法同時使用了適應(yīng)度地形信息和種群歷史性能的度量，能夠從5個算子的集合中選擇最佳DE變異策略。此外，他們還提出了一個基于改進(jìn)的信息地形負(fù)向搜索特征的多目標(biāo)含約束差分進(jìn)化算法來分析目標(biāo)函數(shù)和約束地形，以便在進(jìn)化過程中更好地選擇算法的最佳進(jìn)化算子[94]。但是，單個特征只能提供有用地形描述的一部分信息，因此特征的提取與選擇在算法配置上的應(yīng)用具有很大的局限性。

3.2 展望

針對適應(yīng)度地形分析技術(shù)中存在的問題，我們擬從以下5個方面對未來進(jìn)化計算的發(fā)展方向及其在適應(yīng)度地形分析上的應(yīng)用進(jìn)行展望。

3.2.1 基于適應(yīng)度空間地形的測試函數(shù)集優(yōu)化設(shè)計 針對現(xiàn)存基準(zhǔn)函數(shù)集無法涵蓋優(yōu)化問題基本特性的缺陷，充分利用適應(yīng)度地形分析技術(shù)，進(jìn)行補(bǔ)充和優(yōu)化，建立更加完備的基準(zhǔn)測試函數(shù)集。近年來，帶有數(shù)據(jù)分析功能的墨爾本算法測試實例庫已提出了包含多種用于分析和可視化優(yōu)化問題(或問題集合)的實例空間的技術(shù)[95-97]。另外，Tian等[98]也設(shè)計了一種樹結(jié)構(gòu)來描述多元連續(xù)函數(shù)，利用樹結(jié)構(gòu)隨機(jī)生成海量函數(shù)的技術(shù)已取得初步成果。目前，對無約束靜態(tài)單目標(biāo)、多目標(biāo)測試函數(shù)集的設(shè)計比較成熟，而動態(tài)或約束條件下的函數(shù)生成還處于發(fā)展階段。因此，通過將復(fù)雜環(huán)境因素考慮在內(nèi)，針對測試問題中的高維、多目標(biāo)、強(qiáng)約束、多模態(tài)、動態(tài)等特點[99]，分析和驗證及改進(jìn)其合理性，進(jìn)一步補(bǔ)充設(shè)計基準(zhǔn)測試問題以及更加科學(xué)合理地優(yōu)化基準(zhǔn)測試問題集是一個值得深入研究的方向。

3.2.2 基于適應(yīng)度地形的高維特征選擇方法研究 適應(yīng)度地形特征選擇問題本質(zhì)上是組合優(yōu)化問題，隨著特征維數(shù)的增加會導(dǎo)致“維數(shù)災(zāi)難”。傳統(tǒng)的窮舉法容易陷入局部最優(yōu)，而進(jìn)化算法作為一種強(qiáng)大的全局搜索技術(shù)，已在數(shù)百個特征選擇問題上顯示出了較好的性能。例如，Sherrah等[100]首次將遺傳規(guī)劃算法用于特征選擇問題，采用廣義線性模型作為分類器來評價所選特征的適應(yīng)度。Hong等[101]使用一種二進(jìn)制向量表示每個個體，利用二進(jìn)制位將預(yù)先定義的小數(shù)轉(zhuǎn)換為整數(shù)來表明對應(yīng)的特征是否被選擇。這些算法都有效降低了高維數(shù)據(jù)集上搜索空間的維度。另外，對于高維特征，快速最近鄰搜索庫(fast library for approximate nearest neighbors，F(xiàn)LANN)也可以較好地解決這些問題[102]。它是一個對大數(shù)據(jù)集和高維特征進(jìn)行最近鄰搜索的算法集合，不但實現(xiàn)了一系列查找算法，還包含了一種自動選取最快算法的機(jī)制，通過進(jìn)化算法的作用實現(xiàn)了特征從高維到低維的有效映射。但是，算法的穩(wěn)定性不僅與適應(yīng)度值的差異相關(guān)，所選特征的一致性也會產(chǎn)生影響。因此，提出新的穩(wěn)定性強(qiáng)的搜索算法也是一項重要任務(wù)。

3.2.3 基于特征學(xué)習(xí)的自適應(yīng)智能優(yōu)化算法設(shè)計 當(dāng)將進(jìn)化算法應(yīng)用于優(yōu)化問題時，算法選擇和參數(shù)設(shè)置是兩個關(guān)鍵問題。如何訓(xùn)練基于適應(yīng)度地形特征的良好性能算法的選擇或模型配置是亟待解決的問題。雖然,目前已有不少研究人員設(shè)計了自適應(yīng)進(jìn)化算法。例如，郭一楠等[103-104]提出了基于進(jìn)化算子歷史信息的自適應(yīng)調(diào)整選擇機(jī)制和自適應(yīng)混合變異文化算法，來同時提高算法解決問題的收斂速度。Sallam等[93]通過在差分進(jìn)化算法的自適應(yīng)算子選擇機(jī)制中同時考慮適應(yīng)度地形信息和進(jìn)化算子的歷史性能，提出了一種新算法(LSAOS-DE)，以便在進(jìn)化過程中動態(tài)選擇最合適的差分進(jìn)化算子。但是，以上成果都沒有從根本上改變進(jìn)化算法的機(jī)理和設(shè)計具有本質(zhì)區(qū)別的新算法。另外，生產(chǎn)生活中的實際優(yōu)化問題，其最優(yōu)解和適應(yīng)度地形很難預(yù)先獲得，如何快速可靠地感知其適應(yīng)度地形的主要屬性特征來指導(dǎo)算法設(shè)計，具有重大需求和理論價值。因此，從問題性質(zhì)和種群數(shù)據(jù)入手，利用與進(jìn)化搜索緊密相關(guān)的地形特征(比如搜索性、對稱性)，建立基于學(xué)習(xí)的自適應(yīng)選擇機(jī)制，使得求解過程中能夠根據(jù)提取的問題特性來自動調(diào)節(jié)最佳的搜索算法和策略，并根據(jù)問題特征對算法進(jìn)行在線自適應(yīng)調(diào)整，完成針對實際優(yōu)化問題特性的優(yōu)化策略自主選擇和優(yōu)化算法的自動構(gòu)建，實現(xiàn)更加智能的新一代優(yōu)化算法是一個極具潛力的發(fā)展方向。

3.2.4 基于適應(yīng)度地形的多目標(biāo)方法研究 目前，單、多模態(tài)優(yōu)化中對單目標(biāo)的適應(yīng)度地形分析的研究很多，但是對多目標(biāo)的優(yōu)化還沒有引起重視。決策空間存在多個帕累托解集(Pareto set, PS)對應(yīng)目標(biāo)空間同一個帕累托前沿(Pareto front, PF)的問題被稱為多模態(tài)多目標(biāo)優(yōu)化問題。在該問題中，多個目標(biāo)之間經(jīng)常存在復(fù)雜的沖突性，某目標(biāo)性能的改善可能會引起其他多個目標(biāo)性能的降低，從而使多目標(biāo)Pareto最優(yōu)解集分析的難度隨目標(biāo)個數(shù)的增加而激增，因此急需對多目標(biāo)Pareto最優(yōu)解集尋求有效的技術(shù)手段。針對現(xiàn)有多模態(tài)多目標(biāo)研究的不足，Verel等[105]分析了多目標(biāo)組合搜索空間的屬性和目標(biāo)函數(shù)間的相關(guān)性，總結(jié)了基于主要適應(yīng)度地形特征的多目標(biāo)局部搜索算法設(shè)計指南。另外，Kerschke等[106]設(shè)計了一個基于特征的用于連續(xù)和約束優(yōu)化問題的R語言包(an R package for feature-based landscape analysis of continuous and constrained optimization problems，F(xiàn)LACCO)。通過這種方式，將來可以在相同條件下進(jìn)行地形分析以及自動算法選擇技術(shù)的研究。以上工作構(gòu)成了適應(yīng)度地形在多模態(tài)多目標(biāo)優(yōu)化研究的基礎(chǔ)。但是，基于適應(yīng)度地形的多目標(biāo)方法研究仍處于發(fā)展階段，而利用決策空間與目標(biāo)空間的結(jié)合可能從中獲得新的見解。比如，構(gòu)建可視化的尋優(yōu)過程可以輔助算法有效策略的設(shè)計及學(xué)習(xí)過程的開發(fā)[107]，檢測多目標(biāo)地形有意義的屬性[105]，以及利用適應(yīng)度地形分析技術(shù)設(shè)計更高效的多目標(biāo)進(jìn)化算法。

3.2.5 適應(yīng)度地形分析技術(shù)在約束問題上的應(yīng)用 現(xiàn)實中很多優(yōu)化問題都含有眾多的約束條件，使用傳統(tǒng)的確定性方法很難求解。近年來，已經(jīng)提出了許多進(jìn)化算法來解決約束優(yōu)化問題，但是在此類設(shè)計中尚未充分探索適應(yīng)度地形信息。適應(yīng)度地形分析是一項關(guān)鍵技術(shù)，這引起了人們對于解空間的極大關(guān)注。Malan等[108]提出了一個約束違反地形特征來分析受約束的連續(xù)搜索空間的性質(zhì)。Poursoltan等[109]設(shè)計了一種熵特征來量化約束問題適應(yīng)度地形的崎嶇性。但是，并沒有對不可行區(qū)域的適應(yīng)度空間地形進(jìn)行表征。因此，對約束問題可行區(qū)域的特征設(shè)計和不可行區(qū)域難度表征的研究是一個新方向。

4 結(jié)語

優(yōu)化問題包括待優(yōu)化的目標(biāo)函數(shù)，影響函數(shù)數(shù)值的變量，以及未知變量的一組約束。盡管優(yōu)化問題表述起來很簡單，但是考慮到現(xiàn)實世界中的諸多因素，優(yōu)化問題就變得復(fù)雜。適應(yīng)度地形分析技術(shù)可以使研究人員避開耗時的反復(fù)實驗方法來解決優(yōu)化問題，而將注意力集中在優(yōu)化問題本身。它不僅為我們提供了有用的指標(biāo)來指示優(yōu)化問題是否具有某些特性，還可以使研究人員提前確定哪些類別的優(yōu)化算法在當(dāng)前問題上表現(xiàn)更好，甚至可以預(yù)知特定算法的哪些參數(shù)配置將表現(xiàn)最佳。因此，適應(yīng)度地形分析技術(shù)擁有巨大的發(fā)展?jié)摿?，并有可能推動人工智能行業(yè)在學(xué)術(shù)界及產(chǎn)業(yè)界的進(jìn)一步發(fā)展。另外，優(yōu)化算法的目的是找到目標(biāo)函數(shù)最大或最小化的未知數(shù)的可行解，這對幫助適應(yīng)度地形分析技術(shù)解決優(yōu)化問題具有天然的優(yōu)勢。

因此，本文對進(jìn)化計算在適應(yīng)度地形中的研究做了較為全面的回顧，并對進(jìn)化計算的主要特點、分類、理論基礎(chǔ)和適應(yīng)度地形的定義、特性、現(xiàn)狀這兩大方面進(jìn)行了詳述。針對適應(yīng)度地形分析技術(shù)中演化生成問題及實例、特征維數(shù)災(zāi)難、特征提取方法及算法配置等突出問題，本文從測試函數(shù)集優(yōu)化設(shè)計、高維特征選擇方法研究、自適應(yīng)智能優(yōu)化算法設(shè)計、多目標(biāo)方法研究和適應(yīng)度地形分析技術(shù)在約束問題上的應(yīng)用這5個方面進(jìn)行了總結(jié)與展望。