文章目录
前言
PSO算法是一种群智能优化算法，特点是布置速度快，收敛性强。同时面对着两大问题，容易早熟和容易陷入局部最优。对于特征选择这类离散型问题，我们使用二进制版本的BPSO进行优化。在PSO的迭代过程中，每个粒子都会向种群历史最优解(Gbest)和粒子本身历史最优解(Pbest)进行学习，同时也会不断地更新Gbest与Pbest，最后会收敛在Gbest与Pbest之间的某个区域。
注意：（Gbest只有一个，所有粒子都会向它学习，而Pbest对于每个粒子都有一个，只属于它们自己，它们只会向自己的Pbest进行学习，这样说应该大家都能听懂了）
一、粒子群算法学习过程
对于特征选择问题是这样描述的，现实中由于采样不均匀导致某些采样偏离了真实的分布，所以这部分特征反而会对数据的利用造成负面影响，那么特征选择的目的就是找出这些错误的特征和冗余的特征。
那么我们定义一个1N维的0-1向量，每一位都只能是0或者1，0代表不用这一维特征，1代表选用这一维
特征。
那么BPSO是怎么进行学习的呢？公式如下：
先看到第一个公式： 代表着粒子的速度更新公式，粒子在每一维都有一个速度值(前面我们已经提到了数据有很多维特征),那么每一维都要进行更新。其中ω ( t ) \omega(t)ω(t )代表着当前迭代次数的惯性系数，也就是说继承来自上次迭代速度的比重，写一篇博客好难啊啊啊啊，继续，另外加上的两项呢，分别是与Pbest和Gbest位置的差异， 这里非常重要！！！*，如果不好好理解，就弄不明白了。位置的差异通过两个系数c1，c2和两个[0,1]随机数r1，r2 相乘，学习系数的作用是加大向Pbest和Gbest靠拢的可能性，而随机数r1，r2的作用是也是一种精髓，启发式随机搜索的精髓，用它，肯定好，为什么？谁也说不清，不用它，鲁棒性真的会变差。
下面举个例子，
粒子 [0 0 1 1 0 1 0 1]
gbest [1 0 1 0 0 0 1 1]
pbest [0 0 1 0 0 1 0 1]
先看第1维，我们现在要更新速度，发现
这两个公式上面公式是0，下面公式是1，对吧，忽略前面的[0,1]随机数系数（期望值0.5）那么加起来对速度的提升我们就假设为 1
现在看第6维，变成了上面公式是-1，下面公式是0，对速度的提升是-1，
由此我们发现，对于一个粒子如果它的Pbest和Gbest的某个维度位置不一致，那么它获得速度的期望大概是-1。
好， 再看第2维，上面公式是0，下面公式也是0，粒子没有获得速度提升，那么之后会怎么样呢？变成了这样
也就是说如果惯性系数小于1，那么速度值越来越小了，大于1则越来越大。
再看到第二个公式： 这就是一个sigmoid函数，没想到吧，这里也会碰见神经网络这哥们，为什么用它？其他函数行嘛？当然可以，S型函数大家族那么多，你挑一挑其他杀马特(非主流)函数也行。大家都用sigmoid，这里就照搬了。
再看到第三个公式：重点来了
如果sigmoid的返回值大于[0,1]随机数(期望0.5),就把这个维度置为1，否则为1. 注意这里不是取反，而是单纯的大于随机数置1，小于随机数置0，千万不要记成取反了(我以前就这样做)
我们再来复习一下sigmoid
那么为什么公式3有效呢？速度大就置为1，速度小就置为0，合理吗？
我总结一下：
Pbest与Gbest为1，粒子为0，位置差异为正，那么速度就大，此时粒子变为1的概率也越大，即完成了学习行为（向Pbest与Gbest靠拢了）
Pbest与Gbest为0，粒子为1，位置差异为负，那么速度就小，此时粒子变为0的概率也越大，即完成了学习行为（向Pbest与Gbest靠拢了）
好好理解上述话语，即理解了BPSO粒子速度与位置更新的含义，网上有很多人说什么以概率表示巴拉巴拉，其实并不好理解，只是想当然得觉得很对。
; 二、特征选择实战
1.数据集以及matlab源码
用一个数据集 Wine(178instance，13features and 3 classes，数据集下载链接和分类器ELM(没别的就是快，下载链接)进行实验。
先把BPSO 源码贴出来再对BPSO算法参数进行一下说明：
代码如下（示例）：
%% BinaryPSO
function [globalbest_x,globalbest_faval] = PSO(gN)
E0=0.999; %允许误差
MaxNum=160; %粒子最大迭代次数
particlesize=30; %粒子群规模
c1=2; %每个粒子的个体学习因子，也称为加速常数
c2=2; %每个粒子的社会学习因子，也称为加速常数
w=0.6; %惯性因子
vmax=2; %粒子的最大飞翔速度
vmin=-vmax;
x = round(rand(particlesize,gN));% 初始化粒子位置
v = 4*rand(particlesize,gN)-2; % 初始化粒子速度
f = zeros(particlesize,1); % 初始化适应度函数
for i=1:particlesize
f(i) = ELMResult(gN);
end
personalbest_x=x;%记录粒子最佳位置
personalbest_faval=f;%记录粒子最佳适应度函数值
[globalbest_faval,i]=max(personalbest_faval);%记录种群最佳适应度函数值
globalbest_x=personalbest_x(i,:);%记录种群最佳位置
k=1; %开始迭代
while k<=MaxNum
parfor i=1:particlesize
f(i) = ELMResult(x(i,:));
if f(i)>personalbest_faval(i) %判断当前位置是否是历史上最佳位置
personalbest_faval(i)=f(i);
personalbest_x(i,:)=x(i,:);
end
end
if max(personalbest_faval)>globalbest_faval
[globalbest_faval,i]=max(personalbest_faval);
globalbest_x=personalbest_x(i,:);
end
% 更新方法，这部分也可以用矩阵完成，我故意贴一个很笨的更新方法，自己动手完成吧！
for i=1:particlesize %更新粒子群里每个个体的最新位置
v(i,:)=w*v(i,:)+c1*rand*(personalbest_x(i,:)-x(i,:))...
+c2*rand*(globalbest_x-x(i,:));
for j=1:gN %速度阈值判断及更新粒子的位置
if v(i,j)>vmax
v(i,j)=vmax;
elseif v(i,j)<vmin
v(i,j)=vmin;
end
if Sigmoid(v(i,j))>rand()
x(i,j) = 1;
else
x(i,j) = 0;
end
end
end
if abs(globalbest_faval)>E0,break,end
k=k+1;
end
end
2.参数说明
MaxNum=160; %粒子最大迭代次数
代表粒子群算法的迭代次数，迭代次数越多当然效果越好啦，就是计算时间就上去了。
particlesize=30; %粒子群规模
种群规模一般不取太大了，30-100都可以把，个人调试一般取30或者40，其实特征维度稍微大一点比如100维，你多少个粒子塞进去，都影响不大了，还是要更快的看见种群之间的迭代差异以方便调参，把种群调小一点。
重点来了！！！！！
c1=2; %每个粒子的个体学习因子，也称为加速常数
c2=2; %每个粒子的社会学习因子，也称为加速常数
这两个参数分别决定着粒子想Gbest和Pbest的学习概率，一般来说设成c1=2，c2=2，建议不要乱改，改下面两个参数。
①
w=0.6; %惯性因子
很多说惯性因子，当然重要啊，重要极了，惯性因子越大，向Pbest与Gbest收敛的速度就越慢。当然，还有一种随着迭代次数慢慢减小的惯性因子:
wmax = 2; wmin = 0.1;
w = wmax - (wmax-wmin)*k/MaxNum;
k为当前迭代次数，MaxNum为最大迭代次数, respectively.
②
vmax=2; %粒子的最大速度
vmin=-vmax;
速度最好要对称呀！，关于0对称，当然不对称也是可以的，反正你拿着速度值域去看看sigmoid函数输出是多少你大概就懂了，比如你取[0,2]就很容易向Pbest与Gbest学习靠拢，很快啊，没有防出去，陷入局部最优了。比如你取[-2,0]，那么粒子就会向按位取反的Gbest与Pbest中间取收敛。实际上，V就可以看成奔向Pbest与Gbest的速度嘛，太大了，容易很快陷入局部最优，建议极小值[-3，-1],极大值[1,3]。一定要进行速度限制，不然惯性系数大于1或者小于1的话，分别就会垂直起飞与垂直降落，直接玩完。
3.实验结果
为了验证特征选择的有效性，我们先用ELM分类器对Wine数据集采用10-fold直接分类10000次(不要问为什么这么嚣张，问就是ELM快，i7-10700八核全开)，ELM两个参数为(100隐藏层神经元，sig激活函数)，你猜猜一万次运行多久？如图：
平均运行时间：27/10000 = 0.0027秒，千分之三秒就分类完一次了，我们分别获得了BestResult=98.24%accuracy，和AvgResult=95.64%acc.
那么我们开启特征选择！
好家伙，就在我摁下去运行按钮的一瞬间代码已经终止了…
因为实际上我还有一个自动调整隐藏层神经元数量的模块防止过拟合，那么迭代两代就找到了一个100%acc的解，它并没有做特征选择，只是把隐藏层神经元数量改为了从100改为131，之前应该是神经元数量太少欠拟合了。那么我们将神经元数量改为131，再来10000次ELM分类看看这个调整是否有效：
因为ELM带有一定的随机性，所以选出来的解运行一次的话不一定更好，但是多次运行肯定是更好的，也就是平均结果。
如上图，万次结果最佳的为100%，与之前一致，平均结果98.82%>95.64%，也有了很大的提升。
啊这，不是说好的特征选择，怎么变成调参了，好我们重新来一次：
可以看到第3次迭代acc已经为1了，选出了两个没用的特征，那么我们将这个特征向量再去做万次ELM，看看平均性能如何。。。。
可以看到，实验了一个很基础，简单的UCI(写这篇的时候服务器抽筋了进不去，所以给了KEEl网址) dataset使用BPSO求解的特征向量选择特征去做ELM分类，万次最优acc为1，Avgacc为99.14%，远高于之前的95.64%。
Wine 完结，撒花！
; 总结
提示：由于源码涉及到机器学习内容，从数据导入，划分数据集，定义K-fold，定义适应度函数等多个文件，所以没有一一贴出来，需要完整源码可以私聊。
Original: https://blog.csdn.net/qq_40811682/article/details/116562213
Author: 我是狮子搏兔
Title: Binary Particle Swarm Optimization(BPSO) for Feature Selection(二进制粒子群求解特征选择)
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/665934/
转载文章受原作者版权保护。转载请注明原作者出处！