粒子群算法的由來及思想

粒子群算法最早是由兩名美國的科學家基于群鳥覓食，尋找最佳覓食區域的過程所提出來的，作為一種智能算法，PSO模擬的就是最佳決策的過程，鳥群覓食類似于人類的決策過程，想想在你做出選擇之前，是不是會受到自己的經驗（局部最優）以及周圍人的經歷（全局最優）的影響？同樣的道理，群鳥在覓食的過程當中，每一只鳥的初始位置都處于隨機狀態，當然也不知道最佳的覓食點在何處，并且每只鳥的飛行方向也是隨機的。可以認為，在覓食的初期，鳥群的運動軌跡都是雜亂無章的，隨著時間的推移，處于隨機位置的鳥類通過群內的相互學習、共享覓食信息，每一只鳥在每一次的覓食過程中結合自己的經驗和同伴傳送的信息估計目前所處的位置能夠找到食物有多大的價值。基于這樣的搜索方式，粒子群算法（Particle Swarm Optimization,PSO）應運而生。

基本概念

每只鳥在某處位置能夠找到食物的可能可以通過適應值來刻畫，每只鳥能夠記住自己的覓食位置，并且找到其中的最佳位置（局部最優），鳥群中所有個體的最佳位置就可以看做整個鳥群的最佳覓食點（全局最優）。可以預見的是，整個鳥群的覓食活動總體上一定是往這個全局最優的覓食區域運動的，通過鳥群覓食位置的不斷移動即不斷地迭代，速度的不斷更新，鳥群往該最優位置步步逼近。

• 鳥群中的每一個個體都可以當做一個粒子，鳥群即可被看做粒子群。假設一個有M個粒子的粒子群在一個N維空間內尋找最優位置，那么可以對每個粒子賦予一個“位置”：

• 對于每一個粒子而言，該位置即為問題的一個潛在解，在這個位置能覓到食物的可能性有多大呢？既可以通過將 帶入目標函數計算其適應值，根據適應值大小來衡量其優劣。在每一次的搜尋過程中，記錄每個粒子的最優位置：

• 在本次覓食搜尋過程中，所有粒子最優位置的最優解即可當做整個粒子群的最佳覓食位置：

• 反復進行食物的搜尋過程（進行迭代），直至找到全局最優解為止。當然在每一次位置的尋找之后，應該對粒子的速度和所在位置進行更新，記第i個粒子的速度為：

• 粒子的速度及位置更新的方式如下：

其中

是一個非負數，稱為慣性因子，對算法的收斂起到很大的作用，其值越大，粒子飛躍的范圍就越廣，更容易找到全局最優，但是也會錯失局部搜尋的能力。

分別為局部和全局最優位置。

加速常數 也是非負常數，是調整局部最優值和全局最優值權重的參數，如果前者為0說明搜尋過程中沒有自身經驗只有社會經驗，容易陷入局部最優解；若后者為0，即只有社會經驗，沒有自身經驗，常常會陷入局部最優解中，不能飛越該局部最優區域。

是[0,1]范圍之內的隨機數， 是約束因子，目的是控制速度的權重。

從上面速度和位置分量的改變規則我們可以看到，速度的存在的根本作用還是為了改變粒子的位置，計算新一輪粒子的適應值，其中的參數的設置也會影響到對全局最優解的搜尋。在一般情況下，我們會對粒子的速度分量進行限制，

,如果粒子的速度分量在更新之后超過最大飛翔速度，則應該根據不同的情況進行優化問題的設定。

迭代終止條件根據具體問題而定，一般達到預定最大迭代次數或者粒子群目前為止搜尋到的最優位置滿足目標函數的最小容許誤差。

PSO算法的主要實現步驟

初始化粒子群。包括粒子的初始位置及速度，慣性因子等參數值

粒子數M一般選取20~40個，不過對于一些特殊的難題需要更多的粒子，粒子數量越多，搜索范圍就越廣，越容易找到全局最優解，但是也會帶來更大的計算消耗。

2. 評價各個粒子的初始適應值。

3. 將初始的適應值作為各個粒子的局部最優解，保存各粒子的最優位置。并找到其中的最優值，作為全局最優解的初值，并記錄其位置

4. 更新粒子速度及位置

5. 計算更新后粒子的適應值，更新每個粒子的局部最優值以及整個粒子群的全局最優值。

6. 重復4~5直至滿足迭代結束條件

圖1 程序設計流程圖

粒子群算法的matlab程序實現

• 問題1：求解 之間的最小值

% 目標函數 function f=target(x) %x in[0,9] f=x+6*sin(4.*x)+9*cos(5.*x); end

主程序：PSO.m

%looking for min-functinal value using "Practicle Swarm Optimization"function [Gbest_x,Gbest_y]=PSO() %Parameter settings lower_bound = 0; higher_bound = 9; particle = 20; % 粒子個數 max_iteration = 100; % 最大迭代數 dimension = 1; % 粒子位置的維度，即自變量個數 c1 = 2; % 加速常數1，控制局部最優解 c2 = 2; % 加速常數2，控制全局最優解 w = 0.6; % 慣性因子 vmax = 0.8; % 速度最大值 precision=0.001; % 精度設置%Initialize x = lower_bound+rand(particle,dimension).*(higher_bound-lower_bound); v = 2*rand(particle,dimension); Pbest_x=x; % 將初始位置設置為局部最優解的位置 Pbest_y=target(x); % 各個粒子的函數值作為其局部最優解 Gbest_y=inf; % 全局最優解的初始值設置為inf Gbest_x = x(1,:); % 初始全局最優位置設定為第一個粒子的位置 k=1; f=zeros(particle,1);%plot the function horizon = linspace(0,9,500); vertical = target(horizon); plot(horizon,vertical); hold on [m,index] = min(vertical); text(horizon(index)+0.5,m,['{F_{min}}= ',num2str(m)]) pic_num = 1;while k<=max_iterationflagx=Gbest_x;flagy=Gbest_y;% 搜尋各個粒子的局部最優for i=1:particlef(i) = target(x(i,:));if f(i)<Pbest_y(i)Pbest_y(i)=f(i); % Personal best function valuePbest_x(i)=x(i,:); % Personal best variableendend% 更新全局最優位置及適應值[Gbest_y,index] = min(Pbest_y);Gbest_x = x(index,:);% 每一次搜尋之后更新粒子的速度及位置for n=1:particlev(n,:)=w*v(n,:)+c1*rand()*(Pbest_x(n,:)-x(n,:))+c2*rand()*(Gbest_x-x(n,:));% 速度越界操作for p=1:dimensionif v(n,p)>vmaxv(n,p)=vmax;elseif v(n,p)<-vmaxv(n,p)=-vmax;endendx(n,:)=x(n,:)+v(n,:);end% 獲取動態搜尋過程gif圖figure(1)scatter(Gbest_x,target(Gbest_x))hold onh1=text(6,-4,['X by TSO=',num2str(Gbest_x)]);h2=text(6,-6,['Y by TSO=',num2str(target(Gbest_x))]);pause(0.2)drawnow;F=getframe(gcf);I=frame2im(F);[I,map]=rgb2ind(I,256);if pic_num == 1imwrite(I,map,'PSO.gif','gif', 'Loopcount',inf,'DelayTime',0.2);elseimwrite(I,map,'PSO.gif','gif','WriteMode','append','DelayTime',0.2);enddelete(h1);delete(h2)pic_num = pic_num + 1;% 如果迭代前后全局最優解的差小于精度要求退出if abs(flagx-Gbest_x)<precision&&abs(flagy-Gbest_y)<precisionbreakelsek=k+1;endendstring=['Min-value by TSO is ',num2str(Gbest_y),', where x= ',num2str(Gbest_x)]; title(string)

其中一次運行結果：

>> [Gbest_x,Gbest_y]=PSO(); >> Gbest_x Gbest_x =4.3744 >> Gbest_y Gbest_y =-10.4199

圖2 PSO算法求一元函數最小值

可見，最終在x=4.3744處找到的全局最優解-10.4199，與函數的最小值

=- 10.4122相差不大。手鏈效果也較好。

• 問題2：PSO算法求解背包問題

背包問題：現有一小偷入室盜竊，可以偷竊的物品數量共有12件，物品對應的價值（萬）為[5;10;13;4;3;11;13;10;8;16;7;4]； 重量（千克）為[2;5;18;3;2;5;10;4;11;7;14;6]。若小偷能拿的物品總質量最大為46kg，如何選取物品使得總價值最大？

%目標函數 function f = target_BAG(x,value,weight,ratio,restriction) Money = sum(x*value); Lost = sum(x*weight); if Lost < restrictionf = Money; elsex=~x;Money = sum(x*value);f = Money-round((Lost-restriction)*ratio); end

目標函數用于計算小偷所投物品的質量及價值，如果此時的重量超過了限制，就將所偷物品價值減小。

function [GBest_x,GBest_y,Record]= PSO_BAG() value = [5;10;13;4;3;11;13;10;8;16;7;4]; % 物品重量 weight = [2;5;18;3;2;5;10;4;11;7;14;6]; % 物品價值 restriction = 46; % 背包重量限制 practicle = 20; % 粒子數 max_iteration = 100; dimension = size(value,1); ratio = 2.5; c1 = 2; c2 = 2; wmin = 0.6; wmax = 0.8; vmax = 0.8; time=1; %Initialize x = round(rand(practicle,dimension)); % 背包問題中的粒子取值為0或1，代表選擇物品或不選擇物品 v=rand(practicle,dimension)*(2*vmax)-vmax;PBest_x = x; PBest_y = zeros(1,dimension); for i=1:practiclePBest_y(i) = target_BAG(PBest_x(i,:),value,weight,ratio,restriction); %將總價值作為局部最優解 endGBest_x = ones(1,dimension); GBest_y = 0; Record = zeros(1,max_iteration); for j=1:practicleif PBest_y(j)>GBest_yGBest_y = PBest_y(j);GBest_x = x(j,:);end endwhile time<=max_iteration% Personal-Best searchingfor i=1:practiclef = target_BAG(x(i,:),value,weight,ratio,restriction);if f>PBest_y(i)PBest_y(i)=f;PBest_x(i,:)=x(i,:);end% Global Best searchingif PBest_y(i) > GBest_yGBest_y = PBest_y(i);GBest_x = PBest_x(i,:);end% Updating the speed and positionw=wmin+rand()*(wmax-wmin); % weight is dynamicv(i,:) = w*v(i,:) + c1*rand()*(PBest_x(i,:)-x(i,:)) + c2*rand()*(GBest_x-x(i,:));for ii=1:dimensionif (v(i,ii)<-vmax)||(v(i,ii)>vmax)v(i,ii)=rand*(2*vmax)-vmax;endendvv(i,:)=1./(1+exp(-v(i,:)));for k=1:dimensionif vv(i,k)>randx(i,k)=1;elsex(i,k)=0;endendendRecord(k) = GBest_y;time = time+1; endM = GBest_y; % the value of the bag N = GBest_x*weight; % the weight of the bag disp('---------------------------------------') disp(['The final steal value is:',num2str(M)]); disp(['The final steal weight is:',num2str(N)]); string=strcat('Steal items:',num2str(GBest_x)); disp(string)

其中一次運行結果：

--------------------------------------- The final steal value is:76 The final steal weight is:44 Steal items:1 1 0 1 1 1 1 1 0 1 0 1選取第1,2,4,5,6,7,8,10,12個物品，總價值為76，總重量為44.

當然，PSO是一個基于概率的隨機自搜索算法，每次的搜索結果都不盡相同，但是若算法的收斂性表現的較好，也可以認為對算法的設計是合理的。

---

總結

以上是生活随笔為你收集整理的粒子群算法组卷_粒子群（PSO）算法概念及代码实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。