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

本文首先給出二進(jìn)前向多層網(wǎng)幾何學(xué)習(xí)算法［1，2］的一個(gè)改進(jìn)策略，提高了原算法的學(xué)習(xí)效率.然后提出一個(gè)新的神經(jīng)網(wǎng)絡(luò)啟發(fā)式遺傳幾何學(xué)習(xí)算法(簡(jiǎn)稱(chēng)HGGL算法).HGGL算法采用面向知識(shí)的交叉算子和變異算子對(duì)幾何超平面進(jìn)行優(yōu)化的劃分，同時(shí)確定隱層神經(jīng)元的個(gè)數(shù)及連接權(quán)系數(shù)和閾值.對(duì)任意布爾函數(shù)，HGGL算法可獲得迄今為止隱節(jié)點(diǎn)數(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ù)的簡(jiǎn)化實(shí)現(xiàn)在編碼、密碼、數(shù)字邏輯設(shè)計(jì)等領(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ò)實(shí)現(xiàn)或逼近任意布爾函數(shù)的輸入輸出映射.目前布爾函數(shù)神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)結(jié)構(gòu)最簡(jiǎn)單的是文［1，2］的幾何學(xué)習(xí)算法，把布爾函數(shù)輸入空間2n個(gè)二進(jìn)制樣本視作n維超立方體的2n個(gè)頂點(diǎn)，隱層的學(xué)習(xí)是通過(guò)對(duì)學(xué)習(xí)樣本的幾何分析尋找一系列超平面對(duì)超立方體進(jìn)行劃分，使得劃分后兩個(gè)超平面之間的學(xué)習(xí)樣本頂點(diǎn)擁有相同的布爾函數(shù)輸出，隱層網(wǎng)絡(luò)學(xué)習(xí)過(guò)程是劃分超平面的逐次產(chǎn)生過(guò)程，直至所有的樣本頂點(diǎn)都被相應(yīng)的超平面分離.最后超平面的個(gè)數(shù)等于隱層神經(jīng)元的個(gè)數(shù)，超平面方程的系數(shù)即為隱層神經(jīng)元的權(quán)系數(shù).幾何學(xué)習(xí)算法把非線(xiàn)性可分問(wèn)題轉(zhuǎn)化為若干線(xiàn)性可分問(wèn)題求解，從而用一個(gè)三層網(wǎng)實(shí)現(xiàn)任意布爾函數(shù)映射 .然而在幾何學(xué)習(xí)算法的訓(xùn)練過(guò)程中，只有劃分超平面決定了全部布爾函數(shù)樣本頂點(diǎn)，學(xué)習(xí)才告結(jié)束.本文提出并證明了一個(gè)新的學(xué)習(xí)結(jié)束的判別條件，減少了可能的隱層神經(jīng)元個(gè)數(shù)及學(xué)習(xí)時(shí)間.文［1，2］學(xué)習(xí)算法樣本的先后排序?qū)W(xué)習(xí)效果影響很大，對(duì)于變量個(gè)數(shù)少的布爾函數(shù)可以利用窮舉法獲得最優(yōu)的神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)結(jié)構(gòu)，而對(duì)于變量個(gè)數(shù)多的布爾函數(shù)(如編碼密碼中的布爾函數(shù))，這種排序的搜索問(wèn)題實(shí)際上是一個(gè)NP難解問(wèn)題.在對(duì)幾何學(xué)習(xí)算法分析改進(jìn)后，本文針對(duì)幾何學(xué)習(xí)提出一種啟發(fā)式遺傳算法，尋找最優(yōu)的排序路徑，形成完整的HGGL學(xué)習(xí)算法.最后通過(guò)典型的例子說(shuō)明了算法的特點(diǎn)及有效性.

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

Tmax＜Tmin　(1)

　　如果Xk+1可擴(kuò)展，即Vk與U-Vk線(xiàn)性可分，Vk+1={Xk，Xk+1}，得到權(quán)系數(shù)wi=2Ci-C0和閾值T=［(Tmax+Tmin)/2］,［x］表示取整函數(shù)，否則尋找新的樣本頂點(diǎn)，不斷擴(kuò)展直至U-Vk不再存在可擴(kuò)展的與XK有相同布爾函數(shù)輸出的頂點(diǎn)樣本，則一個(gè)分離超平面形成，w1j={wi},Tj=T，這時(shí)有：當(dāng);當(dāng)0，從而確定一個(gè)隱層神經(jīng)元，再令Vk的輸出取反，K=k,重復(fù)擴(kuò)展.不斷得到新的超平面或隱層神經(jīng)元，直至U-Vk=φ(所有樣本頂點(diǎn)訓(xùn)練完畢).最后得到L個(gè)超平面及相應(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í)樣本頂點(diǎn)都擴(kuò)展為真頂點(diǎn)分離集合，學(xué)習(xí)才告結(jié)束.在確定超平面的過(guò)程中，下面定理將說(shuō)明在某些情形下，這個(gè)學(xué)習(xí)結(jié)束條件是不必要的.這樣會(huì)減少若干分離超平面，意味著減少隱層神經(jīng)元.
　　定理：在真頂點(diǎn)分離集合VK的擴(kuò)展過(guò)程中，如果U-VK中所有樣本頂點(diǎn)布爾函數(shù)輸出相同，則只需要一個(gè)超平面(或一個(gè)隱層神經(jīng)元)即可把這些樣本與VK中的其它樣本區(qū)分開(kāi)來(lái)，并得到正確的布爾函數(shù)輸出.
　　證明：設(shè)分離集合VK中的K個(gè)樣本由L個(gè)超平面確定，根據(jù)真頂點(diǎn)分離集合的擴(kuò)展原理可知：

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

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

fa(P)=1/L　(3)

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

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

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