【路径规划】基于matlab改进的粒⼦算法路径规划【含Matlab源码491期】⼀、粒⼦算法简介 1 引⾔
⾃然界中的鸟和鱼的体⾏为⼀直是科学家的研究兴趣所在。⽣物学家Craig Reynolds在1987年提出了⼀个⾮常有影响的鸟聚集模型，在他的仿真中，每⼀个个体都遵循：避免与邻域个体相撞：匹配邻域个体的速度；飞向鸟中⼼，且整个体飞向⽬标。仿真中仅利⽤上⾯三条简单的规则，就可以⾮常接近地模拟出鸟飞⾏的现象。1990年， ⽣物学家Frank Heppner也提出了鸟类模型， 它的不同之处在于：鸟类被吸引飞到栖息地。在仿真中，⼀开始每⼀只鸟都没有特定的飞⾏⽬标，只是使⽤简单的规则确定⾃⼰的飞⾏⽅向和飞⾏速度，当有⼀只鸟飞到栖息地时，它周围的鸟也会跟着飞向栖息地，最终整个鸟都会落在栖息地。 1995年， 美国社会⼼理学家James Kennedy和电⽓⼯程师RussellEberhart共同提出了粒⼦算法(ParticleS warm Optimization，PSO) ， 该算法的提出是受对鸟类体⾏为进⾏建模与仿真的研究结果的启发。他们的模型和仿真算法主要对Frank Heppner的模型进⾏了修正，以使粒⼦飞向解空间并在最优解处降落。粒⼦算法⼀经提出，由于其算法简单，容易实现，⽴刻引起了进化计算领域学者们的⼴泛关注， 形成⼀个研究热点。2001年出版的J.Kennedy与R.Eberhart合著的《体智能》将体智能的影响进⼀步扩⼤[] ， 随后关于粒⼦优化算法的研究报告和研究成果⼤量涌现，继⽽掀起了国内外研究热潮[2-7]。 粒⼦优化算法来源于鸟类体活动的规律性，进⽽利⽤体智能建⽴⼀个简化的模型。它模拟鸟类的觅⾷⾏为，将求解问题的搜索空间⽐作鸟类的飞⾏空间，将每只鸟抽象成⼀个没有质量和体积的粒 ⼦，⽤它来表征问题的⼀个可能解，将寻问题最优解的过程看成鸟类寻⾷物的过程，进⽽求解复杂的优化问题。粒⼦优化算法与其他进化算法⼀样，也是基于“种”和“进化”的概念，通过个体间
的协作与竞争，实现复杂空间最优解的搜索。同时，它⼜不像其他进化算法那样对个体进⾏交叉、变异、选择等进化算⼦操作，⽽是将体中的个体看作在l维搜索空间中没有质量和体积的粒⼦，每个粒⼦以⼀定的速度在解空间运动， 并向⾃⾝历史最佳位置P best和邻域历史最佳位置g best聚集， 实现对候选解的进化。粒⼦算法具有很好的⽣物社会背景⽽易于理解，由于参数少⽽容易实现，对⾮线性、多峰问题均具有较强的全局搜索能⼒，在科学研究与⼯程实践中得到了⼴泛关注。⽬前，该算法已⼴泛应⽤于函数优化、神经⽹络训练、模式分类、模糊控制等领域。
2 粒⼦算法理论
2.1粒⼦算法描述
鸟类在捕⾷过程中，鸟成员可以通过个体之间的信息交流与共享获得其他成员的发现与飞⾏经历。在⾷物源零星分布并且不可预测的条件下，这种协作机制所带来的优势是决定性的，远远⼤于对⾷物
的竞争所引起的劣势。粒⼦算法受鸟类捕⾷⾏为的启发并对这种⾏为进⾏模仿，将优化问题的搜索空间类⽐于鸟类的飞⾏空间，将每只鸟抽象为⼀个粒⼦，粒⼦⽆质量、⽆体积，⽤以表征问题的⼀个可⾏解，优化问题所要搜索到的最优解则等同于鸟类寻的⾷物源。粒⼦算法为每个粒⼦制定了与鸟类运动类似的简单⾏为规则，使整个粒⼦的运动表现出与鸟类捕⾷相似的特性，从⽽可以求解复杂的优化问题。粒⼦算法的信息共享机制可以解释为⼀种共⽣合作的⾏为，即每个粒⼦都在不停地进⾏搜索，并且其搜索⾏为在不同程度上受到体中其他个体的影响[8]，同时这些粒⼦还具备对所经历最佳位置的记
忆能⼒，即其搜索⾏为在受其他个体影响的同时还受到⾃⾝经验的引导。基于独特的搜索机制，粒⼦算法⾸先⽣成初始种，即在可⾏解空间和速度空间随机初始化粒⼦的速度与位置，其中粒⼦的位置⽤于表征问题的可⾏解，然后通过种间粒⼦个体的合作与竞争来求解优化问题。
2.2粒⼦算法建模
粒⼦优化算法源⾃对鸟捕⾷⾏为的研究：⼀鸟在区域中随机搜索⾷物，所有鸟知道⾃⼰当前位置离⾷物多远，那么搜索的最简单有效的策略就是搜寻⽬前离⾷物最近的鸟的周围区域。粒⼦算法
利⽤这种模型得到启⽰并应⽤于解决优化问题。在粒⼦算法中，每个优化问题的潜在解都是搜索空间中的⼀只鸟，称之为粒⼦。所有的粒⼦都有⼀个由被优化的函数决定的适应度值，每个粒⼦还有⼀
金钢绳个速度决定它们飞翔的⽅向和距离。然后，粒⼦们就追随当前的最优粒⼦在解空间中搜索[9]。
粒⼦算法⾸先在给定的解空间中随机初始化粒⼦，待优化问题的变量数决定了解空间的维数。每个粒⼦有了初始位置与初始速度，然后通过迭代寻优。在每⼀次迭代中，每个粒⼦通过跟踪两个“极值”来更新⾃⼰在解空间中的空间位置与飞⾏速度：⼀个极值就是单个粒⼦本⾝在迭代过程中到的最优解粒⼦，这个粒⼦叫作个体极值：另⼀个极值是种所有粒⼦在迭代过程中所到的最优解粒⼦，这个粒⼦是全局极值。上述的⽅法叫作全局粒⼦算法。如果不⽤种所有粒⼦⽽只⽤其中⼀部分作为该粒⼦的邻居粒⼦，那么在所有邻居粒⼦中的极值就是局部极值，该⽅法称为局部粒⼦算法。
2.3粒⼦算法的特点
粒⼦算法本质是⼀种随机搜索算法，它是⼀种新兴的智能优化技术。该算法能以较⼤概率收敛于全局最优解。实践证明，它适合在动态、多⽬标优化环境中寻优，与传统优化算法相⽐，具有较快的计
算速度和更好的全局搜索能⼒。
(1)粒⼦算法是基于智能理论的优化算法，通过体中粒⼦间的合作与竞争产⽣的体智能指导优化搜索。与其他算法相⽐，粒⼦算法是⼀种⾼效的并⾏搜索算法。
(2)粒⼦算法与遗传算法都是随机初始化种，使⽤适应值来评价个体的优劣程度和进⾏⼀定的随机
搜索。但粒⼦算法根据⾃⼰的速度来决定搜索，没有遗传算法的交叉与变异。与进化算法相⽐，粒⼦算法保留了基于种的全局搜索策略，但是其采⽤的速度-位移模型操作简单，避免了复杂的遗传操作。
(3)由于每个粒⼦在算法结束时仍保持其个体极值，即粒⼦算法除了可以到问题的最优解外，还会得到若⼲较好的次优解，因此将粒⼦算法⽤于调度和决策问题可以给出多种有意义的⽅案。
(4)粒⼦算法特有的记忆使其可以动态地跟踪当前搜索情况并调整其搜索策略。另外，粒⼦算法对种的⼤⼩不敏感，即使种数⽬下降时，性能下降也不是很⼤。
3 粒⼦算法种类
3.1基本粒⼦算法
3.2标准粒⼦算法
引⼊研究粒⼦算法经常⽤到的两个概念：⼀是“探索”，指粒⼦在⼀定程度上离开原先的搜索轨迹，向新的⽅向进⾏搜索，体现了⼀种向未知区域开拓的能⼒，类似于全局搜索；⼆是“开发”，指粒⼦在⼀定程度上继续在原先的搜索轨迹上进⾏更细⼀步的搜索，主要指对探索过程中所搜索到的区域进⾏更进⼀步的搜索。探索是偏离原来的寻优轨迹去寻⼀个更好的解，探索能⼒是⼀个算法的全局搜索能⼒。开发是利⽤⼀个好的解，继续原来的寻优轨迹去搜索更好的解，它是算法的局部搜索能⼒。如何确定局部搜索能⼒和全局搜索能⼒的⽐例， 对⼀个问题的求解过程很重要。1998年， Shi Yuhui等⼈提出了带有惯性权重的改进粒⼦算法[10]，由于该算法能够保证较好的收敛效果，所以被默认为标准粒⼦算法。其进化过程为：
在式(6.7)中，第⼀部分表⽰粒⼦先前的速度，⽤于保证算法的全局收敛性能；第⼆部分、第三部分则使算法具有局部收敛能⼒。可以看
出，式(6.7)中惯性权重w表⽰在多⼤程度上保留原来的速度：W
负离子灯较⼤，则全局收敛能⼒较强，局部收敛能⼒较弱；w较⼩，则局部收敛能⼒较强，全局收敛能⼒较弱。
当w=1时，式(6.7)与式(6.5)完全⼀样，表明带惯性权重的粒⼦算法是基本粒⼦算法的扩展。实验结果表明：w在0.8~1.2之间时，粒⼦算法有更快的收敛速度；⽽当w>1.2时，算法则容易陷⼊局部极值。
另外，在搜索过程中可以对w进⾏动态调整：在算法开始时，可给w赋予较⼤正值，随着搜索的进⾏，可以线性地使w逐渐减⼩，这样可以保证在算法开始时，各粒⼦能够以较⼤的速度步长在全局范围内探
测到较好的区域；⽽在搜索后期，较⼩的w值则保证粒⼦能够在极值点周围做精细的搜索，从⽽使算法有较⼤的概率向全局最优解位置收敛。对w进⾏调整，可以权衡全局搜索和局部搜索能⼒。⽬前，采⽤较多的动态惯性权重值是Shi提出的线性递减权值策略， 其表达式如下：
3.3压缩因⼦粒⼦算法
Clerc等⼈提出利⽤约束因⼦来控制系统⾏为的最终收敛[11] ， 该⽅法可以有效搜索不同的区域，并且能得到⾼质量的解。压缩因⼦法的速度更新公式为：
实验结果表明：与使⽤惯性权重的粒⼦优化算法相⽐，使⽤具
有约束因⼦的粒⼦算法具有更快的收敛速度。
3.4离散粒⼦算法
基本的粒⼦算法是在连续域中搜索函数极值的有⼒⼯具。继基本粒⼦算法之后， Kennedy和Eber
hart⼜提出了⼀种离散⼆进制版的粒⼦算法[12]。在此离散粒⼦⽅法中，将离散问题空间映射到连续粒⼦运动空间，并适当修改粒⼦算法来求解，在计算上仍保留经典粒⼦算法速度-位置更新运算规则。粒⼦在状态空间的取值和变化只限于0和1两个值， ⽽速度的每⼀维vi y代表位置每⼀位xi取值为1的可能性。因此， 在连续粒⼦中的vij更新公式依然保持不变， 但是P best和：best只在[0， 1] 内取值。其位置更新等式表⽰如下：
4 粒⼦算法流程
粒⼦算法基于“种”和“进化”的概念，通过个体间的协作与竞争，实现复杂空间最优解的搜索[13]，其流程如下：
(1)初始化粒⼦，包括体规模N，每个粒⼦的位置x；和速度Vio
(2) 计算每个粒⼦的适应度值fit[i] 。
(3) 对每个粒⼦， ⽤它的适应度值fit[门和个体极值P best(i)⽐较。如果fit[i] <P best(i) ， 则⽤fit[i] 替换掉P best(i) 。
(4) 对每个粒⼦， ⽤它的适应度值fit[i] 和全局极值g best⽐较。如果fit[i] < 8 best， 则⽤fit[i] 替换g best。
永磁同步电机反电动势
(5)迭代更新粒⼦的速度v；和位置xj。
(6)进⾏边界条件处理。
(7)判断算法终⽌条件是否满⾜：若是，则结束算法并输出优化结果；否则返回步骤(2)。
粒⼦算法的运算流程如图6.1所⽰。
粒⼦算法的运算流程如图6.1所⽰。
5 关键参数说明
在粒⼦优化算法中，控制参数的选择能够影响算法的性能和效率；如何选择合适的控制参数使算法性能最佳，是⼀个复杂的优化问题。在实际的优化问题中，通常根据使⽤者的经验来选取控制参数。
粒⼦算法的控制参数主要包括：粒⼦种规模N，惯性权重w，加速系数c和c， 最⼤速度Via x， 停⽌准则， 邻域结构的设定， 边界条件处理策略等[14]，
粒⼦种规模N
粒⼦种⼤⼩的选择视具体问题⽽定，但是⼀般设置粒⼦数为20~50。对于⼤部分的问题10个粒⼦，已经可以取得很好的结果：不过对于⽐较难的问题或者特定类型的问题，粒⼦的数量可以取到100或
双向dcdc变换器200。另外，粒⼦数⽬越⼤，算法搜索的空间范围就越⼤，也就更容易发现全局最优解；当然，算法运⾏的时间也越长。
惯性权重w
惯性权重w是标准粒⼦算法中⾮常重要的控制参数，可以⽤来控制算法的开发和探索能⼒。惯性权重的⼤⼩表⽰了对粒⼦当前速度继承的多少。当惯性权重值较⼤时，全局寻优能⼒较强，局部寻优能⼒
较弱：当惯性权重值较⼩时，全局寻优能⼒较弱，局部寻优能⼒较强。惯性权重的选择通常有固定权重和时变权重。固定权重就是选择常数作为惯性权重值，在进化过程中其值保持不变，⼀般取值为
[0.8，1.2]：时变权重则是设定某⼀变化区间，在进化过程中按照某种⽅式逐步减⼩惯性权重。时变权重的选择包括变化范围和递减率。固定的惯性权重可以使粒⼦保持相同的探索和开发能⼒，⽽时变权重可以使粒⼦在进化的不同阶段拥有不同的探索和开发能⼒。
加速常数c1和c2
加速常数c和c 2分别调节向P best和g best⽅向飞⾏的最⼤步长， 它们分别决定粒⼦个体经验和体经验对粒⼦运⾏轨迹的影响，反映粒⼦之间的信息交流。如果cr=c2=0，则粒⼦将以当前的飞⾏速度飞到边界。此时，粒⼦仅能搜索有限的区域，所以难以到最优解。如果q=0，则为“社会”模型，粒⼦缺乏认知能⼒，⽽只有体经验，它的收敛速度较快，但容易陷⼊局部最优；如果oy=0，则为“认
知”模
型，没有社会的共享信息，个体之间没有信息的交互，所以到最优解的概率较⼩，⼀个规模为D的体等价于运⾏了N个各⾏其是的粒⼦。因此⼀般设置c1=C2，通常可以取c1=cg=1.5。这样，个体经验和体经验就有了同样重要的影响⼒，使得最后的最优解更精确。
粒⼦的最⼤速度vmax
粒⼦的速度在空间中的每⼀维上都有⼀个最⼤速度限制值vd max，⽤来对粒⼦的速度进⾏钳制， 使速度控制在范围[-Vimax， +va max]内，这决定问题空间搜索的⼒度， 该值⼀般由⽤户⾃⼰设定。Vmax是⼀个⾮常重要的参数，如果该值太⼤，则粒⼦们也许会飞过优秀区域：⽽如果该值太⼩，则粒⼦们可能⽆法对局部最优区域以外的区域进⾏充分的探测。它们可能会陷⼊局部最优，⽽⽆法移动⾜够远的距离
域：⽽如果该值太⼩，则粒⼦们可能⽆法对局部最优区域以外的区域进⾏充分的探测。它们可能会陷⼊局部最优，⽽⽆法移动⾜够远的距离⽽跳出局部最优， 达到空间中更佳的位置。研究者指出， 设定Vmax和调整惯性权重的作⽤是等效的， 所以!max⼀般⽤于对种的初始化进⾏设定， 即将vmax设定为每维变量的变化范围， ⽽不再对最⼤速度进⾏细致的选择和调节。
停⽌准则
悬挂式指示牌
最⼤迭代次数、计算精度或最优解的最⼤停滞步数▲t(或可以接受的满意解)通常认为是停⽌准则，即算法的终⽌条件。根据具体的优化问题，停⽌准则的设定需同时兼顾算法的求解时间、优化质量和
搜索效率等多⽅⾯性能。
邻域结构的设定
全局版本的粒⼦算法将整个体作为粒⼦的邻域，具有收敛速度快的优点，但有时算法会陷⼊局部最优。局部版本的粒⼦算法将位置相近的个体作为粒⼦的邻域，收敛速度较慢，不易陷⼊局部最优
值。实际应⽤中，可先采⽤全局粒⼦算法寻最优解的⽅向，即得到⼤致的结果，然后采⽤局部粒⼦算法在最优点附近进⾏精细搜索。边界条件处理
当某⼀维或若⼲维的位置或速度超过设定值时，采⽤边界条件处理策略可将粒⼦的位置限制在可⾏搜索空间内，这样能避免种的膨胀与发散，也能避免粒⼦⼤范围地盲⽬搜索，从⽽提⾼了搜索效率。
具体的⽅法有很多种， ⽐如通过设置最⼤位置限制Xmax和最⼤速度限制Vmax， 当超过最⼤位置或最⼤速度时， 在范围内随机产⽣⼀个数值代替，或者将其设置为最⼤值，即边界吸收。
⼆、部分源代码
function [xOpt,fval,exitflag,output,population,scores]=...
pso(fitnessfcn,nvars,Aineq,bineq,Aeq,beq,LB,UB,nonlcon,options)
% Find the minimum of a function using Particle Swarm Optimization.
%
% This is an implementation of Particle Swarm Optimization algorithm using
% the same syntax as the Genetic Algorithm Toolbox, with some additional
% options specific to PSO. Allows code-reusability when trying different
% population-based optimization algorithms. Certain GA-specific parameters
% such as cross-over and mutation functions will not be applicable to the
% PSO algorithm. Demo function included, with a small library of test
% functions. Requires Optimization Toolbox.
%
刮腻子的机器% New features will be added regularly until this is made redundant by an
% official MATLAB PSO toolbox.
%
% Author: S. Samuel Chen. Version 1.31.2.
% Available from www.mathworks/matlabcentral/fileexchange/25986
% Distributed under BSD license. First published in 2009.
%
% Syntax:
% psodemo
% pso
% x =pso(fitnessfcn,nvars)
% x =pso(fitnessfcn,nvars,Aineq,bineq)
% x =pso(fitnessfcn,nvars,Aineq,bineq,Aeq,beq)
% x =pso(fitnessfcn,nvars,Aineq,bineq,Aeq,beq,LB,UB)
% x =pso(fitnessfcn,nvars,Aineq,bineq,Aeq,beq,LB,UB,nonlcon)
% x =pso(fitnessfcn,nvars,Aineq,bineq,Aeq,beq,LB,UB,nonlcon,options)
% x =pso(problem)
%[x, fval]=pso(...)
%[x, fval,exitflag]=pso(...)
%[x, fval,exitflag,output]=pso(...)
%[x, fval,exitflag,output,population]=pso(...)
%[x, fval,exitflag,output,population,scores]=pso(...)
%
% Description:
% psodemo
% Runs a demonstration of the PSO algorithm using test function specified
% by user.
%
% pso
% Runs a default demonstration using Rosenbrock's banana function.
%
% x =pso(fitnessfcn,nvars)
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议