粒子群优化算法
2024-05-06 01:21
1. 粒子群优化算法
姓名：杨晶晶 学号：21011210420 学院：通信工程学院
【嵌牛导读】
传统的多目标优化方法是将多目标问题通过加权求和转化为单目标问题来处理的,而粒子算法主要是解决一些多目标优化问题的（例如机械零件的多目标设计优化）,其优点是容易实现,精度高,收敛速度快。
【嵌牛鼻子】粒子群算法的概念、公式、调参以及与遗传算法的比较。
【嵌牛提问】什么是粒子群算法？它的计算流程是什么？与遗传算法相比呢？
【嵌牛正文】
1. 概念
粒子群优化算法(PSO：Particle swarm optimization) 是一种进化计算技术（evolutionary computation），源于对鸟群捕食的行为研究。
粒子群优化算法的基本思想：是通过群体中个体之间的协作和信息共享来寻找最优解。
PSO的优势：在于简单容易实现并且没有许多参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。
2. 算法
2.1 问题抽象
鸟被抽象为没有质量和体积的微粒(点)，并延伸到N维空间，粒子i在N维空间的位置表示为矢量Xi＝(x1，x2，…，xN)，飞行速度表示为矢量Vi＝(v1，v2，…，vN)。每个粒子都有一个由目标函数决定的适应值(fitness value)，并且知道自己到目前为止发现的最好位置(pbest)和现在的位置Xi。这个可以看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(gbest)(gbest是pbest中的最好值)，这个可以看作是粒子同伴的经验。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。
2.2 更新规则
PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest，gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。
公式(1)的第一部分称为【记忆项】，表示上次速度大小和方向的影响；公式(1)的第二部分称为【自身认知项】，是从当前点指向粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的部分；公式(1)的第三部分称为【群体认知项】，是一个从当前点指向种群最好点的矢量，反映了粒子间的协同合作和知识共享。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。
以上面两个公式为基础，形成了PSO的标准形式。
公式(2)和 公式(3)被视为标准PSO算法。
2.3 标准PSO算法流程
标准PSO算法的流程：
1）初始化一群微粒(群体规模为N)，包括随机位置和速度；
2）评价每个微粒的适应度；
3）对每个微粒，将其适应值与其经过的最好位置pbest作比较，如果较好，则将其作为当前的最好位置pbest；
4）对每个微粒，将其适应值与其经过的最好位置gbest作比较，如果较好，则将其作为当前的最好位置gbest；
5）根据公式(2)、(3)调整微粒速度和位置；
6）未达到结束条件则转第2）步。
迭代终止条件根据具体问题一般选为最大迭代次数Gk或(和)微粒群迄今为止搜索到的最优位置满足预定最小适应阈值。
公式(2)和(3)中pbest和gbest分别表示微粒群的局部和全局最优位置。
当C1＝0时，则粒子没有了认知能力，变为只有社会的模型(social-only)：
被称为全局PSO算法。粒子有扩展搜索空间的能力，具有较快的收敛速度，但由于缺少局部搜索，对于复杂问题
比标准PSO 更易陷入局部最优。
当C2＝0时，则粒子之间没有社会信息，模型变为只有认知(cognition-only)模型：
被称为局部PSO算法。由于个体之间没有信息的交流，整个群体相当于多个粒子进行盲目的随机搜索，收敛速度慢，因而得到最优解的可能性小。
2.4 参数分析
参数：群体规模N，惯性因子 ，学习因子c1和c2，最大速度Vmax，最大迭代次数Gk。
群体规模N：一般取20～40，对较难或特定类别的问题可以取到100～200。
最大速度Vmax：决定当前位置与最好位置之间的区域的分辨率(或精度)。如果太快，则粒子有可能越过极小点；如果太慢，则粒子不能在局部极小点之外进行足够的探索，会陷入到局部极值区域内。这种限制可以达到防止计算溢出、决定问题空间搜索的粒度的目的。
权重因子：包括惯性因子和学习因子c1和c2。使粒子保持着运动惯性，使其具有扩展搜索空间的趋势，有能力探索新的区域。c1和c2代表将每个粒子推向pbest和gbest位置的统计加速项的权值。较低的值允许粒子在被拉回之前可以在目标区域外徘徊，较高的值导致粒子突然地冲向或越过目标区域。
参数设置：
1)如果令c1＝c2＝0，粒子将一直以当前速度的飞行，直到边界。很难找到最优解。
2)如果＝0，则速度只取决于当前位置和历史最好位置，速度本身没有记忆性。假设一个粒子处在全局最好位置，它将保持静止，其他粒子则飞向它的最好位置和全局最好位置的加权中心。粒子将收缩到当前全局最好位置。在加上第一部分后，粒子有扩展搜索空间的趋势，这也使得的作用表现为针对不同的搜索问题，调整算法的全局和局部搜索能力的平衡。较大时，具有较强的全局搜索能力；较小时，具有较强的局部搜索能力。
3)通常设c1＝c2＝2。Suganthan的实验表明：c1和c2为常数时可以得到较好的解，但不一定必须等于2。Clerc引入收敛因子(constriction factor) K来保证收敛性。
通常取为4.1,则K＝0.729.实验表明，与使用惯性权重的PSO算法相比，使用收敛因子的PSO有更快的收敛速度。其实只要恰当的选取和c1、c2，两种算法是一样的。因此使用收敛因子的PSO可以看作使用惯性权重PSO的特例。
恰当的选取算法的参数值可以改善算法的性能。
3. PSO与其它算法的比较
3.1 遗传算法和PSO的比较
1)共性：
(1)都属于仿生算法。
(2)都属于全局优化方法。
(3)都属于随机搜索算法。
(4)都隐含并行性。
(5)根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等。
(6)对高维复杂问题，往往会遇到早熟收敛和收敛 性能差的缺点，都无法保证收敛到最优点。
2)差异：
(1)PSO有记忆，好的解的知识所有粒子都保 存，而GA（Genetic Algorithm），以前的知识随着种群的改变被改变。
(2)PSO中的粒子仅仅通过当前搜索到最优点进行共享信息，所以很大程度上这是一种单共享项信息机制。而GA中，染色体之间相互共享信息，使得整个种群都向最优区域移动。
(3)GA的编码技术和遗传操作比较简单，而PSO相对于GA，没有交叉和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。
(4)应用于人工神经网络(ANN)
GA可以用来研究NN的三个方面：网络连接权重、网络结构、学习算法。优势在于可处理传统方法不能处理的问题，例如不可导的节点传递函数或没有梯度信息。
GA缺点:在某些问题上性能不是特别好；网络权重的编码和遗传算子的选择有时较麻烦。
已有利用PSO来进行神经网络训练。研究表明PSO是一种很有潜力的神经网络算法。速度较快且有较好的结果。且没有遗传算法碰到的问题。
2. 粒子群优化算法
粒子群算法 的思想源于对鸟/鱼群捕食行为的研究，模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于Swarm Intelligence的优化方法。它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作，它通过追随当前搜索到的最优值来寻找全局最优。粒子群算法与其他现代优化方法相比的一个明显特色就是所 需要调整的参数很少、简单易行 ，收敛速度快，已成为现代优化方法领域研究的热点。
设想这样一个场景：一群鸟在随机搜索食物。已知在这块区域里只有一块食物；所有的鸟都不知道食物在哪里；但它们能感受到当前的位置离食物还有多远。那么找到食物的最优策略是什么呢？
1. 搜寻目前离食物最近的鸟的周围区域
2. 根据自己飞行的经验判断食物的所在。
PSO正是从这种模型中得到了启发，PSO的基础是 信息的社会共享
每个寻优的问题解都被想像成一只鸟，称为“粒子”。所有粒子都在一个D维空间进行搜索。
所有的粒子都由一个fitness function 确定适应值以判断目前的位置好坏。
每一个粒子必须赋予记忆功能，能记住所搜寻到的最佳位置。
每一个粒子还有一个速度以决定飞行的距离和方向。这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整。
粒子速度更新公式包含三部分： 第一部分为“惯性部分”，即对粒子先前速度的记忆；第二部分为“自我认知”部分，可理解为粒子i当前位置与自己最好位置之间的距离；第三部分为“社会经验”部分，表示粒子间的信息共享与合作，可理解为粒子i当前位置与群体最好位置之间的距离。
第1步 在初始化范围内，对粒子群进行随机初始化，包括随机位置和速度
第2步 根据fitness function，计算每个粒子的适应值
第3步 对每个粒子，将其当前适应值与其个体历史最佳位置（pbest）对应的适应值作比较，如果当前的适应值更高，则用当前位置更新粒子个体的历史最优位置pbest
第4步 对每个粒子，将其当前适应值与全局最佳位置（gbest）对应的适应值作比较，如果当前的适应值更高，则用当前位置更新粒子群体的历史最优位置gbest
第5步 更新粒子的速度和位置
第6步 若未达到终止条件，则转第2步
【通常算法达到最大迭代次数或者最佳适应度值得增量小于某个给定的阈值时算法停止】
粒子群算法流程图如下：
以Ras函数（Rastrigin's Function）为目标函数，求其在x1,x2∈[-5,5]上的最小值。这个函数对模拟退火、进化计算等算法具有很强的欺骗性，因为它有非常多的局部最小值点和局部最大值点，很容易使算法陷入局部最优，而不能得到全局最优解。如下图所示，该函数只在(0,0)处存在全局最小值0。
3. 粒子群优化的算法原理
PSO算法是基于群体的，根据对环境的适应度将群体中的个体移动到好的区域。然而它不对个体使用演化算子，而是将每个个体看作是D维搜索空间中的一个没有体积的微粒（点），在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。第i个微粒表示为Xi = (xi1, xi2, …, xiD)，它经历过的最好位置（有最好的适应值）记为Pi = (pi1, pi2, …, piD)，也称为pbest。在群体所有微粒经历过的最好位置的索引号用符号g表示，即Pg，也称为gbest。微粒i的速度用Vi = (vi1, vi2, …, viD)表示。对每一代，它的第d维(1 ≤ d ≤ D)根据如下方程进行变化：vid = w∙vid+c1∙rand()∙(pid-xid)+c2∙Rand()∙(pgd-xid) (1a)xid = xid+vid其中w为惯性权重(inertia weight)，c1和c2为加速常数(acceleration constants)，rand()和Rand()为两个在[0,1]范围里变化的随机值。此外，微粒的速度Vi被一个最大速度Vmax所限制。如果当前对微粒的加速导致它的在某维的速度vid超过该维的最大速度vmax,d，则该维的速度被限制为该维最大速度vmax,d。对公式(1a)，第一部分为微粒先前行为的惯性，第二部分为“认知(cognition)”部分，表示微粒本身的思考；第三部分为“社会(social)”部分，表示微粒间的信息共享与相互合作。“认知”部分可以由Thorndike的效应法则(law of effect)所解释，即一个得到加强的随机行为在将来更有可能出现。这里的行为即“认知”，并假设获得正确的知识是得到加强的，这样的一个模型假定微粒被激励着去减小误差。“社会”部分可以由Bandura的替代强化(vicarious reinforcement)所解释。根据该理论的预期，当观察者观察到一个模型在加强某一行为时，将增加它实行该行为的几率。即微粒本身的认知将被其它微粒所模仿。PSO算法使用如下心理学假设：在寻求一致的认知过程中，个体往往记住自身的信念，并同时考虑同事们的信念。当其察觉同事的信念较好的时候，将进行适应性地调整。 a). 初始化一群微粒（群体规模为m），包括随机的位置和速度；b). 评价每个微粒的适应度；c). 对每个微粒，将它的适应值和它经历过的最好位置pbest的作比较，如果较好，则将其作为当前的最好位置pbest；d). 对每个微粒，将它的适应值和全局所经历最好位置gbest的作比较，如果较好，则重新设置gbest的索引号；e). 根据方程(1)变化微粒的速度和位置；f). 如未达到结束条件（通常为足够好的适应值或达到一个预设最大代数Gmax），回到b)。
4. 粒子群优化的算法参数
PSO参数包括：群体规模m，惯性权重w，加速常数c1和c2，最大速度Vmax，最大代数Gmax，解空间[Xmin Xmax]。Vmax决定在当前位置与最好位置之间的区域的分辨率（或精度）。如果Vmax太高，微粒可能会飞过好解，如果Vmax太小，微粒不能进行足够的探索，导致陷入局部优值。该限制有三个目的：防止计算溢出；实现人工学习和态度转变；决定问题空间搜索的粒度。惯性权重w使微粒保持运动的惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。加速常数c1和c2代表将每个微粒推向pbest和gbest位置的统计加速项的权重。低的值允许微粒在被拉回来之前可以在目标区域外徘徊，而高的值导致微粒突然的冲向或者越过目标区域。如果没有后两部分，即c1 = c2 = 0，微粒将一直以当前的速度飞行，直到到达边界。由于它只能搜索有限的区域，将很难找到好的解。如果没有第一部分，即w = 0，则速度只取决于微粒当前的位置和它们历史最好位置pbest和gbest，速度本身没有记忆性。假设一个微粒位于全局最好位置，它将保持静止。而其它微粒则飞向它本身最好位置pbest和全局最好位置gbest的加权中心。在这种条件下，微粒群将统计的收缩到当前的全局最好位置，更象一个局部算法。在加上第一部分后，微粒有扩展搜索空间的趋势，即第一部分有全局搜索的能力。这也使得w的作用为针对不同的搜索问题，调整算法全局和局部搜索能力的平衡。如果没有第二部分，即c1 = 0，则微粒没有认知能力，也就是“只有社会(social-only)”的模型。在微粒的相互作用下，有能力到达新的搜索空间。它的收敛速度比标准版本更快，但是对复杂问题，比标准版本更容易陷入局部优值点。如果没有第三部分，即c2 = 0，则微粒之间没有社会信息共享，也就是“只有认知(cognition-only)”的模型。因为个体间没有交互，一个规模为m的群体等价于m个单个微粒的运行。因而得到解的几率非常小。
5. 粒子群优化算法的参数设置
从上面的例子我们可以看到应用PSO解决优化问题的过程中有两个重要的步骤: 问题解的编码和适应度函数PSO的一个优势就是采用实数编码, 不需要像遗传算法一样是二进制编码(或者采用针对实数的遗传操作.例如对于问题 f(x) = x1^2 + x2^2+x3^2 求解,粒子可以直接编码为 (x1, x2, x3), 而适应度函数就是f(x). 接着我们就可以利用前面的过程去寻优.这个寻优过程是一个叠代过程, 中止条件一般为设置为达到最大循环数或者最小错误PSO中并没有许多需要调节的参数,下面列出了这些参数以及经验设置粒子数: 一般取 20–40. 其实对于大部分的问题10个粒子已经足够可以取得好的结果, 不过对于比较难的问题或者特定类别的问题, 粒子数可以取到100 或 200粒子的长度: 这是由优化问题决定, 就是问题解的长度粒子的范围: 由优化问题决定,每一维可是设定不同的范围Vmax: 最大速度,决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度,例如上面的例子里,粒子 (x1, x2, x3) x1 属于 [-10, 10], 那么 Vmax 的大小就是 20学习因子: c1 和 c2 通常等于 2. 不过在文献中也有其他的取值. 但是一般 c1 等于 c2 并且范围在0和4之间中止条件: 最大循环数以及最小错误要求. 例如, 在上面的神经网络训练例子中, 最小错误可以设定为1个错误分类, 最大循环设定为2000, 这个中止条件由具体的问题确定.全局PSO和局部PSO: 我们介绍了两种版本的粒子群优化算法: 全局版和局部版. 前者速度快不过有时会陷入局部最优. 后者收敛速度慢一点不过很难陷入局部最优. 在实际应用中, 可以先用全局PSO找到大致的结果,再用局部PSO进行搜索.另外的一个参数是惯性权重, 由Shi 和Eberhart提出, 有兴趣的可以参考他们1998年的论文(题目: A modified particle swarm optimizer)。
6. 粒子群算法的算法介绍
如前所述，PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO 初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。 在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和新的位置：v[] = w * v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a)present[] = present[] + v[] (b)v[] 是粒子的速度, w是惯性权重,present[] 是当前粒子的位置. pbest[] and gbest[] 如前定义 rand () 是介于（0， 1）之间的随机数. c1, c2 是学习因子. 通常 c1 = c2 = 2.程序的伪代码如下For each particle____Initialize particleENDDo____For each particle________Calculate fitness value________If the fitness value is better than the best fitness value (pBest) in history____________set current value as the new pBest____End____Choose the particle with the best fitness value of all the particles as the gBest____For each particle________Calculate particle velocity according equation (a)________Update particle position according equation (b)____EndWhile maximum iterations or minimum error criteria is not attained在每一维粒子的速度都会被限制在一个最大速度Vmax，如果某一维更新后的速度超过用户设定的Vmax，那么这一维的速度就被限定为Vmax
7. 最优化 粒子群法
运行结果。
function [xm,fv] = zhidaoPSO(fitness,N,c1,c2,w,M,D)
%[xm,fv] = zhidaoPSO(@fitness,40,2,2,0.8,1000,2)
%
% 求解无约束优化问题
% fitness 待优化目标函数
% N 粒子数目，
% cX 学习因子
% W 惯性权重
% M 最大迭代次数
% D 自由变量的个数
% xm 目标函数取最小值时的自由变量
% fv 目标函数的最小值
% Detailed explanation goes here
tic;
format long;
%------step1.初始化种群的个体------------
x = zeros(N,D);
v = zeros(N,D);
for i=1:N
for j=1:D
x(i,j)=100*rand - 50; %随机初始化位置
v(i,j)=100*rand - 50; %随机初始化速度
end
end
%------step2.先计算各个粒子的适应度，并初始化Pi和PgPg为全局最优-------------
p = zeros(N,1);
%y = zeros(N,D);
for i=1:N
p(i)=fitness(x(i,:));
%y(i,:)=x(i,:);
end
y = x;
pg = x(N,:); %Pg为全局最优
for i=1:(N-1)
if fitness(x(i,:))<fitness(pg)
pg=x(i,:);
end
end
%------step3.进入主要循环，按照公式依次迭代------------
%Pbest = zeros(M,1);
for t=1:M
for i=1:N
v(i,:)=w*v(i,:)+c1*rand*(y(i,:)-x(i,:))+c2*rand*(pg-x(i,:));
for k=1:D
if v(i,k) > 10 %10=vmax
v(i,k) = 10;
end
end
x(i,:)=x(i,:)+v(i,:);
for k=1:D
if x(i,k) > 50 %50=xmax
x(i,k) = 31;
end
end
if fitness(x(i,:))<p(i)
p(i)=fitness(x(i,:));
y(i,:)=x(i,:);
end
if p(i)<fitness(pg)
pg=y(i,:);
end
end
%Pbest(t)=fitness(pg);
end
xm = pg';
fv = fitness(pg);
toc;
8. 粒子群算法
粒子群算法（Particle Swarm Optimization），又称鸟群觅食算法，是由数学家J. Kennedy和R. C. Eberhart等开发出的一种新的进化算法。它是从随机解开始触发，通过迭代寻找出其中的最优解。本算法主要是通过适应度来评价解的分数，比传统的遗传算法更加的简单，它没有传统遗传算法中的“交叉”和“变异”等操作，它主要是追随当前搜索到的最优值来寻找到全局最优值。这种算法实现容易，精度高，收敛快等特点被广泛运用在各个问题中。 粒子群算法是模拟鸟群觅食的所建立起来的一种智能算法，一开始所有的鸟都不知道食物在哪里，它们通过找到离食物最近的鸟的周围，再去寻找食物，这样不断的追踪，大量的鸟都堆积在食物附近这样找到食物的几率就大大增加了。粒子群就是这样一种模拟鸟群觅食的过程，粒子群把鸟看成一个个粒子，它们拥有两个属性——位置和速度，然后根据自己的这两个属性共享到整个集群中，其他粒子改变飞行方向去找到最近的区域，然后整个集群都聚集在最优解附近，最后最终找到最优解。 算法中我们需要的数据结构，我们需要一个值来存储每个粒子搜索到的最优解，用一个值来存储整个群体在一次迭代中搜索到的最优解，这样我们的粒子速度和位置的更新公式如下： 其中pbest是每个粒子搜索到的最优解，gbest是整个群体在一次迭代中搜索到的最优解，v[i]是代表第i个粒子的速度，w代表惯性系数是一个超参数，rang()表示的是在0到1的随机数。Present[i]代表第i个粒子当前的位置。我们通过上面的公式不停的迭代粒子群的状态，最终得到全局最优解
最新文章
热门文章
推荐阅读