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

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

2、能在沒有集中控制且不提供全局模型的前提下，為尋找復(fù)雜的分布式問題的解決方案提供了基礎(chǔ)。 本文分別闡述和分析了微粒群算法在聚類分析和多約束組播路由問題上的應(yīng)用。在聚類分析方面，提出了基于空間特性PSO理論的混沌聚類算法，并在其基礎(chǔ)上擴(kuò)展了對(duì)最終聚類不明確的聚類問題的一般性解決辦法；在多約束組播路由問題上，有別于傳統(tǒng)方法，采用樹形變換方法，依托于微粒群理論對(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)的早熟問題，本文算法也引入了混沌的思想。仿真實(shí)驗(yàn)也表明，算法在數(shù)字屬性的聚類問題上表現(xiàn)出良好的求解能力，通過引入內(nèi)部空間特性和混沌思想，算法求解的平均性能也有顯著的改善。 （2）針對(duì)K—Means等聚類算法，初始需要指定聚類數(shù)目的問題，本文通過引入貝葉斯信

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