劉 冰，劉廣璞

(中北大學(xué)機(jī)械工程與自動(dòng)化學(xué)院，山西太原 030051)

0 引言

人臉識(shí)別是模式識(shí)別和機(jī)器視覺領(lǐng)域中最有挑戰(zhàn)性的課題之一，同時(shí)也具有廣泛的應(yīng)用意義。它的重要性越來越引起人們的重視，所以在近幾年研究學(xué)者們找到了許多人臉識(shí)別的方法。

支持向量機(jī)(Support Vector Machine，SVM)是由 AT＆T貝爾實(shí)驗(yàn)室的Vapnik及其研究小組于20世紀(jì)90年代中期提出的一種新的模式識(shí)別方法，具有很強(qiáng)的泛化能力，在解決小樣本、局部極小點(diǎn)、非線性等問題上具有顯著的優(yōu)勢(shì)，并且已經(jīng)成功應(yīng)用到了許多領(lǐng)域。經(jīng)典的SVM訓(xùn)練是對(duì)若干個(gè)子問題的逐一優(yōu)化，該方法可能會(huì)導(dǎo)致結(jié)果只有一個(gè)次優(yōu)解，并且分類速度難以滿足實(shí)驗(yàn)的要求。文獻(xiàn)［1］提出一種基于遺傳算法的SVM訓(xùn)練方法，文中通過遺傳算法對(duì)SVM的參數(shù)進(jìn)行優(yōu)化。文獻(xiàn)［2］提出了一種基于混沌搜索的遺傳算法，此算法應(yīng)用在短波通信控制器的診斷分類器中，得到了良好的分辨率。針對(duì)以上問題，作者受此啟發(fā)，將此算法引進(jìn)到人臉識(shí)別中，以改善傳統(tǒng)遺傳算法容易進(jìn)入“早熟”等缺點(diǎn)，并提高計(jì)算速度和識(shí)別準(zhǔn)確率。

1 支持向量機(jī)基本概念

假設(shè)一組訓(xùn)練樣本{(x1+y1)，(x2+y2)，…，(xn+yn)}，其中 x∈R，類標(biāo)簽 y∈{－1，+1}，即只有兩個(gè)樣本。根據(jù)訓(xùn)練樣本確定最大分類間隔的分割超平面，設(shè)最優(yōu)超平面方程為w·x+b=0。其中w為分類超平面的權(quán)向量，b是分類閾值。對(duì)線性可分的情形，若得到這個(gè)超平面，需要求解下面的二次規(guī)劃問題:

約束條件:yi［(xi·w)－b］≥1，i=1，2，…，n

此時(shí)，利用Lagrange優(yōu)化方法把上述最優(yōu)分類面問題轉(zhuǎn)化為對(duì)偶問題:

其中，C是對(duì)現(xiàn)行不可分樣本的分類錯(cuò)誤代價(jià)系數(shù)，αi為拉格朗日乘數(shù)，k(xi，xj)為RBF核函數(shù)。

2 基本遺傳算法與基于變尺度的混沌遺傳算法

遺傳算法是模仿生物遺傳和進(jìn)化機(jī)制的一種優(yōu)化方法，能夠?qū)崿F(xiàn)全局的并行搜索，具有快捷、簡(jiǎn)單、魯棒性好的特點(diǎn)，一般過程包含幾個(gè)步驟:編碼、生成初始群體、選擇、交叉、變異等，通過迭代的方法產(chǎn)生新群體，進(jìn)而得到最優(yōu)解。但通過學(xué)者多年的實(shí)驗(yàn)研究表明，在實(shí)際的應(yīng)用當(dāng)中，遺傳算法會(huì)出現(xiàn)局部尋優(yōu)能力較差、出現(xiàn)“早熟”等現(xiàn)象。所以文獻(xiàn)［2］提出了一種新的遺傳算法——混沌遺傳算法。

混沌(Chaos)是自然界中較為普遍的現(xiàn)象，它看似混亂無序，卻有精致的內(nèi)在結(jié)構(gòu)，具有“遍歷性”、“規(guī)律性”和“隨機(jī)性”等特點(diǎn)，在一定范圍內(nèi)能按照自身的規(guī)律不重復(fù)地遍歷所有的狀態(tài)。計(jì)算機(jī)上，常用Logistic迭代方程來模擬混沌現(xiàn)象:xi+1=uxi(1－xi)(u為吸引子，0＜u≤4)，利用此方程進(jìn)行迭代，能夠得到混沌序列 X=［x1，x2，…，xn］(n為迭代次數(shù))。

混沌遺傳算法(CGA)，結(jié)合混沌現(xiàn)象的遍歷性和遺傳算法的反演性，利用混沌映射通過對(duì)原群體進(jìn)行變換得到混沌群體，再進(jìn)行遺傳步驟，利用Logistic迭代方程進(jìn)行迭代，得到混沌群體，實(shí)現(xiàn)對(duì)原群體的映射［3］。

2.1 變尺度操作

變尺度混沌算法利用混沌現(xiàn)象的特點(diǎn)，將混沌變量映射到待尋優(yōu)變量區(qū)間，不斷縮小優(yōu)化變量的搜索范圍并且提高搜索精度，所以具有較高的搜索效率［4］。

設(shè)當(dāng)前待尋優(yōu)變量C的搜索區(qū)間為［a1，b1］，在一次尋優(yōu)過程后得到的最優(yōu)值為C*，則利用下面的方程進(jìn)行變尺度操作:

其中，μ為尺度參數(shù)，μ∈(0，0.5)，μ 越大，搜索區(qū)間縮減程度越小;i是變尺度的次數(shù)。

同時(shí)，設(shè)置μ的值為:

其中，r為當(dāng)前已經(jīng)進(jìn)行變尺度操作的次數(shù)。

2.2 種群初始化

傳統(tǒng)的遺傳算法的初始種群是隨機(jī)產(chǎn)生的，而初始種群的好壞直接影響進(jìn)化過程的速度。本文提出了運(yùn)用混沌搜索策略，對(duì)初始種群進(jìn)行優(yōu)化。首先，隨機(jī)生成一個(gè)群體，再按照變尺度操作對(duì)最好的個(gè)體進(jìn)行混沌遍歷搜索，然后將經(jīng)過混沌優(yōu)化的最優(yōu)個(gè)體加入到初始種群中。反復(fù)此過程，直到初始種群達(dá)到預(yù)先設(shè)定的規(guī)模。

2.3 染色體的編譯碼

染色體編碼是由尋優(yōu)問題得到的解空間轉(zhuǎn)換為尋優(yōu)方法所能處理的搜索空間。本文將人臉圖像樣本的SVM參數(shù)(錯(cuò)誤代價(jià)系數(shù)C和核函數(shù)的參數(shù)γ)進(jìn)行編碼，采用二進(jìn)制的編碼。設(shè)第 t代染色體為 pt={β1t，β2t，…，βvt，θ1t，θ2t，…，θwt}，其中，βit(i=1，2，…，v)為錯(cuò)誤代價(jià)系數(shù)位串，θit(i=1，2，…，w)為核參數(shù)位串。編碼位串?dāng)?shù)的長(zhǎng)度由參數(shù)的搜索精度決定。搜索精度為(b1－a1)/2v。本文設(shè)定v和w的長(zhǎng)度均為16位。

染色體譯碼是編碼的反過程，它將二進(jìn)制位串轉(zhuǎn)換為解空間的值。C和γ參數(shù)的解碼方式相同，其轉(zhuǎn)換方程的表達(dá)式為:

其中，C=［a1，b1］;dec(σ)為二進(jìn)制位串 σ 的十進(jìn)制數(shù)值;n是位串σ的長(zhǎng)度。

2.4 定義適用度函數(shù)

適應(yīng)度函數(shù)的設(shè)計(jì)對(duì)遺傳算法尤為重要，因?yàn)榉N群泛化能力的適用度函數(shù)與提高遺傳算法的尋優(yōu)能力有直接的關(guān)系。定義如下SVM在訓(xùn)練樣本集上的準(zhǔn)確率:

則1－Caccuracy為錯(cuò)分樣本率，從而可以定義適應(yīng)度函數(shù)為:

2.5 交叉和變異

2.5.1 交叉操作

文獻(xiàn)［5］提出的自適應(yīng)交叉概率和相關(guān)性配對(duì)交叉，并采用“與/或”交叉法和單交叉法相結(jié)合的方式實(shí)現(xiàn)交叉操作。相對(duì)于傳統(tǒng)的遺傳算法，有利于優(yōu)秀基因的保留和較差基因的淘汰。

(1)自適應(yīng)交叉概率

不同的個(gè)體賦予不同的交叉概率，適應(yīng)度高于群體平均適應(yīng)度的個(gè)體，賦予比較低的交叉概率，最大程度的保留住優(yōu)秀的基因;相反，適應(yīng)度低于群體平均適應(yīng)度的個(gè)體，賦予比較高的交叉概率。自適應(yīng)交叉概率為:

其中，fmax為最大適應(yīng)度值，favg為群體的平均適應(yīng)度值。

(2)基于個(gè)體相關(guān)性的交叉配對(duì)

1)不相關(guān)指數(shù)

設(shè)兩個(gè)染色體編碼 A={a1，a2，…，an}和 B={b1，b2，…，bn}，其中 aibi∈{0，1}，i=1，2，3，…，n，若 A 和 B 相關(guān)性越小，則A和B交叉時(shí)出現(xiàn)無效操作的可能性就越小。所以首先要判斷兩個(gè)個(gè)體間的相關(guān)性，個(gè)體A、B之間不相關(guān)指數(shù)為:

2)配對(duì)概率

為了避免近親繁殖所產(chǎn)生的無效后代，采取非等概率配對(duì)策略［6］，在種群中選取不相關(guān)性指數(shù)大的個(gè)體并賦予較大的被選概率。被選擇的個(gè)體Bi和個(gè)體A交叉配對(duì)的概率定義為:

其中，σ為常數(shù)，0≤σ≤1;L為種群中不包含個(gè)體A的總個(gè)數(shù)。

(3)交叉方法

采用“與/或”的交叉法，即對(duì)父代按位“與”產(chǎn)生下一代X，按位“或”產(chǎn)生另一后代Y，確保了交叉操作的有效性。

2.5.2 變異操作

編碼的每一位都以同樣的變異概率進(jìn)行位翻轉(zhuǎn)。

3 基于變尺度的混沌遺傳算法訓(xùn)練SVM

做好了上述的基礎(chǔ)以后，就可以利用CGA對(duì)SVM模型的參數(shù)進(jìn)行優(yōu)化，具體算法如下:

(1)確定每個(gè)參數(shù)的范圍并對(duì)其進(jìn)行二進(jìn)制編碼并產(chǎn)生初始種群。

(2)利用以上介紹的方法優(yōu)化初始種群，此時(shí)初始種群的每個(gè)個(gè)體表示優(yōu)化問題的一個(gè)解。

(3)對(duì)每個(gè)個(gè)體進(jìn)行編碼。

(4)進(jìn)行選擇、交叉和變異的三種操作。

(5)對(duì)優(yōu)化后的個(gè)體進(jìn)行譯碼，根據(jù)適應(yīng)度函數(shù)求出優(yōu)化后的新種群。

(6)再次對(duì)此時(shí)適應(yīng)度較高的個(gè)體進(jìn)行變尺度混沌優(yōu)化，來找到更為優(yōu)化的值。

(7)跳到第(3)步，重復(fù)(3)－(7)，直到達(dá)到給定的要求。

4 仿真實(shí)驗(yàn)及結(jié)果分析

采用劍橋大學(xué)ORL人臉圖像庫作為實(shí)驗(yàn)數(shù)據(jù)，比較了本文算法訓(xùn)練SVM與基本遺傳算法訓(xùn)練SVM的人臉識(shí)別性能。該圖庫有40人的正面灰度臉像組成，每個(gè)人有10幅不同的圖像，每幅圖像為256級(jí)灰度圖，像素為92×112，每幅圖的獲取具有不同的時(shí)間、表情和環(huán)境。

隨機(jī)選取10個(gè)人的前5幅圖像共50幅作為訓(xùn)練樣本，剩下的50幅作為測(cè)試樣本。圖1是其中兩個(gè)人的10幅圖像:

圖1 ORL人臉庫中的部分圖像

本實(shí)驗(yàn)用機(jī)的PC配置:CPU為Core i5 2.2GHz，內(nèi)存為1G，軟件環(huán)境為MATLAB 2010b.本文算法的參數(shù)設(shè)置如下:初始種群規(guī)模為30，最大進(jìn)化代數(shù)為20，C∈［1，1000000］，γ∈［0.01，1］，自適應(yīng)交叉概率中，較高的交叉概率為 0.7，較低的交叉概率為0.3，變異概率為0.02。

表1 SVM參數(shù)選取結(jié)果和人臉識(shí)別正確率

表1實(shí)驗(yàn)結(jié)果表明，隨著迭代次數(shù)的增加，誤代價(jià)系數(shù)C和識(shí)別率也逐步提升到了一個(gè)穩(wěn)定的值，同時(shí)識(shí)別正確率也比傳統(tǒng)的訓(xùn)練算法的識(shí)別率高。

5 結(jié)束語

通過對(duì)遺傳算法的改進(jìn)，提出了基于變尺度的混沌遺傳算法，對(duì)人臉識(shí)別中SVM參數(shù)的優(yōu)化有了明顯的改善。此算法中由于利用混沌映射，有效地避免了傳統(tǒng)算法容易陷入局部最優(yōu)解和“早熟”的現(xiàn)象;另外基于變尺度的混沌搜索，篩選出了優(yōu)化種群，并在尋優(yōu)過程中使搜索范圍動(dòng)態(tài)縮小，提高了搜索范圍和精度。通過實(shí)際應(yīng)用，該方法在人臉識(shí)別中可以獲得較好的預(yù)測(cè)結(jié)果。

［1］汪世義，陶亮，王華彬.支持向量機(jī)和遺傳算法的人臉識(shí)別方法［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46(28):175－177.

［2］杜占龍，譚業(yè)雙，甘彤.基于混合核函數(shù)支持向量機(jī)和遺傳算法的人臉識(shí)別［J］.計(jì)算機(jī)工程，2010，38(5):163－166.

［3］何仁芳，王乘，楊文兵.基于混沌遺傳算法的圖像匹配［J］.紅外與激光工程，2003，32(1):13－16.

［4］張明火，楊建民.變尺度混沌優(yōu)化方法的改進(jìn)［J］.華東船舶工業(yè)學(xué)院學(xué)報(bào)，2004，18(4):21－26.

［5］盧厚清，陳亮，宋以勝，等.一種遺傳算法交叉算子的改進(jìn)算法［J］.解放軍理工大學(xué)學(xué)報(bào)，2007，8(3):250－253.

［6］蔡良偉，李霞.遺傳算法交叉操作的改進(jìn)［J］.系統(tǒng)工程與電子技術(shù)，2006，28(6):925－928.