賦權(quán)圖上優(yōu)化問(wèn)題的DNA計(jì)算方法研究.pdf

1、在賦權(quán)圖上優(yōu)化問(wèn)題的DNA計(jì)算方法研究中，權(quán)值的DNA編碼方法是求解問(wèn)題的關(guān)鍵。本文討論了中國(guó)郵遞員、旅行商、最大權(quán)團(tuán)、最小生成樹(shù)等賦權(quán)圖上經(jīng)典優(yōu)化問(wèn)題的DNA計(jì)算方法，改進(jìn)了它們?cè)蠨NA計(jì)算模型中的權(quán)值編碼方法，給出了利用改進(jìn)DNA編碼方法求解的新DNA算法。我們通過(guò)設(shè)計(jì)賦權(quán)無(wú)向圖的廣義邊圖給出了中國(guó)郵遞員問(wèn)題的一種DNA編碼方法及計(jì)算模型，通過(guò)設(shè)計(jì)賦權(quán)圖的相對(duì)長(zhǎng)度圖給出了旅行商問(wèn)題的一種DNA編碼方法及計(jì)算模型，通過(guò)選取DNA序列

2、的最佳逆補(bǔ)比對(duì)給出了最小生成樹(shù)問(wèn)題的基于逆補(bǔ)比對(duì)的一種DNA編碼方法及計(jì)算模型，并通過(guò)改進(jìn)已有的DNA編碼方法給出了最大權(quán)團(tuán)問(wèn)題、頂點(diǎn)覆蓋問(wèn)題及0/1背包問(wèn)題的DNA計(jì)算模型。我們給出的DNA計(jì)算模型提高了DNA計(jì)算中數(shù)值表示和處理能力。具體研究工作如下： 對(duì)于中國(guó)郵遞員問(wèn)題，我們首先提出了廣義邊圖的概念，然后設(shè)計(jì)了一種新的基于廣義邊圖的DNA編碼方法及DNA算法。所提出的廣義邊圖DNA編碼方法利用邊到點(diǎn)映射把賦權(quán)圖中的邊映射為

3、頂點(diǎn)，構(gòu)造給定賦權(quán)圖的廣義邊圖，使得賦權(quán)圖中的邊權(quán)值轉(zhuǎn)換為廣義邊圖中頂點(diǎn)的權(quán)值，從而利用頂點(diǎn)的編碼長(zhǎng)度表示權(quán)值，使得權(quán)值的處理變得更容易。具體地說(shuō)，對(duì)于任一賦權(quán)連通無(wú)向圖G=(V，E)，首先通過(guò)邊到點(diǎn)映射把圖G轉(zhuǎn)換為廣義邊圖G'=(V',E')，其中每個(gè)頂點(diǎn)v'i∈V'對(duì)應(yīng)于圖G的一條邊ei。若圖G中邊ei與ej鄰接，則在G'中頂點(diǎn)v'i和v'j之間加一條無(wú)向邊：若圖G中vi的度數(shù)為奇數(shù)，則在與vi關(guān)聯(lián)的邊對(duì)應(yīng)的G'的頂點(diǎn)上添加自環(huán)。用

4、于編碼圖G'中頂點(diǎn)v'i的DNA串si的長(zhǎng)度等于圖G中邊ei的權(quán)值。用于編碼圖G'中邊eij'=(v'i,v'j)的DNA串sij為si的后半部分與sj的前半部分并置后的逆補(bǔ)。這種編碼方法提高了用DNA計(jì)算求解賦權(quán)圖上具有邊權(quán)值的優(yōu)化問(wèn)題的數(shù)值表示和處理能力。 對(duì)于旅行商問(wèn)題，我們首先提出了權(quán)值序號(hào)和相對(duì)長(zhǎng)度圖的概念，然后設(shè)計(jì)了一種基于相對(duì)長(zhǎng)度圖的DNA編碼方法和一種改進(jìn)的DNA編碼方法，并給出了相應(yīng)的DNA算法。對(duì)于任一賦權(quán)連

5、通無(wú)向圖G=(V,E)，所提出的相對(duì)長(zhǎng)度DNA編碼方法利用權(quán)值的序號(hào)和相對(duì)長(zhǎng)度圖代替權(quán)值本身來(lái)對(duì)權(quán)值進(jìn)行編碼。由于該編碼方法中用于編碼權(quán)值的DNA串的長(zhǎng)度只與權(quán)值的序號(hào)有關(guān)，與權(quán)值本身無(wú)關(guān)，因此它能直接處理整數(shù)或?qū)崝?shù)權(quán)值，甚至很小或很大的權(quán)值，并且所獲得的最優(yōu)解不與DNA串的長(zhǎng)度成正比，這就使得這種編碼方法能處理一個(gè)較寬范圍的權(quán)值。所提出的改進(jìn)DNA編碼方法用兩條不同長(zhǎng)度的DNA串去編碼每條邊，其中較長(zhǎng)DNA串由首段、權(quán)值段及尾段三部分

6、組成，較短DNA串是較長(zhǎng)串權(quán)值段的逆補(bǔ)。該編碼方法是對(duì)先前的權(quán)編碼方法的一種改進(jìn)，改進(jìn)后的編碼方法生成的是穩(wěn)定的DNA雙鏈而不是單雙交替的DNA串，因而更容易生成問(wèn)題的最優(yōu)解。對(duì)于最小生成樹(shù)問(wèn)題，我們?cè)O(shè)計(jì)了一種基于頂點(diǎn)識(shí)別碼的DNA編碼方法以及一種基于DNA序列的逆補(bǔ)比對(duì)的DNA編碼方法，并給出了相應(yīng)的DNA計(jì)算模型。由于非線性的最小生成樹(shù)不能直接用線性的DNA串表示，因此不能直接給出最小生成樹(shù)問(wèn)題的基于DNA計(jì)算基本操作的DNA編碼方

7、法及DNA算法。對(duì)于任一賦權(quán)連通無(wú)向圖G=(V，E)，所提出的基于頂點(diǎn)識(shí)別碼的DNA編碼方法用一個(gè)長(zhǎng)度為l=max{「log4n」，6}的識(shí)別碼ri去編碼圖G的每個(gè)頂點(diǎn)vi，用一個(gè)長(zhǎng)度為2p=2×max{wij,l}的DNA串sij去編碼圖G的每條邊eij，其中sij的長(zhǎng)度為wij的前部分標(biāo)記為Swij1,長(zhǎng)度為wij的后部分標(biāo)記為swij2，并對(duì)圖G的任意兩條相鄰邊eij和ejk，增加一個(gè)長(zhǎng)度為wij+wjk的DNA串saijk=-h

8、(swij2Swjk1)作為附加碼。基于所提出的DNA編碼方法，我們給出了最小生成樹(shù)問(wèn)題的一種基于頂點(diǎn)識(shí)別碼的DNA算法，該算法首先獲得對(duì)應(yīng)于最小生成樹(shù)的Euler回路，然后把Euler回路轉(zhuǎn)化為最小生成樹(shù)。在此基礎(chǔ)上，針對(duì)DNA雙鏈中堿基之間的互補(bǔ)/非互補(bǔ)、同向/非同向關(guān)系，提出了DNA序列的補(bǔ)比對(duì)和逆補(bǔ)比對(duì)的概念，給出了DNA序列的補(bǔ)比對(duì)和逆補(bǔ)比對(duì)的計(jì)分方法，并利用DNA序列的逆補(bǔ)比對(duì)的計(jì)分方法給出了最小生成樹(shù)問(wèn)題的一種新DNA編碼

9、方法及DNA算法。對(duì)于任一賦權(quán)連通無(wú)向圖G=(V，E)，vi∈V,eijE,1≤i，j≤n，其中邊eij上的權(quán)值為wij，用一個(gè)長(zhǎng)度為l=max{「log4n」，6}的識(shí)別碼ri去編碼每個(gè)頂點(diǎn)vi，用一個(gè)長(zhǎng)度為2p=2×max{wij,l}的DNA串sij去編碼每條邊eij，然后計(jì)算swij1,swij2,rj的逆補(bǔ)比對(duì)aswij1,aswjk2,arj,并選取DNA串Saijk=Lower(aswij2｜arj)+Lower(aswj

10、k1｜arj)作為附加碼?；谒岢龅腄NA編碼方法，我們給出了最小生成樹(shù)問(wèn)題的一種基于逆補(bǔ)比對(duì)的DNA算法，該算法借助于Euler圖獲得給定賦權(quán)圖的最小生成樹(shù)。這種DNA編碼方法可推廣到其它賦權(quán)圖上優(yōu)化問(wèn)題的DNA計(jì)算模型中。 對(duì)于頂點(diǎn)賦值的最大權(quán)團(tuán)問(wèn)題，我們?cè)贠uyang的最大團(tuán)問(wèn)題的DNA計(jì)算模型的基礎(chǔ)上，增加了權(quán)值的DNA編碼表示，進(jìn)而給出了最大權(quán)團(tuán)問(wèn)題的一種改進(jìn)的DNA編碼方法及DNA算法。對(duì)于任一頂點(diǎn)賦權(quán)的連通無(wú)向圖

11、，我們用兩個(gè)不同長(zhǎng)度的DNA串去編碼每個(gè)頂點(diǎn)，用一個(gè)長(zhǎng)度為20的DNA串去編碼每條邊。相應(yīng)于項(xiàng)點(diǎn)vi的較長(zhǎng)DNA串由三部分組成，其中間部分的長(zhǎng)度為wi，相應(yīng)于頂點(diǎn)vi的較短DNA串是較長(zhǎng)DNA串的中間部分的逆補(bǔ)。在此基礎(chǔ)上，我們給出了最大權(quán)團(tuán)問(wèn)題的DNA算法及其生物實(shí)現(xiàn)方法。所設(shè)計(jì)的DNA算法的空間復(fù)雜度為O(dmaxn)，n表示給定賦權(quán)圖的頂點(diǎn)數(shù)，dmax表示頂點(diǎn)的最大度數(shù)，這比Ouyang的最大團(tuán)問(wèn)題的DNA算法的空間復(fù)雜度O(nn

12、)略低。 此外，我們還給出了0/1背包問(wèn)題和頂點(diǎn)覆蓋問(wèn)題的DNA編碼方法和DN_A算法。對(duì)于0/1背包問(wèn)題，我們對(duì)先前的DNA編碼方法進(jìn)行了一點(diǎn)改進(jìn)，使得連接反應(yīng)生成穩(wěn)定的DNA雙鏈而不是單雙交替的DNA串。對(duì)于頂點(diǎn)覆蓋問(wèn)題，我們首先對(duì)先前的從頂點(diǎn)覆蓋問(wèn)題到Hamilton回路問(wèn)題的多項(xiàng)式變換進(jìn)行了一點(diǎn)改進(jìn)，把具有12個(gè)頂點(diǎn)和14條邊的覆蓋子圖改為具有4個(gè)頂點(diǎn)和4條邊的改進(jìn)覆蓋子圖，使所構(gòu)造的圖G'的頂點(diǎn)數(shù)從K+12│E│減少到