2.3 適應度的相關性

20世紀90年代初，Weinberger首次提出了自相關函數（autocorrelation function）和相關長度（correlation length）這兩個指標，用于衡量適應度地形的崎嶇性^[3]，并且在后續的研究中得到廣泛應用。一般來說，在崎嶇的地形中，鄰域解的適應度相關性更小，因此獲得更長的后續搜索方向就難以確定。反之，當地形更加平坦，鄰域解的適應度相關性更大時，搜索方法就可以跟隨更長的搜索梯度信息。適應度的自相關函數就是這樣一個指標，用來衡量一次隨機游走過程所經過的鄰居解適應度的連續性。

如果隨機游走得到一組隨機解的適應度值是，相距s步的兩點之間的自相關函數定義如下

式中，E[f_t]為f_t的期望值；V[f_t]為f_t的方差。

這里的一步是指在適應度地形中從當前解移動到它的鄰域解。基于這個自相關函數，相關長度l可以定義為^[4]

式中，ρ（1）≠0。

這里相關長度便是步長s為1的特殊情況，可以直接反映地形的崎嶇程度。l的值越小，地形越崎嶇。如果通過統計分析發現適應度地形在所有方向上有著相同的拓撲特征，那么該指標就可以作為衡量問題困難程度的指標。

在后續的研究中，學者們提出了相關性分析的各種修正方法，如Manderick^[5]提出將自相關度和相關長度結合起來，可以用來評估與進化算子有關的相關系數，即

式中，F_i為第i代種群的適應度值的集合；Cov[F_i，F_i+s]為F_i與F_i+s之間的協方差；V[F_i]為方差。

另外，Hordijk^[6]使用Box和Jenkins的方法^[7]來拓展相關性分析。Weinberger在1990年^[3]使用自回歸（Auto Regressive，AR）模型統計分析在適應度地形上的隨機游走。但是，Hordijk的分析是基于自回歸滑動平均（Autoregressive Moving Average，ARMA）模型，并給出了自相關和一個更精確地描述時間序列的隨機模型。