多旅行商问题遗传算法.pdf
function varargout = mtspf_ga(dmat,salesmen,min_tour,pop_size,num_iter,show_prog,show_res)%dmat 任意两城市间的最短路径矩阵通过 floyed 算法求得结果。%salesmen 旅行商个数%min_tour 每个旅行商最少访问的城市数%pop_size 种群个体数%num_iter迭代的代数%show_prog,show_res 显示的参数设定nargs = 7;%处理输入参数，用来给定一些默认的参数；for k = nargin:nargs-1switch kcase 0dmat = 10*rand(20,20);case 1salesmen = 5;case 2min_tour = 2;case 3pop_size = 80;case 4num_iter = 5e3;case 5show_prog = 1;case 6show_res = 1;otherwiseendend% 检查输入 矩阵nr,nc = size(dmat);if nr = ncerror(Invalid XY or DMAT inputs!)endn = nr - 1; % 除去起始的城市后剩余的城市的数% 输入参数的检查salesmen = max(1,min(n,round(real(salesmen(1);min_tour = max(1,min(floor(n/salesmen),round(real(min_tour(1);pop_size = max(8,8*ceil(pop_size(1)/8);num_iter = max(1,round(real(num_iter(1);show_prog = logical(show_prog(1);show_res = logical(show_res(1);% 初始化路线、断点的选择num_brks = salesmen-1;dof = n - min_tour*salesmen;% 可以自由访问的城市数addto = ones(1,dof+1);for k = 2:num_brksaddto = cumsum(addto);endcum_prob = cumsum(addto)/sum(addto);% 初始化种群pop_rte = zeros(pop_size,n);% 路径集合的种群pop_brk = zeros(pop_size,num_brks);% 断点集合的种群for k = 1:pop_sizepop_rte(k,:) = randperm(n)+1;pop_brk(k,:) = randbreaks();end% 选择绘图时的个商人的颜色可删去；clr = 1 0 0; 0 0 1; 0.67 0 1; 0 1 0; 1 0.5 0;if salesmen 5clr = hsv(salesmen);end% 开始运行遗传算法过程global_min = Inf;%初始化最短路径total_dist = zeros(1,pop_size);dist_history = zeros(1,num_iter);tmp_pop_rte = zeros(8,n);%当前的路径设置tmp_pop_brk = zeros(8,num_brks); %当前的断点设置new_pop_rte = zeros(pop_size,n); %更新的路径设置new_pop_brk = zeros(pop_size,num_brks);%更新的断点设置if show_progpfig = figure(Name,MTSPF_GA | Current Best Solution,Numbertitle,off);endfor iter = 1:num_iter% 评价每一代的种群 适应情况并作出选择。for p = 1:pop_sized = 0;p_rte = pop_rte(p,:);p_brk = pop_brk(p,:);rng = 1 p_brk+1;p_brk n;for s = 1:salesmend = d + dmat(1,p_rte(rng(s,1); % 添加开始的路径for k = rng(s,1):rng(s,2)-1d = d + dmat(p_rte(k),p_rte(k+1);endd = d + dmat(p_rte(rng(s,2),1); % 添加结束的的路径dis(p,s)=d;%d=d+myLength(dmat,p_rte(rng(s,1):rng(s,2);%可调用函数处理endtotal_dist(p) = d;%distan(p)=max(dis(p,:);%计算三个人中的最大值end% 在每代种群中找到最好的路径min_dist,index = min(total_dist);dist_history(iter) = min_dist;%+max(distan);if min_dist global_minglobal_min = min_dist;opt_rte = pop_rte(index,:);%最优的最短路径opt_brk = pop_brk(index,:);%最优的断点设置rng = 1 opt_brk+1;opt_brk n;%设置记录断点的方法end% 遗传算法算子的操作集合rand_grouping = randperm(pop_size);for p = 8:8:pop_sizertes = pop_rte(rand_grouping(p-7:p),:);brks = pop_brk(rand_grouping(p-7:p),:);dists = total_dist(rand_grouping(p-7:p);ignore,idx = min(dists);best_of_8_rte = rtes(idx,:);best_of_8_brk = brks(idx,:);rte_ins_pts = sort(ceil(n*rand(1,2);I = rte_ins_pts(1);J = rte_ins_pts(2);for k = 1:8 % 产生新的方案tmp_pop_rte(k,:) = best_of_8_rte;tmp_pop_brk(k,:) = best_of_8_brk;switch kcase 2 % 倒置操作tmp_pop_rte(k,I:J) = fliplr(tmp_pop_rte(k,I:J);case 3 % 互换操作tmp_pop_rte(k,I J) = tmp_pop_rte(k,J I);case 4 % 滑动平移操作tmp_pop_rte(k,I:J) = tmp_pop_rte(k,I+1:J I);case 5 % 更新断点tmp_pop_brk(k,:) = randbreaks();case 6 % 倒置并更新断点tmp_pop_rte(k,I:J) = fliplr(tmp_pop_rte(k,I:J);tmp_pop_brk(k,:) = randbreaks();case 7 % 互换并更新断点tmp_pop_rte(k,I J) = tmp_pop_rte(k,J I);tmp_pop_brk(k,:) = randbreaks();case 8 % 评议并更新断点tmp_pop_rte(k,I:J) = tmp_pop_rte(k,I+1:J I);tmp_pop_brk(k,:) = randbreaks();otherwise % 不进行操做endendnew_pop_rte(p-7:p,:) = tmp_pop_rte;new_pop_brk(p-7:p,:) = tmp_pop_brk;endpop_rte = new_pop_rte;pop_brk = new_pop_brk;end% 返回结果部分rng = 1 opt_brk+1;opt_brk n;dis_e=zeros(1,salesmen);%设置并计算每个旅行商的最短路径for s = 1:salesmendis_e(s)=myLength(dmat,opt_rte(rng(s,1):rng(s,2);endif nargoutvarargout1 = opt_rte;varargout2 = opt_brk;varargout3 = min_dist;varargout4 = dis_e;end%做出迭代过程的图示plot(dist_history);grid on;xlabel(迭代的代数);ylabel(所走的路径之和);% 随机产生一套断点 的集合function breaks = randbreaks()if min_tour = 1 % 一个旅行商时，没有断点的设置tmp_brks = randperm(n-1);breaks = sort(tmp_brks(1:num_brks);else % 强制断点至少找 到最短的履行长度num_adjust = find(rand cum_prob,1)-1;spaces = ceil(num_brks*rand(1,num_adjust);adjust = zeros(1,num_brks);for kk = 1:num_brksadjust(kk) = sum(spaces = kk);endbreaks = min_tour*(1:num_brks) + cumsum(adjust);endendend
