关于MATLAB用遗传算法解决TSP问题昨天的详细描述

laomaizpy · 发表于 2006-4-24 13:14

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？我要加入

x

那位高手能帮小弟解决下如何解决TSP问题最后的输出一个坐标的直观图吗 前面的程序已经调试好了，，我想在最后的输出中输出一个坐标图来描述该问题,输出的坐标图的横坐标和纵坐标分别描述的是某个城市点的具体位子，我这里包含了10个城市。。比如一个城市A的位子在坐标上的表示是（Xa，Ya）。然后依次罗列出10个城市对应的坐标上的位子```程序的输出结果是把遗传算法反复迭代后的最优的路径用线连接起来描述一个路径``` 对了` 我这里还有个相应的距离距阵，根据这个距离句阵来绘制坐标系``` 我的距离距阵是这样的： diskTSP.txt: 0 0.3361 0.3141 0.3601 0.5111 0.5176 0.2982 0.4564 0.3289 0.2821 0.3361 0 0.1107 0.6149 0.8407 0.8083 0.5815 0.6418 0.4378 0.3897 0.3141 0.1107 0 0.5349 0.7919 0.8207 0.5941 0.6908 0.4982 0.4464 0.3601 0.6149 0.5349 0 0.3397 0.6528 0.5171 0.7375 0.6710 0.6310 0.5111 0.8407 0.7919 0.3397 0 0.4579 0.4529 0.6686 0.7042 0.6862 0.5176 0.8083 0.8207 0.6528 0.4579 0 0.2274 0.2937 0.4494 0.4683 0.2982 0.5815 0.5941 0.5171 0.4529 0.2274 0 0.2277 0.2690 0.2694 0.4564 0.6418 0.6908 0.7375 0.6686 0.2937 0.2277 0 0.2100 0.2529 0.3289 0.4378 0.4982 0.6710 0.7042 0.4494 0.2690 0.2100 0 0.0531 0.2821 0.3897 0.4464 0.6310 0.6862 0.4683 0.2694 0.2529 0.0531 0
谢谢了我的邮箱是<a href="mailtlaomai@cqwu.net" target="_blank" >laomai@cqwu.net</A> 以下是我的程序： function [bestpop,trace,mindistance]=ga(d,termops,num,pc,cxops,pm,alpha) clear; load diskTSP.txt; % %———————————————————————— %[bestpop,trace]=ga(d,termops,num,pc,cxops,pm,alpha) %d:距离矩阵 %termops:种群带数 %num:每带染色体的个数 %pc:交叉概率 %cxops:由于本程序采用单点交叉，交叉点的设置在本程序中没有很好的解决，所以本文了采用定点，即第cxops，可以随机产生。 %pm:变异概率 %alpha:评价函数eval(vi)=alpha*(1-alpha).^(i-1). %bestpop:返回的最优种群 %trace:进化轨迹 %------------------------------------------------ d=diskTSP; citynum=size(d,2); n=nargin; if n<2 termops=100; num=10; pc=0.25; cxops=3; pm=0.30; alpha=0.10; end if n<3 num=10; pc=0.25; cxops=3; pm=0.30; alpha=0.10; end if n<4 pc=0.25; cxops=3; pm=0.30; alpha=0.10; end if n<5 cxops=3; pm=0.30; alpha=0.10; end if n<6 pm=0.30; alpha=0.10; end if n<7 alpha=0.10; end if isempty(cxops) cxops=3; end %========================================= citynum=size(d,2); for i=1:num t(i,:)=randperm(citynum); end %========================================= for i=1:termops; %========================================= [m,n]=size(t); for k=1:m for i=1:n-1 l(k,i)=d(t(k,i),t(k,i+1)); end l(k,n)=d(t(k,n),t(k,1)); l(k)=-sum(l(k,:)); end %========================================= [x,y]=find(max(l)); trace(i)=-l(y(1)); bestpop=t(y(1),:);
%========================================= [m,n]=size(l); t1=t; [beforesort,aftersort1]=sort(l,2);%fsort from l to u for i=1:n aftersort(i)=aftersort1(n+1-i); %change end for k=1:n; t(k,:)=t1(aftersort(k),:); l1(k)=l(aftersort(k)); end t1=t; l=l1; for i=1:size(aftersort,2) evalv(i)=alpha*(1-alpha).^(i-1); end m=size(t,1); q=cumsum(evalv); qmax=max(q); for k=1:m r=qmax*rand(1); for j=1:m if j==1&r<=q(1) t(k,:)=t1(1,:); elseif j~=1&r>q(j-1)&r<=q(j) t(k,:)=t1(j,:); end end end %========================================== [m,n]=size(t); for k=1:m t0=1:n; for i=1:n for j=1:length(t0) if t(k,i)==t0(j) g(k,i)=j; t0(j)=[]; break end end end end %============================================ [m,n]=size(g); ran=rand(1,m); r=cxops; [x,ru]=find(ran<pc); if ru>=2 for k=1:2:length(ru)-1 g1(ru(k),:)=[g(ru(k),[1:r]),g(ru(k+1),[(r+1):n])]; g(ru(k+1),:)=[g(ru(k+1),[1:r]),g(ru(k),[(r+1):n])]; g(ru(k),:)=g1(ru(k),:); end end %=============================================== %均匀变异 [m,n]=size(g); ran=rand(1,m); r=rand(1,3); %dai gai jin rr=floor(n*rand(1,3)+1); [x,mu]=find(ran<pm); for k=1:length(mu) for i=1:length(r) umax(i)=n+1-rr(i); umin(i)=1; g(mu(k),rr(i))=umin(i)+floor((umax(i)-umin(i))*r(i)); end end %均匀变异 %=================================================== [m,n]=size(g); for k=1:m t0=1:n; for i=1:n t(k,i)=t0(g(k,i)); t0(g(k,i))=[]; end end end
 

[ 本帖最后由 cdwxg 于 2006-8-8 19:41 编辑 ]

cdwxg · 发表于 2006-8-8 19:28

原帖由 laomaizpy 于 2006-4-24 13:14 发表
那位高手能帮小弟解决下如何解决TSP问题最后的输出一个坐标的直观图吗 前面的程序已经调试好了，，我想在最后的输出中输出一个坐标图来描述该问题,输出的坐标图的横坐标和纵坐标分别描述的是 ...

好象TSP用蚁群算法好吧?

[ 本帖最后由 cdwxg 于 2006-8-8 19:41 编辑 ]

账号		自动登录	找回密码
密码			我要加入

[综合讨论] 关于MATLAB用遗传算法解决TSP问题昨天的详细描述

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

关于MATLAB用遗传算法解决TSP问题昨天的详细描述