1.4 適應度地形

1.4.1 適應度地形的基本概念

實際中的優化問題往往非常復雜，元啟發式算法在解決這些問題時取得了較好的效果，但是在解決某一特定問題時，選擇何種算法和如何進行參數設置給研究人員帶來了巨大挑戰。解決這一困境的方法是在確定算法前，利用適應度地形理論分析了解問題的特性，為算法設計提供先驗知識。對于多數優化問題，都存在一個適應度函數來反映問題所要解決的目標。適應度函數決定了問題潛在解的適應度值，并由此衡量解的優劣。

適應度地形的概念來源于生物學，最早由Wright在1932年提出^[22]，作為基因型和適應度值的一種映射關系?；蛐涂梢酝ㄟ^變異的方式變化到鄰近基因型，而適應度地形則自然地由每個基因型的適應度值組成。適應度地形的拓撲結構特征對于觀察解空間的動態演進具有重要意義，便于解釋隨著演進過程的推進，基因型的變化規律。另一方面，隨著算法的迭代，適應度地形表面的演進路徑也往往成為關注的重點，它由一系列連續生成的基因型組成，刻畫了種群中的基因型從低適應度值區域到高適應度值區域的演進過程。

適應度地形以適應度函數為基礎，它將解空間中的解按照某種鄰域方式排列，并由每個解的適應度值組成適應度地形。一般的適應度地形由三個元素確定：問題的解空間X，基于X的鄰域、最小距離或可達性定義，以及適應度函數f（x）：。按照規定的順序將解的適應度值表示成一維數組的形式，即得到適應度向量。將X中的解視為離散點，按照定義的順序排列作為橫坐標，適應度向量作為縱坐標繪制二維曲線，即得到適應度地形圖。這是以靜態適應度地形為例，其可以表示為：

式中，X為解空間；N（x）為鄰域結構，它決定了每個解x∈X的鄰域解；f（x）：為適應度函數，它決定了每個解的適應度值并以此衡量解的質量。

以鄰域結構相連接的解空間表達了“位置”的概念，而適應度值是從位置衍生出的正投影，表達了“海拔”或“高度”的概念，并為每個“位置”賦予了其最重要的特征。適應度值往往是一個單一的參數，但它有可能由多維高度值表征。

1.4.2 適應度地形的發展

適應度地形的相關理論在20世紀90年代才得到關注并發展，其發展過程如圖1-1所示。

圖1-1 適應度地形理論的發展過程

目前，適應度地形理論在地形拓撲結構、特征參數以及對算法設計的指導等方面取得了一些研究成果。針對不同的適應度地形特征建立相應的參數描述體系是適應度地形理論發展的一個主要方向。參數描述體系是對適應度地形進行定性和定量刻畫的一個基礎，它通過描述地形的形狀、崎嶇性、可演進性等性質，反映問題的困難程度等特征。由于優化問題可分為靜態優化問題和動態優化問題，因此參數描述體系也相應地分為靜態和動態兩類。相關研究的分類和指標如圖1-2所示，在后續章節中將進行詳細的介紹。

圖1-2 適應度地形的分類和指標

研究人員對于靜態適應度地形的研究起步較早，經過長時間的探索與改進，有關靜態適應度地形的評價參數已較為豐富，其研究過程主要分為以下幾個基本階段。在80年代后期到90年代中期，相關研究主要集中在地形崎嶇性的分析。地形崎嶇性是指地形的波動程度，它與局優解的數目和分布密切相關。衡量地形崎嶇性的評價參數較多，Weinberger^[23]提出了自相關函數和相關長度的概念，它通過隨機游走在地形中獲得一系列適應度值，然后計算這些值與一段距離之外的同樣數目的適應度值的相關性，相關性越小，地形越崎嶇。Lip-sitch^[24]提出了相關長度的另一種計算方式，簡化了自相關函數的計算。這些評價只能在地形統計各向同性的前提下使用。幾年后，Vassilev^[25]等人提出了第一熵和第二熵測量，他們通過計算與序列中崎嶇元素的概率分布有關的信息熵，獲得一個圖表來反映地形崎嶇性。此外，Hordijk^[26]另辟蹊徑，通過幅度譜反映地形的整體特征，利用傅里葉變換和拉普拉斯矩陣，將適應度地形分解為子地形，并獲得相關長度信息。

在同一時期，地形間的依賴性也引起了學者的廣泛關注。依賴性是指變量間的依賴程度，當優化問題中的各變量相互依賴時，就意味著不可能只通過獨立地調節一個變量獲得最優解。衡量依賴性的典型方法有依賴方差和按位依賴性。依賴方差是由Davidor提出的用于遺傳算法的評價參數^[27]，它通過一個字符串的適應度值的一系列線性計算，得到預測字符串值，該字符串的適應度值和預測值的方差就是依賴方差的大小。按位依賴是由Fonlupt等人提出的另一種衡量依賴性的方法^[28]，它按位比較基因型中每位為0和1時的適應度值的差值，計算這些差值的方差。

在90年代后期，一些學者投入到中性特征的研究中。中性是與崎嶇性相對應的一個特征，它表征了地形中解的適應度值相同或相近的某一區域，能揭示局優解的信息并暗示搜索算法成功的可能性。Reidys^[29]提出了一種基于離散空間的中性游走，它從起始點開始，尋找使總距離（距起始點的距離）增大的中性鄰居，直到不存在使總距離增加的中性鄰居，最終獲得中性游走的步數。該方法在邊緣相關性較大時會有較大的偏差，且需事先明確鄰域的定義，只能用于離散空間。Verel等人^[30]由局優網絡分析適應度地形的中性結構，但該方法需要通過枚舉獲得全部解空間。

2000年以后，可演進性成為適應度地形研究的主流?？裳葸M性是指能使搜索過程移動到更好區域的能力，這個更好的區域具有更好的適應度值。與其他評價指標不同，可演進性與算法相關，只有當明確特定搜索策略時才有意義。Smith等人提出了適應度可演進圖^[31]，它通過計算子代適應度值大于等于父代適應度值的概率、子代平均適應度值等一系列可演進性指標，獲得適應度值相同解的平均度量，并以此建立適應度可演進圖。適應度云^[32]是衡量可演進性的另一種方法，它將父代適應度值所對應的子代適應度值在演進圖中繪制出來，以此描述父代與子代適應度值之間的關系。Vanneschi^[33]等人在適應度云的基礎上又提出了負斜率系數，它將適應度云分成離散的幾部分，并定義線段作為相鄰部分的中心距，計算線段間的負斜率之和即可得到負斜率系數。此外，Lu等人提出了適應度概率云^[34]，基于個體的適應度值和逃脫率研究地形的可演進性，它改進了適應度云的不足，不依賴地形間相關性的變化。

除了以上提到的研究地形特征的方法外，還有其他一些地形評價參數。比如，欺騙性是地形的一種特征，它是指地形中存在誤導算法搜索的信息，并且與特定算法有關。Deb提出了在基因算法中衡量欺騙性的參數，即基因欺騙性^[35]，它將欺騙程度分為完全欺騙和部分欺騙，并給出了每種欺騙程度的定義和條件。該方法計算量不大，但只給出了充分條件，不滿足這些條件的地形也有可能具有欺騙性。全局地形結構是地形的另一特征^[36]，它是指由集中的局優解組成的全局盆地形狀。離差度量是衡量全局地形結構的一種方法，它通過計算采樣點中最好部分點之間的兩兩距離平均值，衡量采樣點之間的鄰近程度，進而反映地形特征。

以上評價參數衡量了地形各方面的特征，但均是針對靜態適應度地形提出的。自2013年以來，學者們將目光逐步投向了動態地形評價參數的研究，并獲得了一些研究成果。Rohlfshagen給出了動態適應度地形的基本定義與數學描述^[37]，并給出了動態中立性以及崎嶇性的基本描述。在評價指標方面，動態適應度距離相關是衡量搜索困難程度的一種方法^[38]，它首先計算每個變化周期內的適應度距離相關性，然后計算這些適應度距離相關性與初始地形的平均差值。平均最優適應度值通過計算最優解在連續變化周期內的平均變化差值，反映最優解適應度值的變化。

主要亞穩狀態間的平均距離由Tinós提出^[38]，它衡量了主要亞穩狀態在連續變化周期內的平均歐式距離。主要亞穩狀態是指搜索空間的收斂點，它的計算與算法有關，不同的優化算法具有不同的計算方式。與主要亞穩狀態有關的另一評價參數是達到亞穩狀態的平均時間百分比，它是指種群向量到達亞穩狀態的平均時間，即所需的進化代數。這兩種評價參數計算較為復雜，并且依賴于特定算法，不具有一般性。

綜上所述，目前的適應度地形參數大部分都是針對某一領域特定的靜態問題開展的研究，基于動態適應度地形分析的參數較少。如衡量崎嶇性的評價指標與動態適應度距離相關，在計算時需要最優解的先驗信息，且變量必須為二元正態分布。衡量依賴性的典型方法，如依賴方差和按位依賴性是針對遺傳算法提出的，不適用于其他算法。衡量中性的方法，如中性游走、局優網絡分析需要依賴鄰域距離的定義方式或需要解空間的全枚舉，限制了它們的使用范圍?？裳葸M性指標反映了算法產生更優子代的能力，只有明確了特定算法、特定操作算子后才有意義，并不能通過適應度地形直接反映問題特性。因此，適應度地形理論本身處于發展完善的過程，相應的特征參數、分析手段無法完全適用于各種問題的解空間特性分析。

適應度地形的研究為了解問題特性提供了一種手段，利用適應度地形的研究成果指導優化算法設計，成為目前和未來發展的主要趨勢。目前，在優化領域中已經出現了一些研究成果。Cotta^[39]用以調度規則為基礎的啟發式算法，發現產品調度問題的適應度地形存在大山谷和高原，局部最優解很多，進而說明初始化的重要性。華中科技大學高亮教授團隊針對靜態單目標車間調度問題開展了研究工作，文峰^[40]提出了一種基于Logistic模型的適應度地形研究方法。Lu^[41]針對單目標測試任務調度問題提出了基于編輯距離的適應度地形分析方法。Verel^[42]重點分析多目標組合優化算法的行為，提出一種考慮各目標函數間相關性的多目標地形。該研究考慮了問題的維度、非線性程度、目標個數、各目標Pareto前沿的相關性等因素。Fabre^[43]重點研究基于原始目標函數分解的多目標優化理論，并針對多目標優化提出相應的適應度地形理論和中立性分析方法。He^[44]提出利用適應度地形指導進化計算領域中標準測試函數的設計，并對適應度函數的難易程度進行了理論分析和評估方法研究。Bas-seur^[45]重點關注爬山組合優化問題，考慮了問題的大小、地形的崎嶇度和中立性等因素，同時提出一種預測機制幫助爬山算法快速進入最優狀態。Huang^[46]分析了基于認知無線電系統的多用戶OFDM（Orthogonal Frequeny Dirision Multiple Xing）系統資源分配問題的適應度地形，研究利用適應度地形的分析來指導算法中遺傳操作的選擇。Lu等^[47]將適應度地形分析引入到算法的參數控制，通過適應度地形調整所提出方法的參數，從而進一步提升算法求解測試任務調度問題的能力。