粒子群算法路径规划

Ⅰ 如何用粒子群算法实现有障碍物时的最短路径规划（从起点到终点路径最短，并避开障碍物），用Matlab实现！

我知道的是A*算法 + 二叉堆优化....
我做的游戏中有用到寻路,我使用上面的方式实现的....
地图是10 * 20 ,怪物采用的是跟随策略....
感觉效率还不错
这种方法是牺牲空间换的效率

不知道地图是否是动态改变的呢?如果是的话,要注意路径的重复出现问题..

还有,看你的图貌似可以简化路径的,应该是什么多边形的凸什么理论,这个没研究过了

希望能帮到你...

Ⅱ 如何用粒子群优化（PSO）算法实现多目标优化

粒子群算法，也称粒子群优化算法（ParticleSwarmOptimization），缩写为PSO，是近年来发展起来的一种新的进化算法(EvolutionaryAlgorithm-EA)。PSO算法属于进化算法的一种，和模拟退火算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”(Crossover)和“变异”(Mutation)操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。粒子群算法是一种并行算法。

Ⅲ 粒子群算法的优缺点

优点：PSO同遗传算法类似，是一种基于迭代的优化算法。系统初始化为一组随机解，通过迭代搜寻最优值。同遗传算法比较，PSO的优势在于简单容易实现，并且没有许多参数需要调整。

缺点：在某些问题上性能并不是特别好。网络权重的编码而且遗传算子的选择有时比较麻烦。最近已经有一些利用PSO来代替反向传播算法来训练神经网络的论文。

(3)粒子群算法路径规划扩展阅读：

注意事项：

基础粒子群算法步骤较为简单。粒子群优化算法是由一组粒子在搜索空间中运动，受其自身的最佳过去位置pbest和整个群或近邻的最佳过去位置gbest的影响。

对于有些改进算法，在速度更新公式最后一项会加入一个随机项，来平衡收敛速度与避免早熟。并且根据位置更新公式的特点，粒子群算法更适合求解连续优化问题。

Ⅳ 什么是粒子群算法

粒子群算法，也称粒子群优化算法（Partical Swarm Optimization），缩写为 PSO， 是近年来发展起来的一种新的进化算法(（Evolu2tionary Algorithm - EA）。PSO 算法属于进化算法的一种，和遗传算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。 PSO 初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个"极值"来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。 粒子公式 在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和新的位置： v[] = w * v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a) present[] = persent[] + v[] (b) v[] 是粒子的速度, w是惯性权重,persent[] 是当前粒子的位置. pbest[] and gbest[] 如前定义 rand () 是介于（0， 1）之间的随机数. c1, c2 是学习因子. 通常 c1 = c2 = 2. 程序的伪代码如下 For each particle ____Initialize particle END Do ____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) ____End While maximum iterations or minimum error criteria is not attained 在每一维粒子的速度都会被限制在一个最大速度Vmax，如果某一维更新后的速度超过用户设定的Vmax，那么这一维的速度就被限定为Vmax

Ⅳ 粒子群优化算法的PSO

演化计算可以用来研究神经网络的三个方面：网络连接权重，网络结构(网络拓扑结构，传递函数)，网络学习算法。
不过大多数这方面的工作都集中在网络连接权重，和网络拓扑结构上。在GA中，网络权重和/或拓扑结构一般编码为染色体(Chromosome)，适应函数(fitness function)的选择一般根据研究目的确定。例如在分类问题中，错误分类的比率可以用来作为适应值。 这里用一个简单的例子说明PSO训练神经网络的过程。这个例子使用分类问题的基准函数 (Benchmark function)IRIS数据集。(Iris 是一种鸢尾属植物) 在数据记录中，每组数据包含Iris花的四种属性：萼片长度，萼片宽度，花瓣长度，和花瓣宽度，三种不同的花各有50组数据. 这样总共有150组数据或模式。
我们用3层的神经网络来做分类。现在有四个输入和三个输出。所以神经网络的输入层有4个节点，输出层有3个节点我们也可以动态调节隐含层节点的数目，不过这里我们假定隐含层有6个节点。我们也可以训练神经网络中其他的参数。不过这里我们只是来确定网络权重。粒子就表示神经网络的一组权重，应该是4*6+6*3=42个参数。权重的范围设定为[-100，100] (这只是一个例子，在实际情况中可能需要试验调整).在完成编码以后，我们需要确定适应函数。对于分类问题，我们把所有的数据送入神经网络，网络的权重有粒子的参数决定。然后记录所有的错误分类的数目作为那个粒子的适应值。现在我们就利用PSO来训练神经网络来获得尽可能低的错误分类数目。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进行搜索. 代码来自2008年数学建模东北赛区B题， #includestdafx.h#include<math.h>#include<time.h>#include<iostream>#include<fstream>usingnamespacestd;intc1=2;//加速因子intc2=2;//加速因子doublew=1;//惯性权重doubleWmax=1;//最大惯性权重doubleWmin=0.6;//最小惯性权重intKmax=110;//迭代次数intGdsCnt;//物资总数intconstDim=10;//粒子维数intconstPNum=50;//粒子个数intGBIndex=0;//最优粒子索引doublea=0.6;//适应度调整因子doubleb=0.5;//适应度调整因子intXup[Dim];//粒子位置上界数组intXdown[Dim]=;//粒子位置下界数组intValue[Dim];//初始急需度数组intVmax[Dim];//最大速度数组classPARTICLE;//申明粒子节点voidCheck(PARTICLE&,int);//约束函数voidInput(ifstream&);//输入变量voidInitial();//初始化相关变量doubleGetFit(PARTICLE&);//计算适应度voidCalculateFit();//计算适应度voidBirdsFly();//粒子飞翔voidRun(ofstream&,int=2000);//运行函数classPARTICLE//微粒类{public:intX[Dim];//微粒的坐标数组intXBest[Dim];//微粒的最好位置数组intV[Dim];//粒子速度数组doubleFit;//微粒适合度doubleFitBest;//微粒最好位置适合度};PARTICLEParr[PNum];//粒子数组intmain()//主函数{ofstreamoutf(out.txt);ifstreaminf(data.txt);//关联输入文件inf>>GdsCnt;//输入物资总数Input(inf);Initial();Run(outf,100);system(pause);return0;}voidCheck(PARTICLE&p,intcount)//参数:p粒子对象,count物资数量{srand((unsigned)time(NULL));intsum=0;for(inti=0;i<Dim;i++){if(p.X>Xup)p.X=Xup;elseif(p.X<Xdown)p.X=Xdown;if(p.V>Vmax)p.V=Vmax;elseif(p.V<0)p.V=0;sum+=p.X;}while(sum>count){p.X[rand()%Dim]--;sum=0;for(inti=0;i<Dim;i++){if(p.X>Xup)p.X=Xup;elseif(p.X<Xdown)p.X=Xdown;if(p.V>Vmax)p.V=Vmax;elseif(p.V<0)p.V=0;sum+=p.X;}}voidInput(ifstream&inf)//以inf为对象输入数据{for(inti=0;i<Dim;i++)inf>>Xup;for(inti=0;i<Dim;i++)inf>>Value;}voidInitial()//初始化数据{GBIndex=0;srand((unsigned)time(NULL));//初始化随机函数发生器for(inti=0;i<Dim;i++)Vmax=(int)((Xup-Xdown)*0.035);for(inti=0;i{for(intj=0;j<Dim;j++){Parr.X[j]=(int)(rand()/(double)RAND_MAX*(Xup[j]-Xdown[j])-Xdown[j]+0.5);Parr.XBest[j]=Parr.X[j];Parr.V[j]=(int)(rand()/(double)RAND_MAX*(Vmax[j]-Vmax[j]/2));}Parr.Fit=GetFit(Parr);Parr.FitBest=Parr.Fit;if(Parr.Fit>Parr[GBIndex].Fit)GBIndex=i;}}doubleGetFit(PARTICLE&p)//计算对象适应度{doublesum=0;for(inti=0;i<Dim;i++)for(intj=1;j<=p.X;j++)sum+=(1-(j-1)*a/(Xup-b))*Value;returnsum;}voidCalculateFit()//计算数组内各粒子的适应度{for(inti=0;i{Parr.Fit=GetFit(Parr);}}voidBirdsFly()//粒子飞行寻找最优解{srand((unsigned)time(NULL));staticintk=10;w=Wmax-k*(Wmax-Wmin)/Kmax;k++;for(inti=0;i{for(intj=0;j<Dim;j++){Parr.V[j]=(int)(w*Parr.V[j]);Parr.V[j]+=(int)(c1*rand()/(double)RAND_MAX*(Parr.XBest[j]-Parr.X[j]);Parr.V[j]+=c2*rand()/(double)RAND_MAX*(Parr[GBIndex].XBest[j]-Parr.X[j]));}}Check(Parr,GdsCnt);for(intj=0;j<Dim;j++){Parr.X[j]+=Parr.V[j];Check(Parr,GdsCnt);}CalculateFit();for(inti=0;i{if(Parr.Fit>=Parr.FitBest){Parr.FitBest=Parr.Fit;for(intj=0;j<Dim;j++)Parr.XBest[j]=Parr.X[j];}}GBIndex=0;for(inti=0;i{if(Parr.FitBest>Parr[GBIndex].FitBest&&i!=GBIndex)GBIndex=i;}}voidRun(ofstream&outf,intnum)//令粒子以规定次数num飞行{for(inti=0;i<num;i++){BirdsFly();outf<<(i+1)<<ends<for(intj=0;j<Dim;j++)outf<outf<<endl;}cout<<Done!<<endl;}

Ⅶ 粒子群算法的matlab程序，一个线性规划问题的解决。主要是那个限制条件的处理。

[r,c] = find(R == max(R(:))); 检索R中最大元素所在的位置（行标r和列标c）
thetap = theta(c(1)); theta（）是自定义函数

Ⅷ 粒子群算法解决实际问题时 其维度如何与实际问题相对应

要明白粒子群算法中，粒子的位置即代表了问题的解，例如你需要求一条路径 路径上假定N个节点 那么N即是这个粒子中的维度

Ⅸ 关于粒子群算法的目标函数优化，优化函数如下图

function main()
clc;clear all;close all;
tic; %程序运行计时
E0=0.001; %允许误差
MaxNum=100; %粒子最大迭代次数
narvs=1; %目标函数的自变量个数
particlesize=30; %粒子群规模
c1=2; %每个粒子的个体学习因子，也称为加速常数
c2=2; %每个粒子的社会学习因子，也称为加速常数
w=0.6; %惯性因子
vmax=0.8; %粒子的最大飞翔速度
x=-5+10*rand(particlesize,narvs); %粒子所在的位置
v=2*rand(particlesize,narvs); %粒子的飞翔速度
%用inline定义适应度函数以便将子函数文件与主程序文件放在一起，
%目标函数是：y=1+(2.1*(1-x+2*x.^2).*exp(-x.^2/2))
%inline命令定义适应度函数如下：
fitness=inline('1/(1+(2.1*(1-x+2*x.^2).*exp(-x.^2/2)))','x');
%inline定义的适应度函数会使程序运行速度大大降低
for i=1:particlesize
for j=1:narvs
f(i)=fitness(x(i,j));
end
end
personalbest_x=x;