粒子群算法論文

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