云模型貓群優化算法的矢量量化碼書設計研究

浦靈敏 張 健

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

?

云模型貓群優化算法的矢量量化碼書設計研究

浦靈敏1張 健2

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

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

貓群優化算法 云模型 矢量量化 碼書設計

0 引 言

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

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

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

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

1 貓群優化算法

貓群優化算法(CSOA)按照一定的分組率MR隨機讓貓群中大部分的貓處于搜尋模式下，剩下的貓處于跟蹤模式。

1) 搜尋模式

該模式下的貓處于休息、環顧、搜尋下一個目標的狀態，類似于優化問題中的全局搜索模式。定義了3個基本參數：記憶池(SMP)用于存放每個貓的可能搜尋范圍，是一個整數；個體改變維數的個數(CDC)，用來定義每只貓的突變維數的個數，在(0,1)區間內取值；個體維數變化域(SRD)定義貓移動位置的最大范圍，為(0,1)之間的某個值[7]。具體過程如下：

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

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

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

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

2) 跟蹤模式

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

(1) 按照式(1)對第i只貓的當前速度實現更新。

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

(1)

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

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

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

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

(2)

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

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

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

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

圖1 標準貓群算法流程圖

2 云模型理論

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

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

(1) X條件云發生器

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

Step1輸入參數：Ex，En，He，以及n；

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

(3)

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

圖2給出了Ex=0、En=2、He=0.3、n=800的正態云數學特征示意圖。

圖2 正態云數學特征示意圖

(2) Y條件云發生器

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

Step1輸入參數：Ex，En，He，y0以及n；

Step3計算y0的特定值xi：

(4)

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

3 基于云貓群優化算法的碼書設計

3.1 云貓群優化算法

在云貓群優化算法中，搜尋組中不再采用固定數目復制變異個體的方式，而根據其適應度大小來確定每個貓需要克隆變異的規模，降低求解負擔，增大有效搜索范圍[12]；跟蹤組中不再通過調節速度來實現位置的更新，而是通過云發生器來實現進化。

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

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

(3) 進入搜尋組。

① 計算組內所有貓個體的適應度，按適應度大小進行排序。

② 克隆操作：適應度大的貓個體，克隆的規模就越大；適應度小的貓個體，克隆的規模就越小。

(5)

其中，Ni為第i個貓個體需要克隆的個數，M為種群大小，fi為第i個個體的適應度。

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

EX=fg

則:

(6)

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

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

(7)

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

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

(4) 進入跟蹤組。

① 計算個體的適應度，更新局部最優值Pbest和全局最優值Gbest。

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

(8)

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

(9)

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

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

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

3.2 云貓群優化算法在碼書設計中的應用

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

(10)

(11)

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

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

4 實驗與結果分析

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

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

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

圖3 分組率對碼書設計的影響

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

圖4 種群大小對碼書設計的影響

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

圖5 變異率對碼書設計的影響

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

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

圖6 收斂性對比

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

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

(12)

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

假設訓練矢量的總數為N個，類的個數即胞腔的個數為M個，定義類的均衡矢量數為：

(13)

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

(14)

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

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

5 結 語

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

[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] 李霞,羅雪暉,張基宏.基于人工蟻群優化的矢量量化碼書設計算法[J].電子學報,2004,32(7):1082-1085.

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

[4] 趙夢玲,劉紅衛,劉若辰.基于遺傳模擬退火算法的矢量量化碼書設計[J].數學的實踐與認識,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].計算機應用研究,2011,28(10):3684-3686.

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

[8] 葉飛.基于智能優化算法的優秀序列的研究[D].上海大學,2014.

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

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

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

[12] 楊淑瑩,劉旭鵬,陶沖,等.基于免疫貓群優化算法的矢量量化的碼書設計及語音識別[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)；江蘇省高校自然科學研究面上項目(15KJB520016)；2014年蘇州市智能家居無線傳感應用技術重點實驗室建設項目(SZSD201403)；2015年太倉市重點研發計劃(社會發展)項目(TC2015 SF10)。浦靈敏，講師，主研領域：無線通信，物聯網應用技術。張健，博士。

TP301.6 TN912.3

A

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