2.2 NK地形

NK地形是由Kauffman最早提出的一種常用的地形模型，類似于一種基準地形生成器。因每個基因位點有A個可供選擇的等位基因，K個基因位點的不同組合決定了每個基因位點對適應(yīng)度值的貢獻，所以每個基因g∈R的適應(yīng)度值是每個基因位點貢獻的平均值^[4]，即

式中，N為基因模型中的基因位點數(shù)；K為與某基因位點有相互作用的基因位點數(shù)。

因此，K衡量了基因位點間上位相互作用的強度。隨著參數(shù)的變化，NK地形模型可以產(chǎn)生一系列崎嶇性不同的適應(yīng)度地形。當N相同而K增加時，地形由平滑的單峰地形變化為崎嶇的多峰地形，因此NK模型可以產(chǎn)生不同變化特征的地形，從而為模擬不同復(fù)雜度的問題空間和驗證地形評價參數(shù)提供可能，具有重要的實際意義。

當明確了NK地形的N、A、K的參數(shù)值后，還有必要定義N個基因位點中，K個基因位點具有相互作用。例如，在線性結(jié)構(gòu)的染色體中，對每個基因位點有相互作用的其他K個基因位點稱為該基因的鄰居，它們可能是隨機選擇的，或者是一些非隨機的空間分布^[1]。常用的三種鄰居定義方式如下：

1）相鄰鄰居：第i個基因位點的鄰居為依次相鄰的K個基因位點。其鄰居組記為V_i={i，i+1，…i+K}。

2）隨機鄰居：第i個基因位點的鄰居包括它本身以及在整個染色體中隨機選擇的其他K個基因位點。

3）塊狀鄰居：第i個基因位點的鄰居組定義如下：

給定N、A、K，以及每個基因位點的鄰居分布，則NK地形被確定，同時決定了地形特征。

NK模型能提供可調(diào)節(jié)崎嶇性的適應(yīng)度地形，因為參數(shù)K能控制地形的崎嶇程度。當K=0時，每個基因位點都是相互獨立的，因此由每個基因位點較好值組成的某個特定的基因序列就是適應(yīng)度地形中唯一的全局最優(yōu)解。適應(yīng)度地形的相關(guān)性衡量了解空間中一位變異體之間適應(yīng)度值的相似程度。每個長度為N的基因序列有N個一位變異鄰居，通過將任意一位基因換為與其對立的等位基因獲得。在K=0的地形中，由于一位變異只能使適應(yīng)度值改變1/N或更少，因此這類地形具有很強的相關(guān)性。而當K=N-1時，每個基因位的適應(yīng)度值貢獻依賴于其他序列中的所有其他基因位，因此把任意一位基因改變?yōu)榕c其對立的等位基因，都會使該位的適應(yīng)度貢獻值變?yōu)榱硪粋€隨機值。因此，和初始序列相比，任意一個一位變異鄰居的適應(yīng)度值是完全隨機的，這時的地形也是完全隨機的，這類隨機地形一般有很多局優(yōu)解，平均有2^N/N+1個。

假設(shè)每個基因位點只具有兩個等位基因。為每個基因位點分配一個適應(yīng)度貢獻值ω_i，ω_i∈（0，1），1≤i≤N，ω_i的值依賴于自身基因位點i和其他K<N個上位基因。由于每個基因位上的基因型可以為0或1，因此這（K+1）個基因位點有2^（K+1）個狀態(tài)組合來決定基因位點i對整個染色體適應(yīng)度的貢獻值。每個狀態(tài)組合的適應(yīng)度貢獻值是在均勻分布（0，1）中產(chǎn)生的獨立隨機變量，所有狀態(tài)組合的適應(yīng)度貢獻值就組成了第i個基因位點的適應(yīng)度表，每個基因位點都具有一個不同的、獨立產(chǎn)生的適應(yīng)度表。那么，給定任意的長度為N的基因序列，它的整體適應(yīng)度值W就可以由每個基因位點的適應(yīng)度貢獻值的均值給出，即。

總體來看，NK模型可以產(chǎn)生不同崎嶇度和相關(guān)性的隨機地形，可以用于模擬一些問題的解空間特性，并用于相關(guān)評價指標的檢驗。