-
2020-07-10 19:53:22
遗传算法简介
遗传算法包括初始种群生成,适应度的计算,种群选择,交叉和变异这几项内容
TSP问题
TSP问题是旅行商经过一系列城市使得旅行商经过的总路程最短的问题
遗传算法内容
生成初始种群
// An highlighted block for i=1:NP f(i,:)=randperm(N); %初始种群 end
计算个体适应度
// An highlighted block for i=1:NP len(i,1)=D(f(i,N),f(i,1)); for j=1:N-1 len(i,1)=len(i,1)+D(f(i,j),f(i,j+1)); end end maxlen=max(len); minlen=min(len %计算归一化适应值 for i=1:NP fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.001)); end
轮盘赌选择
// An highlighted block sumFit=sum(fitness); fitvalue=fitness./sumFit; fitvalue=cumsum(fitvalue); ms=sort(rand(NP,1)); fiti=1; newi=1; while newi <= NP if (ms(newi)) < fitvalue(fiti) nf(newi,:)=f(fiti,:); %种群重新生成 newi=newi+1; else fiti=fiti+1; end end
交叉操作
交叉操作是单点交叉的方式,例如12345678和87654321,假如第一个点交叉则变成8234571和17654328
// An highlighted block for i=1:2:NP for j=1:N if rand<pc %同一种群变化 A=find(nf(i,:)==nf(i+1,j)); nf(i,A)=nf(i,j); B=find(nf(i+1,:)==nf(i,j)); nf(i+1,B)=nf(i+1,j); %交换位置 temp1=nf(i+1,j); nf(i+1,j)=nf(i,j); nf(i,j)=temp1; end end end
变异操作
变异是采用单点变异的方式,比如12345678第5个位置变异,则在随机生成一个值比如1赋给第5个位置,则生成的个体是52341678
// An highlighted block for i=1:NP for j=1:N if rand<pm temp2=nf(i,j); temp3=randi([1,N],1,1); A=find(nf(i,:)==temp3); nf(i,j)=temp3; nf(i,A)=temp2; end end end
图像输出
figure for i=1:N-1 plot([C(R(i),1),C(R(i+1),1)],[C(R(i),2),C(R(i+1),2)],'bo-') hold on; end plot([C(R(N),1),C(R(1),1)],[C(R(N),2),C(R(1),2)],'ro-') title(['优化最短距离:',num2str(minlen)])
完整代码
close all clear all clc %读入初始数据 FP1=fopen('shuju.txt','rt'); N=fscanf(FP1,'%d',1); %初始个体数 C=fscanf(FP1,'%f',[2,N]); %个体坐标 C=C'; D=zeros(N); %两两距离 for i=1:N for j=1:N D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;%求任意两个城市的间距 end end NP=200; %种群规模 G=500; %迭代次数 f=zeros(NP,N); %种群 nf=zeros(NP,N); %子种群 pc=0.4; %交叉概率 pm=0.2; %变异概率 F=[]; for i=1:NP f(i,:)=randperm(N); %初始种群 end R=f(1,:); %最优种群 len=zeros(NP,1); %存储路径长度 fitness=zeros(NP,1); %存储归一化值 gen=0; %计算各种群的适应度值,即种群的长度 while gen<G for i=1:NP len(i,1)=D(f(i,N),f(i,1)); for j=1:N-1 len(i,1)=len(i,1)+D(f(i,j),f(i,j+1)); end end maxlen=max(len); minlen=min(len); rr=find(len==minlen); %找到最小值种群所在的位置 R=f(rr(1,1),:); %最小值种群的基因 %计算归一化适应值 for i=1:NP fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.001)); end %基于轮盘赌的复制操作 sumFit=sum(fitness); fitvalue=fitness./sumFit; fitvalue=cumsum(fitvalue); ms=sort(rand(NP,1)); fiti=1; newi=1; while newi <= NP if (ms(newi)) < fitvalue(fiti) nf(newi,:)=f(fiti,:); %种群重新生成 newi=newi+1; else fiti=fiti+1; end end %交叉操作 for i=1:2:NP for j=1:N if rand<pc %同一种群变化 A=find(nf(i,:)==nf(i+1,j)); nf(i,A)=nf(i,j); B=find(nf(i+1,:)==nf(i,j)); nf(i+1,B)=nf(i+1,j); %交换位置 temp1=nf(i+1,j); nf(i+1,j)=nf(i,j); nf(i,j)=temp1; end end end %变异操作 for i=1:NP for j=1:N if rand<pm temp2=nf(i,j); temp3=randi([1,N],1,1); A=find(nf(i,:)==temp3); nf(i,j)=temp3; nf(i,A)=temp2; end end end f=nf; f(1,:)=R; clear F gen=gen+1; Rlength(gen)=minlen; end figure for i=1:N-1 plot([C(R(i),1),C(R(i+1),1)],[C(R(i),2),C(R(i+1),2)],'bo-') hold on; end plot([C(R(N),1),C(R(1),1)],[C(R(N),2),C(R(1),2)],'ro-') title(['优化最短距离:',num2str(minlen)]) figure plot(Rlength) xlabel('迭代次数') ylabel('目标函数') title('适应度进化曲线') disp('最短路径路程是:') disp(R)
运行结果
总结
利用遗传算法可以解决TSP问题,结果较准确,但是迭代收敛的慢,易陷入局部最优
更多相关内容 -
遗传算法 TSP 实现
2018-10-31 12:00:46遗传算法(GeneticAlgorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,通过模拟自然进化过程搜索最优解。遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的,初代... -
遗传算法tsp案例
2019-04-26 18:26:07遗传算法解决tsp(旅行商问题)的python实现代码,有图形和控制台输出 -
基于遗传算法的TSP算法_基于遗传算法的TSP算法_matlab_遗传算法TSP_
2021-09-29 03:57:03基于遗传算法的TSP算法的MATLAB实现 -
基于遗传算法的TSP算法
2019-05-06 09:33:40这是基于遗传算法的TSP算法的MATLAB仿真源码,下载后直接运行主程序即可,请大家参考!!! -
Matlab TSP(遗传算法)
2019-12-09 22:44:53关于TSP问题的遗传算法求解总代码 包含每个过程单独函数 可以自己修改选择变异函数 备有注释 易于理解 -
遗传算法解决TSP问题(全)
2017-12-26 16:26:24遗传算法解决TSP问题··························································································... -
遗传算法 TSP
2018-10-16 14:45:21解压直接运行即可 有画图功能 主程序. 主程序中有一rand('seed',n) n 为某一整 数, 这是设置随机数发生器的种子,这样实际上规定 了随机数发生的方式,因此后面的随机数其实都是定 下来的,这样所有人就可以看到... -
遗传算法解决 TSP 问题(附matlab源程序).docx-综合文档
2021-05-25 06:07:47遗传算法解决 TSP 问题(附matlab源程序).docx -
遗传算法tsp
2018-12-29 11:53:3610个城市的路径优化单纯的使用了遗传算法,其中使用了交叉和变异,没有进行更深的优化。 -
TSP问题的遗传算法_遗传算法TSP_breathe86w_
2021-09-29 18:39:04用于TSP旅商问题的遗传算法,txt文件内涵源代码,复制粘贴即可 -
tps_matlab_tsp_遗传算法TSP_
2021-10-04 04:56:24旅行商问题(TSP问题)。假设有一个旅行商人要拜访全国31 个省会城市,他需要选择所要走的路径,路径的限制是每个城市只能拜访 一次,而且最后要回到原来出发的城市。对路径选择的要求是:所选路径 的路程为所有路径... -
tsp_遗传算法TSP_
2021-09-28 21:05:40遗传算法解决tsp问题,可自行生成城市坐标,也可选择导入,交叉方法也有两种 -
遗传算法TSP变异matlab代码
2022-04-08 21:17:47遗传算法TSP变异matlab代码,代码简洁明了,超级适合新手小白上手练习,没有复杂运算, -
遗传算法解决TSP问题的Python代码
2017-03-20 22:42:18遗传算法解决TSP问题的Python代码,三个py文件,一个小DEMO -
GA遗传算法TSP优化_遗传算法_
2021-09-30 17:36:27经典的TSP旅行商问题,遗传算法优化问题,可用于解决各种复杂的问题,欢迎大家交流指正。 -
遗传算法 TSP 城市最短路径
2019-04-13 01:19:46NULL 博文链接:https://tristan-s.iteye.com/blog/1122493 -
GA-TSP_遗传算法TSP_
2021-09-30 01:03:51TSP(旅行商问题)是典型的NP完全问题,即其最坏情况下的时间复杂度随着问题规模的增大按指数方式增长,到目前为止还没有一个多项式时间的有效算法。 -
遗传算法TSP.txt
2021-08-11 18:54:57matlab遗传TSP算法.txt -
遗传算法TSP
2014-01-07 21:26:03遗传算法解决TSP求解问题设计,包括大中小地图文件 -
遗传算法解决TSP旅行商问题 python
2018-12-18 23:50:15遗传算法解决TSP旅行商问题 python,带图像输出,可自行修改经纬度。 -
模拟退火模型_遗传算法TSPmatlab_
2021-09-29 11:09:51用于学习和介绍旅行商问题的遗传算法基础教学 -
0脚本档_matlab遗传算法tsp问题_
2021-10-01 15:51:31使用了较为简单的遗传算法,来解决一般的tsp问题 -
遗传算法解决TSP问题(C++版)
2018-03-29 15:05:41遗传算法解决TSP问题(C++版),内容详细,可以很好地帮助初学者学习遗传算法 -
遗传算法解决TSP问题
2017-01-17 21:48:49资源包含“遗传算法解决TSP问题”的相关代码(.cpp和.h)以及TSP相关的城市数据。 -
matlab遗传算法解决tsp问题
2021-06-20 13:17:42MATLAB遗传算法求解TSP问题 -
Untitledycsf_recentlyu1d_遗传算法TSP_最优搜索路线_源码
2021-10-01 07:28:58遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法算法流程:1. 开始2.建立种群(或者更新种群)3.记录上次迭代... -
遗传算法求解TSP标准程序_TSP问题_遗传算法_
2021-09-30 14:28:41使用遗传算法优化旅行规划问题,目标是使总的路程最短或路费最少 -
C++程序—遗传算法TSP.docx
2022-05-07 11:39:34C++程序—遗传算法TSP.docx