基于粒子群算法的碼書設計研究

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、書大小為1024的全局更新對圖參考文獻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