一個新的二進(jìn)前向多層網(wǎng)學(xué)習(xí)算法及布爾函數(shù)優(yōu)化實現(xiàn)

一個新的二進(jìn)前向多層網(wǎng)學(xué)習(xí)算法及布爾函數(shù)優(yōu)化實現(xiàn)

本文首先給出二進(jìn)前向多層網(wǎng)幾何學(xué)習(xí)算法［1，2］的一個改進(jìn)策略，提高了原算法的學(xué)習(xí)效率.然后提出一個新的神經(jīng)網(wǎng)絡(luò)啟發(fā)式遺傳幾何學(xué)習(xí)算法(簡稱HGGL算法).HGGL算法采用面向知識的交叉算子和變異算子對幾何超平面進(jìn)行優(yōu)化的劃分，同時確定隱層神經(jīng)元的個數(shù)及連接權(quán)系數(shù)和閾值.對任意布爾函數(shù)，HGGL算法可獲得迄今為止隱節(jié)點數(shù)最少的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu).
　　關(guān)鍵詞:遺傳算法；神經(jīng)網(wǎng)絡(luò)；學(xué)習(xí)算法；布爾函數(shù)

A New Learning Algorithm of Binary Neural Network Used for Optimum Design of Boolean Function

MA Xiao-min　YANG Yi-xian
(Department of Information Engineering,Beijing University of Posts and Telecommunications,Beijing 100876,China)
ZHANG Zhao-zhi
(Institute of System Science,Academia Sinica,Beijing 100080,China)

　　Abstract:A modification to the geometrical learning algorithm of binary neural network,which tries to enhance efficiency of the algorithm,is demonstrated.Then a new Heuristic Genetic Geometrical Learning algorithm(called HGGL algorithm) of the neural network used for arbitrary Boolean function approximation is presented.The algorithm imtroduces knowledge based crossover operator and mutation operator to optimally divede geometrical hypercube and evaluate the number of the hidden neurons,connection weight and threshold. For arbitrary Boolean function,the neural network trained by HGGL algorithm has the fewest number of hidden layer neurons comparde with existed learning algorithms.
　　Key words:genetic algorithm;neural network;learning algorithm;Boolean function

一、引　　言
　　布爾函數(shù)的簡化實現(xiàn)在編碼、密碼、數(shù)字邏輯設(shè)計等領(lǐng)域的理論和應(yīng)用都有重要意義.設(shè)n元布爾函數(shù)f(X)=f(x1,x2,…,xn)為GF(2n)→GF(2)上的函數(shù)，其中GF(2n)為二元域GF(2)上的n維向量空間，xi∈{0,1},i=1,2,…,n.本文研究的核心是利用前向三層神經(jīng)網(wǎng)絡(luò)實現(xiàn)或逼近任意布爾函數(shù)的輸入輸出映射.目前布爾函數(shù)神經(jīng)網(wǎng)絡(luò)實現(xiàn)結(jié)構(gòu)最簡單的是文［1，2］的幾何學(xué)習(xí)算法，把布爾函數(shù)輸入空間2n個二進(jìn)制樣本視作n維超立方體的2n個頂點，隱層的學(xué)習(xí)是通過對學(xué)習(xí)樣本的幾何分析尋找一系列超平面對超立方體進(jìn)行劃分，使得劃分后兩個超平面之間的學(xué)習(xí)樣本頂點擁有相同的布爾函數(shù)輸出，隱層網(wǎng)絡(luò)學(xué)習(xí)過程是劃分超平面的逐次產(chǎn)生過程，直至所有的樣本頂點都被相應(yīng)的超平面分離.最后超平面的個數(shù)等于隱層神經(jīng)元的個數(shù)，超平面方程的系數(shù)即為隱層神經(jīng)元的權(quán)系數(shù).幾何學(xué)習(xí)算法把非線性可分問題轉(zhuǎn)化為若干線性可分問題求解，從而用一個三層網(wǎng)實現(xiàn)任意布爾函數(shù)映射 .然而在幾何學(xué)習(xí)算法的訓(xùn)練過程中，只有劃分超平面決定了全部布爾函數(shù)樣本頂點，學(xué)習(xí)才告結(jié)束.本文提出并證明了一個新的學(xué)習(xí)結(jié)束的判別條件，減少了可能的隱層神經(jīng)元個數(shù)及學(xué)習(xí)時間.文［1，2］學(xué)習(xí)算法樣本的先后排序?qū)W(xué)習(xí)效果影響很大，對于變量個數(shù)少的布爾函數(shù)可以利用窮舉法獲得最優(yōu)的神經(jīng)網(wǎng)絡(luò)實現(xiàn)結(jié)構(gòu)，而對于變量個數(shù)多的布爾函數(shù)(如編碼密碼中的布爾函數(shù))，這種排序的搜索問題實際上是一個NP難解問題.在對幾何學(xué)習(xí)算法分析改進(jìn)后，本文針對幾何學(xué)習(xí)提出一種啟發(fā)式遺傳算法，尋找最優(yōu)的排序路徑，形成完整的HGGL學(xué)習(xí)算法.最后通過典型的例子說明了算法的特點及有效性.

二、幾何學(xué)習(xí)算法的改進(jìn)策略
　　定義1　在學(xué)習(xí)過程中，已由超平面分離的線性可分樣本頂點稱為真頂點；其余樣本稱假頂點；確定超平面選擇的初始樣本頂點稱核心頂點.
　　定義2　設(shè)布爾函數(shù)數(shù)神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)樣本集合U={X1,X2,…,XN}，其中N=2n,Xi={xi1,xi2，…,xin}，則以某一個樣本為核心頂點的真頂點樣本集合稱為真頂點分離集VK={X1,X2,…,XK}，其中K為集合中真頂點樣本的個數(shù).XI為初始核心頂點.
　　神經(jīng)網(wǎng)絡(luò)隱層的學(xué)習(xí)過程實質(zhì)上是真頂點樣本集合VK擴(kuò)展過程：在U-VK中隨機選擇樣本頂點Xk+1，滿足f(X,X∈Vk)=f(X,X∈Vk+1)，并計算集合中心：(Ci/C0)=(1/(k+1))其中C0=k+1,x′i={0,1};i=1,2,…,n,對于Xj∈{Vk,Xk+1},，計算…,k+1；對于Xj∈U-{Vk,Xk+1},計算Tmin=minj,j=k+2,…,2n.這樣判別Xk+1是否可擴(kuò)展為真頂點的條件為：

Tmax＜Tmin　(1)

　　如果Xk+1可擴(kuò)展，即Vk與U-Vk線性可分，Vk+1={Xk，Xk+1}，得到權(quán)系數(shù)wi=2Ci-C0和閾值T=［(Tmax+Tmin)/2］,［x］表示取整函數(shù)，否則尋找新的樣本頂點，不斷擴(kuò)展直至U-Vk不再存在可擴(kuò)展的與XK有相同布爾函數(shù)輸出的頂點樣本，則一個分離超平面形成，w1j={wi},Tj=T，這時有：當(dāng);當(dāng)0，從而確定一個隱層神經(jīng)元，再令Vk的輸出取反，K=k,重復(fù)擴(kuò)展.不斷得到新的超平面或隱層神經(jīng)元，直至U-Vk=φ(所有樣本頂點訓(xùn)練完畢).最后得到L個超平面及相應(yīng)的神經(jīng)網(wǎng)絡(luò)隱層結(jié)構(gòu).
　　輸出層的學(xué)習(xí)目的就是組合隱層神經(jīng)元的輸出以產(chǎn)生理想的布爾函數(shù)輸出.輸出層的連接權(quán)系數(shù)及閾值w2j與θ按以下規(guī)則確定［1，2］：

　(2)

　　文［1，2］中在隱層的訓(xùn)練中，僅當(dāng)所有的學(xué)習(xí)樣本頂點都擴(kuò)展為真頂點分離集合，學(xué)習(xí)才告結(jié)束.在確定超平面的過程中，下面定理將說明在某些情形下，這個學(xué)習(xí)結(jié)束條件是不必要的.這樣會減少若干分離超平面，意味著減少隱層神經(jīng)元.
　　定理：在真頂點分離集合VK的擴(kuò)展過程中，如果U-VK中所有樣本頂點布爾函數(shù)輸出相同，則只需要一個超平面(或一個隱層神經(jīng)元)即可把這些樣本與VK中的其它樣本區(qū)分開來，并得到正確的布爾函數(shù)輸出.
　　證明：設(shè)分離集合VK中的K個樣本由L個超平面確定，根據(jù)真頂點分離集合的擴(kuò)展原理可知：

而j=K+1,…,2n,t=1,2,…,L
故當(dāng)樣本輸入屬于VK，至少有一個隱層神經(jīng)元輸出為1，當(dāng)樣本輸入不屬于VK，則隱層所有神經(jīng)元輸出皆為0.因此若VK以外的樣本布爾函數(shù)值皆相同，超平面L就可以來區(qū)分這些樣本，不需再增加超平面，即使U-VK中有一些樣本不滿足式(1)真頂點的擴(kuò)展條件，仍可得到正確輸出.證畢
　　上述定理為幾何學(xué)習(xí)算法學(xué)習(xí)結(jié)束提供了新的判別條件：即在真頂點分離集擴(kuò)展過程中，當(dāng)U=Vk中所有樣本布爾函數(shù)值相同時，則學(xué)習(xí)結(jié)束.

三、HGGL算法原理及其實現(xiàn)
　　前述幾何學(xué)習(xí)算法真頂點分離集擴(kuò)展過程中，實現(xiàn)同一布爾函數(shù)初始核心頂點樣本的選擇及真頂點擴(kuò)展的次序不同，需要，隱層神經(jīng)元的個數(shù)差異很大.文［1，2］采用窮舉法，即每種可能的初始點及真頂點集合都試一遍，然后找到最優(yōu)的一種組合和神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu).變量個數(shù)為n的布爾函數(shù)，其排列的可能性有(2n)!，因此對于變量很多的布爾函數(shù)很難在有限時間內(nèi)實現(xiàn).本文引入遺傳算法搜索樣本學(xué)習(xí)的最優(yōu)排序即布爾函數(shù)實現(xiàn)復(fù)雜度最小的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu).為避免加大樣本頂點超平面劃分的搜索空間，本文沒有采用基本的遺傳算子，而是基于知識采用了啟發(fā)式遺傳策略尋求此問題的最優(yōu)解.
　　1．問題的編碼及遺傳群體的產(chǎn)生
　　把幾何學(xué)習(xí)算法中樣本真頂點分離集的擴(kuò)展過程看作是樣本頂點在真頂點分離集中依次序排列的過程，遺傳算法的任務(wù)是尋找一組或若干組最優(yōu)真頂點樣本的排列，使得神經(jīng)網(wǎng)絡(luò)實現(xiàn)布爾函數(shù)所需隱層神經(jīng)元個數(shù)最少.遺傳算法的每個基因串按如下方式編碼：P={p1,p2,…,p2n},pi∈{1,2,…,2n},i=1,2,…,2n
　　首先把學(xué)習(xí)樣本從1～2n按次序逐個編號表示樣本在基因串中的順序位置，即P表示真頂點分離集中各樣本參與學(xué)習(xí)的先后順序，代表序號為pi的樣本在時刻i擴(kuò)展參與學(xué)習(xí).根據(jù)啟發(fā)式遺傳算法的要求，P中所代表樣本頂點必須為合法真頂點，所謂合法真頂點應(yīng)滿足如下判別條件：設(shè)Vi-1={Xp1,Xp2，…,Xpi-1}對任意pi代表的新樣本Xpi，①與P中已有樣本點序號沒有重復(fù)；②滿足式(1)真頂點分離集擴(kuò)展條件.
　　在遺傳算法中，對每一個基因串都有一個衡量其特性的適合度函數(shù)作如下定義：

fa(P)=1/L　(3)

這里L(fēng)表示P排列下，幾何劃分的超平面?zhèn)€數(shù)或神經(jīng)網(wǎng)絡(luò)所需神經(jīng)元的個數(shù)，超平面?zhèn)€數(shù)越少，則P的適合度函數(shù)越大，適合度大的基因串繁殖下一代的概率也大.
　　2.遺傳算子的設(shè)計
　　遺傳算子通過交叉、變異、選擇三個遺傳算子以產(chǎn)生下一代更優(yōu)秀性能的群體.
　　交叉是指把父代基因串的部分結(jié)構(gòu)加以替換重組而生成新個體的操作，通過交叉子代個體繼承了父代個體遺傳特性，交叉是HGGL算法尋找最優(yōu)解的主要手段，由于基于神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的幾何超平面劃分問題采用的是樣本序號的編碼，若采取簡單的一點交叉或多點交叉策略，必然以極大的概率產(chǎn)生非法的真頂點分離集合.因此本文引入了基于知識的交叉方法，對于父代基因串P={p1,p2,…,p2n}，交叉算子構(gòu)造后代：Q={q1,q2,…,q2n},qi∈{1,2,…，2n},i=1,2,…,2n,以概率Pc從上一代群體中選取適合度較大的基因串進(jìn)行交叉：
　?、匐S機選取一個樣本頂點，并把其序號作為初始核心樣本序號q1.集合V1={Xq1}；
　?、贔or K=1 to 2n-1.給定Vk={Xq1,…,Xqk}，在父代個體P中尋找與qk鄰接的序號，設(shè)為pm.并根據(jù)式(1)判別Xpm是否為合法真頂點集合，如果是，則令qk+1=pm；如果不是，則在U-Vk中尋找新的合法真頂點添加到真頂點集合，尋找途徑為：首先尋找與qk輸出相同的樣本頂點；如果找不到合法點則找與qk輸出相異的頂點；
　?、壑貜?fù)②相類似的操作，不斷繼承父代基因串的相鄰樣本序號，或?qū)ふ倚碌暮戏颖镜玫絨3,q4,…，直至構(gòu)造出完整的子代基因串Q.如果某一時刻i,U-Vk的樣本滿足定理1的條件，交叉提前完成，qi,qi+1，…,q2n可隨意排列.
　　變異算子是對群體中的個體串的某些基因座上的基因值作變動，以幫助遺傳算法的交叉算子擺脫在進(jìn)化過程中使得群體陷于搜索空間中某個超平面的局面.從而加速向全局最優(yōu)解收斂.考慮到一般的變異策略也會產(chǎn)生非法的真頂點分離集合，引入基于知識的變異方法如下：
　　①以很小的變異概率Pm，在上一代群體中隨機選取父代基因串中輸出相同的兩個樣本序號，交換其位置；
　　②判別被操作的基因串是否為合法真頂點分離集合，如果是則變異結(jié)束；
　?、鄯駝t，以擴(kuò)展過程中第一個不合法樣本點為起點，依據(jù)前述的交叉方法，構(gòu)造新的合法后代基因串.選擇即是把上一代群體中的個體按一定規(guī)律選中繁衍下一代.HGGL的選擇策略為：
　?、儆嬎闵弦淮恳粋€個體的適合度函數(shù)fa；②以選擇概率Ps比例產(chǎn)生適合度函數(shù)值較大的個體作為下一代群體中的個體.

四、HGGL算法實現(xiàn)流程及計算機仿真結(jié)果
　　給定任意布爾函數(shù)學(xué)習(xí)樣本及其相應(yīng)的輸出，HGGL創(chuàng)建一個復(fù)雜性最低的三層前向神經(jīng)網(wǎng)絡(luò)，完全實現(xiàn)布爾函數(shù)的輸入輸出映射關(guān)系.HGGL算法的主要流程可歸納如下：
　　①初始化　根據(jù)具體任務(wù)，確定遺傳算法的交叉概率Pc(0.6～0.9)，變異概率Pm(0.01～0.15)，選擇概率Ps(0.8～0.95)，確定群體大小N，一般取20～60，給定布爾函數(shù)變量個數(shù)n，樣本個數(shù)M=2n.
　?、趩栴}編碼　第一代群體的產(chǎn)生，以幾何學(xué)習(xí)算法確定隱層神經(jīng)元連接系數(shù)及閾值集合，產(chǎn)生N個個體，并計算每個個體的適合度.
　?、巯乱淮后w的進(jìn)化　對上一代群體中的個體進(jìn)行交叉、變異、選擇等遺傳操作，保留適應(yīng)值最大的個體直接進(jìn)入下一代群體，產(chǎn)生下一代N個個代，并計算每個個體的適合度及超平面方程的系數(shù)集合.
　　④重復(fù)②③直至滿足下面的收斂條件　a.進(jìn)化的代數(shù)等于預(yù)先給定的Gmax代群體;b.同一代群體中所有基因串的適合度函數(shù)幾乎相等.
　?、葸x擇最優(yōu)的個體作為隱層學(xué)習(xí)的最終結(jié)果　隱層神經(jīng)結(jié)構(gòu)已經(jīng)確定.
　?、掭敵鰧拥膶W(xué)習(xí)　根據(jù)式(2)輸出層學(xué)習(xí)方法，確定輸出層的權(quán)系數(shù)及閾值.
　　本文通過C語言仿真實現(xiàn)了HGGL算法，對許多布爾函數(shù)進(jìn)行學(xué)習(xí)，得到了一系列很好的結(jié)果，下面給出其中一個典型例子.
　　例　5位布爾函數(shù)的實現(xiàn)［1］，其布爾函數(shù)輸出可表示為：
　　f(0～31)=(0,0,1,0,1,1,0,1,1,1,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,0,1,0,1,0,0,0)
　　取輸入個數(shù)n=5，超立方體頂點個數(shù)為32，交叉概率Pc=0.8,變異概率Pm=0.01；選擇概率Ps=0.9,遺傳算法群體個數(shù)N=30,每個串基因的長度為32.HGGL經(jīng)20代的遺傳學(xué)習(xí)，獲得的最優(yōu)排序其相應(yīng)的超平面參數(shù)(即隱層神經(jīng)元的權(quán)系數(shù)及閾值)如表1所示，布爾函數(shù)只需要3個隱層神經(jīng)元.由式(2)確定輸出層神經(jīng)元連接權(quán)系數(shù)，實現(xiàn)此布爾函數(shù)的三層神經(jīng)網(wǎng)絡(luò)如圖1所示，經(jīng)實驗驗證：HGGL算法能夠可靠收斂，如果沒有變異，算法在很多情形下收斂不到最優(yōu)值，而沒有每代最優(yōu)基因串的直接繼承，收斂曲線會出現(xiàn)振蕩，收斂得不到保證.同樣的布爾函數(shù)文［4］需要15個隱層神經(jīng)元，文［3］需要至少8個神經(jīng)元，而文［1］的幾何學(xué)習(xí)算法經(jīng)窮舉得到的優(yōu)化結(jié)果為4個隱層神經(jīng)元.由于本文采用新的學(xué)習(xí)判別準(zhǔn)則和遺傳算法尋優(yōu)，得到了目前最好的實現(xiàn)結(jié)果.

表1　最優(yōu)排序結(jié)果及超平面系數(shù)