tspga.m

Traveeling sales man problem solved using genetic algorithm in matlab

close all;
clear all;
city_location = [1     2 
                 3     2 
                 6     2
                 5     2 
                 7     2
                 4     2 
                 6     2];
%                  9     3.5
%                  11.5  3.2
%                  13.3  3
%                  3.5   5
%                  9     5.5
%                  15    4.5
%                  6.5   6
%                  10.3  6.3
%                  12    7
%                  13.5  6.4
%                  2     8.2
%                  5.5   9
%                  9     9
%                  15.5  9.2
%                  2.5   12
%                  5.5   13
%                  8     12.5
%                  14    12 ];
                                                                      
n = size(city_location,1);
a = meshgrid(1:n);
dmat = reshape(sqrt(sum((city_location(a,:)-city_location(a',:)).^2,2)),n,n); %To Calculate Distance bet cities

pop_size = 100;
num_iter = 1e3;
pop_size = 4*ceil(pop_size/4);

% Initialize the Population
population = zeros(pop_size,n);
for k = 1:pop_size
    population(k,:) = randperm(n);
end

% Run the GA
tmp_pop = zeros(4,n);
new_pop = zeros(pop_size,n);
global_min = Inf;
total_dist = zeros(1,pop_size);
dist_history = zeros(1,num_iter);
for iter = 1:num_iter
    % Calculate Total Distance
    for p = 1:pop_size
        d = dmat(population(p,n),population(p,1)); 
        for k = 2:n
            d = d + dmat(population(p,k-1),population(p,k));
        end
        total_dist(p) = d;
    end

    % Find the Best Route in the Population
    [min_dist,index] = min(total_dist);
    if min_dist < global_min
        global_min = min_dist;
        optimum_route = population(index,:);
    end
    
    % Genetic Algorithm Operators
    rand_pair = randperm(pop_size);
    for p = 4:4:pop_size
        rtes = population(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
    population = new_pop;
end

    % Plots the GA Results
    figure();
    subplot(2,1,1);
    plot(city_location(:,1),city_location(:,2),'k.');
    title('City Locations');
    subplot(2,1,2);
    route = [optimum_route optimum_route(1)];
    plot(city_location(route,1),city_location(route,2),'r.-');
    title(sprintf('Total Distance = %1.4f, Iteration = %d',min_dist,iter))