浦靈敏 張 健

1(蘇州健雄職業(yè)技術(shù)學(xué)院電氣工程學(xué)院 太倉 江蘇 215411) 2(上海無線通信研究中心 上海 201210)

?

云模型貓群優(yōu)化算法的矢量量化碼書設(shè)計研究

浦靈敏1張 健2

1(蘇州健雄職業(yè)技術(shù)學(xué)院電氣工程學(xué)院 太倉 江蘇 215411)2(上海無線通信研究中心 上海 201210)

針對標(biāo)準(zhǔn)貓群算法在矢量量化碼書設(shè)計中收斂速度慢及易陷入局部最優(yōu)的缺點，將標(biāo)準(zhǔn)貓群優(yōu)化算法和云模型相結(jié)合，提出了一種基于云模型貓群算法。通過運用云發(fā)生器建立貓個體變異程度和適應(yīng)值大小的關(guān)系，實現(xiàn)貓群搜索的自適應(yīng)調(diào)節(jié),從而增強種群多樣性、提高收斂速度，避免局部最優(yōu)。仿真實驗證明，改進的算法較其他同類型算法在收斂性、類間離散度和矢量量化不均勻度等方面有較大的提升。

貓群優(yōu)化算法 云模型 矢量量化 碼書設(shè)計

0 引 言

碼書設(shè)計是矢量量化[1]中的關(guān)鍵技術(shù)，決定了矢量量化的效果。近年來，隨著人們對生物進化理論的研究，提出了眾多優(yōu)化碼書設(shè)計的群智能算法， 而這些算法的出現(xiàn)確實提升了碼書設(shè)計的精確度和準(zhǔn)確率，但同時也存在一些缺點。如文獻[2]提出采用蟻群算法優(yōu)化碼書設(shè)計，一定程度上降低了對初始碼書的依賴性，但增加了算法的收斂時間，降低了收斂效率；文獻[3]提出采用量子粒子群算法優(yōu)化碼書設(shè)計，結(jié)構(gòu)簡單、參數(shù)調(diào)整容易，但增加了最優(yōu)碼書的搜索能力，后期易于陷入局部最優(yōu)；文獻[4]提出采用遺傳模擬退火算法優(yōu)化碼書設(shè)計，通過變異交叉等操作增大碼書的搜索范圍，但收斂速度較慢且不能較好地實現(xiàn)局部搜索。

貓群優(yōu)化算法[5]是由Chu等于2006年通過模擬生物界貓群的生活習(xí)性而提出的。它將貓群的行為分成兩組：休息和捕捉。貓的大部分時間處于休息狀態(tài)，時刻保持警惕，搜尋目標(biāo)，一旦確定獵物，貓就迅速作出捕捉行為。利用貓群的這兩種狀態(tài)相互協(xié)作實現(xiàn)復(fù)雜優(yōu)化問題的最優(yōu)解。

云模型是李德毅教授提出的一種實現(xiàn)定性概念和定量描述之間的不確定轉(zhuǎn)換，該理論是對模糊理論隸屬函數(shù)概念的創(chuàng)新與發(fā)展，已成功應(yīng)用于數(shù)據(jù)挖掘智能控制大系統(tǒng)評估入侵檢測等領(lǐng)域[6]。近年來群智能算法領(lǐng)域也開始關(guān)注云模型。將云模型與群智能算法相融合，試圖改變傳統(tǒng)研究中單純隨機性或模糊性角度研究不確定性的局限，考慮了模糊性和隨機性之間的關(guān)聯(lián)，更推進了不確定性問題的研究和深入。

在貓群優(yōu)化算法中，搜尋模式中借鑒了遺傳算法中的克隆、變異方法來增大全局搜索范圍，但單純靠復(fù)制個體而不考慮每個個體適應(yīng)度的大小，這樣增加了計算量；跟蹤模式中利用粒子群算法更新位置和速度來使個體向最優(yōu)解靠攏，沒有考慮到粒子濃度，極易發(fā)生“早熟”，陷入局部最優(yōu)。本文將云模型和貓群算法結(jié)合起來，利用云模型改進貓群優(yōu)化算法，簡稱云貓群優(yōu)化算法，增大算法的搜索空間，避開搜索過程中的局部最優(yōu)解，自適應(yīng)控制尋找全局最優(yōu)。

1 貓群優(yōu)化算法

貓群優(yōu)化算法(CSOA)按照一定的分組率MR隨機讓貓群中大部分的貓?zhí)幱谒褜つＪ较?，剩下的貓?zhí)幱诟櫮Ｊ健?/p>

1) 搜尋模式

該模式下的貓?zhí)幱谛菹?、環(huán)顧、搜尋下一個目標(biāo)的狀態(tài)，類似于優(yōu)化問題中的全局搜索模式。定義了3個基本參數(shù)：記憶池(SMP)用于存放每個貓的可能搜尋范圍，是一個整數(shù)；個體改變維數(shù)的個數(shù)(CDC)，用來定義每只貓的突變維數(shù)的個數(shù)，在(0,1)區(qū)間內(nèi)取值；個體維數(shù)變化域(SRD)定義貓移動位置的最大范圍，為(0,1)之間的某個值[7]。具體過程如下：

(1) 將貓K的位置復(fù)制N份放在SMP中，此時記憶池的大小就為N，即SMP=N；

(2) 執(zhí)行變異操作，對SMP中的每個候選點按照CDC的值，隨機加上或減去百分之SRD，對原來的位置實現(xiàn)擾動，擾動后的位置取代原來的位置；

(3) 分別計算記憶池中所有候選點的適應(yīng)值FITNESS；

(4) 從所計算的FITNESS中選擇適應(yīng)值為最優(yōu)的位置，使其取代當(dāng)前的位置。

2) 跟蹤模式

跟蹤模式[8]用于模擬貓捕獵過程，當(dāng)貓進入這個模式，它將按照自己的位置開始移動，相當(dāng)于優(yōu)化問題中的局部搜索模式。這個模式下的算法類似于粒子群算法，通過不斷更新位置和速度尋找最優(yōu)解。假設(shè)第i只貓的當(dāng)前位置和速度分別Xi=(xi1,xi2,…,xik)和Vt(vi1,vi2,…,vik)，全局最優(yōu)解為Xbest。

(1) 按照式(1)對第i只貓的當(dāng)前速度實現(xiàn)更新。

vi,d(t+1)=vi,d(t)+r1c1(Xbest,d(t)-xi,d(t))d=1,2,…,M

(1)

其中Xbest,d是擁有最佳適應(yīng)值的貓的位置，xi,d(t)表示第i只貓在第t次迭代時的第d維速度，c1為常量，經(jīng)驗值為2.0，r1是(0，1)區(qū)間中的某一個隨機值。

(2) 檢測更新后的速度是否在最大可變范圍之內(nèi)，若超過，則將其作為最大值。

(3) 由式(2)更新貓i的位置。

xi,d(t+1)=xi,d(t)+vi,d(t+1)

(2)

(4) 判斷更新后的位置是否超過搜索范圍，若超過則反向搜索。

(5) 計算更新后的適應(yīng)度值。

3) 兩個模式的融合，完成算法

將搜尋模式和跟蹤模式下的操作相融合，確定最終條件為設(shè)定的循環(huán)次數(shù)，具體流程如圖1所示。

圖1 標(biāo)準(zhǔn)貓群算法流程圖

2 云模型理論

設(shè)U是一個精確數(shù)值表示的論域，對應(yīng)這一個定性定量的概念，A是論域U中的一個元素，A∈U，x都存在一個穩(wěn)定傾向的隨機數(shù)y=μA(x)，稱為x對于概念A(yù)的確定性，x在U上的分布稱為云模型，簡稱云[9]。

云的數(shù)學(xué)特征可有期望值Ex、熵En和超熵He來表征，其中Ex表示定性知識的信息中心值；En主要反映了在論域中可被這個概念所接受的數(shù)值范圍，表示不確定性；He是En的熵，反映了云滴的離散性[10]。生成云滴的算法或硬件稱為云發(fā)生器，包括X條件云發(fā)生器和Y條件云發(fā)生器[11]。

(1) X條件云發(fā)生器

給定云的三個數(shù)學(xué)特征(Ex，En，He)、特定的和云滴數(shù)n，產(chǎn)生云滴Drop(x0,yi)，這樣的云發(fā)生器稱為X條件云發(fā)生器。

Step1輸入?yún)?shù)：Ex，En，He，以及n；

Step3計算x0的云模型隸屬度yi：

(3)

Step4輸出第i個云滴Drop(x0,yi)，判斷i是否為n，如等于則結(jié)束，否則，返回Step2繼續(xù)生成，直到n個云滴都輸出。

圖2給出了Ex=0、En=2、He=0.3、n=800的正態(tài)云數(shù)學(xué)特征示意圖。

圖2 正態(tài)云數(shù)學(xué)特征示意圖

(2) Y條件云發(fā)生器

給定云的三個數(shù)學(xué)特征(Ex，En，He)、特定的和云滴數(shù)n，產(chǎn)生云滴Drop(xi,y0)，這樣的云發(fā)生器稱為Y條件云發(fā)生器。

Step1輸入?yún)?shù)：Ex，En，He，y0以及n；

Step3計算y0的特定值xi：

(4)

Step4輸出第i個云滴Drop(xi,y0)，判斷i是否為n，如等于則結(jié)束，否則，返回Step2繼續(xù)生成，直到n個云滴都輸出。

3 基于云貓群優(yōu)化算法的碼書設(shè)計

3.1 云貓群優(yōu)化算法

在云貓群優(yōu)化算法中，搜尋組中不再采用固定數(shù)目復(fù)制變異個體的方式，而根據(jù)其適應(yīng)度大小來確定每個貓需要克隆變異的規(guī)模，降低求解負(fù)擔(dān)，增大有效搜索范圍[12]；跟蹤組中不再通過調(diào)節(jié)速度來實現(xiàn)位置的更新，而是通過云發(fā)生器來實現(xiàn)進化。

(1) 初始化貓群，隨機產(chǎn)生M個貓個體。

(2) 按照一定的分組率MR將貓群分為搜尋組和跟蹤組。

(3) 進入搜尋組。

① 計算組內(nèi)所有貓個體的適應(yīng)度，按適應(yīng)度大小進行排序。

② 克隆操作：適應(yīng)度大的貓個體，克隆的規(guī)模就越大；適應(yīng)度小的貓個體，克隆的規(guī)模就越小。

(5)

其中，Ni為第i個貓個體需要克隆的個數(shù)，M為種群大小，fi為第i個個體的適應(yīng)度。

③ 變異操作：隸屬度y越小就表明云滴離云底越近，即越遠離最優(yōu)解，搜索范圍就越寬，有利于全局搜索。為了實現(xiàn)有效變異，利用X條件云發(fā)生器產(chǎn)生yi：

EX=fg

則:

(6)

gh、fw、fi分別為組中貓群搜尋的最優(yōu)、最差和第i個體適應(yīng)度，這樣就可以保證yi自適應(yīng)于適應(yīng)度，根據(jù)yi確定個體的變異程度。

xi=xi+yi·Ni(0,1)

(7)

xi為第i個貓個體的位置，Ni(0,1)是根據(jù)yi產(chǎn)生的一個正態(tài)分布隨機變量。

④ 重新計算適應(yīng)度，選出最優(yōu)個體，與原個體適應(yīng)度相比，如果適應(yīng)度得到了改善，則用新的位置替換原來的個體位置。

(4) 進入跟蹤組。

① 計算個體的適應(yīng)度，更新局部最優(yōu)值Pbest和全局最優(yōu)值Gbest。

② 定義云模型中三個數(shù)學(xué)特征，代入式(3)更新個體。判斷是否達到變異閾值N，若達到，則按照式(8)定義：

(8)

否則，則按照式(9)定義：

(9)

③ 判斷是否達到最終條件，若達到，輸出Gbest，否則轉(zhuǎn)②。

(5) 將搜尋組和跟蹤組中的貓群混合成新的種群，計算適應(yīng)度，選擇最優(yōu)值。

(6) 判斷是否滿足終止條件，滿足則停止，否則將返回步驟(2)。

3.2 云貓群優(yōu)化算法在碼書設(shè)計中的應(yīng)用

將訓(xùn)練矢量系列L={L1,L2,…,Ln}隨機劃分為K個胞腔，胞腔的聚類中心為T={t1,t2,…,tk}，形成初始碼書，每個碼書里有K個碼字。將初始碼書作為貓群的初始化，按式(10)和式(11)計算適應(yīng)度。

(10)

(11)

按照分組率將貓群分成搜尋組和跟蹤組，在搜尋組的碼書按照3.1節(jié)中的步驟(3)進行更新，若適應(yīng)值得到改善則替換原來的碼書，否則保持原碼書不變；在跟蹤組的碼書按照3.1節(jié)中的步驟(4)進行更新，若適應(yīng)值得到改善則替換原來的碼書，否則保持原碼書不變。

判斷是否滿足結(jié)束條件。本文的實驗中，以最大迭代次數(shù)為終止條件。

4 實驗與結(jié)果分析

實驗是以40秒的語音信號為測試信號，采樣率為8 000，幀長為160，在MATLAB平臺上，采用平均失真測度、類間離散度和矢量量化不均勻度[13]作為碼書性能的評價指標(biāo)。實驗比對蟻群算法、粒子群算法、貓群算法和本文算法碼書設(shè)計對實驗語音信號的訓(xùn)練和識別結(jié)果。

在實驗之前，首先分析云貓群算法中的分組率r、種群大小N和變異率SCD等參數(shù)選取對碼書設(shè)計性能的影響，改變其中某一參數(shù)，固定其他參數(shù)，驗證分析其變化對尋求最優(yōu)碼書時平均失真測度和迭代次數(shù)的影響結(jié)果。

圖3給出了分組率不同所產(chǎn)生的平均失真測度和迭代次數(shù)。分組率的大小直接關(guān)系到貓群進入搜尋組和跟蹤組的個體數(shù)，分組率越小，搜尋組個體數(shù)就越少，為之相應(yīng)跟蹤組的個數(shù)就越多。從圖3(a)中可以看出當(dāng)r=0.2時，平均失真測度為最?。粓D3(b) 表示分組率不同，達到最優(yōu)碼書時的迭代次數(shù)，在r=0.2時迭代次數(shù)相對較低，因此本文算法選擇0.2作為貓群的分組率。

圖3 分組率對碼書設(shè)計的影響

圖4給出了貓群種群的大小對搜索最優(yōu)碼書的影響。從圖中可以看出種群大小為600時產(chǎn)生的平均失真測度比種群大小為500時產(chǎn)生的平均測度要稍大一些，而所需要的迭代次數(shù)卻最少，因此本文選取600作為本算法的貓群大小參數(shù)。

圖4 種群大小對碼書設(shè)計的影響

圖5給出了變異率選擇的不同所對碼書設(shè)計的影響。在圖(a)中在SCD=0.7時所達到的平均失真測度最小，而達到最優(yōu)碼書時所需迭代次數(shù)較大，故不考慮，而SCD=0.2時，平均失真測度和達到最優(yōu)碼書時所需迭代次數(shù)均相對于較低，因此本文算法中的變異率選取0.2。

圖5 變異率對碼書設(shè)計的影響

綜上所述，本文算法中的各個參數(shù)的選取如下：分組率為0.2，貓群大小為600，變異率為0.2，迭代次數(shù)越大，所需時間越長，因此取迭代次數(shù)為30。

實驗對比了蟻群算法、粒子群算法、標(biāo)準(zhǔn)貓群算法和云貓群算法在矢量量化碼書設(shè)計中的收斂性。圖6給出了各算法平均失真測度與迭代次數(shù)之間的關(guān)系。從圖中可以看出云貓群算法在碼書設(shè)計中能較好地進行收斂，較快到達全局最優(yōu)，且最優(yōu)值比其他算法更小，而其他的算法收斂速度快，但不同程度地易于局部收斂。

圖6 收斂性對比

類間離散度是指聚類胞腔質(zhì)心之間的距離，可以用來評定一個碼書設(shè)計算法的優(yōu)劣，其值越大，則碼書設(shè)計的性能就越好。用Yi、Yj來表示第i、j胞腔的質(zhì)心，則其類間離散度為：

Sij|Yi-Yj|T|Yi-Yj|

(12)

矢量量化不均勻度用來衡量各個胞腔之內(nèi)所聚類的訓(xùn)練矢量是否均衡，其值越小，碼書設(shè)計的性能就越好。

假設(shè)訓(xùn)練矢量的總數(shù)為N個，類的個數(shù)即胞腔的個數(shù)為M個，定義類的均衡矢量數(shù)為：

(13)

其中，?·」表示向下取整。在聚類完成后，屬于第k個胞腔的訓(xùn)練矢量數(shù)量是nk， 則定義矢量量化不均勻度為：

(14)

表1給出了標(biāo)準(zhǔn)貓群算法和云貓群算法在碼書大小分別為512、1 024時的類間離散度和矢量量化不均勻度對比結(jié)果。從表中可以看出，云貓群算法在同等碼書大小的情況下，類間離散度最大、矢量量化不均勻度最小，根據(jù)式(12)、式(13)和式(14)，可以得到云貓群算法所設(shè)計的碼書性能最好。

表1 類間離散度和矢量量化不均勻度對比結(jié)果

5 結(jié) 語

為了提高矢量量化中碼書設(shè)計的性能，本文提出了基于云模型的貓群優(yōu)化算法的碼書設(shè)計。將整個貓群分為搜尋組和跟蹤組。在搜尋組中運用云發(fā)生器建立個體變異程度和適應(yīng)值大小的關(guān)系，實現(xiàn)克隆變異個數(shù)的自適應(yīng)調(diào)節(jié)；在跟蹤組中通過正態(tài)云算子實現(xiàn)貓群的進化和變異，自適應(yīng)控制貓群的搜索范圍。實驗結(jié)果表明，云貓群優(yōu)化算法能較好地應(yīng)用到碼書設(shè)計中，減少對初始碼書的依賴性，更好地實現(xiàn)全局最優(yōu)的收斂。

[1] Linde Y,Buzo A,Gray R M.An Algorithm for Vector Quantizer Design[J].IEEE Trans on Communications,1980,28(1):84-95.

[2] 李霞,羅雪暉,張基宏.基于人工蟻群優(yōu)化的矢量量化碼書設(shè)計算法[J].電子學(xué)報,2004,32(7):1082-1085.

[3] 李殷,李飛.基于量子粒子群優(yōu)化算法的矢量量化碼書設(shè)計[J].電視技術(shù),2012,36(17):26-29.

[4] 趙夢玲,劉紅衛(wèi),劉若辰.基于遺傳模擬退火算法的矢量量化碼書設(shè)計[J].數(shù)學(xué)的實踐與認(rèn)識,2015,45(1):209-218.

[5] Chu S C,Tsai P W,Pan J S.Cat Swarm Optimization[C]//Proc of the 9thPacific Rim International Conference on Artificial Intelligence.Guilin,China,2006:854-858.

[6] 許波,彭志平,余建平.一種基于云模型的改進型量子遺傳算法[J].計算機應(yīng)用研究,2011,28(10):3684-3686.

[7] 吳偉林,周永華.基于差分演化與貓群算法融合的群體智能算法[J].計算技術(shù)與自動化,2014,33(4):78-83.

[8] 葉飛.基于智能優(yōu)化算法的優(yōu)秀序列的研究[D].上海大學(xué),2014.

[9] 張英杰,邵歲鋒.一種基于云模型的云變異粒子群算法[J].模式識別與人工智能,2011,24(1):90-96.

[10] 劉爭艷,李絮,王慧玲.基于云模型的自適應(yīng)蟻群算法改進研究[J].計算機工程與應(yīng)用,2016,52(19):68-71.

[11] 馬穎,田維堅,樊養(yǎng)余.基于云模型的自適應(yīng)量子免疫克隆算法[J].計算物理,2013,30(4):627-632.

[12] 楊淑瑩,劉旭鵬,陶沖,等.基于免疫貓群優(yōu)化算法的矢量量化的碼書設(shè)計及語音識別[J].模式識別與人工智能,2014,27(7):577-583.

[13] Pu Lingmin,Hu Hongmei.Codebook design using improved particle swarm optimization based on selection probability of artificial bee colony algorithm[J].Journal of Chongqing University(English Edition),2014,13(3):90-98.

RESEARCHONCODEBOOKDESIGNOFVECTORQUANTIZATIONBASEDONCATSWARMOPTIMIZATIONALGORITHMANDCLOUDMODEL

Pu Lingmin1Zhang Jian2
1(InstituteofElectricalEngineering,SuzhouChien-ShiungInstituteofTechnology,Taicang215411,Jiangsu,China)2(ShanghaiResearchCenterforWirelessCommunications,Shanghai201210,China)

Standard cat swarm optimization algorithm has slow convergence rate and easily fall into local optimum in vector quantization codebook design. Therefore, a new codebook design algorithm is proposed combining standard cat swarm optimization algorithm and cloud model. By using cloud generator to set up the relationship between individual variation of the cat and the value of fitness, search range of cats will realize adaptive control, improving the diversity of populations and the convergence rate and avoiding local optimum. Experiment shows that the improved algorithm has higher performance than other similar algorithms in convergence, class scatter and vector quantization uniformity.

Cat swarm optimization algorithm Cloud model theory Vector quantization Codebook design

2016-06-06。2014江蘇省“青藍工程”資助(201423)；江蘇省高校自然科學(xué)研究面上項目(15KJB520016)；2014年蘇州市智能家居無線傳感應(yīng)用技術(shù)重點實驗室建設(shè)項目(SZSD201403)；2015年太倉市重點研發(fā)計劃(社會發(fā)展)項目(TC2015 SF10)。浦靈敏，講師，主研領(lǐng)域：無線通信，物聯(lián)網(wǎng)應(yīng)用技術(shù)。張健，博士。

TP301.6 TN912.3

A

10.3969/j.issn.1000-386x.2017.08.050