求解計算困難問題的膜計算模型與算法研究.pdf_第1頁
已閱讀1頁,還剩112頁未讀 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、膜計算是自然計算的一個新的分支。它是由細胞以及由細胞組成的組織或器官的結構和功能得到啟發(fā),而抽象出來的一種計算模式。從“膜計算”的概念提出至今十幾年的時間里,關于膜計算的計算理論、模型、算法及應用得到了飛速發(fā)展。膜計算為計算機科學提供了新的分布式并行信息處理方法和技術,促進了新型高性能計算技術的發(fā)展,為求解計算困難問題提供了新的途徑。類細胞膜系統(tǒng)和類組織膜系統(tǒng)是膜計算模型的兩種基本類型。本文主要研究了在這兩種模型框架下求解計算困難問題的

2、膜計算算法。
  計算有效性描述的是模型求解計算困難問題的能力,是自然計算中的一個關鍵問題。膜計算模型基于常用的空間換時間的方法(通常使用受生物啟發(fā)的操作,如膜分裂、膜分割和膜創(chuàng)生),可以在多項式時間內求解計算困難問題。如何構造算法在多項式時間內求解計算困難問題,特別是,NP完全問題,PSPACE完全問題;如何改進已有的結果,構造半統(tǒng)一形式(semi-uniform)的解與統(tǒng)一形式(uniform)的解等都是值得研究的方向。本文對

3、幾個經典的NP完全問題— CAP問題、三匹配問題、二次分配問題,給出了不同膜系統(tǒng)框架或不同規(guī)則使用模式下的算法,分析了不同膜系統(tǒng)模型在計算中的表現(xiàn)。
  空間換時間的膜計算算法盡管從理論上來說是正確的,但目前尚無真正意義上的生物或物理實現(xiàn)。從算法實現(xiàn)的現(xiàn)實考慮,膜計算優(yōu)化算法成為解決計算困難問題的另外一種途徑。它是膜系統(tǒng)框架與優(yōu)化算法結合而成的,可以通過電子計算機仿真實現(xiàn),得到關于計算困難問題的近似解。本文分別構造了兩類膜系統(tǒng)框架

4、下的膜計算優(yōu)化算法,并將它們應用到路徑規(guī)劃領域,成功地求解了帶容量約束的交通路徑問題和帶時間窗的交通路徑問題。膜系統(tǒng)提供的并行分布式計算模型、結構變化方式和信息交流方式可以很好的改進傳統(tǒng)優(yōu)化算法的性能。主要工作如下:
  首先,研究了帶活性膜的膜系統(tǒng)框架下的算法設計。帶活性膜的膜系統(tǒng)是類細胞膜系統(tǒng)的一種重要類型。該模型在計算過程中往往包含膜結構的不斷進化。早期的帶活性膜的膜系統(tǒng)是受電荷(+,?,0)控制的模型。但是,電荷的頻繁變化

5、不符合生物實際,從計算的角度看,也浪費了大量的計算資源。對于一個經典的NP完全問題――CAP問題,本文改進了P′erez-Jim′enez等人的已有結論,設計了不帶電荷的情況下,求解該問題的算法,并給出了由半統(tǒng)一形式的解到統(tǒng)一形式的解的改進。另外,本文還研究了在極小并行的規(guī)則使用模式下如何求解該問題。特別地,這里首次在極小并行的情況下,給出了無電荷的帶活性膜的膜系統(tǒng)求解NP問題的統(tǒng)一形式的解。
  其次,研究了組織膜系統(tǒng)框架下的算

6、法設計。本文延續(xù)類細胞膜系統(tǒng)求解CAP問題的研究,給出了在組織膜系統(tǒng)框架下求解該問題的算法,證明了組織膜系統(tǒng)的有效性。通過與前面的算法比較可以看出,組織膜系統(tǒng)只用兩類規(guī)則即可實現(xiàn)對該問題的求解。系統(tǒng)的結構和規(guī)則簡單,易于理解。此外,本文還給出了組織膜系統(tǒng)求解三匹配問題的算法。三匹配問題的算例可以與圖論中的超圖聯(lián)系起來。以前的文獻構造的求解一般圖論問題的算法通常都既與頂點數目有關,又與邊的數目有關。當邊的數目改變時,通常需要重新構造系統(tǒng)。

7、本文構造的算法只與超圖的頂點數目有關,與超邊的數目無關。因此,當邊的數目改變時,只要點的數目不變,都無需重新構造系統(tǒng)。從這個意義上說,本文的構造技術優(yōu)于之前的構造技術。
  本文還特別研究了帶二元輸入的組織膜系統(tǒng)。以往的膜系統(tǒng)在求解NP困難問題時,通常都是采用一元編碼的方式。因此,二進制編碼的NP問題通常要先轉化成一元編碼的形式,再通過膜系統(tǒng)求解。但是,對于NP完全數值問題或牽扯到大量數值計算的NP問題,一元編碼機制并不適當(較復

8、雜)。通過膜系統(tǒng)解決這類問題時,二進制編碼需要的計算資源更少。本文通過使用帶二元輸入的組織膜系統(tǒng)求解二次分配問題,證明了二進制編碼的NP問題可以直接通過帶二元輸入的組織膜系統(tǒng)求解,而不需要轉化為一元編碼的形式。
  最后,本文設計了兩類膜計算優(yōu)化算法,并分別用于求解帶容量約束的交通路徑問題和帶時間窗的交通路徑問題,將膜算法的應用擴展到路徑規(guī)劃領域。帶容量約束的交通路徑問題是大量路徑問題的基本模型。本文設計的膜算法采用類細胞的膜結構

9、,蟻群算法作為其子算法。特別地,將膜計算中“非確定的規(guī)則使用模式”引入到算法設計中,改善了蟻群算法的性能,有助于平衡收斂速度與搜索效果之間的矛盾。帶時間窗的交通路徑問題增加了時間調度這一環(huán)節(jié),有更廣泛的實際應用背景。為解決這一問題,本文設計了一種基于類組織膜系統(tǒng)的膜算法。該算法融合了“分布式結構”、“同向傳輸”等膜系統(tǒng)特性,擴展了搜索模型,避免了遺傳算法容易過早收斂的問題。通過將仿真實驗結果與文獻中的當前最好結果作比較,證明了該算法的競

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論