修建新， 范曉敏， 張 磊

(黑龍江東方學(xué)院計(jì)算機(jī)科學(xué)與電氣工程學(xué)部，黑龍江哈爾濱150086)

0 引言

1994年，DNA計(jì)算理論由L．Adleman首次提出[1]．DNA編碼在DNA計(jì)算過(guò)程中起到十分重要的作用，數(shù)據(jù)信息通過(guò)DNA編碼以后，就具有了DNA染色體的許多的特性，可以解決現(xiàn)實(shí)中的很多問(wèn)題．在有限的離散的數(shù)學(xué)空間中，在滿足多個(gè)約束條件下，如何去求得目標(biāo)函數(shù)的最優(yōu)解問(wèn)題就是多約束目標(biāo)的組合優(yōu)化問(wèn)題．DNA編碼和DNA計(jì)算表現(xiàn)出來(lái)的新特性，正好符合多重約束目標(biāo)的組合優(yōu)化問(wèn)題的要求．所以，本文將DNA編碼引入到多重約束目標(biāo)的組合優(yōu)化問(wèn)題中，完成了基于DNA編碼的多重約束目標(biāo)的組合優(yōu)化的全過(guò)程，并提出了相關(guān)組合優(yōu)化算法，經(jīng)過(guò)實(shí)驗(yàn)證明其求解的結(jié)果優(yōu)于其他算法．

1 DNA編碼

DNA編碼是DNA計(jì)算中的一個(gè)非常重要的組成部分，DNA編碼利用了DNA染色體特殊的雙螺旋結(jié)構(gòu)和堿基互補(bǔ)配對(duì)的特性來(lái)進(jìn)行編碼[2]．關(guān)于DNA編碼的問(wèn)題可以表述為:DNA分子的四個(gè)堿基對(duì)可以定義為字母表P(A，C，G，T)，對(duì)于一個(gè)長(zhǎng)度為N的DNA編碼的集合S，對(duì)于任意一個(gè)子集C，C?S，使得對(duì)于任意的Xi，Yj?C，F(xiàn)(Xi，Yj)≥k，k為任意的整數(shù)，F(xiàn)函數(shù)是DNA序列的評(píng)價(jià)函數(shù)，也就是編碼應(yīng)滿足的約束條件．如果有多個(gè)約束條件，可以預(yù)先設(shè)定多個(gè)約束函數(shù)．

2 多重約束目標(biāo)組合優(yōu)化

某一對(duì)象要同時(shí)滿足多個(gè)約束條件都會(huì)得到一個(gè)目標(biāo)值，要求得目標(biāo)值就必須建立相應(yīng)的目標(biāo)約束函數(shù)，這些約束函數(shù)的值和目標(biāo)值之間的偏差達(dá)到最小就是多重約束目標(biāo)的組合優(yōu)化[3]．多重約束目標(biāo)組合優(yōu)化問(wèn)題可以用數(shù)學(xué)形式表述如下:已知一個(gè)n元組(X1，X2，…，Xn)，一個(gè)約束集C(C1，C2，…，Cm)，組成的一個(gè)狀態(tài)空間S∈{(X1，X2，…，Xn)|Xi∈Di，i=l，2，…，n}，S是滿足C中的所有約束條件的所有n元組．其中，Di是分量Xi的定義域，且Di是有限集，則S就是滿足C的所有約束條件的任一n元組為問(wèn)題的一個(gè)解．

3 優(yōu)化過(guò)程

基于DNA編碼的多重約束目標(biāo)的組合優(yōu)化的過(guò)程包括DNA編碼、初始化種群、計(jì)算個(gè)體適應(yīng)度、個(gè)體選擇、交叉、變異6個(gè)步驟，本文在DNA編碼、初始化種群、遺傳操作、控制參數(shù)等方面都提出了自己的方案，經(jīng)過(guò)優(yōu)化后可以得到較好的效果[4－5]．具體優(yōu)化過(guò)程如下:

3．1 DNA 編碼

傳統(tǒng)的編碼方式都是采用二進(jìn)制編碼，二進(jìn)制編碼方式編碼過(guò)長(zhǎng)造成搜索空間過(guò)大，速度較慢．本文采用分段的DNA編碼方式，采用DNA編碼方式可以減少一半編碼長(zhǎng)度，大大克服了二進(jìn)制編碼的缺點(diǎn)．同時(shí)分段的方式可以滿足多重約束目標(biāo)的組合優(yōu)化的需要，每段編碼可以對(duì)應(yīng)相應(yīng)的約束條件，效果較好．DNA的堿基用二進(jìn)制數(shù)來(lái)表示就分別是A=00，C=01;G=10，T=11 ，假設(shè)任意二進(jìn)制編碼序列為001101000111100100011011，采用DNA編碼方式為ATCACTGCACGT，對(duì)DNA序列根據(jù)不同的約束條件可以分成多段，形式如下AT|CACT|GCACGT．

3．2 初始化種群

種群的初始化直接影響到遺傳的計(jì)算結(jié)果和效率，一般都采用隨機(jī)函數(shù)生成種群，本文在隨機(jī)函數(shù)的基礎(chǔ)上選擇具有離散功能的隨機(jī)函數(shù)，離散的種群有利于實(shí)現(xiàn)全局最優(yōu)，可以提高求解速度．種群的初始化過(guò)程如下:

For i=1 to Pop_size do

Discrete_random(i)隨機(jī)生成第i個(gè)DNA endfor

圖1 遺傳算法(GA)和DNA_YH算法的最優(yōu)適應(yīng)度的結(jié)果比較

3．3 計(jì)算個(gè)體適應(yīng)度

每個(gè)種群中的個(gè)體一個(gè)最主要的遺傳指標(biāo)就是個(gè)體適應(yīng)度，個(gè)體適應(yīng)度就是個(gè)體對(duì)各個(gè)約束目標(biāo)的適應(yīng)程度，一般用適應(yīng)度函數(shù)來(lái)表示．本文采用加權(quán)函數(shù)法來(lái)求得個(gè)體適應(yīng)度函數(shù)．假設(shè)用fi(x)(i=1，2，…，n)表示目標(biāo)函數(shù)，用Si(i=1，2，…，n)表示函數(shù)權(quán)系數(shù)，0 ≤Si≤ 1，(i=1，2，…，n)，且，Si的大小表示在各個(gè)目標(biāo)函數(shù)中的重要的程度，則各個(gè)目標(biāo)函數(shù)的線性加權(quán)和為．

若f(x)非負(fù)，可以采用轉(zhuǎn)換F(x)=，則最終的適應(yīng)度函數(shù)為

3．4 選 擇

在傳統(tǒng)的遺傳算法中，選擇算子采用的是輪盤(pán)賭選擇法，這種方法會(huì)出現(xiàn)未成熟收斂和搜索速度較慢的缺點(diǎn)．所以對(duì)已有的生物的小生境方法進(jìn)行改進(jìn)，先對(duì)個(gè)體進(jìn)行分組，然后選擇每組中個(gè)體適應(yīng)度較高個(gè)體進(jìn)行遺傳，同時(shí)子代個(gè)體的適應(yīng)度超過(guò)父代個(gè)體就可以替換，這樣就解決了未成熟收斂和父子代的相似度較高所產(chǎn)生的冗余個(gè)體．

3．5 交叉和變異

交叉算子和變異算子的選擇直接影響到遺傳的結(jié)果，交叉算子選的過(guò)大，將影響到遺傳個(gè)體的適應(yīng)度急劇變小，交叉算子過(guò)小，會(huì)造成搜索緩慢．變異算子過(guò)大就大大降低了遺傳的效果，變異算子過(guò)小就會(huì)造成未成熟收斂，使個(gè)體早熟．交叉算子fc和變異算子fm直接受到平均適應(yīng)度f(wàn)avg和最大適應(yīng)度f(wàn)max的影響，根據(jù)它們之間的線性變化的規(guī)律，交叉算子和變異算子如公式4－3和4－4所示:

其中k1=k2=0．9，k3=k4=0．3，fmax是最大適應(yīng)度值，favg是平均適應(yīng)度值，f'是要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值，f是變異個(gè)體的適應(yīng)度值．

4 算法設(shè)計(jì)

根據(jù)以上幾個(gè)步驟的優(yōu)化，很容易得到相應(yīng)的基于DNA編碼的多重約束目標(biāo)組合優(yōu)化算法，本文成為DNA_YH，具體的算法如下:

(1)對(duì)輸入的數(shù)據(jù)進(jìn)行DNA編碼．

(2)設(shè)置參數(shù)，初始化種群．

(3)計(jì)算種群中個(gè)體的適應(yīng)度函數(shù)的值．

(4)在種群中選擇相應(yīng)的個(gè)體進(jìn)行交叉、變異的操作，產(chǎn)生下一代個(gè)體．

(5)子代適應(yīng)度大于父代的進(jìn)行替換．

(6)達(dá)到終止條件時(shí)結(jié)束算法，否則轉(zhuǎn)(2)．

5 實(shí)驗(yàn)與結(jié)論

本文提出的基于DNA編碼的多重約束目標(biāo)的組合優(yōu)化算法在在線考試系統(tǒng)的組卷子系統(tǒng)中已經(jīng)得到實(shí)現(xiàn)[6]．DNA_YH算法采用的交叉算子和變異算子和最優(yōu)適應(yīng)度的關(guān)系如表1，2所示，從表中數(shù)據(jù)可以看出本算法的交叉算子和變異算子對(duì)最優(yōu)適應(yīng)度的影響都非常小，得到了較好優(yōu)化．

表1 DNA_YH的交叉算子和適應(yīng)度關(guān)系

表2 DNA_YH的變異算子和適應(yīng)度關(guān)系

實(shí)驗(yàn)還將傳統(tǒng)的遺傳算法和本文提出的DNA_YH算法進(jìn)行了10代種群的比對(duì)，具體數(shù)據(jù)和比對(duì)結(jié)果如表3和圖1所示:從圖1中可以看出DNA_YH算法的種群最優(yōu)適應(yīng)度遠(yuǎn)遠(yuǎn)高于傳統(tǒng)GA算法的最優(yōu)適應(yīng)度，驗(yàn)證了采用DNA_YH算法進(jìn)行多重約束目標(biāo)的組合優(yōu)化可以得到更優(yōu)的目標(biāo)解．

表3 遺傳算法(GA)和DNA_YH算法的10代種群最優(yōu)適應(yīng)度數(shù)據(jù)

[1] Adleman L M．Molecular Computation of Solutions to Combinational Problems．Science．1994，266(5187):1021 －1023．

[2] 許世明，張強(qiáng)．基于遺傳粒子群算法的DNA編碼優(yōu)化．計(jì)算機(jī)工程．2008，34(1):1 －4．

[3] Shin Si－ Yong，Kim Dong－Min．Evolutionary Sequence Generation for Reliable DNA Computing Proc of Congress on Evolutionary Computation[C]．IEEE Computer Society Press，2002．

[4] Baum EB．DNA Sequences Useful for Computation[C]．Proc．The 2nd Annual DIMACS Meeting on DNA － based Computers．Princeton．1996 －06．

[5] Tanaka F，Yamamoto M，et al．Developing Support System for Sequence Design in DNA Computing Proc of the 7th International Workshop on DNA － based Computers[C]．Tampa，F(xiàn)L，USA:2001．

[6] 陳宇，陳治平．啟發(fā)式遺傳算法組卷模型研究[J]．計(jì)算技術(shù)與自動(dòng)化．2006，25(l):35 －120．