1、粒子群算法简介
粒子群优化算法(Particle Swarm Optimization——PSO），由James Kennedy（社会心理学博士）和Russell Eberhart（电子工程学博士，于1995年提出的一种基于种群的随机优化算法 。
文章插图
鸟被抽象为没有质量和体积的微粒(点)，并延伸到N维空间，粒子I 在N维空间的位置表示为矢量Xi＝(x1，x2，…，xn)，飞行速度表示为矢量Vi＝(v1，v2，…，vn),每个粒子都有一个由目标函数决定的适应值(fitness value)；并且知道自己到目前为止发现的最好位置(pbest)；除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(gbest)(gbest是pbest中的最好值) 。
2、粒子群算法核心概念
如果鸟群觅食的过程中会有信息的交流，则每一个小鸟都会向最优的路径进行觅食的 。每一个小鸟其对应的位置矢量和速度矢量，所以在寻优的过程中会对每一个粒子的位置和速度进行更新 。
文章插图
其中（1）式为粒子i在第k+1次迭代时的速度更新公式，（2）式为相对应的位置更新公式 。
rand()是介于0~1之间的实数，ω为惯性因子，c1为个体学习因子，c2为群体认知因子 。
从社会学的角度来看，公式(1)的第一部分称为记忆项，表示上次速度大小和方向的影响；公式第二部分称为自身认知项，是从当前点指向粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的分；公式的第三部分称为群体认知项，是一个从当前点指向种群最好点的矢量，反映了粒子间的协同合作和知识共享 。
粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动 。ω值较大，全局寻优能力强，局部寻优能力弱，ω较小，则反之 。初始时，ω取为常数，后来实验发现，动态能够获得比固定值更好的寻优结果 。动态可以在PSO搜索过程中线性变化，也可根据PSO性能的某个测度函数动态改变 。
在解决TSP问题中，每一个粒子相当于遗传算法中的每一个个体，粒子的位置则相当于该个体访问所有城市的路径，粒子的速度则是一个交换序列的矩阵 。该交换序列是把个体最优或群体最优的粒子与粒子群的路径关系 。就是说在最优个体的粒子其中一个元素在待优化的粒子中的位置记录下来，并且在接下来的更新粒子位置时，尽量复制最优个体的元素序列 。
3、粒子群算法流程
Step1:初始化一群微粒(群体规模为M)，包括随机位置和速度；
Step2:评价每个微粒的适应度；
Step3:对每个微粒，将其适应值与其经过的最好位置pbest作比较，如果较好，则将其作为当前的最好位置pbest;
Step4:对每个微粒，将其适应值与其经过的最好位置gbest作比较，如果较好，则将其作为当前的最好位置gbest;
Step5:根据(1)、(2)式调整微粒速度和位置；
Step6:未达到结束条件则转Step2 。
4、粒子群算法实例及代码
文章插图
解决TSP问题的Matlab代码如下:
function Psorout = PSO_TSP(xy,dmat,Popsize,IterNum,showProg,showResult)%利用粒子群优化算法解决TSP问题nargs = 6;%代表函数要输入参数的个数for i = nargin:nargs-1switch icase 0%产生城市数据xy = [488,814;1393,595;2735,2492;4788,4799;4825,1702;789,2927;4853,1120;4786,3757;2427,1276;4002,2530;710,3496;2109,4455;4579,4797;3962,2737;4798,694;3279,747;179,1288;4246,4204;4670,1272;3394,4072;3789,1218;3716,4647;1962,1750];%xy = 5000*rand(39,2);%产生40个城市坐标40*2矩阵case 1%计算距离矩阵N = size(xy,1);a = meshgrid(1:N);%生成N*N升序矩阵dmat = reshape(sqrt(sum((xy(a,:)-xy(a\',:)).^2,2)),N,N);% \'为矩阵的转置，reshape把数据生成N*N的矩阵case 2%设置粒子群数目Popsize = 500;case 3%设置迭代次数IterNum = 2000;case 4%是否展示迭代过程showProg = 1;case 5%是否展示结果showResult = 1;otherwiseendend%对输入参数进行检查[N,~] = size(xy);%城市个数、维数[nr,nc] = size(dmat);%距离矩阵的行数和列数if N~=nr || N~=ncerror(\'城市坐标或距离矩阵输入有误\')endshowProg = logical(showProg(1));%将数值转变为逻辑值showResult = logical(showResult(1));%画出城市位置分布图figure(1);plot (xy(:,1),xy(:,2),\'k.\',\'MarkerSize\',14);title(\'城市坐标位置\');%% PSO参数初始化c1 = 0.1;%个体学习因子c2 = 0.075;%社会学习因子w = 1;%惯性因子pop = zeros(Popsize,N);%粒子位置v = zeros(Popsize,N);%粒子速度iter = 1;%迭代次数计时fitness = zeros(Popsize,1); %适应度函数值Pbest = zeros(Popsize,N);%个体极值路径Pbest_fitness = zeros(Popsize,1);%个体极值Gbest = zeros(IterNum,N);%群体极值路径Gbest_fitness = zeros(Popsize,1);%群体极值Length_ave = zeros(IterNum,1);ws = 1;%惯性因子最大值we = 0.5;%惯性因子最小值%% 产生初始位置和速度for i = 1:Popsizepop(i,:) = randperm(N);v(i,:) = randperm(N);end%计算粒子适应度值for i =1:Popsizefor j =1:N-1fitness(i) = fitness(i) + dmat(pop(i,j),pop(i,j+1));endfitness(i) = fitness(i) + dmat(pop(i,end),pop(i,1));%加上终点回到起点的距离end%计算个体极值和群体极值Pbest_fitness = fitness;Pbest = pop;[Gbest_fitness(1),min_index] = min(fitness);Gbest(1,:) = pop(min_index);Length_ave(1) = mean(fitness);%% 迭代寻优while iter
- 乳腺癌会遗传吗？如何预防？
- 何氏狐臭净最新消息 何氏狐臭净有效果吗
- 鱼鳞病遗传方式
- 发际线越来越高了怎么办 发际线太高了会遗传吗
- 亚马逊A9算法三大核心支柱
- 亚马逊“算法动态定价”曝光
- 淘宝全球购特色店铺准入要求解读
- 拼多多竞价有什么最优算法？流量大吗？
- 淘宝客佣金设置规则和算法
- 淘宝爱逛街视频投稿要求解读
特别声明：本站内容均来自网友提供或互联网，仅供参考，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。