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

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

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

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

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

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

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

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

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

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

10、k1｜arj)作為附加碼。基于所提出的DNA編碼方法，我們給出了最小生成樹問題的一種基于逆補(bǔ)比對的DNA算法，該算法借助于Euler圖獲得給定賦權(quán)圖的最小生成樹。這種DNA編碼方法可推廣到其它賦權(quán)圖上優(yōu)化問題的DNA計算模型中。 對于頂點賦值的最大權(quán)團(tuán)問題，我們在Ouyang的最大團(tuán)問題的DNA計算模型的基礎(chǔ)上，增加了權(quán)值的DNA編碼表示，進(jìn)而給出了最大權(quán)團(tuán)問題的一種改進(jìn)的DNA編碼方法及DNA算法。對于任一頂點賦權(quán)的連通無向圖

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

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