粒子群算法

粒子群算法学习

一、简介~

==因鸟而起~==：

  • 1995年，美国社会心理学者James Kennedy和电气工程师Russell Eberhart合作提出了粒子群算法。他们在模拟鸟群觅食的社会模型时获得了启发，将这个模型应用到优化问题求解中,开发出了粒子群算法。
  • 该算法模拟鸟群觅食的行为，每个解对应一个鸟，称为“粒子”。粒子在解空间飞行，当粒子发现更好的解时，会向那里飞行。全体粒子最终会聚集到最优解处。
  • 粒子群算法借鉴了遗传算法的思想，但它没有遗传算法的选育、交叉、变异等操作。其只根据粒子本身经验和群体经验来调整粒子的飞翔方向和速度。
  • 与遗传算法等其他群智能优化算法相比，粒子群算法具有计算简单、易实现、快速收敛等特点，因此应用广泛。

二、粒子群优化~

2.1 工作原理

假设有一群鸟在某个区域觅食，目标是找到食物最丰富的地方。

P1

  • 每只鸟可以看作一个“粒子“，它可以在区域内飞翔，代表算法中的一个潜在解。
  • 每只鸟有一个当前位置(解)和飞翔速度。它会根据自身以往的觅食经验，和群体中其他鸟所传递的食物信息，来调整自己的飞行方向和速度。
  • 每只鸟都记载着它自己发现过的食物最丰富的位置(个体经验最优，pbest)。整群鸟发现的食物最丰富区域就是全局最优(gbest)。
  • 随着时间的迭代，每只鸟根据下式更新自己的速度和位置： 新速度 = 旧速度 + 自身经验 + 群体经验 新位置 = 旧位置 + 新速度
  • 自身经验是它飞向自己最佳地点的趋势，群体经验是它飞向群体最佳地点的趋势。
  • 通过这个更新过程，整群鸟会最终聚集在食物最多的那片区域。

2.2 基本参数

  • 表示一大群粒子集合
  • 表示群体中具有位置 和速度 的个体
  • 为粒子 的位置
  • 为粒子在 位置的速度
  • 为单个粒子的最优解（经验）
  • 为粒子群的最优解（经验），也就是全局最优解
  • 为适应度函数
  • 为加速度函数（认知和社会参数）
  • 为介于0~1之间的随机数
  • 为迭代次数

2.3 迭代方程

式(1)为速度更新方程，式(2)为位置更新方程。

  • 上一次迭代的速度；
  • 代表粒子本身经验的影响， 为粒子本身经验对自身的置信度， 为自身经验影响的随机效应；
  • 代表社会经验对粒子的影响， 为社会经验对自身的置信度， 为社会经验影响的随机效应；
  • 根据新得到的速度 来更新位置 ；
  • 为对上一次动作的信任程度，一种自适应调整的策略，随着迭代次数的增加，惯性权重 不断减小，从而使得粒子群算法在初期具有较强的全局收敛能力，在后期具有较强的局部收敛能力；

P2

粒子当前位置 的个体经验会驱使它走向 处，但是收到群体经验的影响粒子也会趋向 处，根据其他因素 的影响粒子同时会进行方向折中（两个方向都沾点)和幅度折中（两个方向的比例都沾点），根据式(1)可以得出最后的速度，从而驱动粒子从当前位置 走向新的位置，从而完成迭代。

2.4 优化步骤

三、 优化举例~

3.1 问题描述

Example:

已知函数 其中 求解y的最小值

3.2 Matlab代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
clc;clear;close all;
%% 功能 PSO算法求最小值
%% 说明
% PSO算法，寻找函数y的最小值
% 其中        y = f(x1,x2) = x1^2+x2^2
% x的范围     -10 <= x1,x2 <= 10
% 无惯性因子w或w=1，维度为1
%% 参数
%  v_max :粒子速度最大值
%  v_min :粒子速度最小值
%  p_max :粒子位置最大值
%  p_min :粒子位置最小值
%  p_num :粒子个数
%  fvar  :目标函数自变量个数function varries
%  t     :迭代次数
%  t_max :最大迭代次数
%  pos   :粒子位置向量position
%  spd   :粒子速度向量speed
%  pbest :粒子个体最优解（经验）
%  gbest :粒子群体最优解（经验）
%  c1    :粒子的个体学习因子
%  c2    :粒子的社会学习因子
%  p_cfit:粒子当前适应度向量current fitness
%  p_bfit:粒子最优适应度向量best fitness
%  g_bfit:粒子群体最优适应度
%  g_bs  :存储向量->粒子群体最优适应度
%  cond1 :群体最优适应度<cond1退出循环

%% 基本常量初始化
p_num = 20;
fvar = 2;
cond1 = 0;
v_max = 4;
v_min = -2;
p_max = 10;
p_min = -10;
c1 = 2;
c2 = 2;
t = 1;
t_max = 300;
p_cfit = zeros(p_num,1);
g_bs = zeros(t_max,1);

%% 主函数
%初始化粒子速度和位置
[spd,pos]= Init_pos_spd(v_min,v_max,p_num,fvar,p_min,p_max);
%初始化适应度函数值
[pbest,p_bfit,g_bfit,gbest] = Init_fits(p_num,pos,p_cfit);

while (t < t_max)%退出条件1：超过最大迭代次数
    % 1.更新速度和位置
    [pos,spd] = update_pos_spd(p_num,spd,pos,c1,c2,pbest, ...
                              gbest,fvar,v_min,v_max,p_min,p_max);
    % 2.更新适应度函数值
    [g_bfit,gbest,pbest,p_bfit] = update_fits(p_num,pos,p_bfit,p_cfit,pbest);
    % 存储全局最优自适应函数值
    g_bs(t) = g_bfit; 
    % 退出条件2：群体最优适应度 < cond1提前退出循环
    if g_bfit < cond1
        break
    end
    % 迭代+1
    t = t + 1;
end

figure(1)
set(gcf,'color','white');
plot(1:length(g_bs),g_bs)


%% 函数块
function [fitness] = fit_fn(p)
% 适应度函数，计算粒子适应度
fitness = p(1)^2 + p(2)^2;
end

function [g_bfit,gbest,pbest,p_bfit] = update_fits(p_num,pos,p_bfit,p_cfit,pbest)
% 更新适应度函数值
	for i=1:p_num
		p_cfit(i)=fit_fn(pos(i,:));
		if p_cfit(i) < p_bfit(i)
		    p_bfit(i) = p_cfit(i);
			pbest(i,:) = pos(i,:);
		end
	end
	[g_bfit,min_index]=min(p_bfit);
    gbest = pbest(min_index);
end

function [position,speed] = update_pos_spd(p_num,spd,pos,c1,c2,pbest, ...
                              g_best,fvar,v_min,v_max,p_min,p_max)
% 更新速度和位置，加边界约束
    for i=1:p_num
            %更新速度向量
            spd(i) = spd(i) + c1*rand*(pbest(i)-pos(i))+c2*rand*(g_best-pos(i));
            %如果速度越界则取边界值
            for j=1:fvar
                if spd(i,j) < v_min
                    spd(i,j) = v_min;
                end
                if spd(i,j) > v_max
                    spd(i,j) = v_max;
                end
            end
            %更新位置向量
            pos(i) = pos(i) + spd(i);
            %如果位置越界则取边界值
            for j=1:fvar
                if pos(i,j) < p_min
                    pos(i,j) = p_min;
                end
                if pos(i,j) > p_max
                    pos(i,j) = p_max;
                end
            end
    end
    position = pos;
    speed = spd;
end

function [speed,position] = Init_pos_spd(v_min,v_max,p_num,fvar,p_min,p_max)
% 初始化速度、位置向量
speed = v_min + (v_max - v_min)*rand(p_num,fvar);
position = p_min + (p_max - p_min)*rand(p_num,fvar);
end

function [pbest,p_bfit,g_bfit,gbest] = Init_fits(p_num,pos,p_cfit)
%初始化粒子适应度和群体适应度
for i=1:p_num
        p_cfit(i)=fit_fn(pos(i,:));	
end
pbest = pos;
p_bfit = p_cfit;
[g_bfit,min_index] = min(p_bfit);
gbest = pbest(min_index);
end

3.3 仿真结果

P4

结果显示其找到了接近全局最小0的解，但是未收敛到0处

Reference:

[1] 粒子群优化算法(Particle Swarm Optimization, PSO)的详细解读 - 知乎 (zhihu.com)

[2] 粒子群优化如何工作？ |Baeldung 谈计算机科学