1、PAGE 13粒子群算法的尋優(yōu)算法摘要：粒子群算法是在仿真生物群體社會(huì)活動(dòng)的基礎(chǔ)上，通過模擬群體生物相互協(xié)同尋優(yōu)能力，從而構(gòu)造出一種新的智能優(yōu)化算法。這篇文章簡要回顧了粒子群算法的發(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)重目錄： 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編程實(shí)現(xiàn) PAGEREF _Toc500682397 h 6 HYPERLINK l _Toc500682398 3.1設(shè)置PSO算法的運(yùn)行參數(shù) 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迭代尋優(yōu) PAGEREF _Toc500682401 h 7 HYPERLINK l _Toc500682402 3.5結(jié)果分析 PAGEREF _Toc500682402 h 7 HYPERLINK l _Toc500682403 4.慣性權(quán)重對(duì)PSO算法的影響 PAGEREF _Toc500682403 h 9 HYPERLINK l _Toc500682404 4.1慣性權(quán)重的選擇 PAGEREF _Toc500682404 h 9 HYPERLINK l _Toc500682405 4.2慣性權(quán)重變化的算法性能分析 PAGE

5、REF _Toc500682405 h 9 HYPERLINK l _Toc500682406 5 結(jié)論 PAGEREF _Toc500682406 h 11 HYPERLINK l _Toc500682407 參考文獻(xiàn)： PAGEREF _Toc500682407 h 121.粒子群算法的簡介粒子群算法（Particle Swarm Optimization）是一種新的智能優(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é)研究、

6、工程技術(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) （最大或最小）。傳統(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í)際問題的困難程度正在日益增長，它們大多

7、是根本無法在可接受的時(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è)定簡單的運(yùn)動(dòng)規(guī)則，來模擬鳥群整體的復(fù)雜行為。1986 年 Craig ReynolS 提

8、出了 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é)家 Frank Heppner 在此基礎(chǔ)上增加了棲息地對(duì)鳥吸引的仿真條件，提出了新的鳥群模型。這個(gè)新的鳥群模型的關(guān)鍵在于以個(gè)體之間的運(yùn)算操作為基礎(chǔ)，這個(gè)操作也就是群體行為的同步必須在于個(gè)體努力維持自身與鄰居之間的距離為最優(yōu)，為此每個(gè)個(gè)體必須知道自身位置和鄰居的位置信息。這些都表明群體中個(gè)體之間信息的社會(huì)共享有助于群體的進(jìn)化。在 1995年，受到 Frank Heppner 鳥群模型的影響，社會(huì)心理學(xué)博士 James K

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

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

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

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

13、體極值。本題中，適應(yīng)度函數(shù)為函數(shù)表達(dá)式，適應(yīng)度值為函數(shù)值。種群粒子數(shù)設(shè)置為20，每個(gè)粒子的維數(shù)為2，算法迭代次數(shù)定為300次。3.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ī)初始化粒子位

14、置和粒子速度，并根據(jù)適應(yīng)函數(shù)計(jì)算粒子適應(yīng)度值。% 產(chǎn)生初始粒子和速度for i=1:sizepop %隨機(jī)產(chǎn)生一個(gè)種群 pop(i,:)=2*rands(1,2); %初始種群 V(i,:)=0.5*rands(1,2); %初始化速度 %計(jì)算適應(yīng)度 fitness(i)=fun(pop(i,:); %計(jì)算粒子的適應(yīng)度值end適應(yīng)度函數(shù)代碼如下：function y = fun(x)%函數(shù)用于計(jì)算粒子適應(yīng)度值 %x input 輸入粒子 %y output 粒子適應(yīng)度值 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尋找初始極值% 個(gè)體極值和群體極值bestfitness bestindex=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)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 %群體最優(yōu)更新 if fitness(j) fitnesszbest zbest = pop(j,:); fitnesszbest = fitnes

17、s(j); end end yy(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左右的

18、極值結(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)重使算

19、法保持了較強(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)問題

20、中，將距離最優(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ǔ)上，通過模擬群體生物相互

21、協(xié)同尋優(yōu)能力，從而構(gòu)造出的一種新的智能優(yōu)化算法。本篇文章簡要回顧了粒子群算法的發(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ì)目前使用較多的五種

22、慣性權(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.

23、3 薛婷.粒子群優(yōu)化箅法的研究與改進(jìn)D.大連：大連海亊大學(xué),2008.4 馮翔，陳國龍，郭文忠.粒子群優(yōu)化算法中加速因子的設(shè)置與實(shí)驗(yàn)分析J.集美大學(xué)學(xué)報(bào)，2006,11（2）:146-151.5 張選平，杜玉平，秦國強(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;for i=1:sizepop pop(i,:)=2*rands(1,2); %初始種群 V(i,:)=0.5*rands(1,2); %初始化速度 fitness(i)=fun(p