改進的DNA遺傳算法在指派問題中的應用

李孝忠，任吉棟

(天津科技大學計算機科學與信息工程學院，天津 300222)

改進的DNA遺傳算法在指派問題中的應用

李孝忠，任吉棟

(天津科技大學計算機科學與信息工程學院，天津 300222)

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

DNA計算；遺傳算法；指派問題

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

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

DNA計算是一種新的計算模式．1994年Adelman首次用實驗顯示了DNA計算的可能性[4].其最大優點是充分利用了DNA分子具有海量存儲遺傳密碼以及生化反應的海量并行性．近年來，一大批科學家投身于DNA計算這一新的研究領域，提出了許多組合優化問題的DNA計算模型[5]．

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

1 DNA遺傳算法

1.1 DNA遺傳算法的基本概念

1.1.1 DNA

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

DNA分子具有變性和復性的性質．DNA變性就是指DNA分子中維持雙螺旋穩定性的氫鍵和疏水鍵的斷裂，使穩定的雙螺旋結構松解為無規則線性結構的現象．DNA復性是指變形的DNA鏈在適當條件下，二條互補鏈全部或部分恢復到天然雙螺旋結構的現象．熱變性DNA一般經緩慢冷卻后即可復性，此過程稱之為“退火”．熱循環就是利用這兩性質使來源不同的DNA片段按堿基互補關系形成雜交雙鏈分子的一個過程．

1.1.2 生物酶

限制內切酶能夠識別特定的堿基序列，并在相應的位置切斷作分離操作．聚合酶能夠在DNA序列的一端上添加核苷酸使序列加長，作復制操作．

1.2 DNA遺傳算法的結構

DNA遺傳算法的結構與傳統的遺傳算法相類似，如圖1所示．

1.2.1 DNA編碼

使用n個具有任意長度的DNA鏈組成初始編碼群體P(t)．一條DNA鏈由4種堿基A，T，G，C的序列構成．初始化時，待解問題的設計參數是通過4個字母的符號集 Σ(A，T，G，C)編碼以形成染色體，即DNA鏈．DNA編碼是一個關鍵的環節.DNA鏈的長短將直接影響問題求解的精度和收斂度．

1.2.2 計算適應度

按照編碼規則，根據具體問題構造具體的適應度函數．通過這種評價函數決定哪個染色體是適合問題的最佳解，適應度函數值越大，解的質量越好．

1.2.3 選擇

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

1.2.4 交叉

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

1.2.5 變異

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

1.2.6 倒位

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

2 改進的DNA遺傳算法

2.1 改進思想

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

2.2 改進技術

基于上述思想，本文在傳統DNA遺傳算法的基礎上對DNA遺傳算法做了以下幾方面的改進：

選擇操作改進．采用“輪盤賭法”選擇適應度高的個體，其優點是對適應度低的個體也給予選擇的機會，這樣保證了優秀基因片段來源的多樣性．然后在適應度高的個體中根據一定的規則選擇出一段優秀的基因片段．確定一個長度L，從選出的每個適應度高的個體中隨機選出n個長度為L的子序列，從中選出適應度最高的作為優秀基因片段．

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

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

2.3 算法編碼及操作算子

2.3.1 編碼

DNA序列采用A、G、C、T四個字母來對長度為L，由腺嘌呤、鳥嘌呤、胞嘧啶、胸腺嘧啶四種堿基組成的DNA序列進行編碼．

2.3.2 操作算子

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

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

(3),變異算子．根據問題的特點選擇是否使用動態的變異概率．

3 改進的DNA遺傳算法求解指派問題

3.1 指派問題

指派問題的提法是：某單位需完成n項任務，恰好有n個人可承擔這些任務．各人完成任務不同，效率也不同.那么，如何進行指派，使總效率最高呢?

設決策變量為xij(i，j＝1，2，…，n)，當指派第i個人去完成第j項任務時，xij＝1；否則，xij＝0．設第i個人完成第j項任務的時間為cij(i，j＝1，2，…，n)，cij＞0．若要求指派后的總時間最小，則最優指派問題的數學模型為

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

3.2 算法編碼及算法步驟

3.2.1 DNA編碼

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

3.2.2 算法步驟

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

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

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

(3)分別以步驟(2)產生的優秀片段為母板，繼續與n×n個片段進行熱循環，產生N/2個帶有優秀片段的新個體，與保存下來的時間短的N/2個個體組成新的N個個體．

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

將上述步驟產生的種群重復進行步驟(2)、(3)、(4)的操作G－1次，得到最優解．

4 仿真實驗

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

表1 8×8指派問題時間數據Tab.1 Tim e data of 8×8 assignm ent problem d

實驗表明，平均迭代4.5次就可以收斂到最優方案：7A—3B—6C—0D—1E—5F—4G—2H，而傳統的DNA遺傳算法平均迭代9.5次才能達到最優解．改進前后的實驗對比見表2．可以看出，改進后的方法收斂更快．

表2 改進前后的實驗對比Tab.2 Results of com parison experiment

5 結 語

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

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

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

［3］ 徐麗娜. 神經網絡控制[M]. 哈爾濱：哈爾濱工業大學出版社，1999：1–15.

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

［5］ 丁永生. 計算智能：理論、技術與應用[M]. 北京：科學出版社，2004：294–303.

［6］ 丁永生，任立紅. DNA遺傳算法及其函數尋優應用[C]//中國控制與決策學術年會論文集. 沈陽：控制與決策編輯部，2000：235–239.

［7］ 張雷，楊大地，冉戎. 基于DNA遺傳算法的曲面最短路徑問題[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

國家自然科學基金資助項目(61070021)

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