求解計算困難問題的膜計算模型與算法研究.pdf

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

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

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

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

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

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

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

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

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