資源描述：
《基于賦權(quán)圖上優(yōu)化問(wèn)題的dna計(jì)算方法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、山東大學(xué)博士學(xué)位論文賦權(quán)圖上優(yōu)化問(wèn)題的DNA計(jì)算方法研究姓名：韓愛(ài)麗申請(qǐng)學(xué)位級(jí)別：博士專業(yè)：計(jì)算機(jī)軟件與理論指導(dǎo)教師：朱大銘20080405山東大學(xué)博十學(xué)位論文摘要在賦權(quán)圖上優(yōu)化問(wèn)題的DNA計(jì)算方法研究中，權(quán)值的DNA編碼方法是求解問(wèn)題的關(guān)鍵。本文討論了中國(guó)郵遞員、旅行商、最大權(quán)團(tuán)、最小生成樹等賦權(quán)圖上經(jīng)典優(yōu)化問(wèn)題的DNA計(jì)算方法，改進(jìn)了它們?cè)蠨NA計(jì)算模型中的權(quán)值編碼方法，給出TN用改進(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)題的一種DN
2、A編碼方法及計(jì)算模型，通過(guò)選取DNA序列的最佳逆補(bǔ)比對(duì)給出了最小生成樹問(wèn)題的基于逆補(bǔ)比對(duì)的一種DNA編碼方法及計(jì)算模型，并通過(guò)改進(jìn)已有的DNA編碼方法給出了最大權(quán)團(tuán)問(wèn)題、頂點(diǎn)覆蓋問(wèn)題及o／1背包問(wèn)題的DNA計(jì)算模型。我們給出的DNA計(jì)算模型提高了DNA計(jì)算中數(shù)值表示和處理能力。具體研究工作如下：對(duì)于中國(guó)郵遞員問(wèn)題，我們首先提出了廣義邊圖的概念，然后設(shè)計(jì)了一種新的基于廣義邊圖的DNA編碼方法及DNA算法。所提出的廣義邊圖DNA編碼方法利用邊到點(diǎn)映射把賦權(quán)圖中的邊映射為頂點(diǎn)，構(gòu)造給定賦權(quán)圖的廣義邊圖，使得賦權(quán)圖中的邊權(quán)值轉(zhuǎn)換為廣義邊圖中頂點(diǎn)的權(quán)值，從而利用頂點(diǎn)的
3、編碼長(zhǎng)度表示權(quán)值，使得權(quán)值的處理變得更容易。具體地說(shuō)，對(duì)于任一賦權(quán)連通無(wú)向圖G=(形D，首先通過(guò)邊到點(diǎn)映射把圖G轉(zhuǎn)換為廣義邊圖G’=(礦，F(xiàn))，其中每個(gè)頂點(diǎn)vf，∈礦對(duì)應(yīng)于圖G的一條邊e，。若圖G中邊e，與ej鄰接，則在G’中頂點(diǎn)Ⅳ和v／之間加一條無(wú)向邊：若圖G中vf的度數(shù)為奇數(shù)，則在與M關(guān)聯(lián)的邊對(duì)應(yīng)的G，的頂點(diǎn)上添加自環(huán)。用于編碼圖G’中頂點(diǎn)v。7的DNA串s，的長(zhǎng)度等于圖G中邊e，的權(quán)值。用于編碼圖G，中邊e擴(kuò)k(v，，，Ⅳ)的DNA串％為曲的后半部分與s，的前半部分并置后的逆補(bǔ)。這種編碼方法提高了用DNA計(jì)算求解賦權(quán)圖上具有邊權(quán)值的優(yōu)化問(wèn)題的數(shù)值表示和
4、處理能力。對(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)連通無(wú)向圖G=(一目，所提出的相對(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)值IIJ東大學(xué)博+學(xué)位論文本身無(wú)關(guān)，因此它能直接處理整數(shù)或?qū)崝?shù)權(quán)值，甚至很小或很大的權(quán)值，并且所獲得的最優(yōu)解不與DNA串的長(zhǎng)度成正比，這就使得這種編碼方法能處理一個(gè)較寬范圍的權(quán)值。所提出的改進(jìn)DNA編碼方法用兩
5、條不同長(zhǎng)度的DNA串去編碼每條邊，其中較長(zhǎng)DNA串由首段、權(quán)值段及尾段三部分組成，較短DNA串是較長(zhǎng)串權(quán)值段的逆補(bǔ)。該編碼方法是對(duì)先前的權(quán)編碼方法的一種改進(jìn)，改進(jìn)后的編碼方法生成的是穩(wěn)定的DNA雙鏈而不是單雙交替的DNA串，因而更容易生成問(wèn)題的最優(yōu)解。對(duì)于最小生成樹問(wèn)題，我們?cè)O(shè)計(jì)了一種基于頂點(diǎn)識(shí)別碼的DNA編碼方法以及一種基于DNA序列的逆補(bǔ)比對(duì)的DNA編碼方法，并給出了相應(yīng)的DNA計(jì)算模型。由于非線性的最小生成樹不能直接用線性的DNA串表示，因此不能直接給出最小生成樹問(wèn)題的基于DNA計(jì)算基本操作的DNA編碼方法及DNA算法。對(duì)于任一賦權(quán)連通無(wú)向圖G=(K目
6、，所提出的基于頂點(diǎn)識(shí)別碼的DNA編碼方法用一個(gè)長(zhǎng)度為，=max{lloganl，6)的識(shí)別碼一去編碼圖G的每個(gè)頂點(diǎn)M，用一個(gè)長(zhǎng)度為2p=2×max{w帕，)的DNA串Sg去編碼圖G的每條邊e擴(kuò)，其中呀的長(zhǎng)度為w盯的前部分標(biāo)記為s。盯l，長(zhǎng)度為w{：，的后部分標(biāo)記為s，．．蛇，并對(duì)圖G的任意兩條相鄰邊P{：『和饑，增加一個(gè)長(zhǎng)度為W擴(kuò)毗的DNA串J。批=砌(釓蛇s叫)作為附加碼。基于所提出的DNA編碼方法，我們給出了最小生成樹問(wèn)題的一種基于頂點(diǎn)識(shí)別碼的DNA算法，該算法首先獲得對(duì)應(yīng)于最小生成樹的Euler回路，然后把Euler回路轉(zhuǎn)化為最小生成樹。在此基礎(chǔ)上，針
7、對(duì)DNA雙鏈中堿基之間的互補(bǔ)／非互補(bǔ)、同向／!IiE同向關(guān)系，提出了DNA序列的補(bǔ)比對(duì)和逆補(bǔ)比對(duì)的概念，給出了DNA序列的補(bǔ)比對(duì)和逆補(bǔ)比對(duì)的計(jì)分方法，并利用DNA序列的逆補(bǔ)比對(duì)的計(jì)分方法給出了最小生成樹問(wèn)題的一種新DNA編碼方法及DNA算法。對(duì)于任一賦權(quán)連通無(wú)向圖G=(K司，v，∈乃e∥∈E，1≤i,j≤刀，其中邊e擴(kuò)上的權(quán)值為w玎，用一個(gè)長(zhǎng)度為，=max{Il094nl，6}的識(shí)別碼n去編碼每個(gè)頂點(diǎn)'，，，用一個(gè)長(zhǎng)度為印=2×max{w∥，，)的DNA串s礦去編碼每條邊e擴(kuò)，然后計(jì)算Swijl，‰歸，rj的逆補(bǔ)比對(duì)‰卵，aswflc2，嘶，并選取DNA串s
8、緲=Lower(a刪2l僅力+Lower(a,。#x
