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的解空間更崎嶇。一般情況下，在崎嶇解空間的無向圖中，直線向右上角傾斜，而在平坦解空間的無向圖中，直線向右下角傾斜。