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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、書(shū)大小為1024的全局更新對(duì)圖參考文獻(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)工程理論與實(shí)踐，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