同進化算法（見博客《[Evolutionary Algorithm] 進化算法簡介》，進化算法是受生物進化機制啟發(fā)而產(chǎn)生的一系列算法）和人工神經(jīng)網(wǎng)絡(luò)算法（Neural Networks，簡稱NN，神經(jīng)網(wǎng)絡(luò)是從信息處理角度對人腦的神經(jīng)元網(wǎng)絡(luò)系統(tǒng)進行了模擬的相關(guān)算法）一樣，群體智能優(yōu)化算法也屬于一種生物啟發(fā)式方法，它們?nèi)呖梢苑Q為是人工智能領(lǐng)域的三駕馬車（PS：實際上除了上述三種算法還有一些智能算法應(yīng)用也很廣泛，比如模擬金屬物質(zhì)熱力學(xué)退火過程的模擬退火算法（Simulated Algorithm，簡稱SA），模擬人體免疫系統(tǒng)在抗原刺激下產(chǎn)生抗體過程的人工免疫系統(tǒng)算法（Artificial Immune System，簡稱AIS）等，但是相對三者而言，模擬退火和人工免疫系統(tǒng)算法已逐漸處于低潮期）。群體智能優(yōu)化算法主要模擬了昆蟲、獸群、鳥群和魚群的群集行為，這些群體按照一種合作的方式尋找食物，群體中的每個成員通過學(xué)習(xí)它自身的經(jīng)驗和其他成員的經(jīng)驗來不斷地改變搜索的方向。群體智能優(yōu)化算法的突出特點就是利用了種群的群體智慧進行協(xié)同搜索，從而在解空間內(nèi)找到最優(yōu)解。

1. 常見的群體智能優(yōu)化算法分類

　　常見的群體智能優(yōu)化算法主要有如下幾類：

　　（1）蟻群算法（Ant Colony Optimization，簡稱ACO）[1992年提出]；

　　（2）粒子群優(yōu)化算法（Particle Swarm Optimization，簡稱PSO）[1995年提出]（簡單易于實現(xiàn)，也是目前應(yīng)用最為廣泛的群體智能優(yōu)化算法）；

　　（3）菌群優(yōu)化算法（Bacterial Foraging Optimization，簡稱BFO）[2002年提出]；

　　（4）蛙跳算法（Shuffled Frog Leading Algorithm，簡稱SFLA）[2003年提出]；

　　（5）人工蜂群算法（Artificial Bee Colony Algorithm，簡稱ABC）[2005年提出]；

　　除了上述幾種常見的群體智能算法以外，還有一些并不是廣泛應(yīng)用的群體智能算法，比如螢火蟲算法、布谷鳥算法、蝙蝠算法以及磷蝦群算法等等。

回到頂部

2. 粒子群優(yōu)化算法思想

　　由于博主對粒子群優(yōu)化算法比較熟悉，在碩士期間也進行了比較系統(tǒng)的學(xué)習(xí)，所以利用本博文系統(tǒng)的介紹一下應(yīng)用最為廣泛的PSO算法。

　　粒子群優(yōu)化算法是在1995年由Eberhart博士和Kennedy博士一起提出的，它源于對鳥群捕食行為的研究。它的基本核心是利用群體中的個體對信息的共享從而使得整個群體的運動在問題求解空間中產(chǎn)生從無序到有序的演化過程，從而獲得問題的最優(yōu)解。我們可以利用一個有關(guān)PSO的經(jīng)典描述來對PSO算法進行一個直觀的描述。設(shè)想這么一個場景：一群鳥進行覓食，而遠處有一片玉米地，所有的鳥都不知道玉米地到底在哪里，但是它們知道自己當(dāng)前的位置距離玉米地有多遠。那么找到玉米地的最佳策略，也是最簡單有效的策略就是是搜尋目前距離玉米地最近的鳥群的周圍區(qū)域。PSO就是從這種群體覓食的行為中得到了啟示，從而構(gòu)建的一種優(yōu)化模型。

　　在PSO中，每個優(yōu)化問題的解都是搜索空間中的一只鳥，稱之為“粒子”，而問題的最優(yōu)解就對應(yīng)為鳥群要尋找的“玉米地”。所有的粒子都具有一個位置向量（粒子在解空間的位置）和速度向量（決定下次飛行的方向和速度），并可以根據(jù)目標(biāo)函數(shù)來計算當(dāng)前的所在位置的適應(yīng)值（fitness value），可以將其理解為距離“玉米地”的距離。在每次的迭代中，種群中的粒子除了根據(jù)自身的“經(jīng)驗”（歷史位置）進行學(xué)習(xí)以外，還可以根據(jù)種群中最優(yōu)粒子的“經(jīng)驗”來學(xué)習(xí)，從而確定下一次迭代時需要如何調(diào)整和改變飛行的方向和速度。就這樣逐步迭代，最終整個種群的粒子就會逐步趨于最優(yōu)解。

回到頂部

3. 粒子群優(yōu)化算法的基本框架

　　在介紹PSO的算法流程之前，我們寫給出PSO中常用的迭代算子的形式。令?????????

代表粒子? 的位置向量，????????? 代表粒子? 的速度向量（其中?

為優(yōu)化問題的維度大小），最早版本的粒子群優(yōu)化算法的迭代算子形式如下：

　　速度向量迭代公式：

???????????????????

? ? ? (1)

　　位置向量迭代公式：

???????

? ? ? ?(2)

其中在公式（1）中，???

和? 分別代表粒子?

的歷史最佳位置向量和種群歷史最佳位置向量。根據(jù)公式（1）（2）可以看出，種群中的粒子通過不斷地向自身和種群的歷史信息進行學(xué)習(xí)，從而可以找出問題的最優(yōu)解。

　　但是，在后續(xù)的研究中表明，上述原始的公式中存在一個問題：公式（1）中???

的更新太具有隨機性，從而使得整個PSO算法的全局優(yōu)化能力很強，但是局部搜索能力較差。而實際上，我們需要在算法迭代初期PSO有著較強的全局優(yōu)化能力，而在算法的后期，整個種群應(yīng)該具有更強的局部搜索能力。所以根據(jù)上述的弊端，Shi和Eberhart通過引入慣性權(quán)重修改了公式（1），從而提出了PSO的慣性權(quán)重模型：

　　速度向量迭代公式：

???????????????????

? ? ? (3)

其中參數(shù)?

稱為是PSO的慣性權(quán)重（inertia weight），它的取值介于[0,1]區(qū)間，一般應(yīng)用中均采取自適應(yīng)的取值方法，即一開始令? ，使得PSO全局優(yōu)化能力較強，隨著迭代的深入，參數(shù)? 進行遞減，從而使得PSO具有較強的局部優(yōu)化能力，當(dāng)?shù)Y(jié)束時，? 。參數(shù)??? 和??? 稱為是學(xué)習(xí)因子（learn factor），一般設(shè)置為1.4961；而??? 和???

為介于[0,1]之間的隨機概率值。

?　　整個粒子群優(yōu)化算法的算法框架如下：

　　Step 1?種群初始化：可以進行隨機初始化或者根據(jù)被優(yōu)化的問題設(shè)計特定的初始化方法，然后計算個體的適應(yīng)值，從而選擇出個體的局部最優(yōu)位置向量???

和種群的全局最優(yōu)位置向量?

。

　　Step 2?迭代設(shè)置：設(shè)置迭代次數(shù)???

，并令當(dāng)前迭代次數(shù)?

；

　　Step 3?速度更新：根據(jù)公式（3）更新每個個體的速度向量；

　　Step 4?位置更新：根據(jù)公式（2）更新每個個體的位置向量；

　　Step 5?局部位置向量和全局位置向量更新：更新每個個體的???

和種群的?

；

　　Step 6?終止條件判斷：判斷迭代次數(shù)時都達到???

，如果滿足，輸出?

；否則繼續(xù)進行迭代，跳轉(zhuǎn)至Step 3。

　　對于粒子群優(yōu)化算法的運用，主要是對速度和位置向量迭代算子的設(shè)計。迭代算子是否有效將決定整個PSO算法性能的優(yōu)劣，所以如何設(shè)計PSO的迭代算子是PSO算法應(yīng)用的研究重點和難點。

4. 對粒子群優(yōu)化算法中慣性權(quán)重的認識

　　參數(shù)?

被稱之為是慣性權(quán)重，顧名思義? 實際反映了粒子過去的運動狀態(tài)對當(dāng)前行為的影響，就像是我們物理中提到的慣性。如果? ，從前的運動狀態(tài)很少能影響當(dāng)前的行為，粒子的速度會很快的改變；相反，? 較大，雖然會有很大的搜索空間，但是粒子很難改變其運動方向，很難向較優(yōu)位置收斂，由于算法速度的因素，在實際運用中很少這樣設(shè)置。也就是說，較高的? 設(shè)置促進全局搜索，較低的?

設(shè)置促進快速的局部搜索。

5. 粒子群優(yōu)化算法舉例——求解旅行商問題

　　旅行商問題（Traveling Salesman Problem，TSP）又譯為旅行推銷員問題、貨郎擔(dān)問題，簡稱為TSP問題，是最基本的路線問題和最典型的NP難問題，該問題是在尋求單一旅行者由起點出發(fā)，通過所有給定的需求點之后，最后再回到原點的最小路徑成本。最早的旅行商問題的數(shù)學(xué)規(guī)劃是由Dantzig等人于1959年提出的。

　　下面為一個TSP問題的數(shù)據(jù)集，城市個數(shù)為50：

37 5249 4952 6420 2640 3021 4717 6331 6252 3351 2142 4131 325 2512 4236 1652 4127 2317 3313 1357 5862 4242 5716 578 527 3827 6830 4843 6758 4858 2737 6938 4646 1061 3362 6363 6932 2245 3559 155 610 1721 105 6430 1539 1032 3925 3225 5548 2856 3730 40Ctrl+C 復(fù)制代碼

　　50個城市分布圖：

　　下面為PSO求解旅行商問題的matlab代碼：

　　主函數(shù)main.m：

%% 該文件演示基于TSP-PSO算法 clc;clear%% 載入數(shù)據(jù) data=load('eil51.txt') cityCoor=[data(:,2) data(:,3)];%城市坐標(biāo)矩陣figure plot(cityCoor(:,1),cityCoor(:,2),'ms','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g') legend('城市位置') ylim([4 78]) title('城市分布圖','fontsize',12) xlabel('km','fontsize',12) ylabel('km','fontsize',12) %ylim([min(cityCoor(:,2))-1 max(cityCoor(:,2))+1])grid on%% 計算城市間距離 n=size(cityCoor,1); %城市數(shù)目 cityDist=zeros(n,n); %城市距離矩陣 for i=1:nfor j=1:nif i~=jcityDist(i,j)=((cityCoor(i,1)-cityCoor(j,1))^2+...(cityCoor(i,2)-cityCoor(j,2))^2)^0.5;endcityDist(j,i)=cityDist(i,j);end end nMax=1000; %進化次數(shù) indiNumber=50; %個體數(shù)目 individual=zeros(indiNumber,n); %^初始化粒子位置 for i=1:indiNumberindividual(i,:)=randperm(n); end%% 計算種群適應(yīng)度 indiFit=fitness(individual,cityCoor,cityDist); [value,index]=min(indiFit); tourPbest=individual; %當(dāng)前個體最優(yōu) tourGbest=individual(index,:) ; %當(dāng)前全局最優(yōu) recordPbest=inf*ones(1,indiNumber); %個體最優(yōu)記錄 recordGbest=indiFit(index); %群體最優(yōu)記錄 xnew1=individual;%% 循環(huán)尋找最優(yōu)路徑 L_best=zeros(1,nMax); for N=1:nMaxN%計算適應(yīng)度值indiFit=fitness(individual,cityCoor,cityDist);%更新當(dāng)前最優(yōu)和歷史最優(yōu)for i=1:indiNumberif indiFit(i)<recordPbest(i)recordPbest(i)=indiFit(i);tourPbest(i,:)=individual(i,:);endif indiFit(i)<recordGbestrecordGbest=indiFit(i);tourGbest=individual(i,:);endend[value,index]=min(recordPbest);recordGbest(N)=recordPbest(index);%% 交叉操作for i=1:indiNumber% 與個體最優(yōu)進行交叉c1=unidrnd(n-1); %產(chǎn)生交叉位c2=unidrnd(n-1); %產(chǎn)生交叉位while c1==c2c1=round(rand*(n-2))+1;c2=round(rand*(n-2))+1;endchb1=min(c1,c2);chb2=max(c1,c2);cros=tourPbest(i,chb1:chb2);ncros=size(cros,2); %刪除與交叉區(qū)域相同元素for j=1:ncrosfor k=1:nif xnew1(i,k)==cros(j)xnew1(i,k)=0;for t=1:n-ktemp=xnew1(i,k+t-1);xnew1(i,k+t-1)=xnew1(i,k+t);xnew1(i,k+t)=temp;endendendend%插入交叉區(qū)域xnew1(i,n-ncros+1:n)=cros;%新路徑長度變短則接受dist=0;for j=1:n-1dist=dist+cityDist(xnew1(i,j),xnew1(i,j+1));enddist=dist+cityDist(xnew1(i,1),xnew1(i,n));if indiFit(i)>distindividual(i,:)=xnew1(i,:);end% 與全體最優(yōu)進行交叉c1=round(rand*(n-2))+1; %產(chǎn)生交叉位c2=round(rand*(n-2))+1; %產(chǎn)生交叉位while c1==c2c1=round(rand*(n-2))+1;c2=round(rand*(n-2))+1;endchb1=min(c1,c2);chb2=max(c1,c2);cros=tourGbest(chb1:chb2); ncros=size(cros,2); %刪除與交叉區(qū)域相同元素for j=1:ncrosfor k=1:nif xnew1(i,k)==cros(j)xnew1(i,k)=0;for t=1:n-ktemp=xnew1(i,k+t-1);xnew1(i,k+t-1)=xnew1(i,k+t);xnew1(i,k+t)=temp;endendendend%插入交叉區(qū)域xnew1(i,n-ncros+1:n)=cros;%新路徑長度變短則接受dist=0;for j=1:n-1dist=dist+cityDist(xnew1(i,j),xnew1(i,j+1));enddist=dist+cityDist(xnew1(i,1),xnew1(i,n));if indiFit(i)>distindividual(i,:)=xnew1(i,:);end%% 變異操作c1=round(rand*(n-1))+1; %產(chǎn)生變異位c2=round(rand*(n-1))+1; %產(chǎn)生變異位while c1==c2c1=round(rand*(n-2))+1;c2=round(rand*(n-2))+1;endtemp=xnew1(i,c1);xnew1(i,c1)=xnew1(i,c2);xnew1(i,c2)=temp;%新路徑長度變短則接受dist=0;for j=1:n-1dist=dist+cityDist(xnew1(i,j),xnew1(i,j+1));enddist=dist+cityDist(xnew1(i,1),xnew1(i,n));if indiFit(i)>distindividual(i,:)=xnew1(i,:);endend[value,index]=min(indiFit);L_best(N)=indiFit(index);tourGbest=individual(index,:); end tourGbest minbest=min(L_best) %% 結(jié)果作圖 figure plot(L_best) title('算法訓(xùn)練過程') xlabel('迭代次數(shù)') ylabel('適應(yīng)度值') grid onfigure hold on plot([cityCoor(tourGbest(1),1),cityCoor(tourGbest(n),1)],[cityCoor(tourGbest(1),2),...cityCoor(tourGbest(n),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g') hold on for i=2:nplot([cityCoor(tourGbest(i-1),1),cityCoor(tourGbest(i),1)],[cityCoor(tourGbest(i-1),2),...cityCoor(tourGbest(i),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g')hold on end legend('規(guī)劃路徑') scatter(cityCoor(:,1),cityCoor(:,2)); title('規(guī)劃路徑','fontsize',10) xlabel('km','fontsize',10) ylabel('km','fontsize',10)grid on ylim([4 80]) 　目標(biāo)函數(shù)：fitness.m

function indiFit=fitness(x,cityCoor,cityDist) %% 該函數(shù)用于計算個體適應(yīng)度值 %x input 個體 %cityCoor input 城市坐標(biāo) %cityDist input 城市距離 %indiFit output 個體適應(yīng)度值 m=size(x,1); n=size(cityCoor,1); indiFit=zeros(m,1); for i=1:mfor j=1:n-1indiFit(i)=indiFit(i)+cityDist(x(i,j),x(i,j+1));endindiFit(i)=indiFit(i)+cityDist(x(i,1),x(i,n)); end

　　PSO迭代收斂曲線圖：

　　PSO求解50個城市的TSP問題最小距離為473.1536，TSP求解規(guī)劃路徑圖如下：

回到頂部

6. 參考文獻

[1] Eberhart R C and Kennedy J. A new optimizer using particle swarm theory. ?1995.

[2] Shi Y and Eberhart R C. A modified particle optimizer. 1998.

[3] Kennedy J. Particle swarm optimization. 2010.

?

總結(jié)

以上是生活随笔為你收集整理的群体智能优化算法之粒子群优化算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。