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

關(guān)鍵詞:空間關(guān)聯(lián)性;關(guān)聯(lián)長度;異位相關(guān)性

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

一、引言

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

二、適應(yīng)度距離關(guān)聯(lián)測試方法

Jones和Forrest[1]的適應(yīng)度距離關(guān)聯(lián)(Fitness Distance Correlation，F(xiàn)DC)測試法是較早出現(xiàn)的一種適應(yīng)值曲面測試方法。這種方法通過測試適應(yīng)值與距離之間的相關(guān)系數(shù)描述適應(yīng)值曲面的特性。fdcp的計(jì)算公式:

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

三、關(guān)聯(lián)長度測試法

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

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

四、空間關(guān)聯(lián)分析法

Gibbs[5]等提出基于空間關(guān)聯(lián)的適應(yīng)值曲面分析方法，計(jì)算空間關(guān)聯(lián)系數(shù)Rs(d)的公式如下:

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

五、曲面自動機(jī)

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

六、異位顯性差異和異位相關(guān)性測試

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

參考文獻(xiàn):

[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