動(dòng)態(tài)環(huán)境下微粒群優(yōu)化算法的研究及應(yīng)用.pdf

1、動(dòng)態(tài)優(yōu)化問(wèn)題（Dynamic Optimization Problem，簡(jiǎn)稱DOP）是現(xiàn)實(shí)社會(huì)中普遍存在的一類實(shí)際優(yōu)化問(wèn)題。相對(duì)于靜態(tài)優(yōu)化問(wèn)題而言，DOP的目標(biāo)函數(shù)或者約束條件會(huì)隨著時(shí)間而變化。近年來(lái)，利用進(jìn)化算法求解動(dòng)態(tài)優(yōu)化問(wèn)題逐漸成為新的研究熱點(diǎn)。微粒群優(yōu)化算法（Particle Swarm Optimization，簡(jiǎn)稱PSO）也稱為粒子群優(yōu)化算法，屬于進(jìn)化算法的一個(gè)分支，它模擬了生物界中鳥(niǎo)群、魚(yú)群等群體性動(dòng)物的覓食行為，具有算法

2、簡(jiǎn)單、魯棒性強(qiáng)等優(yōu)點(diǎn)，在多個(gè)領(lǐng)域得到了成功的應(yīng)用。PSO算法在靜態(tài)優(yōu)化問(wèn)題中的研究已趨于成熟，且擁有良好的性能，但在動(dòng)態(tài)優(yōu)化問(wèn)題中的研究還不夠完善。
　　論文主要研究了PSO算法在求解動(dòng)態(tài)優(yōu)化問(wèn)題過(guò)程中如何探測(cè)和響應(yīng)環(huán)境的變化以及如何保持種群的多樣性。論文的主要工作如下：
　?、賹?duì)離散動(dòng)態(tài)優(yōu)化問(wèn)題，本文提出了一種求解動(dòng)態(tài)背包問(wèn)題的離散微粒群優(yōu)化算法（Dynamic Set-based Discrete PSO，簡(jiǎn)稱DSDPS

3、O）。DSDPSO算法是在求解集合組合問(wèn)題的離散粒子群優(yōu)化模型的基礎(chǔ)上，引入了環(huán)境變化的探測(cè)以及環(huán)境變化后的響應(yīng)機(jī)制。將DSDPSO算法和經(jīng)典的自適應(yīng)原對(duì)偶遺傳算法在兩個(gè)動(dòng)態(tài)背包問(wèn)題上進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，DSDPSO算法在環(huán)境變化后能迅速找到最優(yōu)解并穩(wěn)定下來(lái)，并且找到的最優(yōu)解為該重量約束下的標(biāo)準(zhǔn)最優(yōu)解；在尋優(yōu)時(shí)間上，DSDPSO算法的尋優(yōu)時(shí)間約為與之比較的算法的尋優(yōu)時(shí)間的0.5~0.7倍。因此，DSDPSO算法更適合于求解動(dòng)態(tài)背

4、包問(wèn)題。
　　②對(duì)連續(xù)動(dòng)態(tài)優(yōu)化問(wèn)題，本文提出了一種基于記憶機(jī)制的聚類微粒群優(yōu)化算法（Memory-based Clustering PSO，簡(jiǎn)稱MCPSO）。當(dāng)微粒群中出現(xiàn)某個(gè)個(gè)體的當(dāng)前適應(yīng)度高于其歷史最優(yōu)適應(yīng)度時(shí)，將該個(gè)體中包含的有用信息傳遞給其余個(gè)體，為此，在MCPSO算法中改進(jìn)了微粒群的學(xué)習(xí)更新機(jī)制。為了保持種群的多樣性，在MCPSO算法中將記憶機(jī)制和多種群方法相結(jié)合，以便在環(huán)境變化后微粒群能有效地對(duì)搜索空間進(jìn)行探索。為了讓

5、微粒群能在環(huán)境變化后及時(shí)做出響應(yīng)，在MCPSO算法中引入了環(huán)境變化的探測(cè)以及環(huán)境變化后的響應(yīng)機(jī)制。用標(biāo)準(zhǔn)動(dòng)態(tài)優(yōu)化測(cè)試問(wèn)題——移動(dòng)峰函數(shù)問(wèn)題對(duì)算法進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，MCPSO算法具有良好的魯棒性以及較強(qiáng)的尋優(yōu)能力。將MCPSO算法和經(jīng)典的基于物種的微粒群優(yōu)化算法進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，MCPSO算法的離線誤差明顯小于與之比較的算法的離線誤差。
　?、蹖⑻岢龅腄SDPSO和MCPSO算法分別應(yīng)用于求解中國(guó)郵政的郵件配送問(wèn)題和