第2章 崎嶇性

2.1 定義

崎嶇性是衡量適應度地形中局部最優解的數量和分布的一種方式，其與適應度值整體的變化程度有關^[1]。如果一個優化問題解空間的適應度值變化劇烈，換句話說，鄰域解的適應度值與解本身的適應度值差異性很大，那么該優化問題的地形就可以被看成是崎嶇的。與此相對應，如果一個優化問題解空間的適應度地形只有一個盆地/山峰，或者是沒有任何特征的平原區域，那么該優化問題的適應度地形就不能被看成是崎嶇的，或者說可以被看成是平坦的。從崎嶇性的特性可以看出，如果一個優化問題的適應度地形是崎嶇的，那么設計該優化問題的搜索算法時需要更加關注其跳出局部最優解的能力。圖2-1給出四種不同崎嶇程度的適應度地形，對于不同崎嶇程度的適應度地形，其相應搜索策略的關注點不同，這也是適應度地形特征為優化算法設計提供指導性的意義所在。

圖2-1 不同崎嶇程度的適應度地形

在定性理解崎嶇性概念的同時，如何定量定義和刻畫地形的崎嶇性，是一個值得關注的問題。Kauffman在研究過程中提出了NK地形模型^[2]，該模型作為一種基準地形產生器，對于適應度地形的研究發揮了非常重要的作用，很多研究工作都是在NK地形的基礎上開展的。在研究崎嶇性時，可以通過調節NK地形的參數控制地形的崎嶇性，進而生成具有不同崎嶇程度的地形，為研究相應的崎嶇性評價指標提供驗證基準。相關性分析作為適應度地形分析的一種經典方法，從自相關分析^[3]和距離相關性分析^[8]的角度入手，分別從不同的角度反映了適應度地形的崎嶇性。自相關分析側重于從采樣解的適應度值之間的關系入手，距離相關性考量的是當前解與全局最優解之間的關系。另外，Vassilev等人基于信息熵提出了評價問題適應度地形崎嶇性的分析方法，該方法從采樣解中提出包含的信息量，可以同時探討地形的平坦性、崎嶇性和中性等多個特征^[11]。本書作者從適應度地形的時域分析角度出發，利用有向圖及其中的坐標值定量描述地形的尖銳性，側面反映地形的崎嶇性。