微粒群算法在聚類分析及QoS組播路由中的應(yīng)用研究.pdf

1、隨著計(jì)算機(jī)應(yīng)用技術(shù)的迅速發(fā)展，人們對(duì)高效優(yōu)化技術(shù)和智能計(jì)算技術(shù)提出了更高更新的要求，并用于求解各種工程問(wèn)題優(yōu)化解的應(yīng)用技術(shù)，在諸多工程領(lǐng)域得到普遍的應(yīng)用。鑒于實(shí)際工程問(wèn)題的復(fù)雜性、約束性、非線性、多局部極小和建模困難等特點(diǎn)，尋找各種適合于工程實(shí)踐需求的新型智能優(yōu)化方法一直是許多學(xué)科的一個(gè)重要研究方向。 微粒群算法作為一種新興的智能計(jì)算技術(shù)已成為越來(lái)越多研究者的關(guān)注焦點(diǎn)。它與人工生命，特別是進(jìn)化策略以及遺傳算法有著特殊的聯(lián)系。群智

2、能在沒(méi)有集中控制且不提供全局模型的前提下，為尋找復(fù)雜的分布式問(wèn)題的解決方案提供了基礎(chǔ)。 本文分別闡述和分析了微粒群算法在聚類分析和多約束組播路由問(wèn)題上的應(yīng)用。在聚類分析方面，提出了基于空間特性PSO理論的混沌聚類算法，并在其基礎(chǔ)上擴(kuò)展了對(duì)最終聚類不明確的聚類問(wèn)題的一般性解決辦法；在多約束組播路由問(wèn)題上，有別于傳統(tǒng)方法，采用樹(shù)形變換方法，依托于微粒群理論對(duì)組播路由進(jìn)行了求解。 （1）目前，主要的聚類算法可以分為如下幾類：劃

3、分方法、層次方法、基于密度的方法和基于網(wǎng)格的方法等。很多方法需要一些條件的限制，需要設(shè)定聚類的數(shù)目，而且聚類結(jié)果往往對(duì)初始狀態(tài)及參數(shù)非常敏感。K—Means聚類算法就是這樣一種代表性的聚類算法，其最后的聚類效果受到初始聚類中心的影響很大，結(jié)果往往是局部最優(yōu)解，為了得到較優(yōu)的聚類結(jié)果，計(jì)算復(fù)雜度迅速增大。而一個(gè)穩(wěn)定的（對(duì)初始中心不敏感）且可以收斂到全局最優(yōu)的算法是實(shí)際工業(yè)中所需要的。本文在PSO算法的基礎(chǔ)上提出了SPA（Spatial P

4、SO Algorithm）聚類算法，在PSO算法中引入粒子的內(nèi)部空間特性，以確保聚類算法中的類內(nèi)數(shù)據(jù)盡可能相似，類間數(shù)據(jù)差異盡可能明顯這一特性。同時(shí)，為了解決PSO算法可能出現(xiàn)的早熟問(wèn)題，本文算法也引入了混沌的思想。仿真實(shí)驗(yàn)也表明，算法在數(shù)字屬性的聚類問(wèn)題上表現(xiàn)出良好的求解能力，通過(guò)引入內(nèi)部空間特性和混沌思想，算法求解的平均性能也有顯著的改善。 （2）針對(duì)K—Means等聚類算法，初始需要指定聚類數(shù)目的問(wèn)題，本文通過(guò)引入貝葉斯信

5、息決策的思想，提出了X—SPA（X—Spatial PSO Algorithm）聚類算法，使得算法可以在運(yùn)行的過(guò)程中，通過(guò)判斷自動(dòng)的進(jìn)行聚類數(shù)目的調(diào)整，實(shí)驗(yàn)結(jié)果也表明，算法不但給出了較準(zhǔn)確的聚類類別數(shù)目，并且聚類的準(zhǔn)確度也有了一定的上升。 （3）本文提出了一種基于樹(shù)的微粒群算法PSOTREE。與傳統(tǒng)組播路由算法的先尋找路再合成樹(shù)的模式不同，PSOTREE采用了以樹(shù)生長(zhǎng)的方式直接尋找組播樹(shù)的模式?；跇?shù)的PSO算法簡(jiǎn)化了尋樹(shù)的機(jī)制