根據(jù)摩爾定律,傳統(tǒng)計(jì)算機(jī)中的晶體管電路逐漸接近性能極限,再加上電子計(jì)算機(jī)在計(jì)算能力等方面存在的局限性,科學(xué)家期待并開始在自然界尋找新的計(jì)算介質(zhì)來代替?zhèn)鹘y(tǒng)的電子計(jì)算機(jī),其中利用生物硬件的分子計(jì)算機(jī)因其極高的并行性與極低的能耗量而受到科學(xué)界的極大青睞。生物系統(tǒng)是個(gè)復(fù)雜的“計(jì)算系統(tǒng)”,是產(chǎn)生新的計(jì)算思想的重要源泉。從各種各樣的生物系統(tǒng)及其進(jìn)化過程中獲得靈感,可為求解傳統(tǒng)計(jì)算方法難于解決的各種復(fù)雜問題提供新的計(jì)算思想或模型。膜計(jì)算(Membrane Computing,也稱為P系統(tǒng))是自然計(jì)算的一個(gè)新分支,其目的是從活細(xì)胞中以及組織、器官或其他結(jié)構(gòu)的細(xì)胞之間相互協(xié)作的方式中獲得新的計(jì)算思想、設(shè)計(jì)新的計(jì)算模型。P系統(tǒng)不僅為計(jì)算機(jī)科學(xué)引入了新的分布式并行信息處理方法和技術(shù),而且為生物系統(tǒng)的建模和仿真提供了新工具,是當(dāng)前非�；钴S的一個(gè)研究領(lǐng)域,預(yù)計(jì)在新一代計(jì)算系統(tǒng)、信息處理系統(tǒng)的技術(shù)開發(fā)方面將起關(guān)鍵作用。 關(guān)于膜計(jì)算的研究工作可歸為三類:理論研究、應(yīng)用研究和軟、硬件實(shí)現(xiàn)研究。膜計(jì)算的理論研究主要集中于各種計(jì)算模型的建立及其計(jì)算能力(Computation Power)的分析;膜計(jì)算的應(yīng)用研究主要是利用P系統(tǒng)的特點(diǎn)和各種模型求解生物學(xué)、計(jì)算機(jī)科學(xué)、語言學(xué)、社會(huì)學(xué)等方面的實(shí)際問題;而膜計(jì)算的軟硬件實(shí)現(xiàn)研究則側(cè)重于在現(xiàn)有計(jì)算機(jī)上用程序?qū)崿F(xiàn)或開發(fā)新的處理器實(shí)現(xiàn)有關(guān)的膜計(jì)算模型或求解有關(guān)問題。 本論文以膜計(jì)算在計(jì)算機(jī)學(xué)科領(lǐng)域的應(yīng)用為研究對(duì)象,本論文的主要工作包括: ①構(gòu)建算術(shù)運(yùn)算P系統(tǒng) 算術(shù)運(yùn)算是加法、減法、乘法和除法四種運(yùn)算的統(tǒng)稱,是數(shù)學(xué)中最古老,最基礎(chǔ)和最初等的部分。作為一種基本的運(yùn)算,實(shí)現(xiàn)算術(shù)運(yùn)算是未來生物計(jì)算機(jī)必須具備的基本功能之一,本論文構(gòu)建一套基于脈沖神經(jīng)P系統(tǒng)求解帶符號(hào)數(shù)的算術(shù)運(yùn)算系統(tǒng),實(shí)現(xiàn)了操作數(shù)的進(jìn)制轉(zhuǎn)換以及加減乘除等運(yùn)算。此工作為實(shí)現(xiàn)基于P系統(tǒng)的數(shù)值計(jì)算系統(tǒng)設(shè)計(jì)提供了理論依據(jù)。 ②設(shè)計(jì)求解HPP問題的P系統(tǒng) 有向圖G的Hamilton路徑問題(Hamilton Path Problem,簡稱HPP問題)是圖論中一個(gè)典型的NP完全問題�；诨钚阅系統(tǒng),本論文構(gòu)建與問題規(guī)模有關(guān)的P系統(tǒng),來求解HPP問題,并從理論上證明該系統(tǒng)的求解方式是完備的,即使用一個(gè)這樣的P系統(tǒng)可以以統(tǒng)一方式來判定有向圖中任意兩點(diǎn)間的是否存在Hamilton路徑。此研究工作進(jìn)一步擴(kuò)展了前人對(duì)P系統(tǒng)求解計(jì)算困難問題的研究成果,為使用P系統(tǒng)以統(tǒng)一方式解決NP完全問題提供了一種新的途徑。 ③提出基于P系統(tǒng)的約束函數(shù)優(yōu)化算法 約束優(yōu)化問題與實(shí)際工程問題密切相關(guān),對(duì)其進(jìn)行研究具有十分重要的理論和實(shí)際意義。此類優(yōu)化問題的難點(diǎn)在于約束條件的處理,引入P系統(tǒng)的并行特征以及膜間通信機(jī)制來處理約束,有利于增加進(jìn)化種群的多樣性,避免過早地陷入局部最優(yōu)。為此,本論文提出了一種基于P系統(tǒng)的約束函數(shù)優(yōu)化算法(Constrained Optimization Evolutionary Algorithms based on Membrane Computing,簡稱為MCCOP算法),設(shè)計(jì)了與優(yōu)化操作相對(duì)應(yīng)的規(guī)則以及規(guī)則執(zhí)行的策略。MCCOP算法充分利用了P系統(tǒng)中的膜間通信機(jī)制,使得個(gè)體可以通過不同的評(píng)估來指導(dǎo)進(jìn)化。實(shí)驗(yàn)測(cè)試表明,MCCOP算法在解的效率和有效性之間取得了較好的折衷,為求解約束優(yōu)化問題提供了一種新的思路。 ④提出基于P系統(tǒng)的求解TSP問題的近似算法 旅行商問題(Traveling Salesman Problem,簡稱為TSP問題)是離散優(yōu)化問題中的一個(gè)典型問題,其應(yīng)用極為廣泛。將局部搜索算子2-Opt和遺傳算子相結(jié)合,本論文提出一種基于P系統(tǒng)的求解TSP問題的近似算法(Approximate Algorithm based on Membrane Computing for Traveling Salesman Problems,簡稱MCTSP算法)�；赑系統(tǒng)中皮膚膜與子膜之間的交流規(guī)則,在MCTSP算法中設(shè)計(jì)了全局進(jìn)化與局部搜索相結(jié)合的控制機(jī)制。對(duì)TSP公共測(cè)試庫TSPLIB中的實(shí)例進(jìn)行測(cè)試并與其他求解TSP問題的混合優(yōu)化算法(包括已提出的基于P系統(tǒng)的優(yōu)化算法)進(jìn)行對(duì)比分析,結(jié)果表明:MCTSP算法在保持群體的多樣性的同時(shí)具有較快的收斂速度,在求解問題的精度上優(yōu)于所對(duì)比的算法。MCTSP算法的設(shè)計(jì)思想可推廣到求解其他的離散優(yōu)化問題。 作為自然計(jì)算的新分枝,目前對(duì)膜計(jì)算的研究還處于數(shù)學(xué)模型建立、理論研究階段。將膜計(jì)算與其他領(lǐng)域相結(jié)合、從理論上來指導(dǎo)解決各自領(lǐng)域中的問題以及實(shí)現(xiàn)技術(shù)的研究還比較薄弱。本論文的研究工作即是在這樣的背景上展開的,論文取得的成果不僅促進(jìn)膜計(jì)算的理論與應(yīng)用研究,也為相關(guān)領(lǐng)域的研究提供新的思路和途徑。
【學(xué)位單位】：重慶大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位年份】：2011
【中圖分類】：TP38
【部分圖文】：

學(xué)界的極大青睞。生物體的信息獲取、存儲(chǔ)與處理方人腦憑借眾多的神經(jīng)元構(gòu)成的復(fù)雜網(wǎng)絡(luò)實(shí)現(xiàn)對(duì)各種信生命的核心，其復(fù)雜結(jié)構(gòu)構(gòu)造了復(fù)雜計(jì)算——生命既細(xì)胞間信息的交換與處理發(fā)生在各種生命體中，以此強(qiáng)大功能。是個(gè)復(fù)雜的“計(jì)算系統(tǒng)”，是產(chǎn)生新的計(jì)算思想的重要領(lǐng)域的一門新興學(xué)科，它主要包括進(jìn)化計(jì)算、神經(jīng)計(jì)名的研究方向。如圖 1.1 所示，自然計(jì)算從生物體的結(jié)出各種各樣的計(jì)算模型或計(jì)算思想[1]。膜計(jì)算(Memb一個(gè)新分支，其目的是從活細(xì)胞中以及組織、器官或作的方式中獲得新的計(jì)算思想、設(shè)計(jì)新的計(jì)算模型。統(tǒng)，也稱為 P 系統(tǒng)。1998 年，歐洲科學(xué)院院士、羅馬在研究生物細(xì)胞結(jié)構(gòu)和功能時(shí)，根據(jù)細(xì)胞處理化學(xué)物質(zhì)算模型[2]，從而拉開了膜計(jì)算研究的序幕。該理論不僅

把 E {λ }+∪ 簡記為*E 。 系統(tǒng)P 系統(tǒng)的生物學(xué)基礎(chǔ)胞是生命的基礎(chǔ)也是最小的生命載體。作為生命結(jié)構(gòu)，細(xì)胞內(nèi)部空間包含細(xì)胞核、線粒體、高爾某些病毒外，都具有生物膜。真核細(xì)胞除質(zhì)膜(又器的內(nèi)膜系統(tǒng)，包括核膜、線粒體膜、內(nèi)質(zhì)網(wǎng)膜體膜、過氧化酶體膜等。如圖 2.1 所示，生物細(xì)胞而其內(nèi)部的細(xì)胞器被內(nèi)部膜包裹著，這些內(nèi)部膜域，每個(gè)區(qū)域內(nèi)存在著獨(dú)立的、不同的生物化學(xué)整個(gè)生命體劃分為一個(gè)個(gè)細(xì)胞所占據(jù)的區(qū)域，每活動(dòng)。細(xì)胞膜和內(nèi)部膜可統(tǒng)稱為生物膜[106]。生物分離和過濾的功能。

圖 2.4 轉(zhuǎn)移 P 系統(tǒng)計(jì)算示例[3]ure 2.4 Example for calculation of the transition P syst的規(guī)則能被執(zhí)行，顯然，在同一時(shí)刻，有其中一組能被執(zhí)行�，F(xiàn)假設(shè){a → ab, f →→ ff}。因 a → bδ的執(zhí)行，使 3#膜被溶解，多，分兩種情況：重集為2bcf 。{b → d , ff → f}或{b → d , cf →{b → d , ff → f}，然后只有{d → de, cf → cd多重集2cd e 被送到#1 膜中。{b → d , cf → cdδ}，#2 膜被溶解，多重集cd重集為112++nbcfn。 {b → d , ff → f}，得到多重集ncdfn +12。
【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 莫海芳;康立山;;求解TSP的混合遺傳算法[J];計(jì)算機(jī)工程與應(yīng)用;2007年18期

2 張煜東;吳樂南;韋耿;;智能算法求解TSP問題的比較[J];計(jì)算機(jī)工程與應(yīng)用;2009年11期

3 王軒;李元香;;一種結(jié)合局部搜索策略的求解TSP的演化算法[J];計(jì)算機(jī)工程;2006年09期

4 張興義;曾湘祥;潘林強(qiáng);羅斌;;脈沖神經(jīng)膜系統(tǒng)求解任意兩個(gè)自然數(shù)的乘積[J];計(jì)算機(jī)學(xué)報(bào);2009年12期

5 張葛祥;潘林強(qiáng);;自然計(jì)算的新分支——膜計(jì)算[J];計(jì)算機(jī)學(xué)報(bào);2010年02期

6 占志剛;張求明;張盛意;王康;;一種改進(jìn)的自適應(yīng)蟻群算法求解TSP問題[J];計(jì)算機(jī)與數(shù)字工程;2010年02期

7 江瑞,羅予頻,胡東成,司徒國業(yè);一種基于種群熵估計(jì)的自適應(yīng)遺傳算法[J];清華大學(xué)學(xué)報(bào)(自然科學(xué)版);2002年03期

8 王勇;蔡自興;周育人;肖赤心;;約束優(yōu)化進(jìn)化算法[J];軟件學(xué)報(bào);2009年01期

9 羅若愚;李亦學(xué);;系統(tǒng)生物學(xué)中建模方法的研究現(xiàn)狀及展望[J];生命科學(xué);2007年03期

10 ;P systems based multi-objective optimization algorithm[J];Progress in Natural Science;2007年04期

相關(guān)博士學(xué)位論文 前2條

1 黃亮;膜計(jì)算優(yōu)化方法研究[D];浙江大學(xué);2007年

2 張興義;脈沖神經(jīng)膜系統(tǒng)的計(jì)算能力研究[D];華中科技大學(xué);2009年

本文編號(hào)：2843561