2.2 NK地形

NK地形是由Kauffman最早提出的一种常用的地形模型，类似于一种基准地形生成器。因每个基因位点有A个可供选择的等位基因，K个基因位点的不同组合决定了每个基因位点对适应度值的贡献，所以每个基因g∈R的适应度值是每个基因位点贡献的平均值^[4]，即

式中，N为基因模型中的基因位点数；K为与某基因位点有相互作用的基因位点数。

因此，K衡量了基因位点间上位相互作用的强度。随着参数的变化，NK地形模型可以产生一系列崎岖性不同的适应度地形。当N相同而K增加时，地形由平滑的单峰地形变化为崎岖的多峰地形，因此NK模型可以产生不同变化特征的地形，从而为模拟不同复杂度的问题空间和验证地形评价参数提供可能，具有重要的实际意义。

当明确了NK地形的N、A、K的参数值后，还有必要定义N个基因位点中，K个基因位点具有相互作用。例如，在线性结构的染色体中，对每个基因位点有相互作用的其他K个基因位点称为该基因的邻居，它们可能是随机选择的，或者是一些非随机的空间分布^[1]。常用的三种邻居定义方式如下：

1）相邻邻居：第i个基因位点的邻居为依次相邻的K个基因位点。其邻居组记为V_i={i，i+1，…i+K}。

2）随机邻居：第i个基因位点的邻居包括它本身以及在整个染色体中随机选择的其他K个基因位点。

3）块状邻居：第i个基因位点的邻居组定义如下：

给定N、A、K，以及每个基因位点的邻居分布，则NK地形被确定，同时决定了地形特征。

NK模型能提供可调节崎岖性的适应度地形，因为参数K能控制地形的崎岖程度。当K=0时，每个基因位点都是相互独立的，因此由每个基因位点较好值组成的某个特定的基因序列就是适应度地形中唯一的全局最优解。适应度地形的相关性衡量了解空间中一位变异体之间适应度值的相似程度。每个长度为N的基因序列有N个一位变异邻居，通过将任意一位基因换为与其对立的等位基因获得。在K=0的地形中，由于一位变异只能使适应度值改变1/N或更少，因此这类地形具有很强的相关性。而当K=N-1时，每个基因位的适应度值贡献依赖于其他序列中的所有其他基因位，因此把任意一位基因改变为与其对立的等位基因，都会使该位的适应度贡献值变为另一个随机值。因此，和初始序列相比，任意一个一位变异邻居的适应度值是完全随机的，这时的地形也是完全随机的，这类随机地形一般有很多局优解，平均有2^N/N+1个。

假设每个基因位点只具有两个等位基因。为每个基因位点分配一个适应度贡献值ω_i，ω_i∈（0，1），1≤i≤N，ω_i的值依赖于自身基因位点i和其他K<N个上位基因。由于每个基因位上的基因型可以为0或1，因此这（K+1）个基因位点有2^（K+1）个状态组合来决定基因位点i对整个染色体适应度的贡献值。每个状态组合的适应度贡献值是在均匀分布（0，1）中产生的独立随机变量，所有状态组合的适应度贡献值就组成了第i个基因位点的适应度表，每个基因位点都具有一个不同的、独立产生的适应度表。那么，给定任意的长度为N的基因序列，它的整体适应度值W就可以由每个基因位点的适应度贡献值的均值给出，即。

总体来看，NK模型可以产生不同崎岖度和相关性的随机地形，可以用于模拟一些问题的解空间特性，并用于相关评价指标的检验。