MATLAB多旅行商问题源代码

MATLAB多旅行商问题源代码 functionvarargout = mtspf_ga(xy,dmat,salesmen,min_tour,pop_size,num_iter,show_prog,show_res) % MTSPF_GA Fixed Multiple Traveling Salesmen Problem (M-TSP) Genetic algorithm (GA) %  Finds a (near) optimal solution to a variation of the M-TSP by setting %  up a GA to search for the shortest route (least distance needed for %  each salesman to travel from the start location to individual cities %  and back to the original starting place) % % Summary: %    1. Each salesman starts at the first point, and ends at the first %        point, but travels to a unique set of cities in between %    2. Except for the first, each city is visited by exactly one salesman % % Note: The Fixed Start/End location is taken to be the first XY point % % Input: %    XY (float) is an Nx2 matrix of city locations, where N is the number of cities %    DMAT (float) is an NxN matrix of city-to-city distances or costs %    SALESMEN (scalar integer) is the number of salesmen to visit the cities %    min_TOUR (scalar integer) is the minimum tour length for any of the %        salesmen, NOT including the start/end point %    POP_SIZE (scalar integer) is the size of the population (should be divisible by 8) %    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 %    OPT_BRK (integer array) is the list of route break points (these specify the indices %        into the route used to obtain the individual salesman routes) %    min_DIST (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 4 2 8 10 3 7], brks = [3 7] %    Taken together, these represent the solution [1 5 6 9 1][1 4 2 8 1][1 10 3 7 1], %    which designates the routes for the 3 salesmen as follows: %        . Salesman 1 travels from city 1 to 5 to 6 to 9 and back to 1 %        . Salesman 2 travels from city 1 to 4 to 2 to 8 and back to 1 %        . Salesman 3 travels from city 1 to 10 to 3 to 7 and back to 1 % % 2D Example: %    n = 35; %    xy = 10*rand(n,2); %    salesmen = 5; %    min_tour = 3; %    pop_size = 80; %    num_iter = 5e3; %    a = meshgrid(1:n); %    dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n); %    [opt_rte,opt_brk,min_dist] = mtspf_ga(xy,dmat,salesmen,min_tour, ... %        pop_size,num_iter,1,1); % % 3D Example: %    n = 35; %    xyz = 10*rand(n,3); %    salesmen = 5; %    min_tour = 3; %    pop_size = 80; %    num_iter = 5e3; %    a = meshgrid(1:n); %    dmat = reshape(sqrt(sum((xyz(a,:)-xyz(a',:)).^2,2)),n,n); %    [opt_rte,opt_brk,min_dist] = mtspf_ga(xyz,dmat,salesmen,min_tour, ... %        pop_size,num_iter,1,1); % % See also: mtsp_ga, mtspo_ga, mtspof_ga, mtspofs_ga, mtspv_ga, distmat % % Author: Joseph Kirk % Email: jdkirk630@gmail.com % Release: 1.3 % Release Date: 6/2/09 % Process Inputs and Initialize Defaults 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 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 - 1; % Separate Start/End City % Sanity Checks salesmen = 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 Selection num_brks = salesmen-1; dof = n - min_tour*salesmen;          % degrees of freedom addto = ones(1,dof+1); for k = 2:num_brks addto = cumsum(addto); end cum_prob = cumsum(addto)/sum(addto); % Initialize the Populations