用于動態(tài)優(yōu)化和動態(tài)聚類問題的粒子群算法.pdf

1、隨著計算機科技和網(wǎng)絡技術在生活中的普及，人們對于優(yōu)化問題的需求也越來越復雜，對動態(tài)多目標優(yōu)化問題的科學研究也隨之崛起。生活中的優(yōu)化問題復雜多變，優(yōu)化的目標大多依賴于外界的環(huán)境，基于數(shù)學理論的優(yōu)化方法已經(jīng)不能滿足現(xiàn)實的優(yōu)化問題。基于群體智能的進化算法通過模擬生物的智能行為，可以在廣闊的解決方案空間中進行全局搜索，找到最優(yōu)解決方案或最優(yōu)解決方案解集。
　　數(shù)據(jù)流作為一種日趨主流的數(shù)據(jù)形式，具有數(shù)據(jù)規(guī)模大、產(chǎn)生速度快、帶有時間標簽的特點

2、，它廣泛產(chǎn)生于各種應用領域中。對數(shù)據(jù)流進行數(shù)據(jù)分析，挖掘其中的有用信息也成為數(shù)據(jù)挖掘領域的研究熱點，也因此涌現(xiàn)出一批數(shù)據(jù)流聚類算法。
　　以此為研究背景，本文分別提出了一種基于預測和分解的動態(tài)多目標優(yōu)化算法，和兩個用于數(shù)據(jù)流的基于粒子群算法的自動聚類算法。本文的工作包括以下內(nèi)容：
　　1.提出了一種基于分解和預測的動態(tài)多目標粒子群優(yōu)化算法（DP-DMPPSO）來處理動態(tài)多目標優(yōu)化問題。算法選取多種群協(xié)同進化的基本框架，每個子

3、種群單獨優(yōu)化一個目標函數(shù)，子種群獨立進化的同時利用外部倉庫實現(xiàn)信息交流。每個環(huán)境的末尾，輸出外部倉庫作為此環(huán)境的最優(yōu)解集。因此針對外部倉庫提出了一種基于目標空間分解的更新維護機制，使得最終解集不僅具有非支配性，而且具有較好的分布性。此外，算法采用了一種基于種群的預測機制來應對環(huán)境變化，通過預測新環(huán)境下的初始種群，使種群的運動更有目標性，從而收斂速度更快。為了測試算法性能，用DP-DMPPSO算法優(yōu)化6組各具特點的測試函數(shù)，并將優(yōu)化結果與

4、另外四種動態(tài)優(yōu)化算法的優(yōu)化結果進行對比。其中有3組是具有復雜非線性變化的Pareto解集的動態(tài)測試函數(shù)。實驗結果表明，DP-DMPPSO算法的預測機制有效地預測了復雜函數(shù)的Pareto前沿，并且，基于目標空間分解的外部倉庫更新方法也使解集擁有更好的分布性。
　　2.提出了兩種針對數(shù)據(jù)流聚類問題的自動聚類算法：一是基于流形距離的粒子群自動聚類算法（MD-PSO），一是基于密度的粒子群聚類算法（Den-PSO）。由于數(shù)據(jù)流產(chǎn)生的數(shù)據(jù)特

5、點未知，不能預先設定類別數(shù)目，自動聚類的方法可以滿足此需求。MD-PSO算法利用可變長度的編碼方式實現(xiàn)自動聚類，根據(jù)粒子代表的類別數(shù)，把總種群分為代表不同類別數(shù)的子種群。每個粒子以聚類中心為編碼，利用基于流形距離的聚類方法對數(shù)據(jù)聚類，那么，每個粒子也就代表了一種聚類結果。按照聚類結果的優(yōu)劣為粒子分配適應度，從而指引粒子的運動。進化結束后，在子種群的全局最優(yōu)解中，依據(jù)另外的目標函數(shù)找出一個最優(yōu)解，作為算法的最終結果。同樣，Den-PSO算

6、法中，利用基于密度的聚類方法對數(shù)據(jù)聚類，每個粒子也代表了一種聚類結果，評價粒子，推動種群運動。進化結束后，依據(jù)新的目標函數(shù)，從所有粒子的歷史最優(yōu)解中選擇出目標函數(shù)的最優(yōu)解作為算法的最終結果。為了測試這兩個算法的性能，用兩個算法分別對模擬數(shù)據(jù)流的數(shù)據(jù)集實現(xiàn)數(shù)據(jù)流聚類。結果表明，兩個算法對數(shù)據(jù)連貫的流形數(shù)據(jù)的聚類結果都不錯，當遇到斷點時，Den-PSO算法會對斷點數(shù)據(jù)開辟新類，比MD-PSO算法更具有自動聚類的特性。這兩種算法是把進化算法用