李孝忠，任吉棟

(天津科技大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院，天津 300222)

改進(jìn)的DNA遺傳算法在指派問題中的應(yīng)用

李孝忠，任吉棟

(天津科技大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院，天津 300222)

提出了一種基于優(yōu)秀基因片段思想的DNA遺傳算法，將這段基因片段提取出來并將它遺傳到后代中，可以加快收斂速度．給出了DNA遺傳算法的結(jié)構(gòu)，討論了選擇、交叉和變異算子的具體操作，并將其運(yùn)用到指派問題最優(yōu)解的求解中，給出了具體的實(shí)現(xiàn)方法．仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性和實(shí)用性．

DNA計(jì)算；遺傳算法；指派問題

Abstract：A DNA genetic algorithm based on the thought of excellent gene was proposed，extracting the excellent gene and inheriting it to future generations can speed up the convergence. The structure of DNA genetic algorithm was given and its specific operations including select，crossover and mutation operator were discussed. The method mentioned above was applied to the optimal solution of assignment problem and the concrete implementation was given. The effectiveness and practicality of the algorithm were verified by computer simulation at last.

Keywords：DNA calculation；genetic algorithm；assignment problem

遺傳算法是近年來迅速發(fā)展起來的一種全新的隨機(jī)搜索與優(yōu)化算法，它具有不依賴于問題模型、易于并行處理、有較強(qiáng)的全局搜索功能、魯棒性強(qiáng)等特點(diǎn)，適用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜和非線性問題[1]．但是，遺傳算法也存在早期收斂[2]和微調(diào)能力差[3]等不足．

DNA計(jì)算是一種新的計(jì)算模式．1994年Adelman首次用實(shí)驗(yàn)顯示了DNA計(jì)算的可能性[4].其最大優(yōu)點(diǎn)是充分利用了DNA分子具有海量存儲(chǔ)遺傳密碼以及生化反應(yīng)的海量并行性．近年來，一大批科學(xué)家投身于DNA計(jì)算這一新的研究領(lǐng)域，提出了許多組合優(yōu)化問題的DNA計(jì)算模型[5]．

為了進(jìn)一步模擬生物的遺傳機(jī)理和基因調(diào)控機(jī)理，一些學(xué)者提出了基于DNA編碼的遺傳算法[6]，并將其用到組合優(yōu)化問題的求解當(dāng)中[7]．DNA遺傳算法既可以提高DNA計(jì)算的效率，又可以拓寬遺傳算法的應(yīng)用范圍．DNA遺傳算法還需要在常規(guī)的遺傳算法上進(jìn)行改進(jìn)．本文基于優(yōu)秀基因片段思想提出了選擇、交叉和變異操作的新方法來提高進(jìn)化效率和加快收斂速度．

1 DNA遺傳算法

1.1 DNA遺傳算法的基本概念

1.1.1 DNA

DNA是在DNA計(jì)算中起中心作用的分子，是重要的基因物質(zhì)，攜帶著生物的遺傳信息．DNA的基本元素是核苷酸，由于化學(xué)結(jié)構(gòu)的不同，核苷酸的堿基劃分為腺嘌呤(A)、鳥嘌呤(G)、胞嘧啶(C)和胸嘧啶(T)四類堿基．堿基之間的配對(duì)關(guān)系是：A與T配對(duì)，C與G配對(duì)，這種配對(duì)原則稱為Watson-Crick互補(bǔ)性原則．DNA通過磷酸二酯鍵可組成DNA單鏈，利用互補(bǔ)性原則，單鏈很容易形成雙鏈分子．

DNA分子具有變性和復(fù)性的性質(zhì)．DNA變性就是指DNA分子中維持雙螺旋穩(wěn)定性的氫鍵和疏水鍵的斷裂，使穩(wěn)定的雙螺旋結(jié)構(gòu)松解為無規(guī)則線性結(jié)構(gòu)的現(xiàn)象．DNA復(fù)性是指變形的DNA鏈在適當(dāng)條件下，二條互補(bǔ)鏈全部或部分恢復(fù)到天然雙螺旋結(jié)構(gòu)的現(xiàn)象．熱變性DNA一般經(jīng)緩慢冷卻后即可復(fù)性，此過程稱之為“退火”．熱循環(huán)就是利用這兩性質(zhì)使來源不同的DNA片段按堿基互補(bǔ)關(guān)系形成雜交雙鏈分子的一個(gè)過程．

1.1.2 生物酶

限制內(nèi)切酶能夠識(shí)別特定的堿基序列，并在相應(yīng)的位置切斷作分離操作．聚合酶能夠在DNA序列的一端上添加核苷酸使序列加長(zhǎng)，作復(fù)制操作．

1.2 DNA遺傳算法的結(jié)構(gòu)

DNA遺傳算法的結(jié)構(gòu)與傳統(tǒng)的遺傳算法相類似，如圖1所示．

1.2.1 DNA編碼

使用n個(gè)具有任意長(zhǎng)度的DNA鏈組成初始編碼群體P(t)．一條DNA鏈由4種堿基A，T，G，C的序列構(gòu)成．初始化時(shí)，待解問題的設(shè)計(jì)參數(shù)是通過4個(gè)字母的符號(hào)集 Σ(A，T，G，C)編碼以形成染色體，即DNA鏈．DNA編碼是一個(gè)關(guān)鍵的環(huán)節(jié).DNA鏈的長(zhǎng)短將直接影響問題求解的精度和收斂度．

1.2.2 計(jì)算適應(yīng)度

按照編碼規(guī)則，根據(jù)具體問題構(gòu)造具體的適應(yīng)度函數(shù)．通過這種評(píng)價(jià)函數(shù)決定哪個(gè)染色體是適合問題的最佳解，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好．

1.2.3 選擇

與常規(guī)遺傳算法類似，從初始編碼群體P(t)中以一定的概率選出個(gè)體來繁殖后代．經(jīng)常使用的方法有期望法、精華保存法和適應(yīng)度比例法等．

1.2.4 交叉

交叉操作是將兩條DNA鏈進(jìn)行互換重組，其效率和精度直接影響到計(jì)算結(jié)果．

1.2.5 變異

以一定的概率從DNA群體P(t＋1)中隨機(jī)地選擇若干個(gè)個(gè)體．隨機(jī)地選取某一基因位進(jìn)行變異．變異是為了使DNA遺傳算法具有局部隨機(jī)搜索能力，從而來維持群體的多樣性，避免出現(xiàn)早熟現(xiàn)象．

1.2.6 倒位

在DNA鏈中兩個(gè)隨機(jī)選擇位置之間的某些堿基的順序進(jìn)行倒位．它可以使在父代中離得很遠(yuǎn)的位在后代中靠在一起．相當(dāng)于重新定義基因塊．倒位操作是可選的，根據(jù)問題的需要而定．

2 改進(jìn)的DNA遺傳算法

2.1 改進(jìn)思想

一個(gè)適應(yīng)度高的個(gè)體中包含著一段好的基因片段．將這段基因片段提取出來并將它遺傳到后代中，可以加快收斂速度．

2.2 改進(jìn)技術(shù)

基于上述思想，本文在傳統(tǒng)DNA遺傳算法的基礎(chǔ)上對(duì)DNA遺傳算法做了以下幾方面的改進(jìn)：

選擇操作改進(jìn)．采用“輪盤賭法”選擇適應(yīng)度高的個(gè)體，其優(yōu)點(diǎn)是對(duì)適應(yīng)度低的個(gè)體也給予選擇的機(jī)會(huì)，這樣保證了優(yōu)秀基因片段來源的多樣性．然后在適應(yīng)度高的個(gè)體中根據(jù)一定的規(guī)則選擇出一段優(yōu)秀的基因片段．確定一個(gè)長(zhǎng)度L，從選出的每個(gè)適應(yīng)度高的個(gè)體中隨機(jī)選出n個(gè)長(zhǎng)度為L(zhǎng)的子序列，從中選出適應(yīng)度最高的作為優(yōu)秀基因片段．

交叉操作改進(jìn)．丁永生等[8]提出了采用基因轉(zhuǎn)移操作來取代交叉算子．將染色體中某一段好的基因串直接傳遞給其他染色體，進(jìn)行信息之間的重組．從而產(chǎn)生更好的個(gè)體，來加快搜索速度．本文以此為基礎(chǔ)，分兩種情況產(chǎn)生新的群體．適應(yīng)度高的個(gè)體按照一定的概率進(jìn)行優(yōu)秀基因片段的互換，適應(yīng)度低的個(gè)體分別以優(yōu)秀基因片段為母體隨機(jī)產(chǎn)生新的個(gè)體．

變異操作改進(jìn)．為保持種群的多樣性和產(chǎn)生新的基因信息，變異操作在所有新個(gè)體中進(jìn)行．文獻(xiàn)[9]在研究DNA序列模型時(shí)指出在同一個(gè)DNA序列的不同位置，存在hot spot和cold spot，位于cold spot的堿基其變異概率遠(yuǎn)遠(yuǎn)小于hot spot的堿基．對(duì)于DNA遺傳算法而言，在進(jìn)化的不同階段，不同位置的碼位對(duì)問題答案的影響是不一樣的．基于上述思想，變異概率應(yīng)該是一個(gè)動(dòng)態(tài)變化的過程，變異的方法也與傳統(tǒng)的單個(gè)基因位的變異不同．從所有DNA鏈中選出適應(yīng)度最高的個(gè)體，隨機(jī)地選取該DNA鏈中的某一段DNA序列，將其傳遞給其他個(gè)體的對(duì)應(yīng)部分．

2.3 算法編碼及操作算子

2.3.1 編碼

DNA序列采用A、G、C、T四個(gè)字母來對(duì)長(zhǎng)度為L(zhǎng)，由腺嘌呤、鳥嘌呤、胞嘧啶、胸腺嘧啶四種堿基組成的DNA序列進(jìn)行編碼．

2.3.2 操作算子

(1),選擇算子．根據(jù)適應(yīng)度函數(shù)值f，采用“輪盤賭法”定義最好的N/2個(gè)個(gè)體為中性個(gè)體，剩下的為有害個(gè)體．為便于計(jì)算，設(shè)N為偶數(shù)．在N/2個(gè)中性個(gè)體中選出N/2個(gè)長(zhǎng)度為l0的優(yōu)秀基因片段，即當(dāng)前序列的子序列R．

(2),交叉算子．交叉分兩種情況：中性個(gè)體兩兩互換優(yōu)秀基因片段，兩個(gè)序列與對(duì)方子序列R相對(duì)應(yīng)的地方分別被對(duì)方的子序列R所替換；有害個(gè)體交叉的概率為100%．通過兩種情況的交叉操作得到N個(gè)子代個(gè)體．

(3),變異算子．根據(jù)問題的特點(diǎn)選擇是否使用動(dòng)態(tài)的變異概率．

3 改進(jìn)的DNA遺傳算法求解指派問題

3.1 指派問題

指派問題的提法是：某單位需完成n項(xiàng)任務(wù)，恰好有n個(gè)人可承擔(dān)這些任務(wù)．各人完成任務(wù)不同，效率也不同.那么，如何進(jìn)行指派，使總效率最高呢?

設(shè)決策變量為xij(i，j＝1，2，…，n)，當(dāng)指派第i個(gè)人去完成第j項(xiàng)任務(wù)時(shí)，xij＝1；否則，xij＝0．設(shè)第i個(gè)人完成第j項(xiàng)任務(wù)的時(shí)間為cij(i，j＝1，2，…，n)，cij＞0．若要求指派后的總時(shí)間最小，則最優(yōu)指派問題的數(shù)學(xué)模型為

從模型中的約束條件的結(jié)構(gòu)不難看出：設(shè)決策變量所組成的矩陣為A＝(xij)n×n，則最優(yōu)指派問題的解xij(i，j＝1，2，…，n)為可行解的充分必要條件為A中恰有n個(gè)數(shù)為1，第j列恰有1個(gè)數(shù)為1(j＝1，2，…，n)，第i(i＝1，2，…，n)行恰有1個(gè)數(shù)為1．

3.2 算法編碼及算法步驟

3.2.1 DNA編碼

根據(jù)指派問題的特點(diǎn)，對(duì)每個(gè)人的每項(xiàng)任務(wù)進(jìn)行編碼，n項(xiàng)任務(wù)n個(gè)人來完成總共需要n×n個(gè)編碼．編碼包括3 bp(base pairs)長(zhǎng)度的數(shù)值序列和10 bp長(zhǎng)度的標(biāo)志序列，分三種情況．第一列的編碼先是數(shù)值序列，然后是標(biāo)志序列；最后一列的編碼與第一列的正好相反，先標(biāo)志序列再數(shù)值序列；中間列為兩個(gè)標(biāo)志序列中間夾一個(gè)數(shù)值序列．如果有后標(biāo)志序列，則它唯一地表示了該列，如果有前標(biāo)志序列，則它是前一列后標(biāo)志序列的補(bǔ)序列．例如第一列的編碼為XXXAACGTGATGC，第二列的編碼為TTGCACACGXXXGTAGCTAGTG．其中XXX為數(shù)值序列，表示此人完成該任務(wù)所需的時(shí)間．第一列編碼中的后標(biāo)志序列AACGTGATGC表明該編碼為第一列編碼．至于編碼屬于哪一行則通過添加藥劑來實(shí)現(xiàn)．從編碼得出每個(gè)序列的長(zhǎng)度為13×n－10．

3.2.2 算法步驟

(1)設(shè)置最大進(jìn)化代數(shù)G和初始種群數(shù)N．將n×n個(gè)編碼片段放在一起進(jìn)行熱循環(huán)，在熱循環(huán)過程中前一列的后標(biāo)志序列和與它互補(bǔ)的后一列的前標(biāo)志序列退火，在聚合酶的作用下形成雙鏈．在聚合前，為每一行的n個(gè)片段設(shè)置相同的特性標(biāo)記，為每一列設(shè)置不同的特性標(biāo)記，使得處在相同行不同列的片段互相排斥不能連接，并且這些標(biāo)記可以疊加，保證已經(jīng)連接的片段不能再與該片段上已有的處在相同行上的片段相連．在此基礎(chǔ)上得到N個(gè)DNA序列作為初始種群．

(2)初始種群中每個(gè)序列的單鏈部分就是每個(gè)人完成任務(wù)所需的時(shí)間．根據(jù)適應(yīng)度將N個(gè)DNA序列分成兩部分．本文的適應(yīng)度函數(shù)設(shè)計(jì)如下：

式中：g(x)是相應(yīng)指派方案中所有人的完成時(shí)間和；Cmax為進(jìn)化過程中g(shù)(x)的最大值或當(dāng)前群體中g(shù)(x)的最大值．從公式可以看出，完成時(shí)間和小的指派方案相應(yīng)的適應(yīng)度值大，所以保留的可能性也較大．采用“輪盤賭法”將適應(yīng)度高的N/2個(gè)個(gè)體保存下來，并從這些個(gè)體中提取出N/2個(gè)優(yōu)秀片段．從1到[n/2]中隨機(jī)生成一個(gè)數(shù)a，在N/2個(gè)體中截取N/2個(gè)從a列到a＋[n/2]–1列長(zhǎng)度為[n/2]的片段，為了滿足這個(gè)要求，用限制性酶的特殊酶切位點(diǎn)來完成．然后計(jì)算每個(gè)的時(shí)間值，選擇時(shí)間最短的．重復(fù)執(zhí)行N/2次，產(chǎn)生N/2個(gè)優(yōu)秀片段．

(3)分別以步驟(2)產(chǎn)生的優(yōu)秀片段為母板，繼續(xù)與n×n個(gè)片段進(jìn)行熱循環(huán)，產(chǎn)生N/2個(gè)帶有優(yōu)秀片段的新個(gè)體，與保存下來的時(shí)間短的N/2個(gè)個(gè)體組成新的N個(gè)個(gè)體．

(4)由于問題的編碼不涉及到高低位，所以不采用動(dòng)態(tài)變異概率．設(shè)定一個(gè)變異概率p，對(duì)每個(gè)個(gè)體都產(chǎn)生一個(gè)隨機(jī)概率pi，如果pi≤p則進(jìn)行變異．變異時(shí)從1到n中隨機(jī)生成一個(gè)數(shù)b，將序列中的第b個(gè)片段剪切下來，這樣產(chǎn)生兩段序列，并將第二段序列的最后一個(gè)片段也去掉．然后將剩下的兩段序列放在不包含剪切下來的兩個(gè)片段的試管中進(jìn)行熱循環(huán)，將兩段序列連接產(chǎn)生新的DNA序列．

將上述步驟產(chǎn)生的種群重復(fù)進(jìn)行步驟(2)、(3)、(4)的操作G－1次，得到最優(yōu)解．

4 仿真實(shí)驗(yàn)

根據(jù)上述步驟將DNA編碼改成實(shí)數(shù)編碼，所有的生物操作采用編程實(shí)現(xiàn)，在Visual C++環(huán)境下采用C++語(yǔ)言編寫程序進(jìn)行仿真．設(shè)有A、B、C、D、E、F、G、H八項(xiàng)任務(wù)由0、1、2、3、4、5、6、7八個(gè)人去完成，其完成時(shí)間如表1所示．實(shí)驗(yàn)參數(shù)為：最大進(jìn)化代數(shù)G為20、初始種群N為10、變異概率p為0.1．

表1 8×8指派問題時(shí)間數(shù)據(jù)Tab.1 Tim e data of 8×8 assignm ent problem d

實(shí)驗(yàn)表明，平均迭代4.5次就可以收斂到最優(yōu)方案：7A—3B—6C—0D—1E—5F—4G—2H，而傳統(tǒng)的DNA遺傳算法平均迭代9.5次才能達(dá)到最優(yōu)解．改進(jìn)前后的實(shí)驗(yàn)對(duì)比見表2．可以看出，改進(jìn)后的方法收斂更快．

表2 改進(jìn)前后的實(shí)驗(yàn)對(duì)比Tab.2 Results of com parison experiment

5 結(jié) 語(yǔ)

本文在傳統(tǒng)DNA遺傳算法的基礎(chǔ)上，根據(jù)優(yōu)秀基因片段思想，對(duì)選擇、交叉和變異操作進(jìn)行改進(jìn)，給出了具體操作．針對(duì)指派問題的最優(yōu)解求解，提出具體的算法步驟，并進(jìn)行仿真，初步驗(yàn)證了改進(jìn)算法的有效性和實(shí)用性．但是對(duì)于如何選擇優(yōu)秀基因片段本文并沒有給出確定的規(guī)則，需要根據(jù)具體的問題進(jìn)行具體的分析，還需要在這方面進(jìn)行進(jìn)一步的研究．

［1］ 俞國(guó)燕，王筱珍. 改進(jìn)遺傳算法的應(yīng)用研究[J]. 機(jī)械制造，2007，45(513)：58–60.

［2］ 蔣騰旭，謝楓. 遺傳算法中防止早熟收斂的幾種措施[J]. 計(jì)算機(jī)與現(xiàn)代化，2006，136(12)：54–56.

［3］ 徐麗娜. 神經(jīng)網(wǎng)絡(luò)控制[M]. 哈爾濱：哈爾濱工業(yè)大學(xué)出版社，1999：1–15.

［4］ Adelman L M. Molecular computation of solutions to combinatorial problems [J]. Science，1994，266(5187)：1021–1024.

［5］ 丁永生. 計(jì)算智能：理論、技術(shù)與應(yīng)用[M]. 北京：科學(xué)出版社，2004：294–303.

［6］ 丁永生，任立紅. DNA遺傳算法及其函數(shù)尋優(yōu)應(yīng)用[C]//中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集. 沈陽(yáng)：控制與決策編輯部，2000：235–239.

［7］ 張雷，楊大地，冉戎. 基于DNA遺傳算法的曲面最短路徑問題[J]. 計(jì)算機(jī)工程，2007(16)：181–185.

［8］ Ren L H，Ding Y S，Ying H，et a1. Emergence of selflearning fuzzy systems by a new virus DNA-based evolutionary algorithm [J]. Intelligent Systems，2003，18(3)：339–354.

［9］ Neuhauser C，Krone S M. The genealogy of samples in models w ith selection[J]. Genetics，1997(2)：519–534.

Im proved DNA Genetic A lgorithm and Its App lication to Assignment Problem

LI Xiao-zhong，REN Ji-dong
(College of Computer Science and Information Engineering，Tianjin University of Science & Technology，Tianjin 300222，China)

TP18

A

1672-6510(2011)02-0061-04

2010–11–04；

2011–01–11

國(guó)家自然科學(xué)基金資助項(xiàng)目(61070021)

李孝忠（1962—），男，山東人，教授，博士，lixz@tust.edu.cn．