- 智能優化技術:適應度地形理論及組合優化問題的應用
- 路輝 周容容 石津華 孫升杰編著
- 614字
- 2021-08-24 11:50:30
3.4 標準遺傳距離
遺傳距離是群體遺傳學的一個術語,用于估計群體間的基因差異。關于遺傳距離有多種定義,這里給出應用廣泛的奈氏標準遺傳距離[16]。
奈氏標準遺傳距離是根據二進制編碼的遺傳算法定義的。具體定義如下:考慮兩個種群X和Y,記xil=nil/M和yil=nil/M是X和Y中第l個等位基因的頻率,其中i=1,…,N,N是基因長度,在二進制編碼GA中l∈{1,2},nil是第l個等位基因的數量,M是種群大小。在種群X種隨機選擇兩個基因的概率是,在種群Y中的概率是
,兩個基因分別來自兩個種群的概率是jxyi=xi1yi1+xi2yi2,種群X和Y之間基因的標準同一化結果為
如果兩個種群有相同頻率的等位基因,那么Ii=1.0。如果它們沒有共同的等位基因,那么Ii=0.0。針對所有的基因位定義X與Y間的歸一化結果為
式中,,
,
。
種群X和Y之間的遺傳距離為
初始種群與最后一代種群之間的遺傳距離可以按如下方式計算
式中,T是最后一代的大小,Dt,t+1是第t和第t+1代種群之間的遺傳距離。
Katada等人在文獻[21]中將標準遺傳算法用于NK地形(包括梯田NK地形和擴展NK地形),從中獲得基因型數據,進而研究奈氏標準遺傳距離的崎嶇性,并重點關注崎嶇性度量。
Smith提出的測量指標[20]用于測量崎嶇性,因為它的適應性相關性可以表示為標量值。后代解的平均適應度,稱為Smith的Eb,即
式中,G(k)為具有適應度k的親本的后代集合;g為后代基因型;V(g)為適應度函數。
圖3-11給出Eb的示意圖,Eb的數值隨著k的增加而減小,其與中性無關,與變異算子的自相關函數成正比。
圖3-11 父代適應度值的子代適合值的示意圖