-
基本求解
-
1.1.公式求解
-
- 梯度优化
- 智能优化算法
老饼讲解：一步一步上手学习
【优化】一篇入门之-粒子群(PSO)
粒子群优化算法(Particle Swarm Optimization，PSO)是J. Kennedy和R. C. Eberhart于1995年提出的一种模拟鸟类捕食的智能优化算法，它借鉴了通过鸟群寻找食物时信息的共享机制，从而使得粒子群能迅速找到目标优秀解。下面我们就一起来详细看看PSO算法的算法原理、算法流程和代码实现吧！
一、PSO粒子群算法
在自然界中，鸟群通过各自搜寻、共享信息的方式来要找到区域中的食物，PSO正是模拟这一机制，先初始化一个解集，然后每个解迭代时会参考整体最优解，从而使得多次迭代后群体往优秀解聚拢。
PSO的算法原理是非常简单的，要了解PSO算法，最直接的就是从它的算法流程上手，上车！
1.1. PSO算法流程
PSO算法流程如下：
一、初始化
1. 初始化粒子群
包括每个粒子的初始位置、初始速度、历史最优值、历史最优位置，以及整个粒子群的全局历史最优位置、最优值，其中，粒子群大小一般设为20-40，复杂问题可以设更大。
二、迭代
1. 更新粒子的速度与位置
更新公式如下：
这个公式大家仔细看一下就会明白它的意思了，就是用个体最优、全局最优粒子，来更新个体的速度。
各个变量的意义如下：
：第个粒子的速度
：个体学习因子，一般设为2
：(0,1]之间的随机数
：第个粒子的历史最优位置
：第个粒子的当前位置
：全局学习因子，一般设为2
：(0,1]之间的随机数
：全局历史最优位置
2. 计算各个粒子的评估函数值，并更新相关信息
包括每个粒子的历史最优值、历史最优位置、粒子群的全局最优位置
3. 判断终止条件
如果达到终止条件，则终止搜索，否则重复1,2
终止条件可设为：达到了最大迭代次数、解的质量足够好、近N次的优化效果不明显等等
三、输出
输出全局历史最优位置、函数值
二、PSO粒子群-常见改进
好了，下面是PSO中的两种最常见改进，在实际使用中，基本都要加入这两种改进，效果才会好些。
2.1. 加入范围限制的PSO
在粒子群算法中，一般会加入搜索区域的范围，以及速度的范围，这样可以避免粒子超出搜索范围、进行无效的搜索、以及避免搜索步长过大。
加入范围限制的具体操作如下：
1. 更新时进行修正
在更新位置、速度时，如果位置或速度超过范围，就进行修正，具体如下：
其中，分别是X的最小、最大取值
分别是速度的最大最小取值
2. 初始化时进行修正
在加入范围限制后，粒子的初始位置、初始速度都需要初始化在范围之内。
粒子的位置可随机初始化在区域之中，如下：
粒子的速度可随机初始在速度范围内，如下：
2.2. 加入惯性权重的PSO
加入惯性权重的PSO，指的是在速度更新公式中加入惯性权重w，如下：
好了，我们来看下的意义，如下：
如果w较大，则代表粒子更倾重于自身的速度方向，此时更有利于全局搜索
如果w较小，则代表更倾重于全局位置方向，此时更有利于收敛到全局位置
一般不会设为固定值，而是用线性递减策略来更新，如下：
其中，：惯性权重的初始值，一般设为0.9
：惯性权重的结束值，一般设为0.4
：最大迭代次数
：当前迭代次数
当时，，随着的增大，逐步减小，直到时，
加入了惯性权重后，相当于加入了"搜索"与"收敛"的控制器，在迭代初期，用较大的，使得算法倾向于全局搜索，而后期则使用更小的，使得算法偏向于收敛。
三、PSO-代码实现
最后，我们用个例子来实现一下PSO，简单起见，设目标函数为：
然后用PSO算法来优化目标函数，我们都知道，上述目标函数在[2,3]处取得最小值0，下面我们就看看PSO算法能不能找到最优解。PSO具体代码实现如下：
% 本代码展示如何用PSO粒子群算法求解函数极小值问题,目标函数:y = (x1-2)^2+(x2-3)^2
% 本代码来自《老饼讲解神经网络》www.bbblearn.com ,matlab版本：2018a
setdemorandstream(88); % 为方便复现,设置随机种子
% ----- 参数设置 -----
N = 20; % 种群大小
T = 1000; % 迭代次数
c1 = 2; % 学习因子c1
c2 = 2; % 学习因子c2
w_init = 0.9; % 惯性权重初始值
w_end = 0.4; % 惯性权重结束值
delta_goal = 0.001; % 近n次下降误差阈值
% ------ 初始化 ------
x_max = [100,100]; % x的最大取值
x_min = [-100,-100]; % x的最小取值
v_max = (x_max - x_min)*0.001; % 速度的最大取值
v_min = (x_min - x_max)*0.001; % 速度的最小取值
m = length(x_max); % 变量个数
x = repmat(x_min,N,1) + rand(N,m).*repmat(x_max-x_min,N,1); % 初始化粒子的位置
v = repmat(v_min,N,1) + rand(N,m).*repmat(v_max-v_min,N,1); % 初始化粒子的速度
f = calF(x); % 计算函数值
pbest = x; % 初始化粒子历史最优位置
pbest_f = f; % 初始化粒子历史最优值
[gbest_f,idx] = min(pbest_f); % 全局最优函数值
gbest = pbest(idx,:); % 全局最优位置
last_f = -inf(1,10); % 初始化最近10次的最佳结果
% ------- 迭代搜索 --------
for t = 0:T % 迭代T轮
w = w_init - t*(w_init - w_end)/T; % 计算当前惯性权重
v = w*v+c1*rand(N,1).*(pbest - x)+c2*rand(N,1).*(repmat(gbest,N,1)- x); % 更新粒子的速度
v = min(max(v,v_min),v_max); % 截取速度的上下界
x = x+v; % 更新粒子的位置
x = min(max(x,x_min),x_max); % 截取位置的上下界
f = calF(x); % 计算粒子的函数值
idx = f<pbest_f; % 找出需要更新的粒子
pbest(idx,:) = x(idx,:); % 更新粒子的历史最佳位置
pbest_f(idx) = f(idx); % 更新粒子的历史最佳函数值
[min_f,min_idx] = min(pbest_f); % 找出本轮最佳函数值
if(min_f<gbest_f) % 如果本轮函数值比历史最佳还小
gbest_f = min_f; % 更新历史全局最优函数值
gbest = pbest(min_idx,:); % 更新历史全局最优位置
end % -
fprintf('第%d轮,函数值为:%d\n',t,gbest_f) % 打印当前优化结果
last_f = [last_f(2:end),gbest_f]; % 记录本轮的全局最优值
if((max(last_f)-min(last_f))<delta_goal) % 如果近N轮的优化提升小于阈值
break % 则终止迭代
end % -
end
fprintf('迭代次数:%d\n',t) % 打印迭代次数
fprintf('最佳函数值为:%f\n',gbest_f) % 打印最佳函数值
fprintf('最佳x为:\n') % 打印标题
gbest % 打印最佳x
% 目标优化函数
function y = calF(x) % 目标优化函数
y = (x(:,1)-2).^2+(x(:,2)-3).^2; % 计算目标函数值
end 代码运行结果如下：
最终的解为x = [1.9976,2.9958]，与我们预期的[2,3]的差异极小，可见，PSO算法已经取得了较好的效果。
总结
PSO算法，就是一种借鉴鸟群捕食的算法，每只鸟飞的时候，会参考历史最优位置与当前最优个体来调整位置，使得每只鸟的飞行方向会趋向更优位置。一般会加入范围限制、惯性权重等改进策略，来提升实际效果。
评论
