精华内容
下载资源
问答
  • MATLAB求解TSP问题的一种改进遗传算法
  • 点击蓝字关注我们TSP问题PART 01问题提出图1|坐标分布图 数据中心为某辆充电小车的出发点,坐标1~坐标29为...模型建立TSP求解算法对比蚁群算法求解TSP问题求解结果图2|移动小车充电路线图MTSP问题PART 02问题提出...

    点击蓝字

    关注我们

    TSP

    问题

    PART 01

    问题提出

    8366d281005c96f93ecc76f6aa2e9ca8.png

    图1|坐标分布图

    数据中心为某辆充电小车的出发点,坐标1~坐标29为29个充电点,充电小车需从数据中心出发并且依次经过29个充电点,最后回到数据中心。为使路线总路径最短,需确定充电小车每一步该怎么走,这就是典型的TSP问题。

    模型建立

    053f5c7e59728f5f6964a8fb749e9dac.png

    TSP求解算法对比

    76a721b88c7d4b44ad5fbbbb046212c7.png

    蚁群算法求解TSP问题

    0bf7a71d6f1b9ae6c2b99c7dfdb00830.png

    求解结果

    80d9457b713516d29a1a62ee0e4c3a19.png

    图2|移动小车充电路线图

    MTSP

    问题

    PART 02

    问题提出

            当数据中心含有4辆小车时,4辆小车需要合作完成充电任务,即每辆小车负责一部分充电点的充电,并且使总路程最短,该问题为典型的多旅行社问题,即MTSP问题。

    模型建立

    bbedee02c7ecdd6bfcbee4e877322748.png

    遗传求解MTSP问题

    a191a22b9ee2abc84d36c6577d346a14.png

    求解结果

    0154830af22438d86c4e3f79059c9a0f.png

    图3|多移动小车充电路线图

    MATLAB源代码

    蚁群算法求解TSP问题

    clc;clf;clear;data1 = xlsread('附件1.xlsx');x = data1(:,1);y = data1(:,2);X = data1(:,1:2);[N,n]=size(X);      % N =测试样本数;n =测试样本的属性数;K = 4;              % K = 组数; R = 100;            % R = 蚂蚁数; t_max = 1000;       % t_max =最大迭代次数;                 % 初始化c = 10^-2;tau = ones(N,K) * c;    %信息素矩阵,初始值为0.01的N*K矩阵(样本数*聚类数)q = 0.9;                % 阈值qrho = 0.1;              % 蒸发率best_solution_function_value = inf; % 最佳路径度量值(初值为无穷大,该值越小聚类效果越好)tict = 1% while ((t<=t_max))                             %达到最大迭代次数而终止% while ((best_solution_function_value>=19727))  %达到一定的聚类效果而终止while ((best_solution_function_value>=19727))        %路径标识字符:标识每只蚂蚁的路径    solution_string = zeros(R,N+1);         for i = 1 : R                       %以信息素为依据确定蚂蚁的路径        r = rand(1,N);    %随机产生值为0-1随机数的1*51的数组        for g = 1 : N            if r(g) < q     %如果r(g)小于阈值                tau_max = max(tau(g,:));                Cluster_number = find(tau(g,:)==tau_max);   %聚类标识数,选择信息素最多的路径                solution_string(i,g) = Cluster_number(1);   %确定第i只蚂蚁对第g个样本的路径标识            else            %如果r(g)大于阈值,求出各路径信息素占在总信息素的比例,按概率选择路径                sum_p = sum(tau(g,:));                 p = tau(g,:) / sum_p;                 for u = 2 : K                     p(u) = p(u) + p(u-1);                 end               rr = rand;                          for s = 1 : K                     if (rr <= p(s))                        Cluster_number = s;                       solution_string(i,g) = Cluster_number;                      break;                 end             end        end    end    % 计算聚类中心    weight = zeros(N,K);       for h = 1:N              %给路径做计算标识           Cluster_index = solution_string(i,h); %类的索引编号                     weight(h,Cluster_index) = 1;          %对样本选择的类在weight数组的相应位置标1       end       cluster_center = zeros(K,n);  %聚类中心(聚类数K个中心)       for j = 1:K           for v = 1:n               sum_wx = sum(weight(:,j).*X(:,v));   %各类样本各属性值之和               sum_w = sum(weight(:,j));            %各类样本个数               if sum_w==0                          %该类样本数为0,则该类的聚类中心为0                 cluster_center(j,v) =0                  continue;               else                                 %该类样本数不为0,则聚类中心的值取样本属性值的平均值               cluster_center(j,v) = sum_wx/sum_w;               end            end       end    % 计算各样本点各属性到其对应的聚类中心的均方差之和,该值存入solution_string的最后一位      F = 0;      for j= 1:K          for ii = 1:N              Temp=0;              if solution_string(i,ii)==j;                                  for v = 1:n                      Temp = ((abs(X(ii,v)-cluster_center(j,v))).^2)+Temp;                  end                  Temp = sqrt(Temp);              end            F = (Temp)+F;          end              end       solution_string(i,end) = F;                          end     %根据F值,把solution_string矩阵升序排序    [fitness_ascend,solution_index] = sort(solution_string(:,end),1);    solution_ascend = [solution_string(solution_index,1:end-1) fitness_ascend];   for k=1:R                   if solution_ascend(k,end)<=best_solution_function_value              best_solution = solution_ascend(k,:);          end      k = k+1;      end       % 用最好的L条路径更新信息数矩阵    tau_F = 0;    L=2;    for j = 1:L           tau_F = tau_F + solution_ascend(j,end);    end    for i = 1 : N               tau(i,best_solution(1,i)) = (1 - rho) * tau(i,best_solution(1,i)) + 1/ tau_F;     %1/tau_F和rho/tau_F效果都很好    end     t=t+1     best_solution_function_value =  solution_ascend(1,end)   endtime=toc;clct timecluster_centerbest_solution = solution_ascend(1,1:end-1);IDY=ctranspose(best_solution)best_solution_function_value =  solution_ascend(1,end)%分类结果显示%plot3(cluster_center(:,1),cluster_center(:,2),cluster_center(:,3),'o');grid;boxplot(cluster_center(:,1),cluster_center(:,2),'o');grid;boxtitle('蚁群聚类结果(R=100,t=10000)')xlabel('X')ylabel('Y')zlabel('Z')YY=[1 2 3 4];index1 = find(YY(1) == best_solution)index2 = find(YY(2) == best_solution)index3 = find(YY(3) == best_solution)index4 = find(YY(4) == best_solution)line(X(index1,1),X(index1,2),'linestyle','none','marker','*','color','g');line(X(index2,1),X(index2,2),'linestyle','none','marker','*','color','r');line(X(index3,1),X(index3,2),'linestyle','none','marker','+','color','b');line(X(index4,1),X(index4,2),'linestyle','none','marker','s','color','b');rotate3d%代码参考:CSDN
    9451e15e82666dd1514ba54e35de1664.gif

    遗传算法求解MTSP问题

    function varargout = mtspf_ga(xy,dmat,salesmen,min_tour,pop_size,num_iter,show_prog,show_res)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            salesmen = 5;        case 3            min_tour = 2;        case 4            pop_size = 80;        case 5            num_iter = 5e3;        case 6            show_prog = 1;        case 7            show_res = 1;        otherwise    endend% Verify Inputs[N,dims] = size(xy);[nr,nc] = size(dmat);if N ~= nr || N ~= nc    error('Invalid XY or DMAT inputs!')endn = N - 1; % Separate Start/End City% Sanity Checkssalesmen = 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));% Initializations for Route Break Point Selectionnum_brks = salesmen-1;dof = n - min_tour*salesmen;          % degrees of freedomaddto = ones(1,dof+1);for k = 2:num_brks    addto = cumsum(addto);endcum_prob = cumsum(addto)/sum(addto);% Initialize the Populationspop_rte = zeros(pop_size,n);          % population of routespop_brk = zeros(pop_size,num_brks);   % population of breaksfor k = 1:pop_size    pop_rte(k,:) = randperm(n)+1;    pop_brk(k,:) = randbreaks();end% Select the Colors for the Plotted Routesclr = [1 0 0; 0 0 1; 0.67 0 1; 0 1 0; 1 0.5 0];if salesmen > 5    clr = hsv(salesmen);end% Run the GAglobal_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_prog    pfig = figure('Name','MTSPF_GA | Current Best Solution','Numbertitle','off');endfor iter = 1:num_iter    % Evaluate Members of the Population    for p = 1:pop_size        d = 0;        p_rte = pop_rte(p,:);        p_brk = pop_brk(p,:);        rng = [[1 p_brk+1];[p_brk n]]';        for s = 1:salesmen            d = d + dmat(1,p_rte(rng(s,1))); % Add Start Distance            for k = rng(s,1):rng(s,2)-1                d = d + dmat(p_rte(k),p_rte(k+1));            end            d = d + dmat(p_rte(rng(s,2)),1); % Add End Distance        end        total_dist(p) = d;    end    % Find the Best Route in the Population    [min_dist,index] = min(total_dist);    dist_history(iter) = min_dist;    if min_dist < global_min        global_min = min_dist;        opt_rte = pop_rte(index,:);        opt_brk = pop_brk(index,:);        rng = [[1 opt_brk+1];[opt_brk n]]';        if show_prog            % Plot the Best Route            figure(pfig);            for s = 1:salesmen                rte = [1 opt_rte(rng(s,1):rng(s,2)) 1];                if dims == 3, 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',min_dist,iter));                hold on            end            if dims == 3, plot3(xy(1,1),xy(1,2),xy(1,3),'ko');            else plot(xy(1,1),xy(1,2),'ko'); end                         for i=1:30        text(xy(i,1)+0.0002,xy(i,2),num2str(i)) ; %加上0.01使标号和点不重合,可以调整        end                        hold off        end    end    % Genetic Algorithm Operators    rand_grouping = randperm(pop_size);    for p = 8:8:pop_size        rtes = 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 % Generate New Solutions            tmp_pop_rte(k,:) = best_of_8_rte;            tmp_pop_brk(k,:) = best_of_8_brk;            switch k                case 2 % Flip                    tmp_pop_rte(k,I:J) = fliplr(tmp_pop_rte(k,I:J));                case 3 % Swap                    tmp_pop_rte(k,[I J]) = tmp_pop_rte(k,[J I]);                case 4 % Slide                    tmp_pop_rte(k,I:J) = tmp_pop_rte(k,[I+1:J I]);                case 5 % Modify Breaks                    tmp_pop_brk(k,:) = randbreaks();                case 6 % Flip, Modify Breaks                    tmp_pop_rte(k,I:J) = fliplr(tmp_pop_rte(k,I:J));                    tmp_pop_brk(k,:) = randbreaks();                case 7 % Swap, Modify Breaks                    tmp_pop_rte(k,[I J]) = tmp_pop_rte(k,[J I]);                    tmp_pop_brk(k,:) = randbreaks();                case 8 % Slide, Modify Breaks                    tmp_pop_rte(k,I:J) = tmp_pop_rte(k,[I+1:J I]);                    tmp_pop_brk(k,:) = randbreaks();                otherwise % Do Nothing            end        end        new_pop_rte(p-7:p,:) = tmp_pop_rte;        new_pop_brk(p-7:p,:) = tmp_pop_brk;    end    pop_rte = new_pop_rte;    pop_brk = new_pop_brk;endif show_res    % Plots    figure('Name','MTSPF_GA | Results','Numbertitle','off');    subplot(2,2,1);    if dims == 3, plot3(xy(:,1),xy(:,2),xy(:,3),'k.');    else plot(xy(:,1),xy(:,2),'k.'); end                for i=1:30        text(xy(i,1)+0.0002,xy(i,2),num2str(i)) ; %加上0.01使标号和点不重合,可以调整        end                title('Locations');    subplot(2,2,2);    imagesc(dmat([1 opt_rte],[1 opt_rte]));    title('Distance Matrix');    subplot(2,2,3);    rng = [[1 opt_brk+1];[opt_brk n]]';    for s = 1:salesmen        rte = [1 opt_rte(rng(s,1):rng(s,2)) 1];        if dims == 3, 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',min_dist));        hold on;    end    if dims == 3, plot3(xy(1,1),xy(1,2),xy(1,3),'ko');    else plot(xy(1,1),xy(1,2),'ko'); end        for i=1:30    text(xy(i,1)+0.0002,xy(i,2),num2str(i)) ; %加上0.01使标号和点不重合,可以调整    end        subplot(2,2,4);    plot(dist_history,'b','LineWidth',2);    title('Best Solution History');    set(gca,'XLim',[0 num_iter+1],'YLim',[0 1.1*max([1 dist_history])]);end% Return Outputsif nargout    varargout{1} = opt_rte;    varargout{2} = opt_brk;    varargout{3} = min_dist;end    % Generate Random Set of Break Points    function breaks = randbreaks()        if min_tour == 1 % No Constraints on Breaks            tmp_brks = randperm(n-1);            breaks = sort(tmp_brks(1:num_brks));        else % Force Breaks to be at Least the Minimum Tour Length            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_brks                adjust(kk) = sum(spaces == kk);            end            breaks = min_tour*(1:num_brks) + cumsum(adjust);        end    endend%代码参考:CSDN
    9451e15e82666dd1514ba54e35de1664.gif

    [1]汤雅连,杨期江.求解旅行商问题的蚁群优化算法参数设计[J].东莞理工学院学报,2020,27(03):48-54.

    [2]宋志飞. 基于蚁群算法的TSP问题研究[D].江西理工大学,2013.

    [3]束东来. 基于遗传算法的多旅行商问题的优化[D].安庆师范大学,2018.

    [4]CSDN,蚁群算法求解TSP问题,遗传算法求解MTSP问题

    参考文献                                          

    521ae5e85a6ac53798a2e8814d350c05.png

    学习笔记

    微信号|我的头发可没乱

    新浪微博|我的头发可没乱

    展开全文
  • MATLAB求解TSP问题

    2009-07-11 11:39:41
    内有求解此NP问题的丰富算法,珍藏版呀,数模竞赛必备的参考资料。
  • 代码有详细注释。实现了三种解决方案,针对固定数据集和随机数据集
  • matlab 人工鱼群求解TSP

    2020-01-28 01:50:17
    matlab 人工鱼群求解TSP matlab 人工鱼群求解TSP matlab 人工鱼群求解TSP matlab 人工鱼群求解TSP
  • matlab蚁群算法求解TSP

    2014-02-25 22:20:47
    matlab蚁群算法求解TSP,人工智能的课程作业,可直接运行,相互学习。
  • matlab禁忌搜索算法求解tsp问题用matlab模拟禁忌搜索算法,TSP问题为假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标...
  • MATLAB源码集锦-蚁群算法求解TSP问题matlab代码
  • 遗传算法求解TSP(旅行商)问题 MATLAB代码
  • 通过禁忌搜索算法求解经典的TSP问题(MATLAB源代码),TSP问题为假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是...
  • matlab人工免疫算法求解TSP问题

    热门讨论 2010-12-21 10:13:47
    基于matlab编写的人工免疫算法求解TSP问题,AIS.m为程序的主入口
  • sa求解tsp问题MATLAB代码,可运行
  • 7.4 2-opt全邻域搜索求解TSP思路及Matlab实现 4 7.5 禁忌搜索算法求解TSP思路及Matlab实现 8 7.5.1 禁忌搜索算法简介 8 7.5.2 禁忌搜索算法基本思想 9 7.5.3 禁忌搜索基本流程 9 7.5.4 禁忌搜索算法基本构成 10 ...
  • MATLAB源码集锦-人工鱼群求解TSP问题源代码
  • MATLAB 蚁群算法 求解 50个城市的TSP 旅行商问题的 详细代码
  • 遗传算法求解TSP问题,例子是15个点的,单点变异方式,奇数和偶数交叉的方法,选择方法采用轮盘赌的方式
  • MATLAB源码集锦-混合粒子群算法求解TSP问题代码
  • 这是一个求解TSP的遗传算法Matlab m文件
  • 蚁群算法求解TSP matlab

    2021-04-01 15:02:44
    蚁群算法求解TSP clear; clc; close all; Ant_Num=50; Alpha=1; %信息素权重 Beta=5; %启发式因子权重 Rho=0.1; %信息素消失系数 G=200; %迭代次数 Q=100;%信息素增加强度系数 City_Num=20; %城市数量 border=100; %...

    蚁群算法求解TSP

    clear; clc; close all;
    Ant_Num=50;
    Alpha=1; %信息素权重
    Beta=5; %启发式因子权重
    Rho=0.1; %信息素消失系数
    G=200; %迭代次数
    Q=100;%信息素增加强度系数
    City_Num=20; %城市数量
    border=100; %城市边界
    City=[rand(City_Num,1)*border,rand(City_Num,1)*border]; %随机城市坐标
    % City=[9.442061706065957e+01     5.554527461175734e+01
    %      7.033585927645424e+01     8.210485000479132e+01
    %      8.513885160801584e+01     2.875386430880210e+01
    %      7.639317665257967e+01     9.899454527886692e+01
    %      4.124371269556116e+01     3.075543952877445e+01
    %      5.845739036088576e+01     6.394249385784040e+01
    %      2.047038459263265e+01     3.416955672791446e+01
    %      9.556319529767441e+01     5.075386755815181e+01
    %      6.864343351256032e+01     9.524654717191730e+01
    %      9.348728571015130e+01     4.280562205659413e+01
    %      3.436836073417421e+01     7.104795575132123e+01
    %      9.817321649623470e+01     2.501489907029606e+01
    %      7.820931971241255e+01     7.332155697803887e+01
    %      8.988323696914080e+01     4.302811953719409e+01
    %      3.575739586131570e+01     9.099463432988888e+01
    %      8.563041161898965e+00     4.548622350697822e+01
    %      6.563114202893138e+01     2.278268090861504e+01
    %      9.477447526974635e+01     9.126965924351660e+01
    %      4.261772603974462e+01     2.400688433476272e+01
    %      4.447512148263895e+01     6.468043451289284e+01];
    %   %%
     
    D=zeros(City_Num);
    for i=1:City_Num
        for j=1:City_Num
            if i~=j
            D(i,j)=sqrt((City(i,1)-City(j,1))^2+(City(i,2)-City(j,2))^2);
            else
             D(i,j)=eps;   
        end
        end
    end
    
    Eta=1./D;                   %启发因子,即越长走的可能性越小
    Tau=ones(City_Num); %信息素矩阵
    Tabu=zeros(Ant_Num,City_Num); %记录路径
    gen=1;                                            %迭代次数
    Best_Record=zeros(G,City_Num);  %每代最优路径
    Length_Record=inf.*ones(G,1);      %每代最短距离
    
    figure(1);
    
    while gen<=G
        Randpos=[];
        for i=1:(ceil(Ant_Num/City_Num))  %每个城市平均放多少蚂蚁
            Randpos=[Randpos,randperm(City_Num)];  %每一堆蚂蚁随机放到城市
        end
        Tabu(:,1)=Randpos(1,1:Ant_Num)';
        
        for j=2:City_Num
            for i=1:Ant_Num
                visited=Tabu(i,1:(j-1)); %当前蚂蚁已经访问过的城市
                J=zeros(1,(City_Num-j+1)); %未访问过的城市
                P=J;
                Jc=1;
                for k=1:City_Num
                    if length(find(visited==k))==0 %将没有访问过的城市加入
                        J(Jc)=k;
                        Jc=Jc+1;
                    end
                end
                
                for k=1:length(J)
                    P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);
                end
                Pcum=cumsum(P/sum(P));%赌轮盘操作
                select=find(Pcum>=rand);%当前蚂蚁选择的下一个城市
                to_visit=J(select(1));
                Tabu(i,j)=to_visit;
            end
        end
        if gen>=2
            Tabu(1,:)=Best_Record(gen-1,:); %留下上一轮的最短路径
        end
        
        L=zeros(Ant_Num,1); %根据路径计算每只蚂蚁的走过距离
        for i=1:Ant_Num
            R=Tabu(i,:);
            for j=1:(City_Num-1)
                L(i)=L(i)+D(R(j),R(j+1));
            end
                L(i)=L(i)+D(R(1),R(City_Num));
        end
        
        Length_Record(gen)=min(L);    %最短路径的距离
        pos=find(L==min(L));
        Best_Record(gen,:)=Tabu(pos(1),:);%最短路径
        
        Delta_Tau=zeros(City_Num);  %以下更新信息素增量
        for i=1:Ant_Num
            for j=1:City_Num-1
                Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);
            end
                Delta_Tau(Tabu(i,City_Num),Tabu(i,1))= Delta_Tau(Tabu(i,City_Num),Tabu(i,1))+Q/L(i);
        end
        Tau=(1-Rho).*Tau+Delta_Tau;        %信息素更新
        
        Tabu=zeros(Ant_Num,City_Num);  %路径清空
        
        %以下为画图部分
        for i=1:City_Num-1
            plot([City(Best_Record(gen,i),1),City(Best_Record(gen,i+1),1)],...
                [City(Best_Record(gen,i),2),City(Best_Record(gen,i+1),2)],'bo-');
            hold on;
        end
        plot([City(Best_Record(gen,1),1),City(Best_Record(gen,City_Num),1)],...
                [City(Best_Record(gen,1),2),City(Best_Record(gen,City_Num),2)],'ro-');
         title(['优化最短距离:',num2str(Length_Record(gen))]);
         hold off;
         pause(0.005);
         gen=gen+1;
         
    end
    
    Pos=find(Length_Record==min(Length_Record));
    Shortest_Route=Best_Record(Pos(1),:);
    Shortest_Length=min(Length_Record);
    figure(2);
    plot(Length_Record);
    xlabel('迭代次数');
    
        
        
    
    展开全文
  • TSP问题是指假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的...本文使用蚁群算法求解TSP问题(matlab代码)
  • 改进遗传算法求解TSP问题的Matlab程序设计
  • 遗传算法求解tsp问题的matlab代码
  • 以遗传算法求解旅行商问题 (TSP) 为例 , 提出一种改进的交叉和变异算子 , 深入讨论了各个遗传算子的程序实 现 , 并给出其算子的 MATLAB 程序编码 , 最后用 5 个城市的非对称 TSP 进行仿真分析 . 结果表明 , 改进的...
  • GA求解旅行商问题的matlab代码,分别有同一终点、不同终点、返回起点、不返回起点的情况,有意愿者可采纳
  • Matlab 遗传算法求解TSP问题

    千次阅读 2013-03-17 23:43:55
    function varargout = tsp_ga(xy,dmat,pop_size,num_iter,show_prog,show_res) %TSP_GA Traveling Salesman Problem (TSP) Genetic Algorithm (GA) % Finds a (near) optimal solution to the TSP by setting up a
    function varargout = tsp_ga(xy,dmat,pop_size,num_iter,show_prog,show_res)
    %TSP_GA Traveling Salesman Problem (TSP) Genetic Algorithm (GA)
    %   Finds a (near) optimal solution to the TSP by setting up a GA to search
    %   for the shortest route (least distance for the salesman to travel to
    %   each city exactly once and return to the starting city)
    %
    % Summary:
    %     1. A single salesman travels to each of the cities and completes the
    %        route by returning to the city he started from
    %     2. Each city is visited by the salesman exactly once
    %
    % Input:
    %     XY (float) is an Nx2 matrix of city locations, where N is the number of cities
    %     DMAT (float) is an NxN matrix of point to point distances/costs
    %     POP_SIZE (scalar integer) is the size of the population (should be divisible by 4)
    %     NUM_ITER (scalar integer) is the number of desired iterations for the algorithm to run
    %     SHOW_PROG (scalar logical) shows the GA progress if true
    %     SHOW_RES (scalar logical) shows the GA results if true
    %
    % Output:
    %     OPT_RTE (integer array) is the best route found by the algorithm
    %     MIN_DIST (scalar float) is the cost of the best route
    %
    % 2D Example:
    %     n = 50;
    %     xy = 10*rand(n,2);
    %     pop_size = 60;
    %     num_iter = 1e4;
    %     show_prog = 1;
    %     show_res = 1;
    %     a = meshgrid(1:n);
    %     dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);
    %     [opt_rte,min_dist] = tsp_ga(xy,dmat,pop_size,num_iter,show_prog,show_res);
    %
    % 3D Example:
    %     n = 50;
    %     xyz = 10*rand(n,3);
    %     pop_size = 60;
    %     num_iter = 1e4;
    %     show_prog = 1;
    %     show_res = 1;
    %     a = meshgrid(1:n);
    %     dmat = reshape(sqrt(sum((xyz(a,:)-xyz(a',:)).^2,2)),n,n);
    %     [opt_rte,min_dist] = tsp_ga(xyz,dmat,pop_size,num_iter,show_prog,show_res);
    %
    % See also: mtsp_ga, tsp_nn, tspo_ga, tspof_ga, tspofs_ga, distmat
    %
    % Author: Joseph Kirk
    % Email: jdkirk630@gmail.com
    % Release: 2.2
    % Release Date: 6/2/09
    % 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
                pop_size = 100;
            case 3
                num_iter = 1e4;
            case 4
                show_prog = 1;
            case 5
                show_res = 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
    pop_size = 4*ceil(pop_size/4);
    num_iter = max(1,round(real(num_iter(1))));
    show_prog = logical(show_prog(1));
    show_res = logical(show_res(1));
    % Initialize the Population
    pop = zeros(pop_size,n);
    for k = 1:pop_size
        pop(k,:) = randperm(n);
    end
    % Run the GA
    global_min = Inf;
    total_dist = zeros(1,pop_size);
    dist_history = zeros(1,num_iter);
    tmp_pop = zeros(4,n);
    new_pop = zeros(pop_size,n);
    if show_prog
        pfig = figure('Name','TSP_GA | Current Best Solution','Numbertitle','off');
    end
    for iter = 1:num_iter
        % Evaluate Each Population Member (Calculate Total Distance)
        for p = 1:pop_size
            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
            total_dist(p) = d;
        end
        % Find the Best Route in the Population
        [min_dist,index] = min(total_dist);
        dist_history(iter) = min_dist;
        if min_dist < global_min
            global_min = min_dist;
            opt_rte = pop(index,:);
            if show_prog
                % Plot the Best Route
                figure(pfig);
                rte = opt_rte([1:n 1]);
                if dims == 3, 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',min_dist,iter));
            end
        end
        % Genetic Algorithm Operators
        rand_pair = randperm(pop_size);
        for p = 4:4:pop_size
            rtes = pop(rand_pair(p-3:p),:);
            dists = total_dist(rand_pair(p-3:p));
            [ignore,idx] = min(dists);
            best_of_4_rte = rtes(idx,:);
            ins_pts = sort(ceil(n*rand(1,2)));
            I = ins_pts(1);
            J = ins_pts(2);
            for k = 1:4 % Mutate the Best to get Three New Routes
                tmp_pop(k,:) = best_of_4_rte;
                switch k
                    case 2 % Flip
                        tmp_pop(k,I:J) = fliplr(tmp_pop(k,I:J));
                    case 3 % Swap
                        tmp_pop(k,[I J]) = tmp_pop(k,[J I]);
                    case 4 % Slide
                        tmp_pop(k,I:J) = tmp_pop(k,[I+1:J I]);
                    otherwise % Do Nothing
                end
            end
            new_pop(p-3:p,:) = tmp_pop;
        end
        pop = new_pop;
    end
    if show_res
        % Plots the GA Results
        figure('Name','TSP_GA | Results','Numbertitle','off');
        subplot(2,2,1);
        if dims == 3, plot3(xy(:,1),xy(:,2),xy(:,3),'k.');
        else plot(xy(:,1),xy(:,2),'k.'); end
        title('City Locations');
        subplot(2,2,2);
        imagesc(dmat(opt_rte,opt_rte));
        title('Distance Matrix');
        subplot(2,2,3);
        rte = opt_rte([1:n 1]);
        if dims == 3, 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',min_dist));
        subplot(2,2,4);
        plot(dist_history,'b','LineWidth',2);
        title('Best Solution History');
        set(gca,'XLim',[0 num_iter+1],'YLim',[0 1.1*max([1 dist_history])]);
    end
    % Return Outputs
    if nargout
        varargout{1} = opt_rte;
        varargout{2} = min_dist;
    end
    来自:http://www.mathworks.com/matlabcentral/fileexchange/13680-traveling-salesman-problem-genetic-algorithm
    展开全文
  • TSP问题是指假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值...(matlab代码)
  • 求解经典TSP问题的蚁群算法MATLAB程序实现 旅行商问题(Traveling Saleman Problem,TSP)是车辆路径调度问题(VRP)的特例,由于数学家已证明TSP问题是NP难题,因此,VRP也属于NP难题。旅行商问题(TSP)又译为旅行推销...
  • 在一片水域中,鱼往往能自行或尾随其他鱼找到营养物质多的地方,因而鱼生存数目最多的地方一般就是本水域中营养物质最多的地方,人工鱼群算法就是根据这一特点,通过构造人工鱼来模仿鱼群的觅食、聚群及追尾行为,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 387
精华内容 154
关键字:

matlab求解tsp

matlab 订阅