[原创]史上最简洁易懂的模拟退火解TSP问题的Matlab源程序+过程图
<P>%this program is written by 刘学智. Finished time is 05.1.23 16:03 <BR>%utilizing it solving TSP problem by simulating stealing algorithm<BR>%=sa_tsp(d,10,0.1,.87)<BR>%d=;</P><P>%the result is fval=2; route=149 4 13 10 12 2 6 3 11 7 5 1 8</P>
<P>function =sa_tsp(d,t0,tf,alpha)<BR>%d is the distance matrix;t0,tf is the initial and finil temperature;<BR>%alpha is controling temperature coeffient<BR>n=length(d);%the number of cities<BR>L=100*n;%the length of Markov chain<BR>route=randperm(n);%the initial traveling route<BR>fval=value(route,d);%the initial goal value<BR>t=t0;ii=0;<BR>tic<BR>while t>tf<BR> for i=1:L<BR> =exchange(route,d);<BR> if fval_after<fval<BR> route=route_after;<BR> fval=fval_after;<BR> elseif exp((fval-fval_after)*2/t)>rand<BR> route=route_after;<BR> fval=fval_after;<BR> else route=route;<BR> fval=fval;<BR> end<BR> end<BR> t=alpha*t;<BR> ii=ii+1;fval_sequence(ii)=fval;<BR>end<BR>plot(1:ii,fval_sequence);%plot the convergence figure<BR>toc<BR>%----------------------------------------------------------------<BR>function fval=value(route,d)%used for reckoning the goal value of the selected traveling route<BR>n=length(d);<BR>fval=0;<BR>for i=1:n-1<BR> fval=fval+d(route(i),route(i+1));<BR>end<BR>%fval=fval+d(route(n),route(1));% if'%'is omited,it computes a circle,else<BR>%a chain------------------------------------------------------------------<BR>function =exchange(route,d)<BR>%changing traveling route by inversing the sequence between two selected 2 locations <BR>n=length(d);<BR>location1=ceil(n*rand);<BR>location2=ceil(n*rand);%the location of two exchanged number<BR>loc1=min(location1,location2);loc2=max(location1,location2);<BR>middle_route=fliplr(route(loc1:loc2));%the part route which has been exchanged<BR>route_after=;%the after traveling route<BR>fval_after=value(route_after,d);<BR>%----------------------------------------------------------------</P> QQ:137278541 <BR>验证:mcm <P>遗传程序接着上传</P> 好好学习下 好好学习下 借鉴了 楼主辛苦了 楼主辛苦了……
页:
[1]