使用最小串行策略的均質脈沖神經膜系統的計算通用性

李立，江克勤

(1. 安慶廣播電視大學, 安徽 安慶 246003；2. 安慶師范大學計算機與信息學院，安徽 安慶 246133)

使用最小串行策略的均質脈沖神經膜系統的計算通用性

李立1，江克勤2

(1. 安慶廣播電視大學, 安徽 安慶 246003；2. 安慶師范大學計算機與信息學院，安徽 安慶 246133)

脈沖神經膜系統是根據神經網絡中神經元相互之間依靠突觸來處理脈沖的生物現象而提出的，具有良好的計算性能及潛在的應用價值。使用最小串行策略的脈沖神經膜系統是一類特殊的脈沖神經膜計算模型，為了驗證其在均質情況下的通用性，引入了帶權值的突觸，構建了均質的基于最小脈沖數目的串行脈沖神經膜系統。使用自動機理論和形式語言，通過模擬注冊機證明了作為數的產生裝置和接受裝置，使用最小串行策略的均質脈沖神經膜系統都是通用的。

膜計算；脈沖神經膜系統；串行性；均質性；注冊機

膜計算模型是由歐洲科學院院士、羅馬尼亞科學院院士Pǎun于1998年在芬蘭圖爾庫計算機中心的研究報告中首次提出，論文于2000年發表[1]，由于膜計算具有良好的計算性能和潛在的應用價值，該方向已成為計算機科學快速發展的新興領域之一。2006年Ionescu等[2]提出的脈沖神經膜系統是一種特殊的類神經膜計算模型。脈沖神經膜系統中基本的計算單元是神經元，神經元之間通過突觸傳遞信號，其中每個神經元中含有若干個激發規則和遺忘規則。

脈沖神經膜系統提出后，受到國內外學者的廣泛關注，基于各種不同的生物動機，提出了一些特殊的脈沖神經膜系統[3-7]，Ibarra等[8]在2009年提出的基于脈沖數目的串行脈沖神經膜系統就是其中的一種。基于最小(或最大)脈沖數目的串行脈沖神經膜系統的串行性是由最小(或最大)脈沖數目引起的，同一時刻只有一個擁有最小(或最大)脈沖數目的活躍神經元(即滿足激發規則的神經元)可以被激發。Pǎun等[9]研究了基于最大脈沖數目的串行脈沖神經膜系統的小通用性。江克勤等研究了基于最小脈沖數目的小通用串行脈沖神經膜系統[10-11]。本文研究的是均質情況下基于最小脈沖數目的串行脈沖神經膜系統的通用性。在系統中引入均質性和帶權值的突觸，構造了加法模塊、減法模塊、輸入模塊和輸出模塊，通過模擬注冊機來證明使用最小串行策略的均質脈沖神經膜系統在產生模式和接受模式下都是通用的。

1 相關定義及概念

1.1 基于最小脈沖數目的串行脈沖神經膜系統

一個度為m(m≥1)的脈沖神經膜系統形式化定義[2]如下：

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

其中：

(i)O={a}表示脈沖的集合；

(ii)σ1,σ2,…,σm代表m個神經元，每個神經元的表示形式為σi=(ni,Ri)(1≤i≤m)，其中ni≥0表示神經元σi中包含的初始脈沖數；Ri是由下列兩種形式的規則構成的有限集合：

①E/ac→a;d(c≥1,d≥0),E為a的正則表達式，d稱為時延，即神經元從被激發到發送脈沖所間隔的時間。

②as→λ(s≥1)，對Ri中的任意規則E/ac→a;d，都滿足as?L(E)；

①中表示的是激發規則，如果神經元σi包含k個脈沖，滿足ak∈L(E)(k≥c),則規則E/ac→a;d可以被激發，神經元σi將消耗c個脈沖，并在d個單位時間后向與它有突觸連接的每個神經元送去一個脈沖。當d=0時，脈沖被立即送出；當d≥1時，若在第t步利用規則激發，則在第t、t+1、…、t+d-1步神經元σi都是封閉的，不能接收和發送任何脈沖，到第t+d步，脈沖被送出，神經元恢復到開放狀態。②中的規則稱為遺忘規則，如果神經元σi包含s個脈沖，則Ri中的遺忘規則as→λ將被使用，消耗其中的s個脈沖，而且沒有新的脈沖產生。若規則E/ac→a;d滿足E=ac，則可以寫成ac→a;d若同時d=0，則可以直接簡寫為ac→a。

(iii) syn?{1,2,…,m}×{1,2,…,m}表示神經元之間的突觸連接，對每個1≤i≤m，都有(i,i)?syn；

(iv) in,out∈{1,2,…,m}，其中in代表輸入神經元，out代表輸出神經元。

在標準脈沖神經膜系統中，所有神經元是并行工作的，在每一個時間單元，所有滿足條件的神經元都必須使用對應規則激發。基于最小脈沖數目的串行脈沖神經膜系統的工作模式不同于標準的脈沖神經膜系統，假設用一個全局時鐘標記整個系統的運行時間，在計算的每一步，當有多個活躍神經元時，只有其中擁有最小脈沖數目的活躍神經元可以使用對應規則激發。如果同一時刻擁有最小脈沖數目的活躍神經元不止一個，則非確定性地選擇其中之一開始激發。

1.2 均質性

均質性是許多計算模型的重要特性之一，如在細胞自動機中，每個細胞取有限的離散狀態，遵循同樣的作用規則，大量細胞通過簡單的相互作用而構成動態系統的演化[12]。2009年曾湘祥等[13]將均質性引入標準脈沖神經膜系統，并證明了其通用性[13-14]。在均質脈沖神經膜系統中，所有神經元有相同的規則集合，即對于系統Π中的任意神經元σi=(ni,Ri)(1≤i≤m)，有R1=R2=…=Rm，這些神經元以一種統一的方式工作。均質脈沖神經膜系統分為突觸上帶權值和不帶權值兩類，帶權的突觸(i,j,r)∈syn表示如果神經元σi向神經元σj發出1個脈沖，則神經元σj會接收到r個脈沖。本文中，我們是在基于最小脈沖數目的串行脈沖神經膜系統中引入均質性和帶權的突觸。在下文第2節的證明中用圖形表示帶權均質脈沖神經膜系統的各模塊，模塊中的神經元用橢圓表示，用帶數字的箭頭表示突觸，若某個突觸的權值是1，則數字不用標出。

1.3 注冊機

注冊機M=(m,H,l0,lh,I)[15]，其中m是注冊器的數目，H是指令的標簽集合，I是指令集合，兩者一一對應，l0是起始指令，lh是終止指令。注冊機有三種形式的指令：

1) 加法指令li:(ADD(r),lj,lk)。先將存儲在注冊器r中的數值加1，再隨機選擇指令lj或指令lk來執行。

2) 減法指令li:(SUB(r),lj,lk)。如果注冊器r中存儲的數值不為0，則先將該數減1，再執行指令lj；如果注冊器r中存儲的數是0，則執行指令lk。

3) 終止指令lh:HALT。注冊機M能在產生和接受兩種模式下運行。在產生模式下，計算初始狀態時，各注冊器都為空。M首先執行的是l0，然后按照相應的指令進行操作，每一步執行一條指令。當注冊機執行到lh時，表示M的計算停止，則存放在注冊器1中的數值即為M所產生的數。在接受模式下，計算初始狀態時，先把一個自然數n存儲在某個注冊器中，其余的都是空注冊器。M首先執行l0，然后按照相應的指令進行操作，如果計算能夠終止于lh，則稱M可以接受數n。注冊機在產生模式和接受模式下都具有計算完備性。

本文將在基于最小脈沖數目的串行脈沖神經膜系統中引入均質性和帶權值的突觸，通過模擬注冊機來證明這類所有神經元中規則相同且含帶權突觸的系統在產生模式和接受模式下的通用性。

2 基于最小脈沖數目的均質串行脈沖神經膜系統的計算通用性

本節研究基于最小脈沖數目的均質串行脈沖神經膜系統的計算能力，證明該系統是通用的產生裝置和接受裝置。用NαHSNP(weightk)表示使用最小串行策略的均質脈沖神經膜系統產生或接受的數的集合簇，其中α∈{gen,acc}(gen表示系統工作在產生模式，acc表示系統工作在接受模式)，weightk表示系統中的突觸的權不超過k。當系統工作在產生模式時，系統可以產生形如0b104n-21的脈沖串；當系統工作在接受模式時，要計算(接受)的數n編碼為t2-t1-1的形式，其中t1,t2分別是輸入神經元輸入前兩個脈沖的時刻。

2.1 產生模式下基于最小脈沖數目的均質串行脈沖神經膜系統

定理1NgenHSNP(weight17)=NRE。

證明由Turing-Church猜想可知：NgenHSNP(weight17)?NRE，因此只需要證明NRE?NgenHSNP(weight17)即可。

構建一個基于最小脈沖數目的均質串行脈沖神經膜系統Π來模擬運行M=(m,H,l0,lh,I)，假設在停機格局時，注冊機M中除了注冊器1之外，其余注冊器都為空，并且在計算過程中，注冊器1中的內容只增不減。在系統Π中，所有神經元具有相同的規則集，如圖1所示。系統Π由加法、減法和輸出三個模塊組成，分別如圖2、圖3和圖4所示。

圖1 系統Π中的神經元Fig.1 The neurons of system Π

對M中的各注冊器r，系統Π都有一個神經元σr與之對應，其中的脈沖數對應r中存儲的數。如果r中存儲的數為n≥0，則神經元σr中包含5n+5個脈沖，即當神經元σr中的脈沖數為5時，表示此時r為空。對M中的每個指令li，系統Π都有一個神經元σli與之對應。一旦神經元σli收到一個脈沖后，達到激發條件，就開始模擬M中的指令li:(op(r),lj,lk)：通過op(r)(對注冊器r進行加或減操作)，最后送出一個脈沖到神經元σlj或σlk。當激發神經元σlh后，系統Π就完成了模擬M的工作，此時兩次激發神經元σout的時間間隔就對應為存儲在注冊器1中所產生的數。

圖2 系統Π的加法模塊Fig.2 The ADD module of system Π

因此，從神經元σli的激發開始，系統向注冊器r的神經元σr送入5個脈沖，然后非確定性地選擇激發神經元σlj或σlk，系統Π正確地模擬了加法指令li:(ADD(r),lj,lk)。

圖3 系統Π的減法模塊Fig.3 The SUB module of system Π

因此，從神經元σli的激發開始，如果注冊器r中存儲的數大于0，則減去1，系統Π結束于神經元σlj；如果注冊器r中存儲的數等于0，系統結束于神經元σlk。系統Π正確地模擬了減法指令li:(SUB(r),lj,lk)。

對某個注冊器r來說，可能會存在多個減法指令和加法指令作用其上，加法模塊和減法模塊之間可能的相互影響分析如下：

在如圖2所示的加法模塊中，神經元σr每次都是收到5個脈沖，不會激發其中的任何規則，因此在加法模塊之間以及加法模塊和減法模塊之間都沒有相互影響。

2.1.3 輸出模塊 系統Π中使用最小串行策略的輸出模塊如上所示，當系統Π執行到了終止指令lh，此時神經元σ1中的脈沖數為5n+5(即注冊器1中存儲的數為n)。當神經元σlh收到一個脈沖后，開始激發，向神經元σout和σ1各發送一個脈沖。下一步，由于突觸(lh,1,8)的權為8，神經元σout和σ1分別擁有1個和5n+13個脈沖，都可以激發，根據最小串行的使用策略，神經元σout優先激發，使用規則a→a，向環境送出第一個脈沖，假設此時是第t步。第t+1步神經元σ1開始激發，使用規則a8(a5)+/a5→a，向神經元σout和σd1各發送一個脈沖。由于突觸(1,out,7)和突觸(1,d1,17)的權分別為7和17，第t+2步神經元σout和σ1分別擁有7個和17個脈沖，神經元σ1擁有5n+8個脈沖，神經元σ1和σd1都可以激發。根據神經元σ1中脈沖數的不同，分析如下：

圖4 系統Π的輸出模塊Fig.4 The OUTPUT module of system Π

(i) 若n=1，神經元σ1中的脈沖數是13個，將優先激發，使用規則a8(a5)+/a5→a，剩余8個脈沖，不再激發，同時向神經元σout和σd1各發送一個脈沖。由于突觸(1,out,7)和突觸(1,d1,17)的權分別為7和17，第t+3步神經元σout和σd1分別擁有14個和34個脈沖，神經元σout是系統中當前唯一的活躍神經元，使用規則a14→a，向環境送出第二個脈沖，計算停止，此時產生的脈沖串為0b1021。

(ii) 若n≥2，神經元σd1優先激發，使用規則a17→a，向神經元σout和σd2各發送一個脈沖。由于突觸(d1,out,3)的權為3，第t+3步，神經元σout和σd2各擁有10個和1個脈沖，神經元σd2可以激發，使用規則a→a，向神經元σout發送一個脈沖,由于突觸(d2,out,2)的權為2，第t+4步，神經元σout擁有12個脈沖，使用遺忘規則a12→λ，移去收到的12個脈沖。第t+5步，神經元σ1激發，接著神經元σd1、神經元σd2、神經元σout和神經元σ1依次激發，不斷重復，直到第t+4n-2步，神經元σ1、σd1和σout中的脈沖數分別為13、17和7，神經元σ1和σd1都可以激發，根據最小串行策略，神經元σ1再次激發，使用規則a8(a5)+/a5→a，剩余8個脈沖，神經元σ1不再激發，同時向神經元σout和σd1各發送一個脈沖。由于突觸突觸(1,out,7)和突觸(1,d1,17)的權分別為7和17，第t+4n-1步，神經元σout和σd1分別擁有14個和34個脈沖，此時神經元σout是系統中當前唯一的活躍神經元，使用規則a14→a，向環境送出第二個脈沖，計算停止，此時產生的脈沖串為0b104n-21。

綜合以上對加法、減法和輸出3個模塊的描述，我們得到在使用最小串行策略下，系統Π正確地模擬了注冊機M，并且系統各模塊中突觸的權最大為17，因此，NRE?NgenHSNP(weight17)成立，定理1得證。

2.2 接受模式下基于最小脈沖數目的均質串行脈沖神經膜系統

定理2NaccHSNP(weight5)=NRE。

證明由Turing-Church猜想可知：NaccHSNP(weight5)?NRE，因此只需要證明NRE?NaccHSNP(weight5)即可。在接受模式下，構造一個基于最小脈沖數目的帶權均質串行脈沖神經膜系統Π′來模擬注冊機M=(m,H,l0,lh,I)，系統Π′中各模塊所含神經元的規則如圖1組成。注冊器1中存儲一個數，其余注冊器都是空的，如果計算最終停止，則該數就被接受。系統Π′由輸入模塊、加法模塊和減法模塊組成，其中加法模塊和減法模塊與定理1中的圖2和圖3相同，輸入模塊如圖5所示。系統Π′要計算(接受)的數n編碼為t2-t1-1的形式，其中t1,t2分別是輸入神經元輸入前兩個脈沖的時刻。

圖5 系統Π′的輸入模塊Fig.5 The INPUT module of system Π′

系統Π′中使用最小串行策略的輸入模塊如圖5所示，初始時神經元σd1，σd2，σd3和σ1分別含有7個、8個、8個和5個脈沖。假設第t步輸入神經元σin從環境收到第一個脈沖，利用規則a→a開始激發，向神經元σd1和σd3各發送一個脈沖。由于突觸(in,d3,5)的權為5，第t+1步神經元σd1和σd3分別擁有8個和13個脈沖，只有神經元可以σd3激發，利用規則a8(a5)+/a5→a，向神經元σd2和σ1各發送1個脈沖，由于突觸(d3,d2,5)和(d3,1,5)的權都為5，此步神經元σd2和σ1都收到5個脈沖。第t+2步神經元σd2擁有13個脈沖，可以激發，利用規則a8(a5)+/a5→a，向神經元σd3和σ1各發送1個脈沖，由于突觸(d2,d3,5)和(d2,1,5)的權都為5，此步神經元σd3和σ1都收到5個脈沖。第t+3步神經元σd3擁有13個脈沖，是系統中唯一的活躍神經元，恢復到第t+1步時的狀態，之后，神經元σd2和σd3將交替激發，神經元σ1每步均收到5個脈沖。

若第t+n+1(n≥1)步，神經元σin從環境收到第二個脈沖，此時神經元σin、σd1和σ1的脈沖數分別為1、8和5n+5，神經元σd2和σd3的脈沖數是13和8(當n為奇數時)或者8和13(當n為偶數時)，根據最小串行的使用策略，神經元σin優先激發，利用規則a→a開始激發，向神經元σd1和σd3各發送一個脈沖。第t+n+2步神經元σd1和σd3的脈沖數分別為9和13(或18)，神經元σd1激發，利用規則a9/a2→a，向神經元σl0、σd2和σd3各發送1個脈沖。第t+n+3步，由于突觸(d1,d2,2)和(d1,d3,2)的權都為2，此步神經元σl0脈沖數為1，σd2和σd3分別擁有脈沖數為15和15，或者是10和20。神經元σl0是系統中唯一的活躍神經元，利用規則a→a開始激發，系統Π′開始模擬注冊機M中的起始指令σl0。系統從環境收到前兩個脈沖的時刻分別為第t步和第t+n+1步，表明系統要接收的數為(t+n+1)-t-1=n。 綜合以上對加法、減法和輸入三個模塊的描述，我們得到在使用最小串行策略下，系統Π′正確地模擬了注冊機M，并且系統各模塊中突觸的權最大為5，因此，NRE?NaccHSNP(weight5)成立，定理2得證。

3 結 論

本文在基于最小脈沖數目的串行脈沖神經膜系統中引入均質性和帶權值的突觸，證明了這類所有神經元中規則相同且含帶權突觸的系統在產生模式和接受模式下都是通用的。本文解決了文獻[16]提出的均質脈沖神經膜系統在最小串行策略下是否具有通用性的問題。

對于使用最小串行策略的脈沖神經膜系統，還有許多問題值得做進一步的探究，比如：將該系統與數據挖掘中的聚類算法相結合[17-19]，構建新的模型；利用該系統來有效解決計算困難問題；設計應用型的均質脈沖神經膜系統等。這些都是基于最小脈沖數目的串行脈沖神經膜系統以后的研究方向。

[2] IONESCU M, PUN G, YOKOMORI T. Spiking neural P systems [J]. Fundamenta Informaticae, 2006, 71(2/3): 279-308.

[3] 潘林強，張興義，曾湘祥，等. 脈沖神經膜計算系統的研究進展及展望[J]. 計算機學報, 2008, 31(12): 2090-2096.

PAN L Q, ZHANG X Y, ZENG X X, et al. Research advances and prospect of spiking neural P systems [J]. Chinese Journal of Computers, 2008, 31(12): 2090-2096.

[4] IONESCU M, PUN G,YOKOMORI T. Spiking neural P systems with an exhaustive use of rules [J]. International Journal of Unconventional Computing, 2007, 3(2): 135-154.

[5] PAN L Q, HOOGEBOOM H J. Spiking neural P systems with astrocytes [J]. Neural Computation, 2012, 24(3): 805-825.

[6] SONG T, PAN L Q, PUN G. Asynchronous spiking neural P systems with local synchronization [J]. Information Sciences, 2013, 21(9): 197-207.

[7] SONG T, PAN L Q, PUN G. Spiking neural P systems with rules on synapses [J]. Theoretical Computer Science, 2014, 529(1): 82-95.

[8] IBARRA O H, PUN A, RODRíGUEZ-PATN A. Sequential SNP systems based on min/max spike number [J]. Theoretical Computer Science, 2009, 410(30): 2982-2991.

[10] JIANG K Q, SONG T, PAN L Q. Universality of sequential spiking neural P systems based on minimum spike number [J]. Theoretical Computer Science, 2013, 499(12): 88-97.

[11] JIANG K Q, HUANG Y F, XU J B, et al. Small universal sequential spiking neural P systems based on minimum spike number [J]. Romanian Journal of Information， 2014, 17(1): 5-18.

[12] WOLFRAM S. Cellular automata as models of complexity [J]. Nature, 1984, 311(4): 419-424.

[13] ZENG X X, ZHANG X Y, PAN L Q. Homogeneous spiking neural P systems [J]. Fundamenta Informaticae, 2009, 97(1): 275-294.

[14] 彭獻武，樊曉平，劉建勛，等. 通用的不帶延遲的同質脈沖神經膜系統[J]. 計算機工程與科學, 2013, 35(3): 1-7.

PENG X W, FANG X P, LIU J X, et al. Universal homogeneous spiking neural P systems without delays [J]. Computer Engineering & Science, 2013, 35(3): 1-7.

[15] KOREC I. Small universal register machines [J].Theoretical Computer Science, 1996, 168(2):267-301.

[16] JIANG K Q, SONG T, PAN L Q. Homogeneous spiking neural P systems working in sequential mode induced by maximum spike number [J]. International Journal of Computer Mathematics, 2013, 90(4): 831-844.

[17] 楊發權，李贊，羅中良. 基于聚類與神經網絡的無線信號聯合調制識別新方法[J]. 中山大學學報(自然科學版), 2015, 54(2):24-29.

YANG F Q, LI Z, LUO Z L. A new specific combination method of wireless communication modulation recognition based on clustering and neural network [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2015, 54(2):24-29.

[18] 黃敏，李爾達，袁媛，等. 基于路網拓撲的聚類分析算法研究與實現[J]. 中山大學學報(自然科學版), 2015, 54(6):99-103.

HUANG M, LI E D, YUAN Y, et al. Research and implementation of clustering analysis algorithm based on road network topology [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2015, 54(6):99-103.

[19] 朱俊勇，逯峰. 基于稀疏子空間聚類的跨域人臉遷移學習方法[J]. 中山大學學報(自然科學版), 2016, 55(5):1-7.

ZHU J Y, LU F. Cross-domain face transfer learning based on sparse subspace clustering [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2016, 55(5):1-7.

ComputationaluniversalityofhomogeneousspikingneuralPsystemsworkinginsequentialmodeinducedbyminimumspikenumber

LILi1,JIANGKeqin2

(1.Anqing Radio and Television University, Anqing 246003, China;2.School of Computer and Information, Anqing Normal University, Anqing 246133, China)

Spiking neural P system is proposed based on the biological phenomenon that the neurons in the neural network are processed by synapses. It has good performance and potential application value. Spiking neural P system working in sequential mode induced by minimum spike number is a special kind of spiking neural computational models. In order to verify the universality of the homogeneous system, weighted synapses are introduced, and the homogeneous spiking neural P systems working in sequential mode induced by minimum spike number are constructed. It is proved that such systems are universal as both generative and acceptive devices by using automata theory, formal language and register machines.

membrane computing; spiking neural P system; sequentiality; homogeneity;register machine

TP301

A

0529-6579(2017)05-0034-07

10.13471/j.cnki.acta.snus.2017.05.005

2016-12-16

國家自然科學基金(61033003)；安徽省自然科學基金(1408085MF131)；安徽高校自然科學研究重點項目(KJ2017A942)

李立(1980年生)，女；研究方向膜計算和數據挖掘；E-mail：lily@aqtvu.cn