遗传算法求解TSP问题 MATLAB代码

  • d1_891253
    了解作者
  • 3.2KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-05-29 02:19
    上传日期
遗传算法求解TSP(旅行商)问题 MATLAB代码
遗传算法.zip
  • 遗传算法
  • disance.m
    101B
  • fitness.m
    99B
  • tspga.m
    4.5KB
  • eliminate.m
    119B
  • YCSF.m
    615B
内容介绍
%%%%%遗传算法计算TSP%%%% function [opt,fval,A]=tspga(map,MaxIter,SizeScale,pm,pc); n=max(size(map)); DistMatrix=zeros(n,n); %初始化距离矩阵DistMatrix,用于存储两城市之间的距离 for i=1:n for j=1:n DistMatrix(i,j)=pdist2(map(i,:),map(j,:),'euclidean'); %计算两城市之间的距离,存储于DistMatrix矩阵中 end end %%%%生成初始种群%%%% Road=ones(SizeScale,n); %初始化矩阵Road for i=1:SizeScale Road(i,:)=randperm(n); %随机生成初始种群(路径矩阵) end iter=1; MinestRoad_fval=ones(MaxIter,1); %初始化最短里程矩阵MinestRoad_fval的历史记录值 MinestRoad_opt=ones(MaxIter,n); %初始化最短里程路径矩阵MinestRoad_opt的历史记录值 while iter<=MaxIter Dist=zeros(SizeScale,1); %初始化里程矩阵Dist,用于存储每条路径的里程值 %%%%%%计算每条路径的里程%%%%% for i=1:SizeScale for j=1:(n-1) Dist(i)=Dist(i)+DistMatrix(Road(i,j),Road(i,j+1)); end Dist(i)=Dist(i)+DistMatrix(Road(i,1),Road(i,n)); %计算每条路径的里程存储于Dist矩阵中 end %%%%%计算每条路径的适应度值%%%%%% fitmatrix=ones(SizeScale,1); [MinRoad,A]=min(Dist(:,1)); %计算出最小里程值 MaxRoad=max(Dist(:,1)); %计算出最大里程值 for i=1:SizeScale fitmatrix(i)=fitness(MinRoad,MaxRoad,Dist(i)); %计算每条路径的适应度的值,存储于fitmatrix中 end %%%%%%%%选择操作%%%%%% [c,p]=sort(fitmatrix(:,1)); %对适应度值进行升序排列,c中存放升序排列结果,p中存放适应度值对应的fitmatrix中的位置 change=20; %选出适应度值最小路径数目 for i=1:change Road(p(i),:)=Road(p(SizeScale),:); %选出适应度值最小的20条路径,用适应度值最大的路径替换 end Roadnew=Road; %%%%%%交叉操作%%%%% for i=1:SizeScale u=randint(2,1,[1 SizeScale]); s=u(1); t=u(2); if rand(1)<pc %判断是否进行交叉操作 oldp1=Road(s,:);%随机选取两个父代染色体 oldp2=Road(t,:); u=randint(2,1,[1 n]); crossj1=u(1);%随机选取两个切点 crossj2=u(2); minjcross=min(crossj1,crossj2); maxjcross=max(crossj1,crossj2); segment1=oldp1(minjcross:maxjcross);%选中的路径(染色体)片段,文中的Axy segment2=oldp2(minjcross:maxjcross);%选中的路径(染色体)片段,文中的Bxy oldp12=eliminate(oldp1,segment2);%在oldp1中删除与segment2相同的元素 oldp21=eliminate(oldp2,segment1);%在oldp2中删除与segment1相同的元素 newp1=[segment2,oldp12];%生成新路径(子代染色体) newp2=[segment1,oldp21];%生成新路径(子代染色体) Roadnew(s,:)=newp1;%更新种群 Roadnew(t,:)=newp2; end end Road1=Roadnew; %%%%%%%计算交叉操作之后的种群的最优解(最短里程路径)%%%%%%% Dist=zeros(SizeScale,1); for i=1:SizeScale for j=1:(n-1) Dist(i)=Dist(i)+DistMatrix(Road1(i,j),Road1(i,j+1)); end Dist(i)=Dist(i)+DistMatrix(Road1(i,1),Road1(i,n));%计算里程,更新里程矩阵 end [MinRoad2,B]=min(Dist); MaxRoad=max(Dist(:,1)); for i=1:SizeScale fitmatrix(i)=fitness(MinRoad2,MaxRoad,Dist(i));%计算适应度函数 end %%%%%%%变异操作(单点交叉)%%%%%%%%% k=1; [d,p]=sort(fitmatrix(:,1)); while k<=SizeScale c=randint(2,1,[1,n]); pos1(1,:)=c(1,:);%随机产生交叉点 pos2(1,:)=c(2,:);%随机产生交叉点 rk=rand(); if rk<=pm&&k~=p(SizeScale); %判断是否进行变异 temp=Road1(p(k),pos1);%进行变异操作,更新种群 Road1(p(k),pos1)=Road1(p(k),pos2); Road1(p(k),pos2)=temp; end k=k+1; end %%%%%计算变异操作后的种群的最优解(最短里程路径)%%%%% Dist=zeros(SizeScale,1); for i=1:SizeScale for j=1:(n-1) Dist(i)=Dist(i)+DistMatrix(Road1(i,j),Road1(i,j+1)); end Dist(i)=Dist(i)+DistMatrix(Road1(i,1),Road1(i,n)); end [MinRoad3,C]=min(Dist); %%%%%%搜索每一代中的最优路径%%%%%% if (MinRoad2>MinRoad)&&(MinRoad3>MinRoad) MinestRoad=MinRoad; D=A; Road(D,:)=Road(A,:); else if(MinRoad>MinRoad2)&&(MinRoad3>MinRoad2) MinestRoad=MinRoad2; D=B; Road(D,:)=Road(B,:); else MinestRoad=MinRoad3; D=C; Road(D,:)=Road(C,:); end end MinestRoad_fval(iter,1)=MinestRoad;%本代最小里程值 MinestRoad_opt(iter,:)=Road(D,:);%本代最优路径 iter=iter+1; Road=Road1; end [MinestRoad,a]=min(MinestRoad_fval);%取路径里程最小值 opt=MinestRoad_opt(a,:);%输出最优路径 fval=MinestRoad;%输出最短里程 A=a;%得到最优路径的迭代次数 %%%%%%%%绘图%%%%%% plot(map(:,1),map(:,2),'*'); hold on; for c=1:n text(map(c,1),map(c,2),['' num2str(c)],'Color','k','FontWeight','b'); end XX=map(MinestRoad_opt(a,:),1); XX=[XX;map(MinestRoad_opt(a,1),1)]; YY=map(MinestRoad_opt(a,:),2); YY=[YY;map(MinestRoad_opt(a,1),2)]; plot(XX,YY); legend('城市','最优路径');
评论
    相关推荐
    • matlab算法经典程序
      一些常用的算法matlab实现,包括各种智能算法,图论算法,以及规划算法
    • 电力系统状态估计MATLAB算法
      状态估计算法 MATLAB 内附readme 详细说明了使用方法和步骤 有专门的txt文件 可以输入自己的bus阵 line阵等 即可进行状态估计
    • matlab算法大全
      matlab 中常用的程序 函数使用示例
    • 粒子滤波matlab算法
      粒子滤波正在得到重视,越来越的人开始注意,在故障诊断和预测领域里,用来估计状态参数。附件中matlab程序介绍了基本粒子滤波算法
    • matlab算法大全
      本文档涵盖了很多数学算法,利用matlab实现,在工程技术上有很高的应用价值
    • Matlab算法大全
      Matlab算法 PDF 分章阅读 高清PDF 很好很全面的阅读材料
    • 各种MATLAB算法
      各种MATLAB算法,代码,可供初学者参考应用,
    • Matlab算法大全
      Matlab算法大全 第01章线性规划 第02章整数规划 第03章非线性规划 第04章动态规划 第05章图与网络 第06章排队论 第07章对策论 第08章层次分析法 第09章插值与拟合 第10章数据的统计描述和分析 第11章方差分析 第12章...
    • matlab算法大全
      matlab算法大全,很全,提供插值,数值微分、积分等功能代码的实现
    • matlab 算法程序
      matlab 算法程序,包括了插值、函数逼近、数值积分、非线性方程求解、统计分析、偏微分方程数值解法等17个部分,每个部分针对各种函数有m文件代码和相关解释说明。