0  引言

生物學(xué)中,，二倍體是指含有兩個(gè)同源基因組的個(gè)體^［1］。根據(jù)孟德?tīng)柗蛛x定律可知,，當(dāng)兩個(gè)同源基因組其中之一為顯性時(shí),，該基因?qū)?yīng)的性狀表現(xiàn)為顯性。僅當(dāng)兩個(gè)同源基因組均為隱性時(shí),，表現(xiàn)型為隱性,，如圖1^［1］所示?；蛑亟M是保持生物特性世代遺傳的基本方式,，也是獲取大量遺傳變異的主要源泉。遺傳算法^［2］中的交叉操作可視為對(duì)生物遺傳過(guò)程中基因重組的直接模擬,，交叉算子選擇得好壞直接影響算法的性能,。對(duì)于占主流的二值編碼（0/1編碼）方法來(lái)說(shuō)，目前最常用的交叉方法主要有以下兩類：

（1）一點(diǎn)交叉,、兩點(diǎn)交叉與多點(diǎn)交叉^［1,3-4］

一點(diǎn)交叉（one-point crossover）又叫簡(jiǎn)單交叉,。具體操作是：在個(gè)體串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)，實(shí)行交叉時(shí),，該點(diǎn)前或后的兩個(gè)個(gè)體的部分結(jié)構(gòu)進(jìn)行互換,，并生成兩個(gè)新個(gè)體。

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

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

（2）一致交叉^［2］

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

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

針對(duì)上述問(wèn)題，參照生物DNA遺傳機(jī)制機(jī)理,，提出并研究設(shè)計(jì)了一類擬合生物遺傳二倍體顯性機(jī)制的新型DNA遺傳算法,。

1  二倍體顯性遺傳算子

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

F1: 0100101101

F2: 1101110100

則由“與／或”交叉方法產(chǎn)生的兩子串分別為：

C1: 0100100100

C2: 1101111101

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

2  二倍體顯性遺傳計(jì)算模式分析

為便于對(duì)AO交叉方法進(jìn)行模式分析,，這里參照Holland模式分析方法,，先定義幾個(gè)有關(guān)基因型模式的概念。

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

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

有了這些定義，再參考 Holland模式分析方法^［1,3-4］,，不難得出二倍體顯性遺傳計(jì)算在模式形成和增長(zhǎng)方面具有如下特性：

（1）1階優(yōu)模式的數(shù)目（數(shù)學(xué)期望）在連續(xù)后代中按式(1)增長(zhǎng)：

（2）高于種群的平均適應(yīng)度的1階0_模式在連續(xù)后代中按式(2)增長(zhǎng)：

（3）高于種群的平均適應(yīng)度的1階1_模式在連續(xù)后代中按式(3)增長(zhǎng)：

其中,，H表示某個(gè)模式，m(H,t)表示在t代種群中隱含模式H的串的個(gè)數(shù),，m(H,t+1)表示在t+1代種群中隱含模式H的串的個(gè)數(shù)（數(shù)學(xué)期望）,，為t代種群中含模式H個(gè)體的平均適應(yīng)度，f為t代種群中所有個(gè)體的平均適應(yīng)度,，Pm為變異概率,，ο(H)為模式H的模階。

很明顯,，與 Holland標(biāo)準(zhǔn)GA相比,，基于二倍體顯性機(jī)制的DNA遺傳計(jì)算（AO交叉）對(duì)于適應(yīng)度高于種群平均適應(yīng)度的0_模式和1_模式有較強(qiáng)的保護(hù)能力。而對(duì)于0,、1混雜的一般模式,，AO交叉方法對(duì)模式H的破壞作用除了與變異概率以及模階的高低相關(guān)外，還與模式H中的0和1個(gè)數(shù)之比相關(guān),。當(dāng)模式H中0和1個(gè)數(shù)相等時(shí),，AO交叉對(duì)模式H的破壞作用最大。

模式H中0和1在數(shù)目上相差越大,，AO交叉對(duì)模式H的破壞作用越?。划?dāng)模式H中的確定信息位全為0或全為1時(shí),，AO交叉對(duì)模式H無(wú)破壞作用,。由此不難推測(cè)AO交叉操作在搜索,、優(yōu)化應(yīng)用中可能具有如下特點(diǎn)：

（1）當(dāng)問(wèn)題全局最優(yōu)解的基因編碼為全0或全1時(shí)，由于AO交叉對(duì)0_模式和1_模式無(wú)破壞作用,，因此,，采用AO交叉的GA可能會(huì)以相當(dāng)高的速度搜索到問(wèn)題的全局最優(yōu)解。

（2）當(dāng)問(wèn)題全局最優(yōu)解的基因編碼0,、1個(gè)數(shù)在數(shù)量比上相差很大時(shí),，由于AO交叉對(duì)這類0、1混雜優(yōu)模式破壞作用較小,，因此,，與一點(diǎn)交叉等方法相比，采用AO交叉的GA可能會(huì)以相對(duì)較快的速度搜索到問(wèn)題的全局最優(yōu)解,。

（3）當(dāng)問(wèn)題全局最優(yōu)解的基因編碼0,、1個(gè)數(shù)在數(shù)量比上相差不大直至相等時(shí)，由于AO交叉對(duì)這類0,、1混雜優(yōu)模式破壞作用較大,，此時(shí)，采用AO交叉的GA的收斂可能比較慢,，甚至不及一點(diǎn)交叉或一致交叉等方法,。

3  遺傳優(yōu)化實(shí)驗(yàn)

為了檢驗(yàn)AO交叉方法的優(yōu)化性能，本文選擇了易于采用 0/1二值編碼方案的典型優(yōu)化問(wèn)題進(jìn)行實(shí)驗(yàn),，即Bohachevsky函數(shù)優(yōu)化問(wèn)題,。

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

Bohachevsky函數(shù)^［5-7］為：

優(yōu)化目標(biāo)為求Bohachevsky函數(shù)的全局最小值。由數(shù)學(xué)分析方法可知Bohachevsky函數(shù)的最小值為0,，發(fā)生在(0,0)點(diǎn),。該函數(shù)三維形狀如圖2所示。

實(shí)驗(yàn)?zāi)康脑谟跈z測(cè)AO交叉方法的性能,，選用一點(diǎn)交叉作為比較對(duì)象,，GA的配種選擇機(jī)制采用正比于適應(yīng)度的賭輪隨機(jī)選擇方式。為了與AO交叉法的邏輯操作形式相一致,，這里的變異操作采用“異或/異或非”方式,，其效果等同于位點(diǎn)變異方法。實(shí)驗(yàn)中的變異概率為0.05,，交叉概率為1.00,，種群規(guī)模為400，種群更新方式采用最佳保留方式。采用二進(jìn)制編碼方式,，實(shí)驗(yàn)結(jié)果如表1所示,，表中列出的優(yōu)化時(shí)間為20次實(shí)驗(yàn)的平均值。

從實(shí)驗(yàn)結(jié)果可以看出各種不同的交叉算子在Bohachevsky函數(shù)優(yōu)化中均能搜索到全局最優(yōu)解但優(yōu)化效率有差異,。AO 交叉操作方法在優(yōu)化效率方面明顯高于一點(diǎn)交叉方法,。根據(jù)前文對(duì)AO交叉方法的分析，AO交叉的優(yōu)化性能可能還與問(wèn)題最優(yōu)解的編碼特性（0和1的數(shù)量比）相關(guān),。為此,，本文通過(guò)設(shè)置最小極值點(diǎn)發(fā)生的位置來(lái)改變?nèi)〉米顑?yōu)解時(shí)自變量編碼的0和1的個(gè)數(shù)。為檢測(cè)最優(yōu)解的編碼特性對(duì)AO交叉法優(yōu)化性能的影響,，令：

          x₁=y₁－m                      (5)

           x₂=y₂－m                      (6)

這樣,，如果針對(duì)自變量y1、y2進(jìn)行遺傳優(yōu)化,，則Bohachevsky函數(shù)的最小極值點(diǎn)發(fā)生在(m,m)。實(shí)驗(yàn)中,，y1,、y2的編碼方式為二進(jìn)制編碼方式，位長(zhǎng)均為30位,。適應(yīng)度函數(shù)設(shè)計(jì)為：

           f（x₁,x₂）=1/（F（x₁,x₂）0.000 001）   (7)

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

從圖3可以看出，AO交叉方法的優(yōu)化效率隨著0,、1數(shù)目的變化有很大差異,；在m值（二進(jìn)制碼）為00…00和11…11時(shí)，AO交叉方法的優(yōu)化效率最高,，而當(dāng)m中的0,、1個(gè)數(shù)比接近于1時(shí)，AO交叉的優(yōu)化效率最低。

4  結(jié)束語(yǔ)

與流行的一點(diǎn)交叉和一致交叉等方法相比,，本文提出并研究設(shè)計(jì)的二倍體顯性DNA遺傳計(jì)算方法在模式抽樣機(jī)理方面有其獨(dú)特性,，主要表現(xiàn)在對(duì)優(yōu)質(zhì)0_模式和優(yōu)質(zhì)1_模式有較強(qiáng)的保護(hù)作用。實(shí)驗(yàn)結(jié)果顯示,，這種抽樣特性導(dǎo)致AO交叉的優(yōu)化效率隨最優(yōu)解（二值編碼）的0,、1分布變化而發(fā)生變化；最優(yōu)解包含的0和1的個(gè)數(shù)相差越大,，則優(yōu)化效率越高,，反之，則優(yōu)化效率越低,。實(shí)驗(yàn)結(jié)果也顯示出在最優(yōu)解包含的0和1的個(gè)數(shù)之比接近于1.00的較小范圍內(nèi),，AO交叉方法的優(yōu)化效率較低。如果假定最優(yōu)解所包含的0（或1）個(gè)數(shù)呈均勻分布,，則AO交叉方法將在總體優(yōu)化效率上明顯超越一點(diǎn)交叉等傳統(tǒng)遺傳算法,，統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果有力支持了上述理論分析與算法設(shè)計(jì)思想。

需要特別指出的是,，生物DNA遺傳過(guò)程除了多倍體顯性機(jī)制機(jī)理外,，還特別依賴于DNA雙螺旋結(jié)構(gòu)。生物DNA雙螺旋二倍體染色體結(jié)構(gòu)在群體遺傳基因多樣性維護(hù)方面有著獨(dú)特的功效,。限于篇幅,，有關(guān)二倍體雙螺旋結(jié)構(gòu)的DNA模擬計(jì)算研究在此不做贅述。

參考文獻(xiàn)

［1］ GLODBERG D E.Genetic algorithms in search, optimization & machine learning［M］.Addison-Wesley, Reading, Mass, 1989.

［2］ Peng Hu,Wu Zhijian,Zhou Xinyu, et al.Dynamic differential evolution algorithm based on elite local learning［J］.Acta Electronica Sinica,2014,，42 (8) : 1522-1530.

［3］ 魯宇明,黎明,李凌.一種具有演化規(guī)則的元胞遺傳算法［J］.電子學(xué)報(bào),2010,38 (7) : 1603-1607.

［4］ 劉淵,楊永輝,張春瑞,等. 一種基于遺傳算法的Fuzzing測(cè)試用例生成新方法［J］.電子學(xué)報(bào),2017,45(3):552-556.

［5］ FOGEL G, FOGEL D.Continous evolutionary programming:analysis and experiments［J］.Journal of Cybernetics and Systems,1994,26（1）:79-90.

［6］ 李柱.基于自適應(yīng)遺傳算法的軟件測(cè)試用例自動(dòng)生成［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用,2016,25(1):192-196

［7］ 陳賢富, 莊鎮(zhèn)泉,王煦法.遺傳算法的自適應(yīng)進(jìn)化策略及TSP問(wèn)題的遺傳優(yōu)化［J］. 電子學(xué)報(bào), 1997,25 (7):111-114.

（收稿日期：2018-04-11）

作者簡(jiǎn)介：

徐凱（1991-）,，女，碩士研究生,，主要研究方向：深度學(xué)習(xí)與人工智能,。

陳賢富（1963-），男,，副教授,，主要研究方向：復(fù)雜系統(tǒng)與計(jì)算智能。