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

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

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

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

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