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

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

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

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

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

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

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