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）模型，并给出了自相关和一个更精确地描述时间序列的随机模型。