DNA計(jì)算及其算法優(yōu)化.pdf

1、在計(jì)算機(jī)中，利用有機(jī)分子的信息處理能力來(lái)代替數(shù)字開(kāi)關(guān)部件，這就是DNA計(jì)算的基本思想。以當(dāng)前的計(jì)算機(jī)技術(shù)要實(shí)現(xiàn)微型化存在明顯的局限性，所以要進(jìn)行大的革新，很早以前就有人提出現(xiàn)代計(jì)算機(jī)的基本部件應(yīng)逐步過(guò)渡到分子水平，這樣一來(lái)，它將會(huì)比我們利用當(dāng)前技術(shù)制造出的任何東西都要小得多，量子計(jì)算和DNA計(jì)算是當(dāng)前這種思想的兩種不同表現(xiàn)，本論文主要介紹DNA計(jì)算。DNA計(jì)算主要基于以下兩點(diǎn)：(1)DNA鏈的巨大并行性；(2)Watson-Crick的

2、互補(bǔ)結(jié)構(gòu)。傳統(tǒng)理論上的計(jì)算機(jī)科學(xué)植根于重復(fù)寫(xiě)操作，這對(duì)于大部分自動(dòng)機(jī)械裝置和語(yǔ)言理論模型是正確的，然而，在計(jì)算行為中，自然界操作DNA分子利用的是完全不同的操作類(lèi)型：剪切、粘貼、連接、插入、刪除等?？梢宰C明，利用這些操作可以建立計(jì)算模型，并且在功能上等價(jià)于圖靈機(jī)。 以前DNA計(jì)算的研究主要集中在一些組合問(wèn)題上，像Hamiltonian路徑問(wèn)題、旅行商問(wèn)題、3-SAT問(wèn)題，甚至破解DES密碼等等，但提出的上述所有問(wèn)題的DNA算法基

3、本上都是蠻力搜索，初始化時(shí)生成問(wèn)題的所有可能的解決方案，然后根據(jù)條件消除掉不正確的答案，最后剩下的方案即是問(wèn)題的正確答案。 但值得注意的是，實(shí)際問(wèn)題的正確答案也許會(huì)在計(jì)算過(guò)程中被破壞掉，最后得到的答案也許是一個(gè)錯(cuò)誤的答案。為了避免這種錯(cuò)誤，我們提出了將啟發(fā)式優(yōu)化算法和DNA計(jì)算結(jié)合，采用新的手段來(lái)設(shè)計(jì)算法。在這篇論文中，我們將蟻群優(yōu)化算法和DNA計(jì)算結(jié)合，來(lái)解決旅行商問(wèn)題。即使正確的答案在處理的過(guò)程中被破壞掉，該正確答案在以后的

4、處理過(guò)程總還會(huì)被構(gòu)造，在過(guò)濾掉不合適的答案以后，我們利用控制變性溫度的方法按比例放大經(jīng)過(guò)過(guò)濾剩下的序列，并把放大的結(jié)果作為下次迭代的輸入，相應(yīng)的代表正確答案的DNA序列的濃度就會(huì)增加。在經(jīng)過(guò)多次迭代之后，若結(jié)果趨于穩(wěn)定，則認(rèn)為剩下的序列即為問(wèn)題的答案。 論文的前兩部分主要介紹生物學(xué)的基礎(chǔ)知識(shí)、DNA計(jì)算的基本概念、基本模型和相關(guān)的著名實(shí)驗(yàn)，接下來(lái)介紹了啟發(fā)式優(yōu)化算法：蟻群優(yōu)化算法；然后提出蟻群優(yōu)化算法和DNA計(jì)算結(jié)合的構(gòu)想與具體