基于二倍體顯性機制的DNA算法研究

徐 凱，陳賢富

(中國科學技術大學 電子科學與技術系，安徽 合肥 230027))

0 引言

生物學中，二倍體是指含有兩個同源基因組的個體[1]。根據孟德爾分離定律可知，當兩個同源基因組其中之一為顯性時，該基因對應的性狀表現為顯性。僅當兩個同源基因組均為隱性時，表現型為隱性，如圖1[1]所示。基因重組是保持生物特性世代遺傳的基本方式，也是獲取大量遺傳變異的主要源泉。遺傳算法[2]中的交叉操作可視為對生物遺傳過程中基因重組的直接模擬，交叉算子選擇得好壞直接影響算法的性能。對于占主流的二值編碼(0/1編碼)方法來說，目前最常用的交叉方法主要有以下兩類：

(1)一點交叉、兩點交叉與多點交叉[1,3-4]

一點交叉(one-point crossover)又叫簡單交叉。具體操作是：在個體串中隨機設定一個交叉點，實行交叉時，該點前或后的兩個個體的部分結構進行互換，并生成兩個新個體。

圖1 孟德爾分離定律

兩點交叉(two-point crossover)方法與一點交叉類似，只是多設置了1個交叉點，交叉時，A、B兩個體中位于這兩個交叉點之間的碼串相互交換，其余碼串不變。

多點交叉(multi-point crossover) 是前述兩種交叉的推廣，有時又被稱為廣義交叉(generalized crossover)，一點交叉和兩點交叉可視為多點交叉的特殊形式。

(2)一致交叉[2]

所謂一致交叉(uniform crossover)是指通過設定屏蔽字(mask)來決定子個體的哪些基因繼承父本A 中的對應基因，哪些基因繼承父本B 中的對應基因。一般來說，點數較多的交叉操作可提供更加豐富的遺傳變異材料，有利于維護種群基因型的多樣性，但對關鍵模式的保護能力較差，收斂的速度也較慢。從模式(schemata)處理角度看，一點、兩點及多點交叉方法存在著“位置相關”的缺陷。在此情況下，短模長模式比長模長模式有更大的存活概率，而對于很多應用問題，因領域知識較少，基因間的關系密切程度不易確定，人為的基因編碼排列方案可能極不合理，這將影響多點交叉操作的效果和GA搜索的效率。

與多點交叉方法相比，一致交叉由于平等對待所有的模式，因而克服了多點交叉方法存在的“位置相關”缺陷，但在種群基因型相似性較高的情況下，由于隨機交換發生在相同基因座之間的概率較高，故存在優化后期階段進化遲鈍、搜索效率欠佳的缺陷。

針對上述問題，參照生物DNA遺傳機制機理，提出并研究設計了一類擬合生物遺傳二倍體顯性機制的新型DNA遺傳算法。

1 二倍體顯性遺傳算子

一點交叉、多點交叉及一致交叉方法的共同之處在于均繼承了兩父串的相同基因，差異僅在于對父串不同基因的處理方式。二倍體顯性遺傳算子也可以繼承親本同型等位基因，而對雜型等位基因則按“與”和“或”邏輯分別進行處理。例如，若兩父串為：

F1: 0100101101

F2: 1101110100

則由“與/或”交叉方法產生的兩子串分別為：

C1: 0100100100

C2: 1101111101

顯然，這一遺傳操作方法使子代繼承了雙親的同型基因；對于雙親的雜型基因，“與/或”交叉方法采取了兩種不同的“強調”策略：“與”運算強調0基因的作用，而“或”運算則強調1基因 的作用。這種交叉方法較為逼真地模擬了生物DNA遺傳的顯性(dominance)機制，“與”運算將1視為隱性基因，而“或”運算將0視為隱性基因。

2 二倍體顯性遺傳計算模式分析

為便于對AO交叉方法進行模式分析，這里參照Holland模式分析方法，先定義幾個有關基因型模式的概念。

定義1：0_模式由字符集{*0*}構成的字符串稱作0_模式，記為H0。其中，字符0為反映模式結構特征的確定性信息，*為反映模式結構特征的不確定性信息。

定義2：1_模式由字符集{*1*}構成的字符串稱作1_模式，記為H1。其中，字符1為反映模式結構特征的確定性信息，*為反映模式結構特征的不確定性信息。

有了這些定義，再參考 Holland模式分析方法[1,3-4]，不難得出二倍體顯性遺傳計算在模式形成和增長方面具有如下特性：

(1)1階優模式的數目(數學期望)在連續后代中按式(1)增長：

(1)

(2)高于種群的平均適應度的1階0_模式在連續后代中按式(2)增長：

(2)

(3)高于種群的平均適應度的1階1_模式在連續后代中按式(3)增長：

(3)

很明顯，與 Holland標準GA相比，基于二倍體顯性機制的DNA遺傳計算(AO交叉)對于適應度高于種群平均適應度的0_模式和1_模式有較強的保護能力。而對于0、1混雜的一般模式，AO交叉方法對模式H的破壞作用除了與變異概率以及模階的高低相關外，還與模式H中的0和1個數之比相關。當模式H中0和1個數相等時，AO交叉對模式H的破壞作用最大。

模式H中0和1在數目上相差越大，AO交叉對模式H的破壞作用越小；當模式H中的確定信息位全為0或全為1時，AO交叉對模式H無破壞作用。由此不難推測AO交叉操作在搜索、優化應用中可能具有如下特點：

(1)當問題全局最優解的基因編碼為全0或全1時，由于AO交叉對0_模式和1_模式無破壞作用，因此，采用AO交叉的GA可能會以相當高的速度搜索到問題的全局最優解。

(2)當問題全局最優解的基因編碼0、1個數在數量比上相差很大時，由于AO交叉對這類0、1混雜優模式破壞作用較小，因此，與一點交叉等方法相比，采用AO交叉的GA可能會以相對較快的速度搜索到問題的全局最優解。

(3)當問題全局最優解的基因編碼0、1個數在數量比上相差不大直至相等時，由于AO交叉對這類0、1混雜優模式破壞作用較大，此時，采用AO交叉的GA的收斂可能比較慢，甚至不及一點交叉或一致交叉等方法。

3 遺傳優化實驗

為了檢驗AO交叉方法的優化性能，本文選擇了易于采用 0/1二值編碼方案的典型優化問題進行實驗，即Bohachevsky函數優化問題。

實驗環境為：Inter(R) Core(TM) i5-7300U CPU @2.6 GHz 2.71 GHz筆記本電腦，Windows 10，Visio Studio 2010。

Bohachevsky函數[5-7]為：

F(x1,x2)=x12+2x22-0.3cos(3πx1)-0.4cos(4πx2)+0.7

x1，x2∈[-1,1]

(4)

優化目標為求Bohachevsky函數的全局最小值。由數學分析方法可知Bohachevsky函數的最小值為0，發生在(0,0)點。該函數三維形狀如圖2所示。

圖2 函數F的三維空間圖

實驗目的在于檢測AO交叉方法的性能，選用一點交叉作為比較對象，GA的配種選擇機制采用正比于適應度的賭輪隨機選擇方式。為了與AO交叉法的邏輯操作形式相一致，這里的變異操作采用“異或/異或非”方式，其效果等同于位點變異方法。實驗中的變異概率為0.05，交叉概率為1.00，種群規模為400，種群更新方式采用最佳保留方式。采用二進制編碼方式，實驗結果如表1所示，表中列出的優化時間為20次實驗的平均值。

表1 Bohachevsky函數GA優化實驗結果

從實驗結果可以看出各種不同的交叉算子在Bohachevsky函數優化中均能搜索到全局最優解但優化效率有差異。AO 交叉操作方法在優化效率方面明顯高于一點交叉方法。根據前文對AO交叉方法的分析，AO交叉的優化性能可能還與問題最優解的編碼特性(0和1的數量比)相關。為此，本文通過設置最小極值點發生的位置來改變取得最優解時自變量編碼的0和1的個數。為檢測最優解的編碼特性對AO交叉法優化性能的影響，令：

x1=y1-m

(5)

x2=y2-m

(6)

這樣，如果針對自變量y1、y2進行遺傳優化，則Bohachevsky函數的最小極值點發生在(m,m)。實驗中，y1、y2的編碼方式為二進制編碼方式，位長均為30位。適應度函數設計為：

f(x1,x2)=1/(F(x1,x2)0.000 001)

(7)

為了調整最優解的編碼特性，本文將m線性映射到30位二進制編碼空間，00…00對應于 -1.00,11…11對應于+1.00；實驗中的其他參數設計與前述Bohachevsky函數優化相同。實驗結果表明，采用AO交叉法的GA算法能搜索到Bohachevsky函數不同位置的全局最優解，但優化所需時間有較大差異。圖3顯示了不同m值下， AO交叉法的優化時間曲線，其中，縱坐標為優化到最優解所需的時間(20次實驗的平均值)，橫軸為m在二進制編碼中所含0的個數，自0直到30。

圖3 函數優化時間與m值的關系

從圖3可以看出，AO交叉方法的優化效率隨著0、1數目的變化有很大差異；在m值(二進制碼)為00…00和11…11時，AO交叉方法的優化效率最高，而當m中的0、1個數比接近于1時，AO交叉的優化效率最低。

4 結束語

與流行的一點交叉和一致交叉等方法相比，本文提出并研究設計的二倍體顯性DNA遺傳計算方法在模式抽樣機理方面有其獨特性，主要表現在對優質0_模式和優質1_模式有較強的保護作用。實驗結果顯示，這種抽樣特性導致AO交叉的優化效率隨最優解(二值編碼)的0、1分布變化而發生變化；最優解包含的0和1的個數相差越大，則優化效率越高，反之，則優化效率越低。實驗結果也顯示出在最優解包含的0和1的個數之比接近于1.00的較小范圍內，AO交叉方法的優化效率較低。如果假定最優解所包含的0(或1)個數呈均勻分布，則AO交叉方法將在總體優化效率上明顯超越一點交叉等傳統遺傳算法，統計實驗結果有力支持了上述理論分析與算法設計思想。

需要特別指出的是，生物DNA遺傳過程除了多倍體顯性機制機理外，還特別依賴于DNA雙螺旋結構。生物DNA雙螺旋二倍體染色體結構在群體遺傳基因多樣性維護方面有著獨特的功效。限于篇幅，有關二倍體雙螺旋結構的DNA模擬計算研究在此不做贅述。