【路径规划-TSP问题】基于遗传算法求解多起点多TSP问题附matlab代码

✅作者简介：热爱科研的Matlab仿真开发者，修心和技术同步精进，matlab项目合作可私信。

🍎个人主页：Matlab科研工作室

🍊个人信条：格物致知。

更多Matlab仿真内容点击👇

智能优化算法  神经网络预测 雷达通信  无线传感器

信号处理 图像处理 路径规划 元胞自动机 无人机  电力系统

⛄ 内容介绍

遗传算法(Genetic Algorithm,简称GA)是一种通过模拟自然进化过程来搜索最优解的启发式搜索算法.由于该算法具有内在的隐并行性,良好的全局寻优能力和较强的鲁棒性,所以被广泛用于求解复杂的组合优化问题,比如旅行商问题(Traveling salesman problem,TSP)和多旅行商问题(Multiple Traveling Salesman Problem,MTSP).TSP是经典的NP-hard组合优化问题,而MTSP是TSP的一种推广,相比TSP,MTSP具有更多的实际应用,但是研究成果却相对较少.

⛄ 部分代码

% 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 or costs

%     MINTOUR (scalar integer) is the minimum tour length for any of the salesmen

%     POPSIZE (scalar integer) is the size of the population (should be divisible by 4)

%     NUMITER (scalar integer) is the number of desired iterations for the algorithm to run

%     SHOWPROG (scalar logical) shows the GA progress if true

%     SHOWRESULT (scalar logical) shows the GA results if true

%

% Output:

%     OPTROUTE (integer array) is the best route found by the algorithm

%     OPTBREAK (integer array) is the list of route break points (these specify the indices

%         into the route used to obtain the individual salesman routes)

%     MINDIST (scalar float) is the total distance traveled by the salesmen

%

% Route/Breakpoint Details:

%     If there are 10 cities and 3 salesmen, a possible route/break

%     combination might be: rte = [5 6 9 1 4 2 8 10 3 7], brks = [3 7]

%     Taken together, these represent the solution [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

%

% Example:

%     n = 35;

%     xy = 10*rand(n,2);

%     minTour = 3;

%     popSize = 40;

%     numIter = 5e3;

%     a = meshgrid(1:n);

%     dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);

%     [optRoute,optBreak,minDist] = mtspv_ga(xy,dmat,minTour,popSize,numIter,1,1);

%

% Example:

%     n = 50;

%     phi = (sqrt(5)-1)/2;

%     theta = 2*pi*phi*(0:n-1);

%     rho = (1:n).^phi;

%     [x,y] = pol2cart(theta(:),rho(:));

%     xy = 10*([x y]-min([x;y]))/(max([x;y])-min([x;y]));

%     minTour = 3;

%     popSize = 40;

%     numIter = 1e4;

%     a = meshgrid(1:n);

%     dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);

%     [optRoute,optBreak,minDist] = mtspv_ga(xy,dmat,minTour,popSize,numIter,1,1);

%

% Example:

%     n = 35;

%     xyz = 10*rand(n,3);

%     minTour = 3;

%     popSize = 40;

%     numIter = 5e3;

%     a = meshgrid(1:n);

%     dmat = reshape(sqrt(sum((xyz(a,:)-xyz(a',:)).^2,2)),n,n);

%     [optRoute,optBreak,minDist] = mtspv_ga(xyz,dmat,minTour,popSize,numIter,1,1);

%

% See also: mtsp_ga, mtspf_ga, mtspo_ga, mtspof_ga, mtspofs_ga, distmat

function varargout = mtspv_ga(xy,dmat,minTour,popSize,numIter,showProg,showResult)

% Process Inputs and Initialize Defaults

nargs = 7;

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

            minTour = 3;

        case 3

            popSize = 80;

        case 4

            numIter = 5e3;

        case 5

            showProg = 1;

        case 6

            showResult = 1;

        otherwise

    end

end

⛄ 运行结果

⛄ 参考文献

[1]温清芳. 遗传算法求解TSP问题的MATLAB实现[J]. 韶关学院学报, 2007, 28(6):5.

❤️ 关注我领取海量matlab电子书和数学建模资料

❤️部分理论引用网络文献，若有侵权联系博主删除