1701007780
popSize = 60; %种群的大小,一般被4整除 numIter = 1e4; %算法迭代的次数 showProg = 1; %如果满足条件,执行遗传算法的步骤 showResult = 1; %如果满足条件,执行遗传算法的结果 a = meshgrid(1
:n); dmat = reshape(sqrt(sum((xy(a,
:)-xy(a’,:)).^2,2)),n,n); %城市之间的距离/成本 [optRoute,minDist] = tsp_ga(xy,dmat,popSize,numIter,showProg, showResult); %%Output
: %optRoute 遗传算法得出的最优路径 %minDist 最优路径下的成本值或距离值 %% figure, imshow(im); %显示图形 for i=1
:n hold on plot(xy(
:,1),xy(:,2),‘r.’,‘Markersize’,20); %绘制图形 text(xy(i,1),xy(i,2)+0.08,num2str(i)); %标记文本 end for i=1
:n-1 plot([xy(optRoute(1,i),1),xy(optRoute(1,i+1),1)],[xy(optRoute (1,i),2),xy(optRoute(1,i+1),2)],‘r-‘,‘linewidth’,2) hold on %图像保持句柄 end for i=n plot([xy(optRoute(1,i),1),xy(optRoute(1,1),1)],[xy(optRoute (1,i),2),xy(optRoute(1,1),2)],‘r-‘,‘linewidth’,2) hold on %图像保持句柄 end
1701007781
1701007782
采用遗传算法的旅行商问题求解程序如下:
1701007783
1701007784
function varargout = tsp_ga(xy,dmat,popSize,numIter,showProg,showResult) %Process Inputs and Initialize Defaults nargs = 6; for k = nargin
:nargs-1 switch k case 0 xy = 10*rand(50,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 popSize = 100; case 3 numIter = 1e4; case 4 showProg = 1; case 5 showResult = 1; otherwise end end %Verify Inputs [N,dims] = size(xy); [nr,nc] = size(dmat); if N ~= nr || N ~= nc error(‘Invalid XY or DMAT inputs!’) end n = N; %Sanity Checks popSize = 4*ceil(popSize/4); numIter = max(1,round(real(numIter(1)))); %求取最大值 showProg = logical(showProg(1)); showResult = logical(showResult(1)); %Initialize the Population 初始化种群 pop = zeros(popSize,n); pop(1,
:) = (1
:n); for k = 2
:popSize pop(k,
:) = randperm(n); end %Run the GA globalMin = Inf; totalDist = zeros(1,popSize); distHistory = zeros(1,numIter); tmpPop = zeros(4,n); newPop = zeros(popSize,n); if showProg pfig = figure(‘Name’,‘TSP_GA | Current Best Solution’,‘Numbertitle’,‘off’); end for iter = 1
:numIter %迭代次数 %Evaluate Each Population Member (Calculate Total Distance) for p = 1
:popSize d = dmat(pop(p,n),pop(p,1)); %Closed Path 选择算子 for k = 2
:n d = d + dmat(pop(p,k-1),pop(p,k)); %交叉算子、变异算子 end totalDist(p) = d; %计算适应度 end %找到最小和最大适应度的染色体及它们在种群中的位置 %Find the Best Route in the Population [minDist,index] = min(totalDist); distHistory(iter) = minDist; %代替上一次进化中最好的染色体 if minDist < globalMin globalMin = minDist; optRoute = pop(index,
:); if showProg %Plot the Best Route figure(pfig); rte = optRoute([1
:n 1]); if dims > 2, plot3(xy(rte,1),xy(rte,2),xy(rte,3),‘r.-‘); else plot(xy(rte,1),xy(rte,2),‘r.-‘); end title(sprintf(‘Total Distance = %1.4f, Iteration = %d’,minDist,iter)); end end %Genetic Algorithm Operators randomOrder = randperm(popSize); for p = 4
:4:popSize rtes = pop(randomOrder(p-3
:p),:); dists = totalDist(randomOrder(p-3
:p)); [ignore,idx] = min(dists); %
#ok bestOf4Route = rtes(idx,
:); routeInsertionPoints = sort(ceil(n*rand(1,2))); I = routeInsertionPoints(1); J = routeInsertionPoints(2); for k = 1
:4 %Mutate the Best to get Three New Routes tmpPop(k,
:) = bestOf4Route; switch k case 2 %倒置 tmpPop(k,I
:J) = tmpPop(k,J
:-1:I); case 3 %交换位置 tmpPop(k,[I J]) = tmpPop(k,[J I]); case 4 %后一刻的值替换当前值 tmpPop(k,I
:J) = tmpPop(k,[I+1
:J I]); otherwise %不做任何操作 end end newPop(p-3
:p,:) = tmpPop; end pop = newPop; end %画图 if showResult %绘制 GA算法求解结果 figure(‘Name’,‘TSP_GA | Results’,‘Numbertitle’,‘off’); %subplot(2,2,1); figure(1), pclr = ~get(0,‘DefaultAxesColor’); if dims > 2, plot3(xy(
:,1),xy(:,2),xy(:,3),’.’,‘Color’,pclr); else plot(xy(
:,1),xy(:,2),’.’,‘Color’,pclr); end title(‘城市位置’); grid on % subplot(2,2,2); figure(2), %画图 imagesc(dmat(optRoute,optRoute)); title(‘距离矩阵-imagesc’); % subplot(2,2,3); figure(3), %画图 rte = optRoute([1
:n 1]); if dims > 2, plot3(xy(rte,1),xy(rte,2),xy(rte,3),‘r.-‘) ; else plot(xy(rte,1),xy(rte,2),‘r.-‘); %画图 end title(sprintf(‘最短距离 = %1.4f’,minDist)); grid on % subplot(2,2,4); figure(4), %画图 plot(distHistory,‘b’,‘LineWidth’,2); title(‘最佳适应度曲线’); grid on set(gca,‘XLim’,[0 numIter+1],‘YLim’,[0 1.1*max([1 distHistory])]); end %Return Outputs if nargout varargout{1} = optRoute; varargout{2} = minDist; end
1701007785
1701007786
运行程序得如图6-14所示。
1701007787
1701007788
1701007789
1701007790
1701007791
图6-14 最优路径
1701007792
1701007793
遍布每一个城市,通过程序找到了一条遍历所有城市且每个城市只被访问一次的路径。
1701007794
1701007795
当然,由于城市位置较少,用户可以手动进行计算绘图,然而当城市有50个或者更多时,人眼看都要看花,更何况还是求解最优解,因此智能化程序应用,给我们更大的平台去挖掘事物的本质。
1701007796
1701007797
1701007798
1701007799
1701007801
我和数学有约:趣味数学及算法解析 6.9 运动员如何以最优速度赛跑
1701007802
1701007803
运动员如何以最优速度赛跑,这是一个数学物理模型。
1701007804
1701007805
数学和物理都是历史悠久的自然学科,数学和物理科学作为自然科学的重要分支,不仅对物质文明的进步和人类对自然界认识的深化起了重要的推动作用,而且对人类的思维发展也产生了不可或缺的影响。从亚里士多德时代的自然哲学,到牛顿时代的经典力学,直至现代物理中的相对论和量子力学等,都是物理学家科学素质、科学精神及科学思维的有形体现。
1701007806
1701007807
运用现代数学方法研究体育运动始于20世纪70年代,Keller首先建立了运动员赛跑模型,将其理论用于运动员中长跑训练取得了优异的成绩。同时,美国计算机专家Ails以力学、数学和计算机为工具对铁饼投掷技术进行研究,提出了新的投掷技术与改进后的训练措施,使运动员在很短的时间内取得了辉煌成绩。因此,现代训练技术将有助于运动员快速提高比赛成绩。
1701007808
1701007809
1701007810
1701007811
为了较好的研究运动员如何进行以最优速度赛跑,假设比赛距离为D,运动员所跑时间为T,速度为v(t);比赛时风力w与速度v成正比,比例系数为;赛跑时体内阻力和体外的空气阻力r与速度v(t)成正比,比例系数为;考虑运动员的4个生理参数,最大冲力F、体内外的阻力系数μ、由氧气的新陈代谢作用提供能量的速度ζ和体内储存能量的初始值E0。
1701007812
1701007813
由于大多数田赛都是在室外进行的,考虑人体4个生理参数和风力影响的情况下,建立了全新的最优速度模型和能量消耗模型,并将其应用于实际赛跑。
1701007814
1701007815
由积分学理论知,比赛距离为:
1701007816
1701007817
1701007818
1701007819
1701007820
速度v(t)受运动员的体力和赛跑时阻力的制约,设运动员的冲力为f(t),由Newton第二定律得m·a+r+w=f,即:
1701007821
1701007822
1701007823
1701007824
1701007825
1701007826
1701007827
其中,与分别为适当的阻力系数,a为加速度,m为运动员的质量。
1701007828
1701007829
因为冲力f(t)是由运动员自身控制的,如血液对肌肉的供氧、肌肉的收缩及身体的上下运动等,所以问题可转化为寻找f(t)的最优控制策略,即当T一定时,D达到最大。
[
上一页 ]
[ :1.70100778e+09 ]
[
下一页 ]