www.pudn.com > anttsp.rar > local_search.m, change:2008-04-20,size:2328b


function new_tour=local_search(city_num,dist,tour,local_iter_num) 
%3-选择局部搜索,产生7中新的路径,其中有3中退化为2-opt 
%若新产生的路径的长度小于原有路径,则用新路径代替原有路径 
new_tour=tour; 
for i=1:local_iter_num 
   temp=new_tour; 
   %随机选取3个节点 
   a=unidrnd(city_num-2); 
   b=unidrnd(city_num-2); 
   while(a==b) 
       b=unidrnd(city_num-2); 
   end 
   c=unidrnd(city_num-2); 
   while(c==a||c==b) 
       c=unidrnd(city_num-2); 
   end 
   %选择起点重新排列路径 
   d=sort([a b c]); 
   a=d(1);a1=temp(a);a2=temp(a+1); 
   b=d(2);b1=temp(b);b2=temp(b+1); 
   c=d(3);c1=temp(c);c2=temp(c+1); 
   temp=[temp(find(temp==a1):city_num) temp(1:find(temp==a1))]; 
   %change the old edges with new edges 
   if dist(b1,c1)+dist(b2,c2)<dist(b1,b2)+dist(c1,c2) 
       index1=find(temp==b2);index2=find(temp==c1); 
       new_tour=opt_2(temp,index1,index2); 
   elseif dist(a1,c1)+dist(a2,c2)<dist(a1,a2)+dist(c1,c2) 
       temp=[temp(find(temp==b1):city_num) temp(1:find(temp==b1))]; 
       index1=find(temp==c2);index2=find(temp==a1); 
       new_tour=opt_2(temp,index1,index2); 
   elseif dist(a1,b1)+dist(a2,b2)<dist(a1,a2)+dist(b1,b2) 
       temp=[temp(find(temp==c1):city_num) temp(1:find(temp==c1))]; 
       index1=find(temp==a2);index2=find(temp==b1); 
       new_tour=opt_2(temp,index1,index2); 
   elseif dist(a1,b2)+dist(c1,a2)+dist(b1,c2)...... 
           <dist(a1,a2)+dist(b1,b2)+dist(c1,c2) 
       temp(a+1)=b2;temp(c+1)=a2;temp(b+1)=c2; 
       new_tour=temp; 
   elseif dist(a1,b1)+dist(a2,c1)+dist(b2,c2)...... 
           <dist(a1,a2)+dist(b1,b2)+dist(c1,c2) 
       index1=find(temp==a2);index2=find(temp==b1);index3=find(temp==c1); 
       new_tour=opt_3(temp,index1,index2,index3); 
   elseif dist(a1,b2)+dist(c1,b1)+dist(a2,c2)...... 
           <dist(a1,a2)+dist(b1,b2)+dist(c1,c2) 
       temp=[temp(find(temp==b1):city_num) temp(1:find(temp==b1))]; 
       index1=find(temp==b2);index2=find(temp==c1);index3=find(temp==a1); 
       new_tour=opt_3(temp,index1,index2,index3); 
   elseif dist(a1,c1)+dist(b1,c2)+dist(a2,b2)...... 
           <dist(a1,a2)+dist(b1,b2)+dist(c1,c2) 
       temp=[temp(find(temp==c1):city_num) temp(1:find(temp==c1))]; 
       index1=find(temp==c2);index2=find(temp==a1);index3=find(temp==b1); 
       new_tour=opt_3(temp,index1,index2,index3); 
   end 
end