3.3 局部最优网络

在搜索空间中，研究局部最优解的分布对于理解在不同地形中搜索的难度有很大帮助，也可以指导高效搜索算法。例如，在许多组合优化问题的适应度地形中，局部最优解并不是随机分布的，相反，它们往往是集中在一个“中央地段”中（如果是最小化问题，则是大峡谷）。在许多组合优化的问题中，包括旅行商问题、流水车间调度，还有NK地形，都呈现出了全局凸的地形结构。

为了得到局部最优网络，文献[8]给出了相关的定义和算法。

1）中性邻居：一个解s的中性邻居指的是与之有相同的适应度值f（s）的邻居x，即

由式（3-2）可以看出，一个解的中性程度就是它的中性邻居的数量。如果有许多解的中性程度都很高，那么该适应度地形就是中性的。那么，该地形就可以被分解为拥有相同适应度值的几个子结构。当然，也允许适应度值之间有一定的差值，这样也认为是中性的。

2）中性网络：一个顶点拥有相同适应度值的连通子图，记作中性网络（Neutral Net-work，NN）。

通过位翻转变异算子，对于所有的解x和y，如果x∈V（y），那么y∈V（x）。在这种情况下，中性网络就与R（x，y）（当且仅当x∈V（y）且f（x）=f（y））是等价关系。为了描述方便，将此中性网络记作NN（s）。

3）局部最优解：一个局部最优解，是局部区域最大的解，即存在一个解s^∗，满足条件∀s∈V（s），f（s）≤f（s^∗）。

4）局部最优中性网络：如果中性网络的所有配置都是局部最优的，则该中性网络就是局部最优的。

可以使用随机爬山算法^[9]，提取局部最优中性网络中的吸引域。在算法中，随机选择一个具有最大适应度值的邻域解，接受适应度值相等或者更优的解。具体的步骤如下：算法3-2：随机爬山

选择一个初始解s∈S

repeat

1.从{Z∈V（s）f（Z）=max{f（x）x∈V（s）}}中随机选择一个解s′；

2.iff（s）≤f（s′）then

s←s′

end if

untils在一个局部最优中性网络中

由于适应度地形的大小是有限的，可以将局部最优中性网络记作NN₁，NN₂，NN₃…NN_n，这些局部最优中性网络是局部最优网络的端点。因此，在这样的情况下，就形成了一个固有网络，其节点本身就是网络。对于每个解s，都有一个概率h（s）∈NN_i，并且将概率P（h（s）∈NN_i）记作p_i（s），对于每个s∈S的解，满足。

在非中性适应度地形中，其中每个中性网络的大小是1，对于每个解s，只有一个中性网络（实际上是一个解）NN_i，使得p_i（s）=1使得p_i（s）=1。

在这种情况下，局部最优中性网络i的吸引域是集合b_i={s∈S｜p_i（s）>0}，但是这个定义不能直接在中性适应度地形中使用，需要按照以下方式扩展该定义^[8]。

5）吸引域：局部最优中性网络i的吸引域是集合b_i={s∈S｜p_i（s）>0}。吸引域的大小即为。

6）局部最优网络：局部最优网络G=（N，E）是一个图，它的节点都是局部最优解NN，而且当两个解s_i∈b_i且s_j∈b_j满足s_i∈V（s_j）时，节点NN_i和NN_j之间就存在一条连接的边。

7）边的权重：对于非中性地形的每个解s和s′，将s′是s邻居的概率记作p（s→s′）。那么，对于s∈S有一个邻域解在吸引域b_j中的概率就应该为

从吸引域b_i移动到吸引域b_j的总概率是所有s∈b_i到s′∈b_j的转移概率的平均值。

#b_i是吸引域b_i的大小。

图3-1给出了加权局部最优网络的示意图。其中，圆形表示局部最优盆地（直径表示盆地大小），加权边表示转移的概率。

对于中性地形，定义解s属于盆地i的概率p_i（s）。因此，需要对下面两个公式做一定的调整。

其中，#b_i是吸引域b_i的大小。

图3-1加权局部最优网络示意图NK地形（N=6，K=2）

8）加权局部最优网络：在一个局部最优中性网络，如果两个节点i和j之间的p（b_i→b_j）>0，那么这条边e_ij∈E就加了权重w_ij=p（b_i→b_j）。这是一个有向图，w_ij与w_ji是两个不同的值。

通过随机爬山算法获得了局部最优中性网络，需要对该网络进行一定的评估，才能达到分析问题、指导算法的目的。以下评估方法从不同的角度对网络特征进行了分析。

Verel等人^[8]利用NK地形开展分析工作，采用不同的参数组合进行相应的实验，从而得出了一些非常有意义的结论。在他们的实验中，将N设置为其最大的可能值。他们分别探讨了标准的网络特性、吸引域和高级网络特性的三种情况。

1.标准的网络特性

对于标准的网络特性，主要探讨节点、边缘的数量以及边缘的权重分布。标准网络特性与相应地形的搜索难度有关，它们既反映了盆地的数量，又反映了探索地形的能力。

在不同的实验条件下得到的数值不同，在图3-2给出节点数量与K之间的示意图，没有具体数值意义，具体的曲线形状和参数取值、地形类型有关。从节点数量来看，节点数量随着参数K的增加而快速增加。对于给定的N和K，标准NK地形总是比相应的中性地形具有更多的节点。由于非中性地形中适应度地形改变的概率要比中性地形中的高，所以对于给定的K，节点的数量随着中性的增加而减少。在其他条件相同的情况下，节点数量越多，搜索将越困难。一般情况下，随着K的增加，搜索更加困难，并且对于给定的K，在中性低的情况下，搜索将更加困难。也就是说，对于较低的K值和高中性，搜索可能会更加容易。

从边的数量来看，边的数量随着K的增加而增长。一般情况下，对于NK地形边数随着所有K的中性增加而减小，当然也存在边数随着中性增加而增加的情况。需要说明的是，具体的曲线形状和参数取值、地形类型有关。图3-3仅为示意图，不代表具体某一参数下的实验结果。

图3-2 节点数示意图

图3-3 边的数量示意图

从权重分布来看，加权网络的权重特征包括每条边的权重w以及权重分布的平均值。对于任意一个节点i，来自i的权重和为1。Verel等人重点关注了自连边的权重w_ii和节点强度s_i（s_i=∑_j∈_V（i）\{i}w_ij），并且w_ii+s_i=1。节点强度代表了节点的连通性。图3-4给出了权重的示意图。网络中所有节点上的权重w_ii的平均值（可以认为是从盆地中一种结构的突变进行爬山算法之后保持在同一盆地中的概率）。可以看出，跳入另一个盆地的可能性远小于在同一盆地中走动的概率。权重w_ii随着K的增加而减小，这也是标准NK地形所遵循的趋势。

图3-4 权重的示意图

关于中性的趋势更加复杂，一般情况下，对于固定的K，保持在同一盆地的平均权重随着中性的增加而降低。相反，也存在保持在同一盆地的平均权重随着中性而增加的情况。中性增加了给定结构逃离其盆地并到达另一个盆地的可能性，但中性也增加了当前结构所连接盆地的数量。

2.吸引域

对于启发式搜索算法来说，吸引域和局部最优网络同样重要。同时，吸引域的某些特征可能和局部最优网络特征有关。对于吸引域，Verel等人分别分析了给定大小的吸引域数量、局部最优解的适应度值和全局最优的吸引域大小。

对于给定大小的吸引域数量来说，主要观测所研究地形中吸引域尺寸的平均值和方差。图3-5给出均值和方差变化曲线的示意图。吸引域的大小随着K的增加而呈指数下降。当地形的中性特征减少时，吸引域的大小也会减少。方差同样随着K的增加而呈指数下降，并且在中性下降时也会下降。

图3-5 吸引域大小的平均值和方差示意图

Verel等人还通过将吸引域的尺寸的某些分布利用对数正态分布进行拟合。对数正态分布意味着大多数盆地的大小接近平均值，并且几乎没有大于平均尺寸的盆地，这可能与潜在地形的搜索难度有关。

对于局部最优解的适应度值来说，一般用吸引域大小与其适应度值之间的相关性进行刻画。正值较大的相关系数意味着较大的吸引域具有较高的适应值，所以一般会更关注较大尺寸的吸引域。因为吸引域尺寸之间的大小差异随着基因关联的增加而减少，所以随着崎岖度的增加，找到具有更高适应性的盆地的难度也增加。就中性而言，全局最大盆地的规模随着中性的增加而增大。图3-6给出相关性的示意图。

对于全局最优的吸引域大小来说，其关注的是具有全局最优值的吸引域的平均大小。随着K的减小，全局最优的吸引域尺寸也减少。就中性而言，全局最大吸引域的规模随着中性的增加而增大。图3-7给出全局最优值的吸引域尺寸平均值的示意图。

图3-6 相关性示意图

图3-7 全局最优值的吸引域尺寸平均值的示意图

3.高级网络特性

高级网络特性主要包括加权聚类系数、节点之间的平均路径长度以及差异系数三个方面。

对于加权聚类系数，Verel等人考虑到标准的聚类系数没有考虑加权的边值，结合拓扑信息和网络权值分布的加权聚类系数。

式中，s_i=∑_j≠iw_ij，如果w_nm>0，那么a_nm=1，如果w_nm=0，那么a_nm=0，并且k_i=∑_j≠ka_ij。

对于在顶点i附近形成的每个三元组，c^w（i）计算顶点i的两个参与边缘的权重。c^w被定义为网络所有顶点上平均的加权聚类系数。

图3-8给出加权聚类系数平均值的示意图。对于NK地形，加权聚类系数随着基因关联程度而降低，并随着中性程度而增加。随着基因关联的增加，聚类系数的降低与标准NK地形的结果一致。对于高度基因关联和低中性的情况，相邻吸引与之间的过渡较少，或者过渡发生的可能性较小。

图3-8 加权聚类系数平均值的示意图

对于差异系数来说，其主要衡量节点i对于总权重贡献的差异值，具体定义如下：

图3-9给出差异系数的示意图，对于低K值，高度中性增加了平均差异。当基因关联高且无论中性程度如何，盆地更均匀地连通，因此我们可以将局部最优网络描绘为更“随机”，即更均匀，这对于地形的搜索难度有潜在的影响。

对于最短路径来说，两个节点之间的距离定义为d_ij=1/w_ij，那么两个节点之间路径的长度就表示为连接各自吸引域边的距离之和。整个网络的平均路径长度是所有可能的最短路径的平均值。

图3-10给出最短路径的示意图，一般情况下，无论地形家族和中立水平如何，基因关联对结果具有相同的影响。即使中性很高，吸引域也会更远，地形的一些结构差异可以由局部最优网络捕获。

图3-9 差异系数的示意图

图3-10 最短路径的示意图