時間膜系統(tǒng)計算性能及其應(yīng)用研究.pdf

1、膜系統(tǒng)通常也稱為P系統(tǒng)，是一類分布式并行計算模型。受生物細(xì)胞、組織以及器官功能與結(jié)構(gòu)的啟發(fā)，形成了膜計算最基本的理論模型框架。不少研究成果已經(jīng)證明，很多膜系統(tǒng)的計算能力與圖靈機(jī)是等價的，從理論上講可作為理想的計算機(jī)器。對于標(biāo)準(zhǔn)膜系統(tǒng)，過去都假定每條規(guī)則的執(zhí)行時間為一個單位時間。但是，該假設(shè)過于理想化，實(shí)際中的生化反應(yīng)通常受到多種因素的影響，它們的執(zhí)行時間往往難以預(yù)知?；谠撋铿F(xiàn)象，本文主要研究了時間無關(guān)模式下P系統(tǒng)的計算能力、計算有效

2、性以及計算效率等性能。通過對現(xiàn)有膜系統(tǒng)研究范圍進(jìn)行擴(kuò)展建立了時間膜系統(tǒng)，從而建立了容錯性能更好的計算系統(tǒng)。另外，受到一些生物特征和生物現(xiàn)象的啟發(fā)，為了建立計算效率更高的時間膜系統(tǒng)，提出了基于促進(jìn)劑的時間活性膜P系統(tǒng)和基于對象進(jìn)化規(guī)則的內(nèi)穩(wěn)態(tài)組織膜系統(tǒng)。最后，受到膜系統(tǒng)中一些特征的啟發(fā)，提出了一種新的分類算法。
　　本研究主要內(nèi)容包括：①提出了一種基于促進(jìn)劑的時間活性膜P系統(tǒng)，分別構(gòu)造了半統(tǒng)一和統(tǒng)一的膜算法并在多項(xiàng)式時間內(nèi)求解了SA

3、T問題，證明了任何圖靈可計算數(shù)都可通過該類膜系統(tǒng)產(chǎn)生。在這類模型中，規(guī)則的應(yīng)用可以通過促進(jìn)劑來進(jìn)行控制，并且系統(tǒng)中每個膜上只有兩類電荷。證明結(jié)果表明，與現(xiàn)有的相關(guān)方法對比，構(gòu)建的P系統(tǒng)求解SAT問題需要更少的計算資源和RS步，顯示了其求解NP完全問題的高效性。②針對膜上帶蛋白的時間膜系統(tǒng)，構(gòu)造了兩種統(tǒng)一的膜算法在多項(xiàng)式時間內(nèi)求解SAT問題。在第一種方法中，系統(tǒng)使用基本膜分裂替代非基本膜分裂，并將系統(tǒng)中進(jìn)化規(guī)則的最大長度減小為4，改進(jìn)了現(xiàn)

4、有的研究結(jié)果。在第二種方法中，提出了觸發(fā)型膜上帶蛋白的時間膜系統(tǒng)（每種蛋白質(zhì)僅有兩種可達(dá)狀態(tài)），證明了SAT問題可以被一族觸發(fā)型膜上帶蛋白的時間膜系統(tǒng)在多項(xiàng)式時間內(nèi)求解，擴(kuò)展了時間膜系統(tǒng)的研究范圍。③針對類組織膜系統(tǒng)，使用帶細(xì)胞分裂的時間組織膜系統(tǒng)，證明了在時間無關(guān)模式下該系統(tǒng)在多項(xiàng)式時間內(nèi)僅使用最大規(guī)則長度為3即可求解SAT問題。最后，通過一個實(shí)例對系統(tǒng)的有效性進(jìn)行驗(yàn)證。④提出了一種基于類組織膜系統(tǒng)新的變體----基于對象進(jìn)化規(guī)則的內(nèi)

5、穩(wěn)態(tài)組織膜系統(tǒng)。構(gòu)造了兩種統(tǒng)一算法分別求解了SAT問題和三著色問題，并證明了任何圖靈可計算數(shù)都可通過該類膜系統(tǒng)產(chǎn)生。在這類系統(tǒng)中，去除了“環(huán)境中可以包含任意多份物質(zhì)”這個條件，并引入了對象進(jìn)化規(guī)則。首先，使用規(guī)則最大長度僅為2在線性時間內(nèi)就能得到SAT問題的統(tǒng)一解。然后，將時間無關(guān)的概念引入到這類系統(tǒng)中，并證明了在時間無關(guān)模式下，構(gòu)建的系統(tǒng)可以得到三著色問題統(tǒng)一解。⑤受到活性膜P系統(tǒng)基本框架以及進(jìn)化規(guī)則的啟發(fā)，提出了基于分類噪聲過濾的分