MTSP遗传算法解决
原标题:MTSP遗传算法解决
原文来自:CSDN 原文链接:https://blog.csdn.net/weixin_42141390/article/details/103640085
每个遗传个体维护两个基因片段,一个是路径片段,一个时中断点片段
什么是路径和中断点呢?
% 假设有 10 个城市 3 个哥们
% 假设得到路径 rte = [5 6 9 1 4 2 8 10 3 7], 中断点 = [3 7]
% 于是可以得到每个哥们的路径 [5 6 9][1 4 2 8][10 3 7],
% which designates the routes for the 3 salesmen as follows:
% . Salesman 1 travels from city 5 to 6 to 9 and back to 5
% . Salesman 2 travels from city 1 to 4 to 2 to 8 and back to 1
% . Salesman 3 travels from city 10 to 3 to 7 and back to 10
于是,每个旅行商的路径就可以用这两段基因来表示了!
基本算法是这样的,设置5000个迭代次数,每一次迭代产生一个最佳个体,若这厮大于以往的最小值,就作为历史全局最小值。然后从本次迭代中的个体,随机分成n组,从每一组中的最佳个体里修改基因片段(有的改路径基因型,有的改中断点基因型),从而得到子代。然后综合每一组的所有子代作为新生代,新生代的个数必须等于父代,也就是说,每一组的子代个数是固定的。
将上次迭代步骤得到的子代作为本次迭代步骤的父代,挑选最佳个体,若再次小于历史最小值,则再次更新他,直到指定的迭代次数完结为止。
下面是一段代码,别人写的,我写了注释:
%基因型设置: %每个遗传个体维护两个基因片段,一个是路径片段,一个时中断点片段 % Summary: % 1. 每个salesmen的起点随意,并返回其所在起点 % 2. 每一个城市只能有同一个家伙遍历 % % Input: % XY %城市坐标 N by 2 矩阵(用于画图) % DMAT %距离矩阵 N by N % NSALESMEN 有多少个salesmen % MINTOUR 每一个salesmen必须 travel 大于等 MINTOUR 个城市 % POPSIZE 每一次迭代的种群个数,必须为8的倍数,因为新生代的产生是由 8 个 % 老家伙产生 8 个新家伙 % NUMITER 迭代次数,这个代码是将这些次数都迭代完的。 % SHOWPROG 画图,如果等于1,就将每一次迭代路径画出来 % SHOWRESULT 画图,如果等于1,将最后的结果,城市坐标,路径和历史总长度 % % Output: % OPTROUTE (integer array) 输出最佳路径 % OPTBREAK (integer array) 输出中断点 % MINDIST (scalar float) 总距离 % % % Author: Joseph Kirk % Email: jdkirk630@gmail.com % Release: 1.5 % Release Date: 11/07/11 % Translator: ze bin zhuo function varargout = mtsp_ga(xy,dmat,nSalesmen,minTour,popSize,numIter,showProg,showResult) nargs = 8; % 下面是默认值处理,也就是说,如果函数中缺乏输入参数,那么下面的代码就自作主张帮你添了。 for k = nargin:nargs-1 switch k case 0 xy = 10*rand(40,2); case 1 N = size(xy,1); a = meshgrid(1:N); dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),N,N); case 2 nSalesmen = 5; case 3 minTour = 3; case 4 popSize = 80; case 5 numIter = 5e3; case 6 showProg = 1; case 7 showResult = 1; otherwise end end % Verify Inputs 验证输入是否可行,验证原理为城市个数 N 是否和 距离矩阵的 size相等 [N,dims] = size(xy); [nr,nc] = size(dmat); if N ~= nr || N ~= nc error('Invalid XY or DMAT inputs!') end n = N; % Sanity Checks 验证输入:可以不看 nSalesmen = max(1,min(n,round(real(nSalesmen(1))))); %验证输入的哥们个数是不是大于1,并且是整数,否则帮你四舍五入改了 minTour = max(1,min(floor(n/nSalesmen),round(real(minTour(1))))); %验证输入的minTour是不是大于1,并且是整数,否则帮你四舍五入改了 popSize = max(8,8*ceil(popSize(1)/8)); %验证输入的个体数是否为8的整数,否则帮你用ceil函数改了 numIter = max(1,round(real(numIter(1)))); %验证输入的迭代次数是否大于1,否则帮改了 showProg = logical(showProg(1)); %验证是否为1或0,下同 showResult = logical(showResult(1)); % Initializations for Route Break Point Selection nBreaks = nSalesmen-1; %设置中断点个数。 dof = n - minTour*nSalesmen; % degrees of freedom addto = ones(1,dof+1); for k = 2:nBreaks addto = cumsum(addto); end cumProb = cumsum(addto)/sum(addto); % Initialize the Populations popRoute = zeros(popSize,n); % population of routes popBreak = zeros(popSize,nBreaks); % population of breaks popRoute(1,:) = (1:n); popBreak(1,:) = rand_breaks(); for k = 2:popSize popRoute(k,:) = randperm(n); popBreak(k,:) = rand_breaks(); end %画图时,将每一个哥们走的路用不用颜色标出来。 pclr = ~get(0,'DefaultAxesColor'); clr = [1 0 0; 0 0 1; 0.67 0 1; 0 1 0; 1 0.5 0]; if nSalesmen > 5 clr = hsv(nSalesmen); end % 开始GA算法啦 globalMin = Inf; totalDist = zeros(1,popSize); %初始化总距离,是一个行向量,每一个个体对一应一个总距离 distHistory = zeros(1,numIter); %历史距离,用于比较最好的距离,每一次迭代,都产生一 %最好距离作为历史距离存起来。 tmpPopRoute = zeros(8,n); %暂时变量,用完就丢。用于产生新个体的,(路径的基因型) tmpPopBreak = zeros(8,nBreaks); %同上,用于产生新的中断点的基因型 newPopRoute = zeros(popSize,n); %新生代的路径基因型 newPopBreak = zeros(popSize,nBreaks); %新生代的断点基因型 if showProg pfig = figure('Name','MTSP_GA | Current Best Solution','Numbertitle','off'); end %画图:初始点 for iter = 1:numIter % Evaluate Members of the Population for p = 1:popSize %遍历所有的个体 d = 0; pRoute = popRoute(p,:); %将相应的个体的路径基因型取出 pBreak = popBreak(p,:); %将相应的个体的中断点基因型取出 rng = [[1 pBreak+1];[pBreak n]]'; %计算每个哥们的距离之用 %下面的迭代用于计算每个个体的对应的所有哥们的总距离 for s = 1:nSalesmen d = d + dmat(pRoute(rng(s,2)),pRoute(rng(s,1))); for k = rng(s,1):rng(s,2)-1 d = d + dmat(pRoute(k),pRoute(k+1)); end end %把每个个体对应的所有哥们的总距离放在向量totalDist中 totalDist(p) = d; end % 找出总距离最短的那个个体用于产生新个体 [minDist,index] = min(totalDist); %记录每一步迭代的最短距离到一个向量中 distHistory(iter) = minDist; %从历史距离中找出最小的那个作为globalMin if minDist < globalMin %若本次迭代时的最佳距离小于历史globalMin %就把他画在图上,并记录一共画了几次。 globalMin = minDist; optRoute = popRoute(index,:); optBreak = popBreak(index,:); rng = [[1 optBreak+1];[optBreak n]]'; %画图代码 if showProg figure(pfig); for s = 1:nSalesmen rte = optRoute([rng(s,1):rng(s,2) rng(s,1)]); if dims > 2, plot3(xy(rte,1),xy(rte,2),xy(rte,3),'.-','Color',clr(s,:)); else plot(xy(rte,1),xy(rte,2),'.-','Color',clr(s,:)); end title(sprintf('Total Distance = %1.4f, Iteration = %d',minDist,iter)); hold on end hold off end end % 子代个体的产生过程 % 产生一个随机序列,用于挑选随机的8个父代产生子代 % 8个家伙来交配产生子代,(其实也不算交配啦!) randomOrder = randperm(popSize); for p = 8:8:popSize rtes = popRoute(randomOrder(p-7:p),:); brks = popBreak(randomOrder(p-7:p),:); %随机挑选的8个父代 dists = totalDist(randomOrder(p-7:p)); [ignore,idx] = min(dists); %从这8个父代中挑选出最佳父代,用于产生8个子代。 bestOf8Route = rtes(idx,:); bestOf8Break = brks(idx,:); routeInsertionPoints = sort(ceil(n*rand(1,2))); %从中挑选出基因序列的2个位置 %这两个位置用来从父代中产生新的基因新的 I = routeInsertionPoints(1); J = routeInsertionPoints(2); for k = 1:8 % Generate New Solutions tmpPopRoute(k,:) = bestOf8Route; tmpPopBreak(k,:) = bestOf8Break; switch k case 2 % Flip %将最佳父代的基因型从上面两个位置中间的片段反转,产生一个子代。 tmpPopRoute(k,I:J) = tmpPopRoute(k,J:-1:I); case 3 % Swap %交换这两个片段的基因,产生新子代。 tmpPopRoute(k,[I J]) = tmpPopRoute(k,[J I]); case 4 % Slide % 自己看吧,描述不出 tmpPopRoute(k,I:J) = tmpPopRoute(k,[I+1:J I]); %上面都是调整路径基因型的 %下面用于调整中断点基因型,过程差不多,大家可以自己看的 case 5 % Modify Breaks %随机产生,跟最佳父代没关系的一代。 tmpPopBreak(k,:) = rand_breaks(); case 6 % Flip, Modify Breaks tmpPopRoute(k,I:J) = tmpPopRoute(k,J:-1:I); tmpPopBreak(k,:) = rand_breaks(); case 7 % Swap, Modify Breaks tmpPopRoute(k,[I J]) = tmpPopRoute(k,[J I]); tmpPopBreak(k,:) = rand_breaks(); case 8 % Slide, Modify Breaks tmpPopRoute(k,I:J) = tmpPopRoute(k,[I+1:J I]); tmpPopBreak(k,:) = rand_breaks(); otherwise % Do Nothing end end newPopRoute(p-7:p,:) = tmpPopRoute; newPopBreak(p-7:p,:) = tmpPopBreak; end popRoute = newPopRoute; popBreak = newPopBreak; end if showResult % Plots figure('Name','MTSP_GA | Results','Numbertitle','off'); subplot(2,2,1); if dims > 2, plot3(xy(:,1),xy(:,2),xy(:,3),'.','Color',pclr); else plot(xy(:,1),xy(:,2),'.','Color',pclr); end title('City Locations'); subplot(2,2,2); imagesc(dmat(optRoute,optRoute)); title('Distance Matrix'); subplot(2,2,3); rng = [[1 optBreak+1];[optBreak n]]'; for s = 1:nSalesmen rte = optRoute([rng(s,1):rng(s,2) rng(s,1)]); if dims > 2, plot3(xy(rte,1),xy(rte,2),xy(rte,3),'.-','Color',clr(s,:)); else plot(xy(rte,1),xy(rte,2),'.-','Color',clr(s,:)); end title(sprintf('Total Distance = %1.4f',minDist)); hold on; end subplot(2,2,4); plot(distHistory,'b','LineWidth',2); title('Best Solution History'); set(gca,'XLim',[0 numIter+1],'YLim',[0 1.1*max([1 distHistory])]); end % Return Outputs if nargout varargout{1} = optRoute; varargout{2} = optBreak; varargout{3} = minDist; end % 改函数用于随机的产生中断点。 function breaks = rand_breaks() if minTour == 1 % No Constraints on Breaks tmpBreaks = randperm(n-1); breaks = sort(tmpBreaks(1:nBreaks)); else % Force Breaks to be at Least the Minimum Tour Length nAdjust = find(rand < cumProb,1)-1; spaces = ceil(nBreaks*rand(1,nAdjust)); adjust = zeros(1,nBreaks); for kk = 1:nBreaks adjust(kk) = sum(spaces == kk); end breaks = minTour*(1:nBreaks) + cumsum(adjust); end end end
demo在这里呢
n = 35; xy = 10*rand(n,2); nSalesmen = 5; minTour = 3; popSize = 80; numIter = 5e3; a = meshgrid(1:n); dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n); [optRoute,optBreak,minDist] = mtsp_ga(xy,dmat,nSalesmen,minTour,popSize,numIter,1,1);
运行结果这里呢
免责声明:本文来自互联网新闻客户端自媒体,不代表本网的观点和立场。
合作及投稿邮箱:E-mail:editor@tusaishared.com
热门资源
Python 爬虫(二)...
所谓爬虫就是模拟客户端发送网络请求,获取网络响...
TensorFlow从1到2...
原文第四篇中,我们介绍了官方的入门案例MNIST,功...
TensorFlow从1到2...
“回归”这个词,既是Regression算法的名称,也代表...
TensorFlow2.0(10...
前面的博客中我们说过,在加载数据和预处理数据时...
机器学习中的熵、...
熵 (entropy) 这一词最初来源于热力学。1948年,克...
智能在线
400-630-6780
聆听.建议反馈
E-mail: support@tusaishared.com