[原创]史上最简洁易懂的模拟退火解TSP问题的Matlab源程序+过程图

mathsoft · 发表于 2006-1-26 07:07:56

<

>%this program is written by 刘学智. Finished time is 05.1.23 16:03 %utilizing it solving TSP problem by simulating stealing algorithm %[fval,route]=sa_tsp(d,10,0.1,.87) %d=[0 2 1 2 0 0 1 0 1 2 1 1 1 1 %2 0 1 4 1 0 1 1 1 3 1 0 2 1 %1 1 0 1 0 0 0 3 1 1 0 2 2 1 %2 4 1 0 1 1 2 1 0 2 1 0 1 1 %0 1 0 1 0 2 0 1 1 1 0 1 1 2 %0 0 0 1 2 0 1 2 1 1 1 2 1 2 %1 1 0 2 0 1 0 1 1 1 0 2 2 1 %0 1 3 1 1 2 1 0 1 2 1 4 2 2 %1 1 1 0 1 1 1 1 0 1 1 1 3 1 %2 3 1 2 1 1 1 2 1 0 1 0 0 3 %1 1 0 1 0 1 0 1 1 1 0 3 1 1 %1 0 2 0 1 2 2 4 1 0 3 0 1 0 %1 2 2 1 1 1 2 2 3 0 1 1 0 4 %1 1 1 1 2 2 1 2 1 3 1 0 4 0];
<

>%the result is fval=2; route=14 9 4 13 10 12 2 6 3 11 7 5 1 8
<

>function [fval,route]=sa_tsp(d,t0,tf,alpha) %d is the distance matrix;t0,tf is the initial and finil temperature; %alpha is controling temperature coeffient n=length(d);%the number of cities L=100*n;%the length of Markov chain route=randperm(n);%the initial traveling route fval=value(route,d);%the initial goal value t=t0;ii=0; tic while t>tf for i=1

[fval_after,route_after]=exchange(route,d); if fval_after<fval route=route_after; fval=fval_after; elseif exp((fval-fval_after)*2/t)>rand route=route_after; fval=fval_after; else route=route; fval=fval; end end t=alpha*t; ii=ii+1;fval_sequence(ii)=fval; end plot(1:ii,fval_sequence);%plot the convergence figure toc %---------------------------------------------------------------- function fval=value(route,d)%used for reckoning the goal value of the selected traveling route n=length(d); fval=0; for i=1:n-1 fval=fval+d(route(i),route(i+1)); end %fval=fval+d(route(n),route(1));% if'%'is omited,it computes a circle,else %a chain------------------------------------------------------------------ function [fval_after,route_after]=exchange(route,d) %changing traveling route by inversing the sequence between two selected 2 locations n=length(d); location1=ceil(n*rand); location2=ceil(n*rand);%the location of two exchanged number loc1=min(location1,location2);loc2=max(location1,location2); middle_route=fliplr(route(loc1:loc2));%the part route which has been exchanged route_after=[route(1:loc1-1) middle_route route(loc2+1:n)];%the after traveling route fval_after=value(route_after,d); %----------------------------------------------------------------

mathsoft · 发表于 2006-1-26 07:09:51

QQ:137278541 验证：mcm

mathsoft · 发表于 2006-1-26 07:12:11

<

>遗传程序接着上传

hlj031140 · 发表于 2011-4-16 18:57:17

好好学习下

hlj031140 · 发表于 2011-4-16 19:01:04

好好学习下

liaoma010101 · 发表于 2011-6-8 20:52:48

借鉴了楼主辛苦了

mingfengzhige · 发表于 2011-9-5 17:16:11

楼主辛苦了……

		自动登录	找回密码
密码			注-册-帐-号