李 立

(安慶廣播電視大學(xué)，安徽 安慶 246003)

使用最小串行策略的小通用脈沖神經(jīng)膜系統(tǒng)

李 立

(安慶廣播電視大學(xué)，安徽 安慶 246003)

膜計(jì)算是生物計(jì)算的新分支，具有強(qiáng)大的計(jì)算能力和潛在的應(yīng)用價(jià)值.使用最小串行策略的脈沖神經(jīng)膜系統(tǒng)是一類基于神經(jīng)元細(xì)胞的膜計(jì)算模型，在該系統(tǒng)中引入帶權(quán)的突觸，分別構(gòu)造了含有71個(gè)神經(jīng)元的基于最小脈沖數(shù)目的函數(shù)計(jì)算型小通用串行脈沖神經(jīng)膜系統(tǒng)和含有66個(gè)神經(jīng)元的基于最小脈沖數(shù)目的數(shù)的產(chǎn)生型小通用串行脈沖神經(jīng)膜系統(tǒng)，通過模擬注冊(cè)機(jī)證明了2個(gè)系統(tǒng)的通用性.

膜計(jì)算；脈沖神經(jīng)膜系統(tǒng)；突觸；通用性；注冊(cè)機(jī)

0 引 言

2006年，Ionescu等[1]根據(jù)神經(jīng)網(wǎng)絡(luò)中神經(jīng)元相互之間通過突觸來處理脈沖的生物現(xiàn)象提出了脈沖神經(jīng)膜系統(tǒng).脈沖神經(jīng)膜系統(tǒng)的拓?fù)浣Y(jié)構(gòu)可以用有向圖來表示，其中的節(jié)點(diǎn)表示神經(jīng)元.神經(jīng)元之間的脈沖信號(hào)由用弧線表示的突觸傳遞，每個(gè)神經(jīng)元中包含若干個(gè)脈沖及一定數(shù)量的激發(fā)規(guī)則和遺忘規(guī)則.據(jù)此，國內(nèi)外學(xué)者根據(jù)不同的生物動(dòng)機(jī)提出了一些特殊的脈沖神經(jīng)膜系統(tǒng)，并對(duì)其計(jì)算性能進(jìn)行了研究[2-8].小通用計(jì)算設(shè)備具有良好的通用性和擴(kuò)展性，可以節(jié)約開發(fā)成本，縮短研發(fā)周期，因此對(duì)小通用計(jì)算系統(tǒng)的研究一直是業(yè)內(nèi)的熱點(diǎn)[9-10].本研究探討使用最小串行策略的脈沖神經(jīng)膜系統(tǒng)的小通用性，并對(duì)文獻(xiàn)[8]構(gòu)造的含137個(gè)神經(jīng)元的函數(shù)計(jì)算型和含126個(gè)神經(jīng)元的數(shù)的產(chǎn)生型的基于最小脈沖數(shù)目的小通用的串行脈沖神經(jīng)膜系統(tǒng)進(jìn)行了改進(jìn)，引入了帶權(quán)的突觸，將神經(jīng)元的個(gè)數(shù)分別降到71和66.

1 相關(guān)定義及概念

1.1 基于最小脈沖數(shù)目的串行脈沖神經(jīng)膜系統(tǒng)

標(biāo)準(zhǔn)的脈沖神經(jīng)膜系統(tǒng)的形式化[1]定義為，

Π=(O,σ1,σ2，…，σm，syn,in,out)

其中：

1)O={a}是系統(tǒng)中脈沖的集合.

2)σ1，σ2，…，σm代表系統(tǒng)中的m(m≥1)個(gè)神經(jīng)元，記為，σ1=(ni，Ri)(1≤i≤m)，其中，ni≥0表示神經(jīng)元σi中包含的初始脈沖數(shù)，Ri是具有下列2種形式的規(guī)則構(gòu)成的有限集合.

激發(fā)規(guī)則：E/ac→a;d(c≥1,d≥0),E為a的正則表達(dá)式，d表示神經(jīng)元從被激發(fā)到發(fā)送脈沖所間隔的時(shí)間，稱為時(shí)延.如果神經(jīng)元σi中含有k個(gè)脈沖，滿足ak∈L(E)(k≥c),那么神經(jīng)元σi被激發(fā)，消耗c個(gè)脈沖，并在d步后向其相關(guān)的神經(jīng)元分別送出1個(gè)脈沖.若規(guī)則E/ac→a;d滿足E=ac，則可以簡寫成ac→a;d，若同時(shí)d=0，則可以直接簡寫為ac→a.

遺忘規(guī)則：as→λ(s≥1),對(duì)Ri中的任意規(guī)則E/ac→a;d，都滿足as?L(E)；如果神經(jīng)元σi中包含s個(gè)脈沖，則Ri中的遺忘規(guī)則as→λ(s≥1)將被使用，其中的全部s個(gè)脈沖被消耗掉，且不會(huì)產(chǎn)生新的脈沖.

3)syn?{1,2,…，m}×{1,2,…，m}表示神經(jīng)元之間的突觸連接，對(duì)每個(gè)1≤i≤m，都有(i,i)?syn，若用正整數(shù)w表示突觸的權(quán)值，則帶權(quán)的突觸記為(i,j,w).

4)in,out∈{1,2,…，m}分別表示輸入神經(jīng)元和輸出神經(jīng)元.

對(duì)于基于最小脈沖數(shù)目的串行脈沖神經(jīng)膜系統(tǒng)，在每步計(jì)算中，若有多個(gè)活躍神經(jīng)元(即滿足激發(fā)條件的神經(jīng)元)，則只有脈沖數(shù)目最少的活躍神經(jīng)元可以使用對(duì)應(yīng)規(guī)則激發(fā).若同一時(shí)刻含最小脈沖數(shù)目的活躍神經(jīng)元有多個(gè)，則可以非確定性地選擇1個(gè)神經(jīng)元開始激發(fā).

1.2 通用注冊(cè)機(jī)

本研究構(gòu)造的基于最小脈沖數(shù)目的串行脈沖神經(jīng)膜系統(tǒng)的通用性是通過模擬通用注冊(cè)機(jī)來實(shí)現(xiàn).注冊(cè)機(jī)M=(m,H,l0,lh,I)有3種形式的指令，即：加法指令(li:(ADD(r),lj))，減法指令(li:(SUB(r),lj,lk))和終止指令(lh：HALT).注冊(cè)機(jī)可以在產(chǎn)生模式或接受模式下工作，產(chǎn)生或接受所有的圖靈可計(jì)算數(shù)集.先向注冊(cè)器r1,r2,…，rk中輸入?yún)?shù)n1,n2,…，nk，然后從起始指令l0一直執(zhí)行到終止指令lh，此時(shí)特定的注冊(cè)器rt中存儲(chǔ)的數(shù)就是函數(shù)計(jì)算的結(jié)果.

本研究采用文獻(xiàn)[9]的1個(gè)特定通用注冊(cè)機(jī)Mu=(8,H,l0,lh,I)的指令集，如圖1所示.輸入的數(shù)分別存放在注冊(cè)器1和2中，計(jì)算結(jié)果存放在注冊(cè)器0中.

圖1文獻(xiàn)[9]中的小通用注冊(cè)機(jī)

2 基于最小脈沖數(shù)目的函數(shù)計(jì)算型小通用串行脈沖神經(jīng)膜系統(tǒng)

定理1 存在1個(gè)包含71個(gè)神經(jīng)元的基于最小脈沖數(shù)目的函數(shù)計(jì)算型小通用串行脈沖神經(jīng)膜系統(tǒng).

證明從環(huán)境中讀取二進(jìn)制字符串102n1102n21…102nk1，其中1對(duì)應(yīng)的每個(gè)計(jì)算步驟表示輸入神經(jīng)元收到1個(gè)脈沖.將計(jì)算結(jié)果定義為輸出神經(jīng)元發(fā)送前2個(gè)脈沖的時(shí)間間隔，在系統(tǒng)發(fā)出第2個(gè)脈沖后，計(jì)算停止.若系統(tǒng)產(chǎn)生形如0b104r-21(b≥0)的脈沖串，則計(jì)算結(jié)果為，r=f(n1,n2,…，nk).

系統(tǒng)Π中的確定型加法模塊如圖2所示，模擬加法指令li:(ADD(r)，lj).初始時(shí)，神經(jīng)元σr中含有(2n+2)(n≥0)個(gè)脈沖，即注冊(cè)器r中存儲(chǔ)的數(shù)為n.神經(jīng)元σli收到1個(gè)脈沖后開始激發(fā)，使用規(guī)則a2/a→a，向神經(jīng)元σlj和σr各發(fā)送1個(gè)脈沖.由于突觸(li,r,2)的權(quán)為2，則神經(jīng)元σr和神經(jīng)元σlj分別獲得2和1個(gè)脈沖.神經(jīng)元σr中的脈沖數(shù)增加了2個(gè)，即模擬了注冊(cè)器r中存儲(chǔ)的數(shù)加1，而神經(jīng)元σlj下一步可以激發(fā)系統(tǒng)，開始模擬注冊(cè)機(jī)中的lj指令.

圖2系統(tǒng)Π的加法模塊

圖3系統(tǒng)Π的減法模塊

因此，從神經(jīng)元σli的激發(fā)開始，如果注冊(cè)器r中存儲(chǔ)的數(shù)大于0，則減去1，系統(tǒng)結(jié)束于神經(jīng)元σlj；如果注冊(cè)器r中存儲(chǔ)的數(shù)等于0，系統(tǒng)結(jié)束于神經(jīng)元σlk.系統(tǒng)Π正確地模擬了相對(duì)應(yīng)的減法指令li:(SUB(r),lj,lk).

對(duì)某個(gè)注冊(cè)器r來說，可能會(huì)存在多個(gè)加法指令和減法指令作用在相同的注冊(cè)器r上，加法模塊和減法模塊之間可能的相互影響分析如下：

在圖2所示的加法模塊中，神經(jīng)元σr每次都是收到2個(gè)脈沖，不會(huì)激發(fā)其中的任何規(guī)則，因此在加法模塊之間以及加法模塊和減法模塊之間都沒有相互影響.

1)若n=1，神經(jīng)元σ8含有3個(gè)脈沖數(shù)，將優(yōu)先激發(fā)，向神經(jīng)元σd1和σout各發(fā)送1個(gè)脈沖.第t+3步，神經(jīng)元σ8、σd1和σout的脈沖數(shù)分別為1、5、2，只有神經(jīng)元σout可以激發(fā)，向環(huán)境發(fā)送第2個(gè)脈沖，計(jì)算停止，此時(shí)產(chǎn)生的脈沖串為0b1021.

2)若n≥2，則神經(jīng)元σd1優(yōu)先激發(fā)，向神經(jīng)元σout發(fā)送1個(gè)脈沖，由于突觸(d1，out,2)的權(quán)為2，神經(jīng)元σout獲得2個(gè)脈沖.第t+3步，神經(jīng)元σout使用其中的遺忘規(guī)則a3→λ，移去現(xiàn)有的3個(gè)脈沖.第t+4步，神經(jīng)元σ8激發(fā)，之后，神經(jīng)元σd1、σout、σ8依次激發(fā)，不斷重復(fù)，直到第(t+4n-2)步，只剩余3個(gè)脈沖的神經(jīng)元σ8再次激發(fā)，向神經(jīng)元σd1和σout各發(fā)送1個(gè)脈沖.第(t+4n-1)步，神經(jīng)元σ8、σd1和σout的脈沖數(shù)分別為1、5、2，只有神經(jīng)元σout可被激發(fā)，向環(huán)境送出第2個(gè)脈沖，計(jì)算停止，產(chǎn)生的脈沖串為0b104n-21.

2)分析6組順序執(zhí)行的減法指令和加法指令(l0和l1、l4和l5、l6和l7、l8和l9、l14和l16、lh和l22)可知：對(duì)應(yīng)的中間指令(l1,l5，l7，l9，l16，l22)在模擬的小通用注冊(cè)機(jī)的其他指令中都未出現(xiàn)，可以把每組的減法指令和加法指令合并，每組可節(jié)省2個(gè)神經(jīng)元，6組可減少12個(gè)神經(jīng)元.

故，系統(tǒng)共需要使用71個(gè)神經(jīng)元.

定理1得證.

3 基于最小脈沖數(shù)目的數(shù)的產(chǎn)生型小通用串行脈沖神經(jīng)膜系統(tǒng)

定理2 存在1個(gè)包含66個(gè)神經(jīng)元的基于最小脈沖數(shù)目的數(shù)的產(chǎn)生型小通用串行脈沖神經(jīng)膜系統(tǒng).

證明作為產(chǎn)生數(shù)集的裝置，脈沖神經(jīng)膜系統(tǒng)的通用性定義[10]為，設(shè)(φ0，φ1，…)為一元部分遞歸函數(shù)的1個(gè)固定可枚舉，對(duì)于數(shù)的產(chǎn)生型脈沖神經(jīng)膜系統(tǒng)，存在1個(gè)遞歸函數(shù)g，對(duì)所有自然數(shù)x，若向系統(tǒng)輸入數(shù)g(x)，系統(tǒng)產(chǎn)生的數(shù)集為{n∈N|φX(n)}，則稱其是通用的.

對(duì)第2節(jié)構(gòu)造的系統(tǒng)做3點(diǎn)修改，就可以得到相應(yīng)的基于最小脈沖數(shù)目的數(shù)的產(chǎn)生型小通用串行脈沖神經(jīng)膜系統(tǒng)Πu.

1)系統(tǒng)Πu不需要單獨(dú)的輸出模塊用來輸出計(jì)算停止后的結(jié)果，因此指令lh和注冊(cè)器8可省略，把輸入模塊和輸出模塊合并為1個(gè).通過從環(huán)境讀取符號(hào)串102g(x)1，向神經(jīng)元σ1中存入2g(x)個(gè)脈沖.

2)合并后的輸入—輸出模塊在計(jì)算開始時(shí)隨機(jī)產(chǎn)生1個(gè)自然數(shù)n，即向神經(jīng)元σ2中存入2n個(gè)脈沖，同時(shí)輸出形如104n-21的脈沖串.

3)為了檢測部分遞歸函數(shù)φx是否對(duì)n已定義，開始執(zhí)行如圖1所示的注冊(cè)機(jī)Mu，其中的注冊(cè)器1和2中已分別存入數(shù)g(x)和數(shù)n.若注冊(cè)機(jī)Mu中的計(jì)算停止，即構(gòu)造的系統(tǒng)Πu停機(jī)，則系統(tǒng)Πu產(chǎn)生了數(shù)n.

由此得到系統(tǒng)Πu中含有神經(jīng)元的個(gè)數(shù)統(tǒng)計(jì)為，8+22+13*3+8=77.根據(jù)上述優(yōu)化方法，系統(tǒng)Πu中的1組順序執(zhí)行的加法指令和5組順序執(zhí)行的減法指令和加法指令，可以減少11個(gè)神經(jīng)元.

故，系統(tǒng)Πu一共需要使用66個(gè)神經(jīng)元.

定理2得證.

4 結(jié) 語

本研究研究了基于最小脈沖數(shù)目的串行脈沖神經(jīng)膜系統(tǒng)的小通用性.作為計(jì)算函數(shù)的裝置，本研究構(gòu)造了1個(gè)含有71個(gè)神經(jīng)元的基于最小脈沖數(shù)目的小通用串行脈沖神經(jīng)膜系統(tǒng)；作為產(chǎn)生數(shù)集的裝置，本研究構(gòu)造了1個(gè)含有66個(gè)神經(jīng)元的基于最小脈沖數(shù)目的小通用串行脈沖神經(jīng)膜系統(tǒng).帶權(quán)突觸的引入減少了輔助神經(jīng)元，使得構(gòu)造的2個(gè)小通用系統(tǒng)比文獻(xiàn)[8]中的系統(tǒng)使用的神經(jīng)元數(shù)目減少了近一半.下一步的研究計(jì)劃能引入更新的思路和更好的證明技巧，構(gòu)造出所需神經(jīng)元更少的基于最小脈沖數(shù)目的小通用串行脈沖神經(jīng)膜系統(tǒng).

[1]Ionescu M,Pǎun G，Yokomori T.SpikingneuralPsystems[J].Fundam Inform,2006,71(2):279-308.

[2]Pǎun G.AquickoverviewofmembranecomputingwithsomedetailsaboutspikingneuralPsystems[J].Front Comput Sci Chin,2007,1(1):37-49.

[3]Metta V P,Krithivasan K.ParallelprogramminginspikingneuralPsystemswithanti-spikes[J].Sci Technol,2014,17(1):33-45.

[4]Paun G.SpikingneuralPsystemswithastrocyte-likecontrol[J].J UCS,2007,13(11):1707-1721.

[5]Pan L,Wang J,Hoogeboom H J.SpikingneuralPsystemswithastrocytes[J].Neural Comput,2012,24(3):805-825.

[6]Song T,Pan L,Paun G.SpikingneuralPsystemswithrulesonsynapses[J].Theoret Comput Sci,2014,25(9):82-95.

[7]Pǎun A,Sidoroff M.SequentialityinducedbyspikenumberinSNPsystems:Smalluniversalmachines[J].Lect Notes Comput Sci,2011,71(84):333-345.

[8]Jiang K Q,Huang Y F,Xu J B.SmalluniversalsequentialspikingneuralPsystemsbasedonminimumspikenumber[J].Rom J Inform Sci Technol,2014,17(1):5-18.

[9]Korec I.Smalluniversalregistermachines[J].Theoret Comput Sci,1996,168(2):267-301.

[10]Pǎun A,Pǎun A G.SmalluniversalspikingneuralPsystems[J].BioSystems,2007,90(1):48-60.

SmallUniversalSpikingNeuralPSystemsWorkinginSequentialModeInducedbyMinimumSpikeNumber

LILi

(Anqing Radio and Television University, Anqing 246003, China)

Membrane computing is a new branch of biological computing with strong computing power and potential application value.Spiking neural P system working in sequential mode induced by minimum spike number is a kind of neural-like computation models in the framework of P systems.In this system,the synapse with weights is introduced.As devices for computing functions,we construct a universal sequential spiking neural P system based on the minimum spike number which uses 71 neurons;as a generator of sets of numbers,a universal sequential spiking neural P system based on minimum spike number with 66 neurons is also obtained.The universality of the two systems is demonstrated by simulation registers.

membrane computing;spiking neural P system;synapse;universality;register

TP301

A

1004-5422(2017)04-0385-05

2017-10-11.

安徽省教育廳高校自然科學(xué)基金(KJ2017A942)資助項(xiàng)目.

李 立(1980 — )，女，碩士，副教授，從事膜計(jì)算與數(shù)據(jù)挖掘研究.