偶然看到自動駕駛的四項關鍵技術:環境感覺,行為決策,路徑規劃和運動控制。然後看到用了粒子群優化算法。
粒子群優化算法聽了很多,但是沒有真正研究過,今天稍微看了下,心得如下。
【What】通過模拟鳥群覓食行為而發展起來的一種基于群體協作的随機搜尋算法。
鳥群覓食現象 | 粒子群優化算法 | |
鳥群 | 搜尋空間的一組有效解 | |
覓食空間 | 問題的搜尋空間 | |
飛行速度 | 類比 | 解的速度向量 |
所在位置 | 解的位置向量 | |
個體認知和與群體協作 | 速度與位置的更新 | |
找到食物 | 找到全局最優解 |
公式不好打,這裡就不打了。下面這個連結裡對粒子群濾波有很白話的講解。
http://www.cnblogs.com/konlil/archive/2012/02/05/2339142.html
【Where】粒子群算法從提出以來就受到很大重視,個人覺得比遺傳算法還簡單點。應用場景随便取幾個:路徑規劃,濾波定位,電力機組組合,順風車路徑等等。随便取知網搜下粒子群應用的論文,很多。
【How】了解一個算法後,最後的目的還是使用。這裡貼一下别人做好的簡單的MATLAB程式。我做了修改,使權重逐漸減小,目的是使快速達到全局最優,最後收斂到局部最優。
tic %該函數表示計時開始
%------初始格式化--------------------------------------------------
clear all;
clc;
format long;
%------給定初始化條件----------------------------------------------
c1=1.4962; %加速常數即學習因子1
c2=1.4962; %加速常數即學習因子2
wmax=0.9; %最大慣性權重
wmin=0.4; %最小慣性權重
%w=0.7298; %慣性權重
MaxDT=10000; %最大疊代次數
D=10; %搜尋空間維數(測試函數sphere中未知數個數)
N=40; %初始化群體個體數目
eps=10^(-7); %設定精度(在已知最小值時候用)
%------初始化種群的個體(可以在這裡限定位置和速度的範圍)------------
for i=1:N
for j=1:D
x(i,j)=randn; %産生一個服從正态分布的随機數作為初始化位置
v(i,j)=randn; %産生一個服從正态分布的随機數作為初始化速度
end
end
%------先計算各個粒子的适應度,并初始化個體最優位置y和全局最優位置Pg--------
for i=1:N
p(i)=sphere(x(i,:),D);%計算适應度,測試函數為sphere
y(i,:)=x(i,:); %初始化個體最優位置y為在時間步t=0時的粒子位置
end
Pg=x(1,:); %Pg為全局最優位置
for i=2:N
if sphere(x(i,:),D)<sphere(Pg,D)
Pg=x(i,:);%更新全局最優位置
end
end
%------進入主要循環,按照公式依次疊代,直到滿足精度要求------------
for t=1:MaxDT
for i=1:N
w = wmax - t*(wmax-wmin)/MaxDT;
v(i,:)=w*v(i,:)+c1*rand*(y(i,:)-x(i,:))+c2*rand*(Pg-x(i,:));
x(i,:)=x(i,:)+v(i,:);
if sphere(x(i,:),D)<p(i)
p(i)=sphere(x(i,:),D);%更新适應度
y(i,:)=x(i,:);%更新個體最佳位置
end
if p(i)<sphere(Pg,D)
Pg=y(i,:);%更新群體最佳位置
end
end
Pbest(t)=sphere(Pg,D);%儲存每一代的群體最佳位置
end
toc %該函數表示計時結束
%------最後給出計算結果
disp('*************************************************************')
disp('函數的全局最優位置為:')
for i=1:D
fprintf('x(%d)=%s\n',i,Pg(i));
end
fprintf('最後得到的優化極值為:%s\n',sphere(Pg,D));
disp('*************************************************************')
%适應度函數源程式(sphere.m)
%參數x為變量名,參數D為維數
function result=sphere(x,D)
sum=0;
for i=1:D
sum=sum+x(i)^2;
end
result=sum;
%%%%%%%%%%%%%%%%%結果
時間已過 1.990896 秒。
*************************************************************
函數的全局最優位置為:
x(1)=-3.157453e-18
x(2)=-7.122292e-18
x(3)=1.224156e-18
x(4)=-6.638475e-18
x(5)=-2.106536e-17
x(6)=-7.853146e-18
x(7)=1.743824e-18
x(8)=-8.920879e-18
x(9)=8.927001e-18
x(10)=-1.042553e-19
最後得到的優化極值為:7.740109e-34
*************************************************************
時間比原來快了1S左右,還可以通過其他方法改進,使得速度更快的,因為隻花了半天時間去了解。想深究的多看看論文。看看他人的方法。
附上一個源代碼的連結,http://blog.csdn.net/yi_tech_blog/article/details/52997081,感謝這位朋友。
還有一篇博士論文,我看了開頭部分,對了解算法去看博士論文是很好的一個方法。李整. 基于粒子群優化算法的機組組合問題的研究[D]. 華北電力大學(北京), 華北電力大學, 2016.
這是第一篇部落格,大佬們求輕噴,希望大家有好的職業規劃和方向。