大家好,又见面了,我是你们的朋友全栈君。
(粒子群算法进阶讲解传送门:(https://blog.csdn.net/DBLLLLLLLL/article/details/103036067)
)
前面一篇文章介绍了遗传算法,这里再介绍一种进化算法,称为粒子群算法。同遗传算法类似,粒子群算法也是仿照了自然界的生物现象得到的。这种现象就是鸟群在某个未知空间内寻找食物这一思想。
鸟群通过自身经验和种群之间的交流调整自己的搜寻路径,从而不断寻找,直到找到食物最多的地点。其中某个个体就是鸟群中某一只鸟,该个体具有的属性就是其所在位置和搜索方向。该个体所在地点对应的食物数量可以理解为该处函数取值的理想程度。开始时先随机放置各个个体在整个寻找范围内,然后根据个体本身搜索到的历史最优地点和整个种群搜索到的历史最优地点来调整自己的搜索方向和搜索跨度,从而经过多次搜索后找到最优的地点,即最优解。
用数学的语言如何描述上述过程呢?如上述所示,每个个体应该有两个属性,一个是该个体所在的位置,一个是该个体的速度(矢量的速度可以同时表征方向和速度大小),当寻找范围是一个多维的空间时,该位置和速度也是一个多维的向量,例如在n维空间内,共有m个个体,第i个个体用 N i Ni Ni表示,其位置属性为 X i Xi Xi,其速度属性为 V i Vi Vi,那么可以说若一个个体包含两个属性,则可以如下式来表示:
N i = [ X i ; V i ] N_i=[X_i;V_i] Ni=[Xi;Vi]
又因为该个体的位置和速度都是在n维空间内,所以用单位向量的方法表示位置和速度,可以将位置和速度写成如下的向量表达式。
X i = [ x i 1 , x i 2 , x i 3 . . . . . . x i n ] X_i=[x_{i1},x_{i2},x_{i3}……x_{in}] Xi=[xi1,xi2,xi3......xin] V i = [ v i 1 , v i 2 , v i 3 . . . . . . v i n ] V_i=[v_{i1},v_{i2},v_{i3}……v_{in}] Vi=[vi1,vi2,vi3......vin]
具备上述属性的就是一个个体,或者叫一个粒子,那么将m个个体视为一个整体,就是整个鸟群,假设为 P P P,则有:
P = [ N 1 , N 2 , N 3 . . . . . . N m ] P=[N_1,N_2,N_3……N_m] P=[N1,N2,N3......Nm]
至此,一个粒子群就建立完成。那么如何知道该粒子群各个粒子所在位置表现出来的结果是什么呢?
首先是对个体所在位置的食物数量做评估,一般来说就是讲个体的位置作为变量带入到目标函数中,得到一个可以用于评估的结果,这里我们用 Y i Y_i Yi来表示第i个个体所在位置对应的结果,则有:
Y i = f ( X i ) = f ( x i 1 , x i 2 , x i 3 . . . . . . x i n ) = y i Y_i=f(X_i)=f(x_{i1},x_{i2},x_{i3}……x_{in})=y_i Yi=f(Xi)=f(xi1,xi2,xi3......xin)=yi
至此,该粒子群和粒子群的结果都得到了,那么如何通过寻找来更新粒子群的位置、速度信息并观察新的结果呢?
首先在寻找之前,我们要确定这次寻找的速度,确定的方法就是根据个体历史最优位置和种群历史最优位置来调整之前的速度,从而得到这次的速度,现在假设每次运动的时间长度为 T T T,且前一次的速度为
V i t − 1 = [ v i 1 t − 1 , v i 2 t − 1 , v i 3 t − 1 . . . . . . v i n t − 1 ] V_i^{t-1}=[v_{i1}^{t-1},v_{i2}^{t-1},v_{i3}^{t-1}……v_{in}^{t-1}] Vit−1=[vi1t−1,vi2t−1,vi3t−1......vint−1]
该个体历史最优位置为
X i b e s t = [ x i 1 b e s t , x i 2 b e s t , x i 3 b e s t . . . . . . x i n b e s t ] X_i^{best}=[x_{i1}^{best},x_{i2}^{best},x_{i3}^{best}……x_{in}^{best}] Xibest=[xi1best,xi2best,xi3best......xinbest]
该种群的历史最优位置为
X a l l b e s t = [ x a l l 1 b e s t , x a l l 2 b e s t , x a l l 3 b e s t . . . . . . x a l l n b e s t ] X_{all}^{best}=[x_{all1}^{best},x_{all2}^{best},x_{all3}^{best}……x_{alln}^{best}] Xallbest=[xall1best,xall2best,xall3best......xallnbest]
所以当前位置到个体的历史最优位置的速度为
V i ; b e s t t = ( X i b e s t − X i t ) / T V_{i;best}^t=(X_i^{best}-X_i^t)/T Vi;bestt=(Xibest−Xit)/T
当前位置到种群历史最优位置的方向为
V a l l ; b e s t t = ( X a l l b e s t − X i t ) / T V_{all;best}^t=(X_{all}^{best}-X_i^t)/T Vall;bestt=(Xallbest−Xit)/T
假设这一次的速度为
V i t = [ v i 1 t , v i 2 t , v i 3 t . . . . . . v i n t ] V_i^{t}=[v_{i1}^{t},v_{i2}^{t},v_{i3}^{t}……v_{in}^{t}] Vit=[vi1t,vi2t,vi3t......vint]
则这一次的速度等于
V i t = a 1 ∗ V i t − 1 + a 2 ∗ V i ; b e s t t + a 3 ∗ V a l l ; b e s t t V_i^{t}=a_1*V_i^{t-1}+a_2*V_{i;best}^t+a_3*V_{all;best}^t Vit=a1∗Vit−1+a2∗Vi;bestt+a3∗Vall;bestt
其中 a 1 , a 2 , a 3 a_1,a_2,a_3 a1,a2,a3分别是这三个速度的权值系数
为了限制最后的速度大小,避免速度过大跳过最优解,或者速度过小,导致变化较小,迟迟到达不了最优解,所以在面对速度的时候,应该对速度的大小有一个限定的取值范围。即当 V i t > V m a x V_i^{t}>V_{max} Vit>Vmax时, V i t = V m a x V_i^{t}=V_{max} Vit=Vmax,当 V i t < V m i n V_i^{t}<V_{min} Vit<Vmin时, V i t = V m i n V_i^{t}=V_{min} Vit=Vmin
已知这一次的速度 V i t V_i^{t} Vit,就可以根据时间 T T T和当前的位置 X i t X_i^t Xit,求出下一次的位置 X i t + 1 X_i^{t+1} Xit+1
X i t + 1 = X i t + T ∗ V i t X_i^{t+1}=X_i^t+T*V_i^{t} Xit+1=Xit+T∗Vit
如此循环,经过若干次的计算后,最后取种群历史最优位置为最优解。
下面写如何用MATLAB具体实现上述过程。
clc;clear;close all;
%% 初始化种群
f= @(a,b)(a .* sin(a) .* cos(2 * a) - 2 * a .* sin(3 * a)).*(b .* sin(b) .* cos(2 * b) - 2 * b .* sin(3 * b)); % 函数表达式
figure(1);
[x0_1, x0_2]=meshgrid(0:.2:20);
y0=f(x0_1,x0_2);
mesh(x0_1, x0_2, y0);
hold on;
N = 500; % 初始种群个数
d = 2; % 空间维数
ger = 300; % 最大迭代次数
limit = [0, 20;0,20]; % 设置位置参数限制(矩阵的形式可以多维)
vlimit = [-1.5, 1.5;-1.5, 1.5]; % 设置速度限制
c_1 = 0.8; % 惯性权重
c_2 = 0.5; % 自我学习因子
c_3 = 0.5; % 群体学习因子
for i = 1:d
x(:,i) = limit(i, 1) + (limit(i, 2) - limit(i, 1)) * rand(N, 1);%初始种群的位置
end
v = rand(N, d); % 初始种群的速度
xm = x; % 每个个体的历史最佳位置
ym = zeros(1, d); % 种群的历史最佳位置
fxm = zeros(N, 1); % 每个个体的历史最佳适应度
fym = -inf; % 种群历史最佳适应度
plot3(xm(:,1),xm(:,2),f(xm(:,1),xm(:,2)), 'ro');title('初始状态图');
hold on;
figure(2);
mesh(x0_1, x0_2, y0);
hold on;
plot3(xm(:,1),xm(:,2),f(xm(:,1),xm(:,2)), 'ro');
hold on;
%% 粒子群工作
iter = 1;
times = 1;
record = zeros(ger, 1); % 记录器
while iter <= ger
fx = f(x(:,1),x(:,2)) ; % 个体当前适应度
for i = 1:N
if fxm(i) < fx(i)
fxm(i) = fx(i); % 更新个体历史最佳适应度
xm(i,:) = x(i,:); % 更新个体历史最佳位置
end
end
if fym < max(fxm)
[fym, nmax] = max(fxm); % 更新群体历史最佳适应度
ym = xm(nmax, :); % 更新群体历史最佳位置
end
v = v * c_1 + c_2 * rand *(xm - x) + c_3 * rand *(repmat(ym, N, 1) - x);% 速度更新
% 边界速度处理
for i=1:d
for j=1:N
if v(j,i)>vlimit(i,2)
v(j,i)=vlimit(i,2);
end
if v(j,i) < vlimit(i,1)
v(j,i)=vlimit(i,1);
end
end
end
x = x + v;% 位置更新
% 边界位置处理
for i=1:d
for j=1:N
if x(j,i)>limit(i,2)
x(j,i)=limit(i,2);
end
if x(j,i) < limit(i,1)
x(j,i)=limit(i,1);
end
end
end
record(iter) = fym;%最大值记录
if times >= 10
cla;
mesh(x0_1, x0_2, y0);
plot3(x(:,1),x(:,2),f(x(:,1),x(:,2)), 'ro');title('状态位置变化');
pause(0.5);
times=0;
end
iter = iter+1;
times=times+1;
end
figure(3);plot(record);title('收敛过程')
figure(4);
mesh(x0_1, x0_2, y0);
hold on;
plot3(x(:,1),x(:,2),f(x(:,1),x(:,2)), 'ro');title('最终状态图');
disp(['最大值:',num2str(fym)]);
disp(['变量取值:',num2str(ym)]);
粒子群运算过程如图所示:
例:五维的代码
clc;clear;close all;
%% 初始化种群
f= @(a,b,c,d,e)(a.*b.*c.*d.*e); % 函数表达式
% figure(1);
% [x0_1, x0_2]=meshgrid(0:.2:20);
% y0=f(x0_1,x0_2);
% mesh(x0_1, x0_2, y0);
% hold on;
N = 500; % 初始种群个数
d = 5; % 空间维数
ger = 300; % 最大迭代次数
limit = [0, 20;0,20;0,20;0,20;0,20]; % 设置位置参数限制(矩阵的形式可以多维)
vlimit = [-1.5, 1.5;-1.5, 1.5;-1.5, 1.5;-1.5, 1.5;-1.5, 1.5]; % 设置速度限制
c_1 = 0.8; % 惯性权重
c_2 = 0.5; % 自我学习因子
c_3 = 0.5; % 群体学习因子
for i = 1:d
x(:,i) = limit(i, 1) + (limit(i, 2) - limit(i, 1)) * rand(N, 1);%初始种群的位置
end
v = rand(N, d); % 初始种群的速度
xm = x; % 每个个体的历史最佳位置
ym = zeros(1, d); % 种群的历史最佳位置
fxm = zeros(N, 1); % 每个个体的历史最佳适应度
fym = -inf; % 种群历史最佳适应度
% plot3(xm(:,1),xm(:,2),f(xm(:,1),xm(:,2)), 'ro');title('初始状态图');
% hold on;
% figure(2);
% mesh(x0_1, x0_2, y0);
% hold on;
% plot3(xm(:,1),xm(:,2),f(xm(:,1),xm(:,2)), 'ro');
% hold on;
%% 粒子群工作
iter = 1;
times = 1;
record = zeros(ger, 1); % 记录器
while iter <= ger
fx = f(x(:,1),x(:,2),x(:,3),x(:,4),x(:,5)) ; % 个体当前适应度
for i = 1:N
if fxm(i) < fx(i)
fxm(i) = fx(i); % 更新个体历史最佳适应度
xm(i,:) = x(i,:); % 更新个体历史最佳位置
end
end
if fym < max(fxm)
[fym, nmax] = max(fxm); % 更新群体历史最佳适应度
ym = xm(nmax, :); % 更新群体历史最佳位置
end
v = v * c_1 + c_2 * rand *(xm - x) + c_3 * rand *(repmat(ym, N, 1) - x);% 速度更新
% 边界速度处理
for i=1:d
for j=1:N
if v(j,i)>vlimit(i,2)
v(j,i)=vlimit(i,2);
end
if v(j,i) < vlimit(i,1)
v(j,i)=vlimit(i,1);
end
end
end
x = x + v;% 位置更新
% 边界位置处理
for i=1:d
for j=1:N
if x(j,i)>limit(i,2)
x(j,i)=limit(i,2);
end
if x(j,i) < limit(i,1)
x(j,i)=limit(i,1);
end
end
end
record(iter) = fym;%最大值记录
% if times >= 10
% cla;
% mesh(x0_1, x0_2, y0);
% plot3(x(:,1),x(:,2),f(x(:,1),x(:,2)), 'ro');title('状态位置变化');
% pause(0.5);
% times=0;
% end
iter = iter+1;
times=times+1;
end
% figure(3);plot(record);title('收敛过程')
% figure(4);
% mesh(x0_1, x0_2, y0);
% hold on;
% plot3(x(:,1),x(:,2),f(x(:,1),x(:,2)), 'ro');title('最终状态图');
disp(['最大值:',num2str(fym)]);
disp(['变量取值:',num2str(ym)]);
代码效果:
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/135260.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...