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

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

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

圖 2.4 轉(zhuǎn)移 P 系統(tǒng)計算示例[3]ure 2.4 Example for calculation of the transition P syst的規(guī)則能被執(zhí)行，顯然，在同一時刻，有其中一組能被執(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。
【參考文獻】

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

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

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

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

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

5 張葛祥;潘林強;;自然計算的新分支——膜計算[J];計算機學(xué)報;2010年02期

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

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

8 王勇;蔡自興;周育人;肖赤心;;約束優(yōu)化進化算法[J];軟件學(xué)報;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 黃亮;膜計算優(yōu)化方法研究[D];浙江大學(xué);2007年

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

本文編號：2843561