基于粒子群算法的碼書設(shè)計研究

1、基于粒子群算法的碼書設(shè)計研究浦靈敏,胡宏梅 (健雄職業(yè)技術(shù)學(xué)院， 江蘇 太倉 215411)摘 要：在基于粒子群算法碼書設(shè)計研究中，提出采用隨機(jī)概率擾動的方式作為基本粒子群算法的全局極值更新條件，從而增加全局最優(yōu)區(qū)域的搜索能力，避免了粒子過早的“趨同性”。關(guān)鍵詞：矢量量化；碼書設(shè)計；粒子群算法中圖分類號：TN 911 文獻(xiàn)標(biāo)識碼：A1引言碼書設(shè)計是矢量量化的關(guān)鍵技術(shù)，碼書性能的好壞直接影響到矢量量化的效果。研究碼書設(shè)計算法的目的就是尋求有效的算法盡可能找到全局最優(yōu)或接近全局最優(yōu)的碼書以提高碼書性能，并盡可能減少計算復(fù)雜度。由Linde、Buzo和Gray于1980年首先提出一種有效和直觀的矢量

2、量化碼書設(shè)計算法LBG算法1。該算法容易實現(xiàn)、理論嚴(yán)密，但計算量大且易陷入局部最優(yōu)解。針對這些問題，學(xué)者們開始提出各種改進(jìn)的算法，如模擬退火碼書設(shè)計算法2、禁止搜索碼書設(shè)計算法3、神經(jīng)網(wǎng)絡(luò)碼書設(shè)計4以及蟻群算法碼書設(shè)計5等，實驗證明，這些算法均在不同程度上改善碼書質(zhì)量，但均存在不同的問題。粒子群算法（Particle Swarm Optimization, PSO）6是在1995年由美國社會心理學(xué)家James Kennedy和電氣工程師Russell Eberhart共同提出的。自粒子群算法提出以來，由于它的計算快速性和算法本身的易實現(xiàn)性，引起了國際上相關(guān)領(lǐng)域眾多學(xué)者的關(guān)注和研究。PSO算法最

3、早應(yīng)用于人工神經(jīng)網(wǎng)絡(luò)的訓(xùn)練方法，隨后，在函數(shù)優(yōu)化、約束優(yōu)化、極大極小問題、多目標(biāo)優(yōu)化等問題中均得到了成功的應(yīng)用。針對PSO應(yīng)用到碼書設(shè)計中容易陷入局部最優(yōu)解的問題，又由于模擬退火算法具有全局搜索能力的特點，提出將模擬退火算法及PSO共同應(yīng)用到碼書設(shè)計中，實驗證明，本文算法有一定的可行性。2標(biāo)準(zhǔn)粒子群算法標(biāo)準(zhǔn)粒子群算法78（PSO）是一種有效的全局尋優(yōu)算法，它是基于群體智能理論的優(yōu)化算法，通過群體中粒子間的合作和競爭產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索。與進(jìn)化算法比較，PSO也采用了“群體”和“進(jìn)化”的概念，同樣是依據(jù)個體（微粒）的適應(yīng)值大小進(jìn)行操作。所不同的是PSO保留了基于種群的全局搜索策略，且它不象

4、其他算法那樣對于個體使用進(jìn)化算法，而是將每個個體看作是在n維搜索空間中的一個沒有重量和體積的微粒，并在搜索空間中以一定的速度飛行。該飛行速度由個體的飛行經(jīng)驗和群體的飛行經(jīng)驗進(jìn)行動態(tài)調(diào)整。在每次迭代中，每個個體（微粒）根據(jù)下式來調(diào)整它的飛行速度和位置： (1) (2)其中，下標(biāo)“j”表示粒子的第j維，“i”表示粒子i，“t”表示第t代，、為加速常數(shù)，通常在02間取值，為兩個相互獨立的隨機(jī)函數(shù)。粒子群算法的基本實現(xiàn)步驟如下，步驟1，在初始化范圍內(nèi)，對粒子群進(jìn)行隨機(jī)初始化，包括隨機(jī)位置和速度。步驟2，計算每個粒子的適應(yīng)值。步驟3，對于每個粒子，將其適應(yīng)值與所經(jīng)歷過的最好位置的適應(yīng)值進(jìn)行比較，如果更好

5、，則將其作為粒子的個體歷史最優(yōu)值，用當(dāng)前位置更新個體歷史最好位置。步驟4，對每個粒子，將其歷史最優(yōu)適應(yīng)值與群體內(nèi)或鄰域內(nèi)所經(jīng)歷的最好位置的適應(yīng)值進(jìn)行比較，若更好，則將其作為當(dāng)前的全局最好位置。步驟5，根據(jù)式（1）和式（2）對粒子的速度和位置進(jìn)行對比。步驟6，若未達(dá)到結(jié)束條（件通常為足夠好的適應(yīng)值或達(dá)到一個預(yù)設(shè)最大代數(shù)），則返回步驟2。3基于粒子群算法的碼書設(shè)計基于粒子群算法的碼書設(shè)計9是利用標(biāo)準(zhǔn)粒子群算法有良好的全局搜索性，使每個粒子對要聚類的訓(xùn)練矢量進(jìn)行搜索、聚類，每個粒子都能得到一組碼書，更新胞腔質(zhì)心。若滿足了終止條件，則輸出最好的那組碼書；否則，再重新聚類，直到產(chǎn)生性能足夠好的碼書為止。

6、3.1粒子群碼書設(shè)計算法的編碼表示與適應(yīng)度選擇粒子群算法采用實數(shù)編碼，一個編碼對應(yīng)一個可行解。在本文算法中，采用的是基于聚類中心的編碼方式，也就是每個粒子的位置是由n個聚類中心組成。粒子除了位置以外，還有速度和適應(yīng)值。由于訓(xùn)練矢量維數(shù)為d，因此粒子的位置X是維變量，所以粒子的速度V也應(yīng)當(dāng)是維變量，另外每個粒子還有一個適應(yīng)度。當(dāng)粒子初始位置確定時，也就是聚類中心確定時，為訓(xùn)練矢量集，則聚類的劃分由下面的最近鄰法則決定。若滿足： (3)則屬于第j類。聚類完后，可得第j類的類內(nèi)離散度為。對于某粒子，按照以下方法計算其適應(yīng)度：（1）按照最近鄰法則（3）式，確定與該粒子對應(yīng)的聚類劃分。（2）根據(jù)聚類劃分

7、，計算類內(nèi)離散度和，即各類中矢量到對應(yīng)類中心的距離的總和。（3）個體的適應(yīng)度可采用，其中是總類內(nèi)離散度和，L是調(diào)節(jié)常數(shù)，根據(jù)具體情況定。這樣個體的適應(yīng)度與離散度和負(fù)相關(guān)，離散度和越小，個體適應(yīng)度越大。3.2 粒子群碼書設(shè)計算法的實現(xiàn)步驟步驟1，種群的初始化。在初始化粒子時，先將每個樣本隨機(jī)指派為某一類，作為最初的聚類劃分，并計算各類的聚類中心，作為初始粒子的位置編碼，計算粒子的適應(yīng)度，并初始化粒子的速度。若有N個粒子，則反復(fù)進(jìn)行N次，共生成N個初始粒子群。步驟2，對每個微粒，比較它的適應(yīng)度和它經(jīng)過的最好位置Pbest的適應(yīng)度，如果更好，更新Pbest。步驟3，對每個粒子，比較它的適應(yīng)度和群體所

8、經(jīng)過的最好位置Gbest的適應(yīng)度，如果更好，更新Gbest。步驟4，根據(jù)粒子群算法的速度和位置更新公式（1）、（2）調(diào)整粒子的速度和位置。步驟5，對新個體進(jìn)行LBG算法優(yōu)化。對于新一代粒子，按照以下的LBG算法進(jìn)行優(yōu)化：（1）根據(jù)粒子的聚類中心編碼，按照最近鄰法則，來確定對應(yīng)該粒子的聚類劃分；（2）按照聚類劃分，計算新的聚類中心，即形成新的碼字，更新粒子的適應(yīng)值，取代原來的編碼值。步驟6，如果達(dá)到結(jié)束條件（形成足夠好的碼書或最大迭代次數(shù)），則結(jié)束，否則轉(zhuǎn)步驟2。4 改進(jìn)的粒子群碼書設(shè)計算法粒子群算法的本質(zhì)是利用本身信息、個體極值信息和全局極值三個信息，指導(dǎo)粒子下一步迭代位置。但是粒子群在追逐最

9、優(yōu)粒子過程中，隨著它接近最優(yōu)粒子，其速度越來越小，因此粒子群表現(xiàn)出強(qiáng)烈的“趨同性”，容易陷入局部極小點10。本文將針對該項缺陷，提出引進(jìn)模擬退火算法對其進(jìn)行相應(yīng)改進(jìn)研究。4.1 改進(jìn)算法的思想在粒子群算法的碼書設(shè)計算法中，粒子通過更新其全局最優(yōu)和自身最優(yōu)的方法來搜索全局最優(yōu)解，進(jìn)而設(shè)計性能較好的碼書。但在其更新過程中，粒子只有遇到更好解的時候才會更新極值，這樣做縮小了粒子的搜索鄰域，使其很容易達(dá)到收斂，陷入局部最優(yōu)。本文提出引進(jìn)模擬退火算法對全局極值的更新條件做了改進(jìn)，基本思想如下：當(dāng)新粒子的適應(yīng)值大于當(dāng)前全局極值時，系統(tǒng)一定接受該粒子；當(dāng)新粒子適應(yīng)度小于全局極值時，按式（4）計算出模擬退火概

10、率p，當(dāng)p大于閾值r的時候，r為 (0,1) 間的隨機(jī)值，也接受該粒子，否則不接受。模擬退火概率計算如下： (4)式中為第t次迭代的溫度，K為降溫系數(shù)；為當(dāng)前粒子失真變化， ， 為第i個粒子的當(dāng)前適應(yīng)值，為當(dāng)前全局最優(yōu)適應(yīng)值。改進(jìn)算法的全局極值更新條件采用了隨機(jī)概率擾動接受的方式，既接收優(yōu)化解，也可以接受惡化解，增大全局搜索范圍。很大時，使局部極值與全局極值之間的差值很大，接受概率比較大，可以接受的較差解比較多；不是很高時，使差值小的狀態(tài)易于接受，即中溫時，易于接受與當(dāng)前狀態(tài)相比不是很差的解；很小時，差值足夠小的狀態(tài)才易于接受，即低溫時，只能接受與當(dāng)前狀態(tài)相比差很少的解。當(dāng)經(jīng)過足夠長時間的溫度

11、下降過程，固體達(dá)到最小能量狀態(tài)時，相應(yīng)也達(dá)到了全局最優(yōu)解。4.2 實驗結(jié)果本文主要是對語音信號進(jìn)行矢量量化碼書設(shè)計。這里的訓(xùn)練矢量為8kHz采樣16比特PCM格式的原始語音波形數(shù)據(jù)，每個矢量為5ms，即40維矢量。設(shè)計的碼書大小分別為512、1024。算法中的參數(shù)選取源于經(jīng)驗值，粒子數(shù)N=30，迭代次數(shù)T=10，、分別為2。關(guān)于慣性權(quán)重w的選取，根據(jù)其對粒子搜索影響的特點，采用了 (5)其中的取為0.9, 取為0.4，iter為迭代次數(shù)，為最大的迭代次數(shù)。采用這樣的慣性權(quán)重，使得開始時有較好的全局收斂能力，隨著迭代次數(shù)的增加，w不斷減小，晚期時使得算法具有較強(qiáng)的局部收斂能力。本文分別從客觀和主

12、觀兩方面來評價改進(jìn)算法及原算法設(shè)計碼書的性能。客觀評價指標(biāo)包括類間離散度、矢量量化不均勻度及全局極值更新性能。而主觀評價指標(biāo)還是依靠人的聽覺感知。類間離散度是指各個胞腔質(zhì)心間的距離，是一個用來評價碼書設(shè)計算法優(yōu)劣的有效指標(biāo)。其值越大，碼書的性能就越好。計算公式如下： (6)其中、分別是指第i、j胞腔的質(zhì)心，T為轉(zhuǎn)置計算。矢量量化不均勻度用來衡量各個胞腔所聚類的訓(xùn)練矢量數(shù)量是否均衡。其值越小，碼書性能越好。假設(shè)訓(xùn)練矢量的總數(shù)為N個，類的個數(shù)即胞腔的個數(shù)為M個，定義類的均衡矢量數(shù)為： (7)其中表示向下取整。在聚類完成后，屬于第k個胞腔的訓(xùn)練矢量數(shù)量是， 則定義矢量量化不均勻度為： (8)表1為標(biāo)

13、準(zhǔn)粒子群碼書設(shè)計算法及改進(jìn)算法在類間離散度及矢量量化不均勻度上的對比結(jié)果。表中顯示，在512及1024兩種碼書的情況下，改進(jìn)算法的類間離散度均大于基本粒子群算法，而矢量量化不均勻度卻均小于基本粒子群算法，說明了改進(jìn)算法比起基本粒子群算法能更好地改善碼書性能。除了這兩個指標(biāo)外，還可以從全局極值的更新性能上比較，可以看出它們趨向全局搜索的能力。通過分析可知，若有N個粒子，迭代次數(shù)為T，基本算法中全局極值更新次數(shù)不多于T次，而改進(jìn)算法中全局極值更新次數(shù)可達(dá)到次。圖1和圖2 分別為碼書大小為512和1024時標(biāo)準(zhǔn)粒子群碼書設(shè)計算法和改進(jìn)算法對全局極值更新過程，反映出這兩種算法的全局搜索能力。算法中T=

14、10，可以得到基本算法更新次數(shù)最多為10次，而改進(jìn)算法的更新次數(shù)可達(dá)。從圖中可以看出標(biāo)準(zhǔn)粒子群算法更新次數(shù)小于10次，易達(dá)到收斂，而改進(jìn)算法卻能較長時間更新極值，其全局搜索能力遠(yuǎn)遠(yuǎn)高于基本粒子群算法，能更好地改善碼書的性能。一個通過語音矢量量化碼書編碼后重構(gòu)語音質(zhì)量主要依靠人的聽覺感知主觀評價。這里采用非正式語音聽力測試語音質(zhì)量。由于碼書大小為512和1024，所以不可能得到高質(zhì)量的重構(gòu)語音，但依然能測試出兩種算法的性能優(yōu)劣。通過試聽，可以發(fā)現(xiàn)基本算法所重構(gòu)的語音具有輕微的模糊，有一定的噪聲，信號不穩(wěn)定，而改進(jìn)算法所重構(gòu)的語音無論是從清晰度、自然度還是理解性上都要好過基本粒子群算法所重構(gòu)的語音

15、。表1 類間離散度及矢量量化不均勻度對比碼書大小 粒子群算法碼書設(shè)計改進(jìn)后的粒子群算法類間離散度不均勻度類間離散度不均勻度5124.1256e-006386.07125.6545e-006361.345610240.5452e-006822.36940.7124e-006712.03125 結(jié)論本文介紹了基本粒子群算法及其在碼書設(shè)計中的應(yīng)用。重點分析了基本粒子群算法碼書設(shè)計原理，針對其不足，提出了相應(yīng)的改進(jìn)算法。為提高全局搜索能力，在改進(jìn)的算法中采用隨機(jī)概率擾動接受作為全局極值更新條件。最后通過將改進(jìn)算法應(yīng)用到語音矢量量化實驗中來驗證其有效性。 圖1 碼書大小為512的全局更新對比圖 圖2 碼

16、書大小為1024的全局更新對圖參考文獻(xiàn)1 -95.2 Wenhuan Xu, Asoke K.Nandi, “Novel quantiser design using reinforced learning as a pre-process” , Signal Processing, 2005, 7 (85): 1315-1333.3 Shin-Ming Pan, Kuo-Sheng Cheng, “An evolution-based tabu search approach to codebook design”, Pattern Recognition, 2007, 2 (40): 47

17、6-491.“A novel training scheme for neural-network-based vector quantization and its application in image compression”, Neurocomputing, 2004, 61: 421-427.“Application of ant K-means on clustering analysis”, Computers&Mathematics with Applications, 2005, 50(1012): 1709-1724.6 Nagoya, Japan, 1995.7

18、 “A Mortified Particle Swarm Optimization”, Proceedings of the IEEE International Conference on Evolutionary Computation. IEEE Press, Piscataway, NJ, 1998, 69-73.8 Shi Y, Eberhart R C, “Empirical Study of Particle Swarm Optimization”.In: Proceedings of the 1999 Congress on Evolutionary Computation, Piscataway, NJ, IEEE Service Centers, 1999, 1945-1950.9 劉靖明，韓麗川，“基于粒子群的K均值聚類算法”，系統(tǒng)工程理論與實踐，2005，6：54-58。10 Xie X F, Zhang W J, Yang Z L,“Overview of particle swarm optimization”, Control and Decision, 2003, 18(2): 129-134.Study of Code