1、PAGE 13粒子群算法的尋優算法摘要：粒子群算法是在仿真生物群體社會活動的基礎上，通過模擬群體生物相互協同尋優能力，從而構造出一種新的智能優化算法。這篇文章簡要回顧了粒子群算法的發展歷史；引入了一個粒子群算法的實例，對其用MATLAB進行編程求解，得出結論。之后還對其中的慣性權重進行了延伸研究，對慣性權重的選擇和變化的算法性能進行分析。關鍵詞：粒子群、尋優、MATLAB、慣性權重目錄： TOC o 1-3 h z u HYPERLINK l _Toc500682390 1.粒子群算法的簡介 PAGEREF _Toc500682390 h 3 HYPERLINK l _Toc500682391

2、 1.1 粒子群算法的研究背景 PAGEREF _Toc500682391 h 3 HYPERLINK l _Toc500682392 1.2 起源 PAGEREF _Toc500682392 h 3 HYPERLINK l _Toc500682393 1.3 粒子群理論 PAGEREF _Toc500682393 h 4 HYPERLINK l _Toc500682394 2.案例背景 PAGEREF _Toc500682394 h 5 HYPERLINK l _Toc500682395 2.1問題描述 PAGEREF _Toc500682395 h 5 HYPERLINK l _Toc50

3、0682396 2.2 解題思路及步驟 PAGEREF _Toc500682396 h 5 HYPERLINK l _Toc500682397 3.MATLAB編程實現 PAGEREF _Toc500682397 h 6 HYPERLINK l _Toc500682398 3.1設置PSO算法的運行參數 PAGEREF _Toc500682398 h 6 HYPERLINK l _Toc500682399 3.2種群初始化 PAGEREF _Toc500682399 h 6 HYPERLINK l _Toc500682400 3.3尋找初始極值 PAGEREF _Toc500682400 h

4、6 HYPERLINK l _Toc500682401 3.4迭代尋優 PAGEREF _Toc500682401 h 7 HYPERLINK l _Toc500682402 3.5結果分析 PAGEREF _Toc500682402 h 7 HYPERLINK l _Toc500682403 4.慣性權重對PSO算法的影響 PAGEREF _Toc500682403 h 9 HYPERLINK l _Toc500682404 4.1慣性權重的選擇 PAGEREF _Toc500682404 h 9 HYPERLINK l _Toc500682405 4.2慣性權重變化的算法性能分析 PAGE

5、REF _Toc500682405 h 9 HYPERLINK l _Toc500682406 5 結論 PAGEREF _Toc500682406 h 11 HYPERLINK l _Toc500682407 參考文獻： PAGEREF _Toc500682407 h 121.粒子群算法的簡介粒子群算法（Particle Swarm Optimization）是一種新的智能優化算法。談到它的發展歷史，就不得不先介紹下傳統的優化算法，正因為傳統優化算法自身的一些不足，才有新智能優化算法的興起，而粒子群算法（PSO）就是在這種情況下發展起來的。1.1 粒子群算法的研究背景最優化是人們在科學研究、

6、工程技術和經濟管理等領域中經常遇到的問題。優化問題研究的主要內容是在解決某個問題時，如何從眾多的解決方案中選出最優方案。它可以定義為：在一定的約束條件下，求得一組參數值，使得系統的某項性能指標達到最優 （最大或最小）。傳統的優化方法是借助于優化問題的不同性質，通常將問題分為線性規劃問題、 非線性規劃 問題、整數規劃問題和多目標規劃問題等。相應的有一些成熟的常規算法，如應用于線性規劃問題的單純形法，應用于非線性規劃的牛頓法、共扼梯度法，應用于整數規則的分枝界定 法、動態規劃等。列舉的這些傳統的優化算法能夠解決現實生活和工程上的很多問題，但工業和科學領域大量實際問題的困難程度正在日益增長，它們大多

7、是根本無法在可接受的時間 內找到解的問題。這類優化問題的困難性不僅體現在具有極大的規模，更為重要的是，它們多數是非線性的、動態的、多峰的、具有欺騙性的或者不具有任何導數信息。因此，發展通用性更強、效率更高的優化算法總是需要的。 1.2 起源在自然界中，鳥群運動的主體是離散的，其排列看起來是隨機的，但在整體的運動中它們卻保持著驚人的同步性，其整體運動形態非常流暢且極富美感。這些呈分布狀態的群體所表現出的似乎是有意識的集中控制，一直是許多研究者感興趣的問題。有研究者對鳥群的運動進行了計算機仿真，他們通過對個體設定簡單的運動規則，來模擬鳥群整體的復雜行為。1986 年 Craig ReynolS 提

8、出了 Boid 模型，用以模擬鳥類聚集飛行的行為，通過對現實世界中這些群體運動的觀察，在計算機中復制和重建這些運動軌跡，并對這些運動進行抽象建模，以發現新的運動模式。之后，生物學家 Frank Heppner 在此基礎上增加了棲息地對鳥吸引的仿真條件，提出了新的鳥群模型。這個新的鳥群模型的關鍵在于以個體之間的運算操作為基礎，這個操作也就是群體行為的同步必須在于個體努力維持自身與鄰居之間的距離為最優，為此每個個體必須知道自身位置和鄰居的位置信息。這些都表明群體中個體之間信息的社會共享有助于群體的進化。在 1995年，受到 Frank Heppner 鳥群模型的影響，社會心理學博士 James K

9、ennedy 和電子工程學博士 Russell Eherhart 提出了粒子群算法。粒子群算法其實也是一種演化計算技術，該算法將鳥群運動模型中的棲息地類比于所求問題空間中可能解的位置，通過個體間的信息傳遞，導引整個群體向可能解的方向移動， 在求解過程中逐步增加發現較好解的可能性。群體中的鳥被抽象為沒有質量和體積的“粒子”，通過這些“粒子”間的相互協作和信息共享，使其運動速度受到自身和群體的歷史運動狀態信息的影響。以自身和群體的歷史最優位置對粒子當前的運動方向和運動速度加以影響，較好地協調粒子本身和群體之間的關系，以利于群體在復雜的解空間中進行尋優操作。1.3 粒子群理論求解優化問題的，算法中每

10、個粒子都代表問題的一個潛在解，每個粒子對應一個由適應度函數決定的適應度值。粒子的速度決定了粒子移動的方向和距離，速度隨自身及其他粒子的移動經驗進行動態調整，從而實現個體在可解空間中的尋優。PSO 算法首先在可行解空間中初始化一群粒子，每個粒子都代表極值優化問題的一個潛在最優解，用位置、速度和適應度值三項指標表示該粒子特征，適應度值由適應度函數計算得到，其值的好壞表示粒子的優劣。粒子在解空間中運動，通過跟蹤個體極值 Pbest 和群體極值Gbest 更新個體位置。個體極值 Pbest是指個體所經歷位置中計算得到的適應度值最優位置，群體極值 Gbest 是指種群中的所有粒子搜索到的適應度最優位置。

11、粒子每更新一次位置，就計算一次適應度值，并且通過比較新粒子的適應度值和個體極值、群體極值的適應度值更新個體極值 Pbest 和群體極值 Gbest 位置。 假設在一個D維的搜索空間中，由n個粒子組成的種群X=(X1，X2，Xn），其中第i個粒子表示為一個D維的向量代表第 i個粒 子在D維搜索空間中的位置，亦代表問題的一個潛在解。根據目標函數即可計算出每個粒子位置Xi對應的適應度值。第i個粒子的速度為，其個體極值為，種群的群體極值為。在每次迭代過程中粒子通過個體極值和群體極值更新自身的速度和位置，即其中為慣性權重，d = l，2，D；i = l，2 ，n；k為當前迭代次數為粒子的速度；c1和c2

12、是非負的常數，稱為加速度因子；r1和r2是分布于0, 1區間的隨機數。為防止粒子的盲目搜索，一般建議將其位置和速度限制在一定的區間、。2.案例背景2.1問題描述本案例尋優的非線性函數為：函數圖形如下圖所示。圖1 函數圖像從函數圖像可以看出，該函數有很多局部最優點，而極限位置為（0，0），在（0,0）附近取得極大值。2.2 解題思路及步驟基于PSO算法的函數極值尋優算法流程圖如圖2所示。圖2 算法流程其中，粒子和速度初始化隨機初始化粒子速度和粒子位置；由第一章中的公式計算粒子適應度值；根據初始粒子適應度值確定個體極值和群體極值；根據公式更新粒子速度和位置；根據新種群中粒子適應度值更新個體極值和群

13、體極值。本題中，適應度函數為函數表達式，適應度值為函數值。種群粒子數設置為20，每個粒子的維數為2，算法迭代次數定為300次。3.MATLAB編程實現 根據PSO算法原理，在MATLAB里編程實現基于PSO算法的函數極值尋優算法。3.1設置PSO算法的運行參數程序代碼如下：% 清空環境clcclear% 參數初始化%粒子群算法中的兩個參數c1 = 1.49445; c2 = 1.49445;maxgen=300; % 進化次數 sizepop=20; %種群規模Vmax=0.5; Vmin=-0.5;popmax=2;popmin=-2; %速度和個體最大最小值3.2種群初始化隨機初始化粒子位

14、置和粒子速度，并根據適應函數計算粒子適應度值。% 產生初始粒子和速度for i=1:sizepop %隨機產生一個種群 pop(i,:)=2*rands(1,2); %初始種群 V(i,:)=0.5*rands(1,2); %初始化速度 %計算適應度 fitness(i)=fun(pop(i,:); %計算粒子的適應度值end適應度函數代碼如下：function y = fun(x)%函數用于計算粒子適應度值 %x input 輸入粒子 %y output 粒子適應度值 y=sin( sqrt(x(1).2+x(2).2) )./sqrt(x(1).2+x(2).2)+exp(cos(2*pi

15、*x(1)+cos(2*pi*x(2)/2)-2.71289;3.3尋找初始極值% 個體極值和群體極值bestfitness bestindex=max(fitness);zbest=pop(bestindex,:); %全局最佳gbest=pop; %個體最佳fitnessgbest=fitness; %個體最佳適應度值fitnesszbest=bestfitness; %全局最佳適應度值3.4迭代尋優 根據上文中的公式更新粒子位置和速度，并且根據新粒子的適應度值更新個體極值和群體極值。程序代碼如下：% 迭代尋優for i=1:maxgen for j=1:sizepop %速度更新 V(j

16、,:) = 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,:)popmax)=popmax; pop(j,find(pop(j,:) fitnessgbest(j) gbest(j,:) = pop(j,:); fitnessgbest(j) = fitness(j); end %群體最優更新 if fitness(j) fitnesszbest zbest = pop(j,:); fitnesszbest = fitnes

17、s(j); end end yy(i)=fitnesszbest; %每代最優值記錄在yy數組中end3.5結果分析 PSO算法反復迭代300次，畫出每代個體適應度值變化圖形，程序代碼如下：plot(yy)title(最優個體適應度,fontsize,12);xlabel(進化代數,fontsize,12);ylabel(適應度,fontsize,12);最優個體適應度值變化如圖三所示。圖3 最優個體適應度值 最終得到的最優個體適應度值為1.0053，對應的粒子位置為（0.0015，-0.0008），PSO算法尋優得到的最優值接近函數實際最優值。但在多次運行的時候會出現結果為0.8477左右的

18、極值結果，如圖4所示，原因在第四章進行探討。圖4 最優個體適應度值的另一結果4.慣性權重對PSO算法的影響4.1慣性權重的選擇慣性權重體現的是粒子繼承先前的速度的能力，Shi.Y 最先將慣性權重引入 PSO算法中，并分析指出一個較大的慣性權值有利于全局搜索，而一個較小的慣性權值則更利于局部搜索。為了更好地平衡算法的全局搜索與局部搜索能力，Shi.Y 提出了線性遞減慣性權重，即其中，為初始慣性權重；為迭代至最大次數時的慣性權重；k為當前迭代代數；為最大迭代代數。一般來說，慣性權值=0.9，= 0.4時算法性能最好。這樣，隨著迭代的進行，慣性權重由0.9線性遞減至0.4，迭代初期較大的慣性權重使算

19、法保持了較強的全局搜索能力，而迭代后期較小的慣性權重有利于算法進行更精確的局部搜索。線性慣性權重只是一種經驗做法，常用的慣性權重的選擇還包括如下幾種：幾種的動態變化如圖5所示，橫坐標為迭代次數，縱坐標為權重值。圖5 四種慣性權重的變化4.2慣性權重變化的算法性能分析算法參數設置：種群規模20，進化300代。每個實驗設置進化100次，將100次的平均值作為最終結果。在上述的參數設置下，運用4.1中的五種取值方法對函數進行求解，并比較所得解的平均值、失效次數和接近最優解的次數，來分析其收斂精度、收斂速度等性能。每種的算法進化曲線如圖6所示。圖6 五種慣性權重下函數平均值的收斂曲線本文解決的尋優問題

20、中，將距離最優解1.0054誤差為0.01的解視為接近最優解，將0.8477及更小的解視為陷人局部最優的解。由圖6和表1可以看出，慣性權重不變的粒子群優化算法雖然具有較快的收斂速度，但其后期容易陷入局部最優，求解精度低；而幾種動態變化的算法雖然在算法初期收斂稍慢，但在后期局部搜索能力強，利于算法跳出局部最優而求得最優解，提高了算法的求解精度。表1第三個函數動態變化方法，前期變化較慢，取值較大，維持了算法的全局搜索能力；后期變化較快，極大地提高了算法的局部尋優能力，從而取得了很好的求解效果。表1 五種慣性權重下的算法性能比較5 結論粒子群算法是在仿真生物群體社會活動的基礎上，通過模擬群體生物相互

21、協同尋優能力，從而構造出的一種新的智能優化算法。本篇文章簡要回顧了粒子群算法的發展歷史，詳細講解了粒子群算法的理論基礎。之后引入了一個粒子群算法的實例即粒子群算法的尋優算法，分析了問題，并進行了解題步驟的推演，對其用MATLAB進行編程求解，得出結論。之后針對粒子群算法尋優算法實例中出現的一個問題進行再探討，即在一定次數內的最優值計算會出現一次最優值不正確的情況。故對粒子群算法中比較重要的一大因素慣性權重（也是導致上文問題的因素）進行了延伸學習和研究，慣性權重體現的是粒子繼承先前的速度的能力，分析指出一個較大的慣性權值有利于全局搜索，而一個較小的慣性權值則更利于局部搜索。并對目前使用較多的五種

22、慣性權重的函數進行了比較分析，列出了五種慣性權重在一定次數內計算中的取值曲線。然后重新編程，分別進行100次的尋優算法的求解，并統計結果做成表格，找到一個最優的取值慣性權重的函數，從而能夠盡量避免陷入局部最優值并且速度較快的完成既定任務。 通過實例更好更詳細的了解和學習了粒子群算法這一智能優化算法，深入的了解了粒子群算法的尋優算法流程和編程思路。參考文獻：1 楊朝霞，方建文，李佳蓉，等.粒子群優化箅法在多參數擬合中的作用J.浙江師范大學學報，2008,31(2)：173 - 177.2 江寶別，胡俊淇.求解多峰函數的改進粒子群算法研究J.寧波大學學報,2008,21(2) :150- 154.

23、3 薛婷.粒子群優化箅法的研究與改進D.大連：大連海亊大學,2008.4 馮翔，陳國龍，郭文忠.粒子群優化算法中加速因子的設置與實驗分析J.集美大學學報，2006,11（2）:146-151.5 張選平，杜玉平，秦國強.一種動態改變慣性權的自適應粒子群算法J.西安交通大學學報，2005,39(10)：1039 - 1042.附錄：clcclear% 參數初始化%粒子群算法中的兩個參數c1 = 1.49445;c2 = 1.49445;maxgen=300; % 進化次數 sizepop=20; %種群規模Vmax=0.5; %速度和個體最大最小值Vmin=-0.5;popmax=2;popmin=-2;for i=1:sizepop pop(i,:)=2*rands(1,2); %初始種群 V(i,:)=0.5*rands(1,2); %初始化速度 fitness(i)=fun(p