產(chǎn)品列表 Products
聯(lián)系我們 Contact
暫時(shí)還沒編寫該信息
新聞信息
當(dāng)前位置：首頁(yè) > 新聞信息- 求解計(jì)算困難問題的膜計(jì)算模型與算法研究
- 錄入時(shí)間: 2012/8/24
- 膜計(jì)算是自然計(jì)算的一個(gè)新的分支。它是由細(xì)胞以及由細(xì)胞組成的組織或器官的結(jié)構(gòu)和功能得到啟發(fā),而抽象出來的一種計(jì)算模式。從“膜計(jì)算”的概念提出至今十幾年的時(shí)間里,關(guān)于膜計(jì)算的計(jì)算理論、模型、算法及應(yīng)用得到了飛速發(fā)展。膜計(jì)算為計(jì)算機(jī)科學(xué)提供了新的分布式并行信息處理方法和技術(shù),促進(jìn)了新型高性能計(jì)算技術(shù)的發(fā)展,為求解計(jì)算困難問題提供了新的途徑。類細(xì)胞膜系統(tǒng)和類組織膜系統(tǒng)是膜計(jì)算模型的兩種基本類型。本文主要研究了在這兩種模型框架下求解計(jì)算困難問題的膜計(jì)算算法。 計(jì)算有效性描述的是模型求解計(jì)算困難問題的能力,是自然計(jì)算中的一個(gè)關(guān)鍵問題。膜計(jì)算模型基于常用的空間換時(shí)間的方法(通常使用受生物啟發(fā)的操作,如膜分裂、膜分割和膜創(chuàng)生),可以在多項(xiàng)式時(shí)間內(nèi)求解計(jì)算困難問題。如何構(gòu)造算法在多項(xiàng)式時(shí)間內(nèi)求解計(jì)算困難問題,特別是,NP完全問題,PSPACE完全問題；如何改進(jìn)已有的結(jié)果,構(gòu)造半統(tǒng)一形式(semi-uniform)的解與統(tǒng)一形式(uniform)的解等都是值得研究的方向。本文對(duì)幾個(gè)經(jīng)典的NP完全問題—CAP問題、三匹配問題、二次分配問題,給出了不同膜系統(tǒng)框架或不同規(guī)則使用模式下的算法,分析了不同膜系統(tǒng)模型在計(jì)算中的表現(xiàn)。 空間換時(shí)間的膜計(jì)算算法盡管從理論上來說是正確的,但目前尚無真正意義上的生物或物理實(shí)現(xiàn)。從算法實(shí)現(xiàn)的現(xiàn)實(shí)考慮,膜計(jì)算優(yōu)化算法成為解決計(jì)算困難問題的另外一種途徑。它是膜系統(tǒng)框架與優(yōu)化算法結(jié)合而成的,可以通過電子計(jì)算機(jī)仿真實(shí)現(xiàn),得到關(guān)于計(jì)算困難問題的近似解。本文分別構(gòu)造了兩類膜系統(tǒng)框架下的膜計(jì)算優(yōu)化算法,并將它們應(yīng)用到路徑規(guī)劃領(lǐng)域,成功地求解了帶容量約束的交通路徑問題和帶時(shí)間窗的交通路徑問題。膜系統(tǒng)提供的并行分布式計(jì)算模型、結(jié)構(gòu)變化方式和信息交流方式可以很好的改進(jìn)傳統(tǒng)優(yōu)化算法的性能。主要工作如下： 首先,研究了帶活性膜的膜系統(tǒng)框架下的算法設(shè)計(jì)。帶活性膜的膜系統(tǒng)是類細(xì)胞膜系統(tǒng)的一種重要類型。該模型在計(jì)算過程中往往包含膜結(jié)構(gòu)的不斷進(jìn)化。早期的帶活性膜的膜系統(tǒng)是受電荷(+,-,0)控制的模型。但是,電荷的頻繁變化不符合生物實(shí)際,從計(jì)算的角度看,也浪費(fèi)了大量的計(jì)算資源。對(duì)于一個(gè)經(jīng)典的NP完全問題—CAP問題,本文改進(jìn)了Perez-Jimenez等人的已有結(jié)論,設(shè)計(jì)了不帶電荷的情況下,求解該問題的算法,并給出了由半統(tǒng)一形式的解到統(tǒng)一形式的解的改進(jìn)。另外,本文還研究了在極小并行的規(guī)則使用模式下如何求解該問題。特別地,這里首次在極小并行的情況下,給出了無電荷的帶活性膜的膜系統(tǒng)求解NP問題的統(tǒng)一形式的解。 其次,研究了組織膜系統(tǒng)框架下的算法設(shè)計(jì)。本文延續(xù)類細(xì)胞膜系統(tǒng)求解CAP問題的研究,給出了在組織膜系統(tǒng)框架下求解該問題的算法,證明了組織膜系統(tǒng)的有效性。通過與前面的算法比較可以看出,組織膜系統(tǒng)只用兩類規(guī)則即可實(shí)現(xiàn)對(duì)該問題的求解。系統(tǒng)的結(jié)構(gòu)和規(guī)則簡(jiǎn)單,易于理解。此外,本文還給出了組織膜系統(tǒng)求解三匹配問題的算法。三匹配問題的算例可以與圖論中的超圖聯(lián)系起來。以前的文獻(xiàn)構(gòu)造的求解一般圖論問題的算法通常都既與頂點(diǎn)數(shù)目有關(guān),又與邊的數(shù)目有關(guān)。當(dāng)邊的數(shù)目改變時(shí),通常需要重新構(gòu)造系統(tǒng)。本文構(gòu)造的算法只與超圖的頂點(diǎn)數(shù)目有關(guān),與超邊的數(shù)目無關(guān)。因此,當(dāng)邊的數(shù)目改變時(shí),只要點(diǎn)的數(shù)目不變,都無需重新構(gòu)造系統(tǒng)。從這個(gè)意義上說,本文的構(gòu)造技術(shù)優(yōu)于之前的構(gòu)造技術(shù)。 本文還特別研究了帶二元輸入的組織膜系統(tǒng)。以往的膜系統(tǒng)在求解NP困難問題時(shí),通常都是采用一元編碼的方式。因此,二進(jìn)制編碼的NP問題通常要先轉(zhuǎn)化成一元編碼的形式,再通過膜系統(tǒng)求解。但是,對(duì)于NP完全數(shù)值問題或牽扯到大量數(shù)值計(jì)算的NP問題,一元編碼機(jī)制并不適當(dāng)(較復(fù)雜)。通過膜系統(tǒng)解決這類問題時(shí),二進(jìn)制編碼需要的計(jì)算資源更少。本文通過使用帶二元輸入的組織膜系統(tǒng)求解二次分配問題,證明了二進(jìn)制編碼的NP問題可以直接通過帶二元輸入的組織膜系統(tǒng)求解,而不需要轉(zhuǎn)化為一元編碼的形式。 最后,本文設(shè)計(jì)了兩類膜計(jì)算優(yōu)化算法,并分別用于求解帶容量約束的交通路徑問題和帶時(shí)間窗的交通路徑問題,將膜算法的應(yīng)用擴(kuò)展到路徑規(guī)劃領(lǐng)域。帶容量約束的交通路徑問題是大量路徑問題的基本模型。本文設(shè)計(jì)的膜算法采用類細(xì)胞的膜結(jié)構(gòu),蟻群算法作為其子算法。特別地,將膜計(jì)算中“非確定的規(guī)則使用模式”引入到算法設(shè)計(jì)中,改善了蟻群算法的性能,有助于平衡收斂速度與搜索效果之間的矛盾。帶時(shí)間窗的交通路徑問題增加了時(shí)間調(diào)度這一環(huán)節(jié),有更廣泛的實(shí)際應(yīng)用背景。為解決這一問題,本文設(shè)計(jì)了一種基于類組織膜系統(tǒng)的膜算法。該算法融合了“分布式結(jié)構(gòu)”、“同向傳輸”等膜系統(tǒng)特性,擴(kuò)展了搜索模型,避免了遺傳算法容易過早收斂的問題。通過將仿真實(shí)驗(yàn)結(jié)果與文獻(xiàn)中的當(dāng)前最好結(jié)果作比較,證明了該算法的競(jìng)爭(zhēng)力。其中兩個(gè)測(cè)例的搜索結(jié)果比當(dāng)前最好結(jié)果分別少一輛車。