1701007763

1701007764

1701007765 图6-12　旅行节点标记

1701007766

1701007767 为了清晰地表示各城市之间的位置关系，采用欧式距离矩阵进行显示，如图6-13所示。

1701007768

1701007769

1701007770

1701007771

1701007772 图6-13　各城市之间的距离图

1701007773

1701007774 由图6-13可知，不同城市之间的距离是不同的，城市1距离城市6、城市7、城市8较远。图中颜色越深，表示相距越远。

1701007775

1701007776 一个旅行者如何游遍整个湖北省各城市使得路径最短呢，这是一个优化问题，笔者采用遗传算法进行求解分析，遗传算法基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。

1701007777

1701007778 具体的MATLAB程序如下：

1701007779

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

1701007800 我和数学有约：趣味数学及算法解析 [:1701004228]

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

[ 上一页 ]  [ :1.701007763e+09 ]  [ 下一页 ]