魏衡華，彭 飛（中國科學(xué)技術(shù)大學(xué) 自動(dòng)化系，安徽 合肥230027）

數(shù)字識(shí)別前景廣闊，廣泛應(yīng)用于郵政編碼的識(shí)別、汽車牌照的識(shí)別以及個(gè)人成績單的識(shí)別。相對(duì)于印刷體數(shù)字識(shí)別，無約束手寫體的識(shí)別是模式識(shí)別領(lǐng)域的難點(diǎn)，也是目前的一個(gè)研究熱點(diǎn)。近幾年來眾多學(xué)者對(duì)手寫體進(jìn)行了較多的研究，提出了多種算法，不過當(dāng)前運(yùn)用較好的主流算法還是以統(tǒng)計(jì)、神經(jīng)網(wǎng)絡(luò)、聚類分析的識(shí)別算法為主。

神經(jīng)網(wǎng)絡(luò)具有很強(qiáng)的學(xué)習(xí)性和自適應(yīng)性，對(duì)于解決目標(biāo)識(shí)別和模式分類具有較大的潛力。其中BP模型被廣泛地應(yīng)用于模式分類、模式識(shí)別等方面，但BP算法收斂速度慢，且很容易陷入局部極小點(diǎn)。遺傳算法具有并行搜索、效率高、不存在局部收斂問題等優(yōu)點(diǎn)而被廣泛應(yīng)用。然而傳統(tǒng)的遺傳算法帶有一定程度的隨機(jī)性和盲從性，且有過早收斂的現(xiàn)象。為了克服遺傳算法的這些缺點(diǎn)，本文采用正交遺傳算法，克服了初始種群的盲目性，并對(duì)選擇過程做了改進(jìn)，不再單純地淘汰劣勢個(gè)體，以保證種群的多樣性。最后，本文將改進(jìn)的遺傳算法應(yīng)用到BP網(wǎng)絡(luò)中，提出遺傳BP神經(jīng)網(wǎng)絡(luò)，通過遺傳算法的全局優(yōu)化能力提高BP神經(jīng)網(wǎng)絡(luò)對(duì)手寫數(shù)字樣本訓(xùn)練的速度。

1 BP神經(jīng)網(wǎng)絡(luò)

BP網(wǎng)絡(luò)是一種典型的前向神經(jīng)網(wǎng)絡(luò)，主要由輸入層、隱含層、輸出層組成，它的基本結(jié)構(gòu)如圖1所示。隱含層可以是單層或多層。每一層由一個(gè)或者多個(gè)節(jié)點(diǎn)組成，同一層的節(jié)點(diǎn)之間沒有連接，而層與層之間的節(jié)點(diǎn)是全連接的，即每一層的節(jié)點(diǎn)與前面一層的所有節(jié)點(diǎn)都有連接。

BP網(wǎng)絡(luò)的核心是BP算法，BP算法由兩部分組成：信息的正向傳遞和誤差的反向傳播。在正向傳播中，輸入信息從輸入層經(jīng)隱含層逐層計(jì)算傳向輸出層，每一層的輸出作用于下一層神經(jīng)元（即為圖中的節(jié)點(diǎn)）的輸入。如果在輸出層沒有得到期望的輸出，則計(jì)算輸出層的誤差變化值，然后轉(zhuǎn)向反向傳播，通過網(wǎng)絡(luò)將誤差信號(hào)沿原來的連接通路反傳回來，修改各層神經(jīng)元的權(quán)值直至達(dá)到期望目標(biāo)。

雖然BP網(wǎng)絡(luò)得到了廣泛的應(yīng)用，但它也存在一些自身的不足和限制，例如訓(xùn)練時(shí)間較長、容易陷入局部最小值等[1]。

2 改進(jìn)的遺傳算法

遺傳算法的操作內(nèi)容主要有種群初始化操作、選擇操作、交叉操作、變異操作。

2.1 種群的初始化

對(duì)于沒有先驗(yàn)知識(shí)的優(yōu)化問題，傳統(tǒng)遺傳算法的初始種群一般采取完全隨機(jī)的方法產(chǎn)生，這樣選出的初始群體帶有一定的盲目性，也很難選出具有代表性的群體。本文采用正交化設(shè)計(jì)方法來初始化種群，利用正交設(shè)計(jì)所選的樣本組合能夠很好地代表所有可能的組合并且正交設(shè)計(jì)在數(shù)值優(yōu)化方面已經(jīng)被證明具有很好的搜索能力[2]，這樣獲得的初始種群更具有魯棒性和統(tǒng)計(jì)合理性。

2.1.1 構(gòu)造正交設(shè)計(jì)矩陣

正交設(shè)計(jì)矩陣的設(shè)計(jì)方法很多，參考文獻(xiàn)[3]中提出的設(shè)計(jì)方法便于計(jì)算。其中Q表示基因變量變化的水平數(shù)，N 表示基因個(gè)數(shù)， 正交設(shè)計(jì)矩陣記為 LM(QN)=[ai，j]M×N，M=QJ且有：

其算法過程如下：

(1)構(gòu)造正交設(shè)計(jì)矩陣基本列

(2)按如下方法構(gòu)造非基本列

(3)給所有 ai，j加 1，其中 1≤i≤M，1≤j≤N。

2.1.2 生成初始種群

由于不知道任何關(guān)于BP網(wǎng)絡(luò)權(quán)值和閾值全局最小的信息，因此，初始種群的染色體均勻分布在可行解空間是合理的，定義xi為第i個(gè)因素，這樣，每個(gè)染色體都有N個(gè)因素，因?yàn)檫@些因素是連續(xù)變化的，所以要把每個(gè)因素離散化為有限個(gè)數(shù)量的值。具體地，把xi的區(qū)間[l，u]等分成Q個(gè)水平，這樣就可以得到初始種群：

其中 ti，j為初始種群矩陣 T元素的值；δ為一個(gè)很小的隨機(jī)數(shù)，一般要求|δ|＜＜。

然而對(duì)于訓(xùn)練手寫數(shù)字樣本的BP網(wǎng)絡(luò)，其需要訓(xùn)練的網(wǎng)絡(luò)權(quán)值和閾值數(shù)量很大。N過大，會(huì)導(dǎo)致M的值也很大，如果用這樣龐大的矩陣作為初始種群不僅會(huì)占用大量的存儲(chǔ)空間，還會(huì)延長遺傳算法的迭代時(shí)間。N值由問題本身決定無法改變，若Q值過小，將不能體現(xiàn)種群的多樣性，也降低了基因變量的精度，本文采用從T中隨機(jī)選擇n個(gè)互不相同的行作為初始種群。

2.2 選擇父代個(gè)體

采用賭輪盤選擇方法對(duì)于復(fù)雜的神經(jīng)網(wǎng)絡(luò)優(yōu)化問題容易過早收斂，為了保證群體的多樣性，減緩算法的收斂速度，在選擇過程中，低于適應(yīng)度平均值的個(gè)體被淘汰，被淘汰的個(gè)體從T中隨機(jī)選擇一行作為新加入的種群個(gè)體，并加大δ的可變范圍。為了使種群具有更好的多樣性，當(dāng)?shù)陀谄骄m應(yīng)度的個(gè)體數(shù)量小于1/4種群數(shù)量時(shí)，被淘汰的個(gè)體數(shù)量將保持在1/4種群數(shù)量。

2.3 交叉操作

在實(shí)數(shù)編碼中常見的交叉算子有單點(diǎn)交叉算子、多點(diǎn)交叉算子、算術(shù)交叉算子等[4]。經(jīng)過比較，在BP網(wǎng)絡(luò)權(quán)值的優(yōu)化中采用算術(shù)交叉算子效果較好。設(shè)父母點(diǎn)為X、Y，后代為 X′、Y′，則：

其中 a稱為交叉算子，且 a∈[0，1]。

2.4 變異操作

變異就是子個(gè)體變量以很小的概率或步長發(fā)生轉(zhuǎn)變，變異概率一般都很小，對(duì)于實(shí)數(shù)編碼簡單而有效的方法就是直接將子個(gè)體的某個(gè)變量用一個(gè)隨機(jī)數(shù)替代。為了減緩局部收斂，本文采用自適應(yīng)變異操作，根據(jù)迭代次數(shù)的不同設(shè)置不同的變異概率，當(dāng)?shù)螖?shù)＜0.25 maxgen時(shí)，Pm=0.01； 當(dāng) 0.25 maxgen＜迭代次數(shù)＜0.75 maxgen時(shí)，Pm=0.2；當(dāng)?shù)螖?shù)>0.75 maxgen時(shí)，Pm=0.4。

3 應(yīng)用實(shí)例及仿真

本文以USPS手寫數(shù)字樣本集中1 100個(gè)樣本數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，每個(gè)樣本數(shù)據(jù)存儲(chǔ)著16×16手寫數(shù)字圖像樣本，所以神經(jīng)網(wǎng)絡(luò)的輸入層數(shù)為 256；0～9總共10種類別，所以輸出層數(shù)設(shè)為10；根據(jù)經(jīng)驗(yàn)隱含層一般設(shè)置為+n（其中I表示輸入層神經(jīng)元的個(gè)數(shù)，Q表示輸出層神經(jīng)元的個(gè)數(shù)，n取 0～10），本文隱含層的個(gè)數(shù)設(shè)為16；訓(xùn)練目標(biāo)epochs=0.01。BP網(wǎng)絡(luò)采用L-M訓(xùn)練方法。改進(jìn)遺傳算法的參數(shù)設(shè)置如下：種群規(guī)模sizepop=20；交叉概率 Pc=0.6；迭代次數(shù) maxgen=60；權(quán)值和閾值的取值范圍為[-2，2]；水平數(shù)Q=9。

下面分別利用BP網(wǎng)絡(luò)和改進(jìn)遺傳-BP網(wǎng)絡(luò)分別對(duì)USPS手寫數(shù)字樣本集中1 100個(gè)手寫數(shù)字進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖2所示。

表1所示為兩種算法的性能比較，從中可以明顯地看出改進(jìn)的遺傳-BP算法比單純的BP算法具有更快的訓(xùn)練速度。而手寫數(shù)字的識(shí)別精度很大程度上取決于訓(xùn)練樣本的數(shù)量，因此，提高大量樣本的訓(xùn)練速度對(duì)手寫數(shù)字識(shí)別具有重要的意義。

表1 兩種算法的性能比較

本文針對(duì)BP網(wǎng)絡(luò)訓(xùn)練大量數(shù)據(jù)時(shí)，訓(xùn)練時(shí)間長、易陷入局部最優(yōu)等問題，提出將BP網(wǎng)絡(luò)與遺傳算法相結(jié)合，并用改進(jìn)的遺傳算法來克服傳統(tǒng)遺傳算法收斂速度慢的缺點(diǎn)，通過計(jì)算正交設(shè)計(jì)矩陣來提高初始種群的質(zhì)量，有效地增強(qiáng)了算法的穩(wěn)定性和全局搜索能力，也說明了此算法具有廣泛的應(yīng)用價(jià)值。

[1]叢爽.神經(jīng)網(wǎng)絡(luò)、模糊系統(tǒng)及其在運(yùn)動(dòng)控制中的應(yīng)用[M].合肥：中國科學(xué)技術(shù)大學(xué)出版社，2001.

[2]LEUNG Y W，WANG Y P.An orthogonal genetic algorithm with quantization for global numerical optimization[J].IEEE Trans.on Evolutionary Computation，2001，5(1)：41-53.

[3]王宇平.進(jìn)化計(jì)算的理論和方法[M].北京：科學(xué)出版社，2011.

[4]王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社，2004.