適應值曲面分析方法綜述

摘 要:適應值曲面分析是一種研究優化問題難度的方法，而優化問題難度研究則是進化算法研究的一個重要分支。本文簡要介紹了適應值曲面分析的五種方法及其近年來的研究進展，不僅包括適應度距離關聯測試法、關聯長度測試法、異位顯性差異和異位相關性測試法等三種常見的適應值曲面分析方法近年的研究進展之外，還包括空間關聯測試法和曲面自動機等兩種適應值曲面分析方法。

關鍵詞:空間關聯性;關聯長度;異位相關性

中圖分類號:O221.4 文獻標識碼:A 文章編號:1674-7712 (2012) 12-0141-02

一、引言

進化算法是智能優化算法的重要分支，但是其應用范圍不僅局限于優化領域，在圖像處理、人工智能、工業設計、自動控制等領域都有廣泛的應用。進化算法研究的一個重要分支，自上世紀八十年代起人們開始在進化計算框架下研究優化問題的難度，而適應值曲面分析則是其中的重要方法之一。適應值曲面是指將優化問題的所有可行解的適應值按照某種鄰域規則排列在一起形成的曲面。分析適應值曲面的特征有助于了解問題的難度，為進化算法的設計和改進提供依據。一般認為，適應值曲面的崎嶇程度與優化問題的難度正相關，大部分適應值曲面測試方法大多是從不同的角度描述適應值曲面的崎嶇程度。目前，國內對適應值曲面分析方法的資料較少且對缺乏對近期研究進展的跟進，因此本文簡要介紹了幾種適應值曲面分析方法，包括適應度距離關聯(Fitness Distance Correlation，FDC)測試法、空間關聯(Spatial Correlation，SC)測試法、曲面自動機(Landscape State Machine，LSM)、關聯長度(Correlation Length，CL)測試法、異位顯性差異(Epistasis Variance，EPV)和異位相關性(Epistasis Correlation，EPC)測試等六種適應值曲面分析方法。

二、適應度距離關聯測試方法

Jones和Forrest[1]的適應度距離關聯(Fitness Distance Correlation，FDC)測試法是較早出現的一種適應值曲面測試方法。這種方法通過測試適應值與距離之間的相關系數描述適應值曲面的特性。fdcp的計算公式:

其中，P表示在適應值曲面上進行的隨機取樣集合， 和 分別表示P的適應值均值和所有點到適應值最優點的距離均值。fdcp∈[-1，1]反映適應值的變化趨勢與適應值曲面的變化趨勢之間的關系，fdcp趨近于-1則與最優解距離越遠的點適應值越小;fdcp趨近于1則與最優解距離越遠的點適應值越大。求最小值問題，fdcp趨近于-1時難度較大，趨近于1時難度較小，求最大值問題的情況則相反。顯然，相同問題的fdcp值的差別僅存在于因樣本集P的選取所產生的誤差中，與fdcp的計算方法本身沒有任何關系。

三、關聯長度測試法

Weinberger[2]的關聯長度(Correlation Length，CL)測試法是通過隨機游走函數在適應值曲面上產生一個隨機游走序列{f(xt)}，通過對這個序列計算相關性相關長度，判斷適應值曲面的崎嶇程度。

適應值曲面上的鄰域規則是連接適應值曲面分析測試方法和進化算法之間的紐帶，若選取的鄰域規則與進化算子的作用方式越一致，則得到的結果與進化算法的性能表現越接近。適應度距離關聯測試法采用的較常見的歐氏距離，但是關聯長度測試法采用的是不確定性鄰域規則，其鄰域規則由隨機游走函數決定。Hauschild[3]等對適應值曲面上的鄰域規則做了比較深入的研究，提出兩種新的適應值曲面上的鄰域定義:固定劃分(Fixed Partition)鄰域和隨機劃分(Random Partition)鄰域，一個個體的固定劃分鄰域是其二進制編碼串的某個確定的子塊中反轉任意的二進制位可以產生的所有新二進制串組成的集合，隨機劃分鄰域是其二進制編碼串中隨機改變其中不超過x位能產生的所有新二進制串組成的集合。Borenstein[4]等提出信息曲面(Information Landscape)的概念實際上是對適應值曲面的一種改進，以使之能夠適應“探索利用平衡理論”等較新穎的優化算法理論研究成果。信息曲面包括三個參數(x， ，t)，其中x表示全部可行解組成的集合，?表示鄰域、距離、集合x的可到達性，t表示一個隨機信息映射，將x中兩個元素的相互關系映射到[0，1]區間內。

四、空間關聯分析法

Gibbs[5]等提出基于空間關聯的適應值曲面分析方法，計算空間關聯系數Rs(d)的公式如下:

其中，n表示在適應值曲面上隨機抽取的樣本數，i，j表示相應的樣本，d表示相應樣本之間的歐式距離，Wij，d表示權重函數，主要作用是體現算法的影響，可以根據需要靈活選取。

五、曲面自動機

Corne[6]等提出曲面自動機作為一種分析進化算法性能和適應值曲面特性的工具。曲面自動機是一種有限狀態自動機，若將全部可行解組成的集合用E表示，M表示某種算子，狀態轉移矩陣T中的元素tij表示在M作用下，狀態i?E跳轉到j?E的概率，曲面自動機也可以用狀態轉換圖表示。Rowe[7]等通過改進采樣方法提出基于模擬退火算法的曲面自動機。Knowles[8-9]認為曲面自動機作為一種進化算法參數自適應調整機制存在巨大的潛力，尤其是處理大量相似的優化問題時具有較高的價值，但是面臨的最大問題是如何為問題的適應值曲面建立精確的數學模型。

六、異位顯性差異和異位相關性測試

異位顯性差異分析方法是關注不同基因位或不同決策變量對適應值的影響以及它們之間的相互影響。Davidor，Reeves 和Forrest等人借鑒一個新的生物術語“異位顯性”:一種基因的表達受另一種非等位基因的抑制)，也稱“上位差異”或“基因關聯”，試圖測量不同問題的GA求解的困難程度。異位顯性描述不同基因的組合所構成的染色體的適應值，并不是單一基因對適應函數貢獻的線性累加，它綜合反映出適應值函數的非線性和不可分性等特點，在一定程度上可以反映GA搜索的困難程度。Naudts等提出在計算基因關聯方差前先標準化適應值函數(在Euclidean度量下)這樣就確保基因關聯方差數值在0與1之間。Naudts和Kallel對多種適應值曲面分析方法進行比較研究，提出準確值與估計值的概念，還對單調適應值函數的進行延伸，提出位導向函數(Sitewise Decidable Function)的概念。Kallel等對基于walsh變換的異位顯性分析方法的優劣進行詳細的說明，提出改進的適應度函數分解方法，還對孤立點、多峰、單峰的不同適應值曲面的細節特點進行詳細分析。Chan等研究實數編碼下的基因關聯測試方法，用方差分析法(Analysis of Variance，ANOVA)獲取適應值曲面的細節并與傳統基因關聯測試方法進行對比研究，并以此為依據提出一種改進的變異算子。

參考文獻:

[1]T.Jones，S.Forrest.Fitness distance correlation as a measure of problem difficulty for genetic algorithms [C].Proceedings of the 6th International Conference on Genetic Algorithms. San Mateo.Morgan Kaufmann，1995:184-192

[2]E.Weinberger.Correlated and uncorrelated fitness landscapes and how to tell the difference[J].Biological Cybernetics，1990，63(5):325-336

[3]M.Hauschild，M.Pelikan.Advanced neighborhoods and problem difficulty measures [C].Proceedings of the 13th annual conference on Genetic and evolutionary computation.Dublin，Ireland.ACM，2011:625-632

[4]Y.Borenstein，R.Poli.Information landscapes[C].Proceedings of the 2005 conference on Genetic and evolutionary computation.Washington DC，USA.ACM.2005:1515-1522

[5]M.S.Gibbs，H.R.Maier，G.C.Dandy.Relationship between problem characteristics and the optimal number of genetic algorithm generations[J].Engineering Optimization，2011，43(4):349-376

[6]D.Corne，M.Oates，D.Kell.Landscape state machines:Tools for evolutionary algorithm performance analyses and landscape/algorithm mapping，2003:187-198

[7]W.Rowe，D.Corne，J.Knowles，IEEE.Predicting stochastic search algorithm performance using Landscape State Machines[C].2006 IEEE Congress on Evolutionary Computation，Vols 1-6，2006:2929-2936

[8]J.Knowles.ParEGO:A hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems[J].IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION，2006，10(1):50-66

[9]J.Knowles.Closed-Loop Evolutionary Multiobjective Optimization[J].IEEE Computational Intelligence Magazine，2009，4(3):77-91