尧图网站建设 
1 简介遗传算法是研究TSP问题中最为广泛的一种算法,它具有全局搜索的能力.而粒子群算法收敛速度较快,但容易造成局部最优的情况.本文基于遗传算法的交叉变异设计了混合粒子群算法,通过对TSP问题求解分析,证实该方法提高了标准粒子群的搜索能力,获得了较高的收敛速度和近似最优解.标准粒子群算法在极值寻优的过程中根据粒子的变化状况除了自身的属性之外只能这个群体中粒子的属性实验发现随着迭代次数的增加粒子之间越来越相似导致无法跳出局部解。而混合粒子群算法在保留粒子群算法原本的性质之外通过引入遗传算法中的交叉、变异的方式 [2]粒子与个体极值与群体极值交叉以及自身的变异来对粒子种群的多样性问题进行改进直接对粒子携带遍历城市的信息进行交叉、变异处理从而直接改变粒子原本想要表达的遍历方案从而搜索最优解。1.1 个体编码粒子个体编码采用整数编码的方式将粒子的呈现形式转化为在 TSP 问题中的遍历路径根据整数的数字来对应每一个城市编码的位置则代表整个遍历方案的实际内容每个粒子能够表达出遍历的方式通过粒子的编码直接解读出遍历所有城市的方案。1.2 交叉操作个体通过和个体极值和群体极值交叉来更新交叉方法采用整数交叉法 。既能够一定程度上保证粒子的独立性质又能够保证粒子所反映出的方案是可行的。若交叉后存在位置重复的情况使用个体中未包括的城市编号去代替原本重复出现的城市。1.3 变异操作变异方法采用个体内部两位互换方法通过变异的形式去实现更多不同的遍历方式从而增加遍历方式的多样性。当变异后的粒子适应度优于原来的粒子则完成更新过程否则保持原来的粒子状态。2 部分代码clc %清空命令行窗口clear %从当前工作区中删除所有变量并将它们从系统内存中释放close all %删除其句柄未隐藏的所有图窗tic % 保存当前时间%% GA-PSO算法求解TSP%输入%City 需求点经纬度%Distance 距离矩阵%NIND 种群个数%MAXGEN 遗传到第MAXGEN代时程序停止%输出%Gbest 最短路径%GbestDistance 最短路径长度%% 加载数据load(./test_data/City.mat) %需求点经纬度用于画实际路径的XY坐标load(./test_data/Distance.mat) %距离矩阵%% 初始化问题参数CityNumsize(City,1)-1; %需求点个数%% 初始化算法参数NIND60; %粒子数量MAXGEN100; %最大迭代次数bestPopDistance(i) CalcDis(Population(i,:),Distance); %计算距离if PopDistance(i) PbestDistance(i) %若新路径长度变短Pbest(i,:)Population(i,:); %更新PbestPbestDistance(i)PopDistance(i); %更新Pbest距离end%% 根据Pbest更新Gbest[mindis,index] min(PbestDistance); %找出Pbest中最短距离if mindis GbestDistance %若Pbest中最短距离小于Gbest距离Gbest Pbest(index,:); %更新GbestGbestDistance mindis; %更新Gbest距离endend%% 显示此代信息fprintf(Iteration %d, Min Distance %.2f km \n,gen,GbestDistance)%% 存储此代最短距离GbestDisByGen(gen)GbestDistance;%% 更新迭代次数gengen1;end%% 计算结果数据输出到命令行disp(-------------------------------------------------------------)toc %显示运行时间TextOutput(Gbest,GbestDistance) %显示最优路径%% 迭代图figureplot(GbestDisByGen,LineWidth,2) %展示目标函数值历史变化xlim([1 gen-1]) %设置 x 坐标轴范围set(gca, LineWidth,1)xlabel(Iterations)ylabel(Min Distance(km))title(HPSO Process)%% 绘制实际路线DrawPath(Gbest,City)3 仿真结果4 参考文献[1]侯颖, 何建军, 米阁,等. 基于混合粒子群算法求解TSP问题[J]. 电子测试, 2016(8X):2. 【路径规划】基于遗传算法结合粒子群算法求解TSP问题matlab代码
1 简介遗传算法是研究TSP问题中最为广泛的一种算法,它具有全局搜索的能力.而粒子群算法收敛速度较快,但容易造成局部最优的情况.本文基于遗传算法的交叉变异设计了混合粒子群算法,通过对TSP问题求解分析,证实该方法提高了标准粒子群的搜索能力,获得了较高的收敛速度和近似最优解.标准粒子群算法在极值寻优的过程中根据粒子的变化状况除了自身的属性之外只能这个群体中粒子的属性实验发现随着迭代次数的增加粒子之间越来越相似导致无法跳出局部解。而混合粒子群算法在保留粒子群算法原本的性质之外通过引入遗传算法中的交叉、变异的方式 [2]粒子与个体极值与群体极值交叉以及自身的变异来对粒子种群的多样性问题进行改进直接对粒子携带遍历城市的信息进行交叉、变异处理从而直接改变粒子原本想要表达的遍历方案从而搜索最优解。1.1 个体编码粒子个体编码采用整数编码的方式将粒子的呈现形式转化为在 TSP 问题中的遍历路径根据整数的数字来对应每一个城市编码的位置则代表整个遍历方案的实际内容每个粒子能够表达出遍历的方式通过粒子的编码直接解读出遍历所有城市的方案。1.2 交叉操作个体通过和个体极值和群体极值交叉来更新交叉方法采用整数交叉法 。既能够一定程度上保证粒子的独立性质又能够保证粒子所反映出的方案是可行的。若交叉后存在位置重复的情况使用个体中未包括的城市编号去代替原本重复出现的城市。1.3 变异操作变异方法采用个体内部两位互换方法通过变异的形式去实现更多不同的遍历方式从而增加遍历方式的多样性。当变异后的粒子适应度优于原来的粒子则完成更新过程否则保持原来的粒子状态。2 部分代码clc %清空命令行窗口clear %从当前工作区中删除所有变量并将它们从系统内存中释放close all %删除其句柄未隐藏的所有图窗tic % 保存当前时间%% GA-PSO算法求解TSP%输入%City 需求点经纬度%Distance 距离矩阵%NIND 种群个数%MAXGEN 遗传到第MAXGEN代时程序停止%输出%Gbest 最短路径%GbestDistance 最短路径长度%% 加载数据load(./test_data/City.mat) %需求点经纬度用于画实际路径的XY坐标load(./test_data/Distance.mat) %距离矩阵%% 初始化问题参数CityNumsize(City,1)-1; %需求点个数%% 初始化算法参数NIND60; %粒子数量MAXGEN100; %最大迭代次数bestPopDistance(i) CalcDis(Population(i,:),Distance); %计算距离if PopDistance(i) PbestDistance(i) %若新路径长度变短Pbest(i,:)Population(i,:); %更新PbestPbestDistance(i)PopDistance(i); %更新Pbest距离end%% 根据Pbest更新Gbest[mindis,index] min(PbestDistance); %找出Pbest中最短距离if mindis GbestDistance %若Pbest中最短距离小于Gbest距离Gbest Pbest(index,:); %更新GbestGbestDistance mindis; %更新Gbest距离endend%% 显示此代信息fprintf(Iteration %d, Min Distance %.2f km \n,gen,GbestDistance)%% 存储此代最短距离GbestDisByGen(gen)GbestDistance;%% 更新迭代次数gengen1;end%% 计算结果数据输出到命令行disp(-------------------------------------------------------------)toc %显示运行时间TextOutput(Gbest,GbestDistance) %显示最优路径%% 迭代图figureplot(GbestDisByGen,LineWidth,2) %展示目标函数值历史变化xlim([1 gen-1]) %设置 x 坐标轴范围set(gca, LineWidth,1)xlabel(Iterations)ylabel(Min Distance(km))title(HPSO Process)%% 绘制实际路线DrawPath(Gbest,City)3 仿真结果4 参考文献[1]侯颖, 何建军, 米阁,等. 基于混合粒子群算法求解TSP问题[J]. 电子测试, 2016(8X):2.