粒子群算法論文

PAGE1粒子群算法的尋優(yōu)算法摘要：粒子群算法是在仿真生物群體社會(huì)活動(dòng)的基礎(chǔ)上，通過模擬群體生物相互協(xié)同尋優(yōu)能力，從而構(gòu)造出一種新的智能優(yōu)化算法。這篇文章簡(jiǎn)要回顧了粒子群算法的發(fā)展歷史；引入了一個(gè)粒子群算法的實(shí)例，對(duì)其用MATLAB進(jìn)行編程求解，得出結(jié)論。之后還對(duì)其中的慣性權(quán)重進(jìn)行了延伸研究，對(duì)慣性權(quán)重的選擇和變化的算法性能進(jìn)行分析。關(guān)鍵詞：粒子群、尋優(yōu)、MATLAB、慣性權(quán)重目錄：1.粒子群算法的簡(jiǎn)介 21.1粒子群算法的研究背景 21.2起源 21.3粒子群理論 32.案例背景 42.1問題描述 42.2解題思路及步驟 43.MATLAB編程實(shí)現(xiàn) 53.1設(shè)置PSO算法的運(yùn)行參數(shù) 53.2種群初始化 53.3尋找初始極值 53.4迭代尋優(yōu) 63.5結(jié)果分析 64.慣性權(quán)重對(duì)PSO算法的影響 84.1慣性權(quán)重的選擇 84.2慣性權(quán)重變化的算法性能分析 85結(jié)論 10參考文獻(xiàn)： 111.粒子群算法的簡(jiǎn)介粒子群算法（ParticleSwarmOptimization）是一種新的智能優(yōu)化算法。談到它的發(fā)展歷史，就不得不先介紹下傳統(tǒng)的優(yōu)化算法，正因?yàn)閭鹘y(tǒng)優(yōu)化算法自身的一些不足，才有新智能優(yōu)化算法的興起，而粒子群算法（PSO）就是在這種情況下發(fā)展起來的。1.1粒子群算法的研究背景最優(yōu)化是人們?cè)诳茖W(xué)研究、工程技術(shù)和經(jīng)濟(jì)管理等領(lǐng)域中經(jīng)常遇到的問題。優(yōu)化問題研究的主要內(nèi)容是在解決某個(gè)問題時(shí)，如何從眾多的解決方案中選出最優(yōu)方案。它可以定義為：在一定的約束條件下，求得一組參數(shù)值，使得系統(tǒng)的某項(xiàng)性能指標(biāo)達(dá)到最優(yōu)（最大或最?。鹘y(tǒng)的優(yōu)化方法是借助于優(yōu)化問題的不同性質(zhì)，通常將問題分為線性規(guī)劃問題、非線性規(guī)劃問題、整數(shù)規(guī)劃問題和多目標(biāo)規(guī)劃問題等。相應(yīng)的有一些成熟的常規(guī)算法，如應(yīng)用于線性規(guī)劃問題的單純形法，應(yīng)用于非線性規(guī)劃的牛頓法、共扼梯度法，應(yīng)用于整數(shù)規(guī)則的分枝界定法、動(dòng)態(tài)規(guī)劃等。列舉的這些傳統(tǒng)的優(yōu)化算法能夠解決現(xiàn)實(shí)生活和工程上的很多問題，但工業(yè)和科學(xué)領(lǐng)域大量實(shí)際問題的困難程度正在日益增長(zhǎng)，它們大多是根本無法在可接受的時(shí)間內(nèi)找到解的問題。這類優(yōu)化問題的困難性不僅體現(xiàn)在具有極大的規(guī)模，更為重要的是，它們多數(shù)是非線性的、動(dòng)態(tài)的、多峰的、具有欺騙性的或者不具有任何導(dǎo)數(shù)信息。因此，發(fā)展通用性更強(qiáng)、效率更高的優(yōu)化算法總是需要的。1.2起源在自然界中，鳥群運(yùn)動(dòng)的主體是離散的，其排列看起來是隨機(jī)的，但在整體的運(yùn)動(dòng)中它們卻保持著驚人的同步性，其整體運(yùn)動(dòng)形態(tài)非常流暢且極富美感。這些呈分布狀態(tài)的群體所表現(xiàn)出的似乎是有意識(shí)的集中控制，一直是許多研究者感興趣的問題。有研究者對(duì)鳥群的運(yùn)動(dòng)進(jìn)行了計(jì)算機(jī)仿真，他們通過對(duì)個(gè)體設(shè)定簡(jiǎn)單的運(yùn)動(dòng)規(guī)則，來模擬鳥群整體的復(fù)雜行為。1986年CraigReynolS提出了Boid模型，用以模擬鳥類聚集飛行的行為，通過對(duì)現(xiàn)實(shí)世界中這些群體運(yùn)動(dòng)的觀察，在計(jì)算機(jī)中復(fù)制和重建這些運(yùn)動(dòng)軌跡，并對(duì)這些運(yùn)動(dòng)進(jìn)行抽象建模，以發(fā)現(xiàn)新的運(yùn)動(dòng)模式。之后，生物學(xué)家FrankHeppner在此基礎(chǔ)上增加了棲息地對(duì)鳥吸引的仿真條件，提出了新的鳥群模型。這個(gè)新的鳥群模型的關(guān)鍵在于以個(gè)體之間的運(yùn)算操作為基礎(chǔ)，這個(gè)操作也就是群體行為的同步必須在于個(gè)體努力維持自身與鄰居之間的距離為最優(yōu)，為此每個(gè)個(gè)體必須知道自身位置和鄰居的位置信息。這些都表明群體中個(gè)體之間信息的社會(huì)共享有助于群體的進(jìn)化。在1995年，受到FrankHeppner鳥群模型的影響，社會(huì)心理學(xué)博士James3.MATLAB編程實(shí)現(xiàn)根據(jù)PSO算法原理，在MATLAB里編程實(shí)現(xiàn)基于PSO算法的函數(shù)極值尋優(yōu)算法。3.1設(shè)置PSO算法的運(yùn)行參數(shù)程序代碼如下：%%清空環(huán)境clcclear%%參數(shù)初始化%粒子群算法中的兩個(gè)參數(shù)c1=1.49445;c2=1.49445;maxgen=300;%進(jìn)化次數(shù)sizepop=20;%種群規(guī)模Vmax=0.5;Vmin=-0.5;popmax=2;popmin=-2;%速度和個(gè)體最大最小值3.2種群初始化隨機(jī)初始化粒子位置和粒子速度，并根據(jù)適應(yīng)函數(shù)計(jì)算粒子適應(yīng)度值。%%產(chǎn)生初始粒子和速度f(wàn)ori=1:sizepop%隨機(jī)產(chǎn)生一個(gè)種群pop(i,:)=2*rands(1,2);%初始種群V(i,:)=0.5*rands(1,2);%初始化速度%計(jì)算適應(yīng)度f(wàn)itness(i)=fun(pop(i,:));%計(jì)算粒子的適應(yīng)度值end適應(yīng)度函數(shù)代碼如下：functiony=fun(x)%函數(shù)用于計(jì)算粒子適應(yīng)度值%xinput輸入粒子%youtput粒子適應(yīng)度值y=sin(sqrt(x(1).^2+x(2).^2))./sqrt(x(1).^2+x(2).^2)+exp((cos(2*pi*x(1))+cos(2*pi*x(2)))/2)-2.71289;3.3尋找初始極值%%個(gè)體極值和群體極值[bestfitnessbestindex]=max(fitness);zbest=pop(bestindex,:);%全局最佳gbest=pop;%個(gè)體最佳fitnessgbest=fitness;%個(gè)體最佳適應(yīng)度值fitnesszbest=bestfitness;%全局最佳適應(yīng)度值3.4迭代尋優(yōu)根據(jù)上文中的公式更新粒子位置和速度，并且根據(jù)新粒子的適應(yīng)度值更新個(gè)體極值和群體極值。程序代碼如下：%%迭代尋優(yōu)fori=1:maxgenforj=1:sizepop%速度更新V(j,:)=V(j,:)+c1*rand*(gbest(j,:)-pop(j,:))+c2*rand*(zbest-pop(j,:));V(j,find(V(j,:)>Vmax))=Vmax;V(j,find(V(j,:)<Vmin))=Vmin;%種群更新pop(j,:)=pop(j,:)+V(j,:);pop(j,find(pop(j,:)>popmax))=popmax;pop(j,find(pop(j,:)<popmin))=popmin;%適應(yīng)度值fitness(j)=fun(pop(j,:));endforj=1:sizepop%個(gè)體最優(yōu)更新iffitness(j)>fitnessgbest(j)gbest(j,:)=pop(j,:);fitnessgbest(j)=fitness(j);end%群體最優(yōu)更新iffitness(j)>fitnesszbestzbest=pop(j,:);fitnesszbest=fitness(j);endendyy(i)=fitnesszbest;%每代最優(yōu)值記錄在yy數(shù)組中end3.5結(jié)果分析PSO算法反復(fù)迭代300次，畫出每代個(gè)體適應(yīng)度值變化圖形，程序代碼如下：plot(yy)title('最優(yōu)個(gè)體適應(yīng)度','fontsize',12);xlabel('進(jìn)化代數(shù)','fontsize',12);ylabel('適應(yīng)度','fontsize',12);最優(yōu)個(gè)體適應(yīng)度值變化如圖三所示。圖3最優(yōu)個(gè)體適應(yīng)度值最終得到的最優(yōu)個(gè)體適應(yīng)度值為1.0053，對(duì)應(yīng)的粒子位置為（0.0015，-0.0008），PSO算法尋優(yōu)得到的最優(yōu)值接近函數(shù)實(shí)際最優(yōu)值。但在多次運(yùn)行的時(shí)候會(huì)出現(xiàn)結(jié)果為0.8477左右的極值結(jié)果，如圖4所示，原因在第四章進(jìn)行探討。圖4最優(yōu)個(gè)體適應(yīng)度值的另一結(jié)果4.慣性權(quán)重對(duì)PSO算法的影響4.1慣性權(quán)重的選擇慣性權(quán)重體現(xiàn)的是粒子繼承先前的速度的能力，Shi.Y最先將慣性權(quán)重引入PSO算法中，并分析指出一個(gè)較大的慣性權(quán)值有利于全局搜索，而一個(gè)較小的慣性權(quán)值則更利于局部搜索。為了更好地平衡算法的全局搜索與局部搜索能力，Shi.Y提出了線性遞減慣性權(quán)重，即其中，為初始慣性權(quán)重；為迭代至最大次數(shù)時(shí)的慣性權(quán)重；k為當(dāng)前迭代代數(shù)；為最大迭代代數(shù)。一般來說，慣性權(quán)值=0.9，=0.4時(shí)算法性能最好。這樣，隨著迭代的進(jìn)行，慣性權(quán)重由0.9線性遞減至0.4，迭代初期較大的慣性權(quán)重使算法保持了較強(qiáng)的全局搜索能力，而迭代后期較小的慣性權(quán)重有利于算法進(jìn)行更精確的局部搜索。線性慣性權(quán)重只是一種經(jīng)驗(yàn)做法，常用的慣性權(quán)重的選擇還包括如下幾種：幾種的動(dòng)態(tài)變化如圖5所示，橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為權(quán)重值。圖5四種慣性權(quán)重的變化4.2慣性權(quán)重變化的算法性能分析算法參數(shù)設(shè)置：種群規(guī)模20，進(jìn)化300代。每個(gè)實(shí)驗(yàn)設(shè)置進(jìn)化100次，將100次的平均值作為最終結(jié)果。在上述的參數(shù)設(shè)置下，運(yùn)用4.1中的五種取值方法對(duì)函數(shù)進(jìn)行求解，并比較所得解的平均值、失效次數(shù)和接近最優(yōu)解的次數(shù)，來分析其收斂精度、收斂速度等性能。每種的算法進(jìn)化曲線如圖6所示。圖6五種慣性權(quán)重下函數(shù)平均值的收斂曲線本文解決的尋優(yōu)問題中，將距離最優(yōu)解1.0054誤差為0.01的解視為接近最優(yōu)解，將0.8477及更小的解視為陷人局部最優(yōu)的解。由圖6和表1可以看出，慣性權(quán)重不變的粒子群優(yōu)化算法雖然具有較快的收斂速度，但其后期容易陷入局部最優(yōu)，求解精度低；而幾種動(dòng)態(tài)變化的算法雖然在算法初期收斂稍慢，但在后期局部搜索能力強(qiáng)，利于算法跳出局部最優(yōu)而求得最優(yōu)解，提高了算法的求解精度。表1第三個(gè)函數(shù)動(dòng)態(tài)變化方法，前期變化較慢，取值較大，維持了算法的全局搜索能力；后期變化較快，極大地提高了算法的局部尋優(yōu)能力，從而取得了很好的求解效果。表1五種慣性權(quán)重下的算法性能比較5結(jié)論粒子群算法是在仿真生物群體社會(huì)活動(dòng)的基礎(chǔ)上，通過模擬群體生物相互協(xié)同尋優(yōu)能力，從而構(gòu)造出的一種新的智能優(yōu)化算法。本篇文章簡(jiǎn)要回顧了粒子群算法的發(fā)展歷史，詳細(xì)講解了粒子群算法的理論基礎(chǔ)。之后引入了一個(gè)粒子群算法的實(shí)例即粒子群算法的尋優(yōu)算法，分析了問題，并進(jìn)行了解題步驟的推演，對(duì)其用MATLAB進(jìn)行編程求解，得出結(jié)論。之后針對(duì)粒子群算法尋優(yōu)算法實(shí)例中出現(xiàn)的一個(gè)問題進(jìn)行再探討，即在一定次數(shù)內(nèi)的最優(yōu)值計(jì)算會(huì)出現(xiàn)一次最優(yōu)值不正確的情況。故對(duì)粒子群算法中比較重要的一大因素慣性權(quán)重（也是導(dǎo)致上文問題的因素）進(jìn)行了延伸學(xué)習(xí)和研究，慣性權(quán)重體現(xiàn)的是粒子繼承先前的速度的能力，分析指出一個(gè)較大的慣性權(quán)值有利于全局搜索，而一個(gè)較小的慣性權(quán)值則更利于局部搜索。并對(duì)目前使用較多的五種慣性權(quán)重的函數(shù)進(jìn)行了比較分析，列出了五種慣性權(quán)重在一定次數(shù)內(nèi)計(jì)算中的取值曲線。然后重新編程，分別進(jìn)行100次的尋優(yōu)算法的求解，并統(tǒng)計(jì)結(jié)果做成表格，找到一個(gè)最優(yōu)的取值慣性權(quán)重的函數(shù)，從而能夠盡量避免陷入局部最優(yōu)值并且速度較快的完成既定任務(wù)。通過實(shí)例更好更詳細(xì)的了解和學(xué)習(xí)了粒子群算法這一智能優(yōu)化算法，深入的了解了粒子群算法的尋優(yōu)算法流程和編程思路。參考文獻(xiàn)：[1]楊朝霞，方建文，李佳蓉，等.粒子群優(yōu)化箅法在多參數(shù)擬合中的作用[J].浙江師范大學(xué)學(xué)報(bào)，2008,31(2)：173-177.[2]江寶別，胡俊淇.求解多峰函數(shù)的改進(jìn)粒子群算法研究[J].寧波大學(xué)學(xué)報(bào),2008,21(2):150-154.[3]薛婷.粒子群優(yōu)化箅法的研究與改進(jìn)[D].大連：大連海亊大學(xué),2008.[4]馮翔，陳國(guó)龍，郭文忠.粒子群優(yōu)化算法中加速因子的設(shè)置與實(shí)驗(yàn)分析[J].集美大學(xué)學(xué)報(bào)，2006,11（2）:146-151.[5]張選平，杜玉平，秦國(guó)強(qiáng).一種動(dòng)態(tài)改變慣性權(quán)的自適應(yīng)粒子群算法[J].西安交通大學(xué)學(xué)報(bào)，2005,39(10)：1039-1042.附錄：clcclear%%參數(shù)初始化%粒子群算法中的兩個(gè)參數(shù)c1=1.49445;c2=1.49445;maxgen=300;%進(jìn)化次數(shù)sizepop=20;%種群規(guī)模Vmax=0.5;%速度和個(gè)體最大最小值Vmin=-0.5;popmax=2;popmin=-2;fori=1:sizepoppop(i,:)=2*rands(1,2);%初始種群V(i,:)=0.5*rands(1,2);%初始化速度f(wàn)itness(i)=fun(pop(i,:));%計(jì)算粒子的適應(yīng)度值end[bestfitnessbestindex]=max(fitness);zbest=pop(bestindex,:);%全局最佳gbest=pop;%個(gè)體最佳fitnessgbest=fitness;%個(gè)體最佳適應(yīng)度值fitnesszbest=bestfitness;%全局最佳適應(yīng)度值fori=1:maxgenforj=1:sizepopV(j,:)=V(j,:)+c1*rand*(gbest(j,:)-pop(j,:))+c2*rand*(zbest-pop(j,:));V(j,find(V(j,:)>Vmax))=Vmax;V(j,find(V(j,:)<Vmin))=Vmin;pop(j,:)=pop(j,:)+V(j,:);pop(j,find(pop(j,:)>popmax))=popmax;pop(j,find(pop(j,:)<popmin))=popm