2.6 尖锐性

本书直接从适应度地形的时域角度出发，通过新序列生成、类别统计、有向图绘制等步骤，利用有向图及其中的坐标值定量描述地形尖锐性[^12]。其主要过程如下：

1）当被比较的两个问题规模不同时，将解空间较大的称为大规模问题，解空间较小的称为小规模问题。将大规模问题的适应度地形分成若干段，每段中的解的个数与小规模问题的解个数相同。

2）用整数序列{1，-1，0}^N-1代替原适应度地形。比较两个相邻解的适应度值的大小。如果前项大于后项，用1代替两者，如果前项小于后项，用-1代替两者；如果两个解的适应度值相等，则用0代替两者。通过这种方法，获得一个新的数据序列。

3）绘制散点图，横坐标为1～5。从前到后遍历新数据序列，如果0连续出现，则计算连0数并记为a_i，i代表该情况出现的次数。以累计方式在横坐标为1处标定这些a_i值，作为纵坐标。如果1或-1连续出现，则计算1或-1连续出现的次数，记为c_i和d_i，并分别在横坐标为3和4的位置标定这些值。如果1和-1交替出现，计算±1交替出现的次数并记为e_i，以累计方式在横坐标为5处记录这些值。如果出现其他情况，则用b_i记录出现次数并标定在横坐标为2处。

4）根据标定点的出现次序依次连接它们得到无向图，并将a_i，b_i，c_i，d_i，e_i最后的累计值记为a_sum、b_sum、c_sum、d_sum、e_sum。

5）根据每种情况对尖锐性的贡献，为a_sum、b_sum、c_sum、d_sum、e_sum分配权重，并最终得到尖锐性为

权重的分配是根据经验值获得的，可以稍作调整以达到更好的效果。尖锐性值越大，地形越尖锐，从而反映地形的崎岖性。

为了便于理解，下面来看两个例子^[13]。假设示例1的解空间具有32个解，并且这些解的适应度值构成如下的适应度值向量[6 3 4 6 8 5 5 5 6 4 7 7 6 4 3 5 2 6 3 9 5 6 10 10 10 10 5 7 4 9 1 2 1 2]，示例1的解空间如图2-4a所示。然后，根据步骤1）到5）计算这个解空间的尖锐性。

1）忽略步骤1，因为只有一个解空间，并且它是小规模的。

2）从解空间中的第一个解开始，3小于6，所以它们被-1代替，4大于3，所以它们被1代替。其余部分可以以相同的方式完成，并且新的数组是[-1 1 1 1 -1 0 0 1 -1 1 0 -1 -1 -1 1 -1 1 -1 1 -1 1 1 0 0 0 -1 1 -1 1 1 0]。

3）前两个数字属于1和-1交替出现的情况，所以e₁=2-1+1=2，第二至第四个数字属于1连续出现的情况，所以c₁=4-2+1=3，第四和第五个数字也属于1和-1交替出现的情况，所以e₂=5-4+1=2。剩下的也可以用同样的方法完成，然后我们可以得到其他值：b₁=2，b₂=2，e₃=3，b₃=3，d₁=3，e₄=8，c₂=2，b₄=2，a₂=3，b₅=2，e₅=4，c₃=2，b₆=2。将这些点标记在散点图的相应位置。

4）根据出现的顺序将散点连接起来，就可以得到：a_sum=a₁+a₂=5，b_sum=b₁+b₂+b₃+b₄+b₅+b₆=13，c_sum=c₁+c₂+c₃=7，d_sum=d₁=3，e_sum=e₁+e₂+e₃+e₄+e₅=19。无向图如图2-5a所示。

5）最后计算尖锐性：kee_td1=5×（-1）+13×（-0.6）+7×（-0.2）+3×（-0.2）+19×1=4.2。

假设示例2的解空间有32个解，并且这些解的适应度值构成如下的适应度值向量[6 6 6 6 8 5 5 5 6 4 7 7 6 4 5 5 5 5 5 5 5 6 10 10 10 10 5 7 4 9 9 9]，示例2的解空间如图2-4b所示，尖锐性为kee_td2=-17.2，对应的无向图如图2-5b所示。

图2-4 不同示例的解空间

图2-5 不同示例的无向图

从仿真结果可以看出kee₁>kee₂，所以示例1的解空间比示例2的解空间更崎岖。一般情况下，在崎岖解空间的无向图中，直线向右上角倾斜，而在平坦解空间的无向图中，直线向右下角倾斜。