Travelling Salesperson Problem using Genetic Algorithm in MATLAB

tsp.m

clc;
clear all;
close all;
%===========================================
number_of_cities=10;
area_size=10;
population_size=500;
number_of_generation=1000;
probability_of_mutation=0.08;
%===========================================
randomly_distribute_cities=importdata('tsp1.txt');%area_size*rand(2,number_of_cities);
distance_matrix=zeros(number_of_cities,number_of_cities);
%===========================================
%DISTANCE/COST MATRIX EVALUATION
%===========================================
for i=1:number_of_cities-1
    r1=randomly_distribute_cities(:,i);
    for j=i+1:number_of_cities
        r2=randomly_distribute_cities(:,j);
        dr=r1-r2;
        dr2=dr'*dr;
        drl=sqrt(dr2);
        distance_matrix(i,j)=drl;
        distance_matrix(j,i)=drl;
    end
end
%===========================================
% START FROM RANDOM CLOSED PATHES
% Chromosome(k,:) :- CHROMOSOME OF k-PATH
%===========================================
Chromosome=zeros(population_size,number_of_cities);
for k=1:population_size
    %for i=1:population_size
    Chromosome(k,:)=randperm(number_of_cities);%
    %Chromosome = importdata('tsp.txt');
    %display(Chromosome);
    %end
end
%===========================================
figure('units','centimeters','position',[5 2 30 15]);
subplot(1,2,1);
%===========================================
% TO PLOT BEST PATH
%===========================================
plot_of_line_btwn_2_cities=plot(NaN,NaN,'blue--');
%plot_of_line_btwn_cities=plot(NaN,NaN,'blue--');
Head_Title=title(' ');
hold on;
%===========================================
% PLOT NODES NUMBERS
%===========================================
for n=1:number_of_cities
    text(randomly_distribute_cities(1,n),randomly_distribute_cities(2,n),num2str(n),'color','black');
    plot(randomly_distribute_cities(1,n),randomly_distribute_cities(2,n),'rs','MarkerEdgeColor','green','MarkerFaceColor','red','MarkerSize',4);
end
axis equal;
xlim([-0.1*area_size 1.1*area_size]);
ylim([-0.1*area_size 1.1*area_size]);
%===========================================
path_lengths=zeros(population_size,1);
avg=zeros(number_of_generation,1);
g=zeros(number_of_generation,1);
probabilities=zeros(population_size,1);
%===========================================
% GENERATIONS LOOP
%===========================================
subplot(1,2,2);
for generation=1:number_of_generation
    g(generation,1)=generation;
    path=0;
    %-------------------------------------------
    % FIND PATHS LENGTH
    %-------------------------------------------
    for k=1:population_size
     
        individual_Chromosome=Chromosome(k,:);
        path_length_summation=0;
        for p=1:number_of_cities-1
            path_length_summation=path_length_summation+distance_matrix(individual_Chromosome(p),individual_Chromosome(p+1));
        end
        %-------------------------------------------
        % LAST AND FAST
        %-------------------------------------------
        path_length_summation=path_length_summation+distance_matrix(individual_Chromosome(number_of_cities),individual_Chromosome(1));
        path_lengths(k)=path_length_summation;
        path=path + path_length_summation;
        avg(generation,1)=path/population_size;  
    end
    %set(plot_of_line_btwn_cities,'Xdata',generation,'YData',avg);
    plot(g,avg,'r*');
 
    %-------------------------------------------
    % FIND THE PROBABILITY OF EACH CHROMOSOME
    %-------------------------------------------
    inverse_path_lengths=1./path_lengths;
    probabilities=inverse_path_lengths/sum(inverse_path_lengths);
    %-------------------------------------------
    % FIND BEST PATH
    %-------------------------------------------
    [x y]=max(probabilities);
    best_path=Chromosome(y,:);
 
    %-------------------------------------------
    % UPDATE BEST PATH ON FIGURE
    %-------------------------------------------
    if mod(generation,5)==0
        set(plot_of_line_btwn_2_cities,'Xdata',[randomly_distribute_cities(1,best_path) randomly_distribute_cities(1,best_path(1))],'YData',[randomly_distribute_cities(2,best_path) randomly_distribute_cities(2,best_path(1))]);
        set(Head_Title,'string',['Generation: ' num2str(generation)  '  Best Path Length: ' num2str(path_lengths(y))]);
        drawnow;
    end
    %-------------------------------------------
    % SELECTION
    %-------------------------------------------
    index=roulette_wheel(population_size,probabilities);
    %-------------------------------------------
    % CHROMOSOME'S TO CROSSOVER
    %-------------------------------------------
    Chromosome_Crossover=Chromosome(index,:);
    Chromosome_Children=zeros(population_size,number_of_cities);
    for prc=1:(population_size/2)
        i1=1+2*(prc-1);
        i2=2+2*(prc-1);
        Chromosome1=Chromosome_Crossover(i1,:);
        Chromosome2=Chromosome_Crossover(i2,:);
        Crossover_Point=ceil((number_of_cities-1)*rand);
        % TWO CHILDREN'S
        Chromosome1_Children=PMX(Chromosome1,Chromosome2,Crossover_Point);
        Chromosome2_Children=PMX(Chromosome2,Chromosome1,Crossover_Point);
        Chromosome_Children(i1,:)=Chromosome1_Children;
        Chromosome_Children(i2,:)=Chromosome2_Children;
    end
    Chromosome=Chromosome_Children;
 
    %-------------------------------------------
    % MUTATION(Interchanging)
    %-------------------------------------------
    for k=1:population_size
        if rand<probability_of_mutation
            % Expected probability of a mutation of one individual is no.of cities * probability_of_mutation)
            i=ceil(number_of_cities*rand);
            j=ceil(number_of_cities*rand);
            Chromosome(k,i:j)=fliplr(Chromosome(k,i:j));
        end
    end
    Chromosome(1,:)=best_path; % elitism    
end
display(best_path);

roulette_wheel.m


function index=roulette_wheel(population_size,probabilities)

cummulative_sum_of_probabilities=cumsum(probabilities);
n=length(probabilities);
sz=size(cummulative_sum_of_probabilities);
if sz(1)>sz(2)
    cpr1=cummulative_sum_of_probabilities';
else
    cpr1=cummulative_sum_of_probabilities;
end
%===========================================
% RANDOM NUMBERS FROM 1:n ACCORDING PROBABILITIES
%===========================================
index1=interp1([0 cpr1],1:(n+1),rand(1,population_size),'linear');
index=floor(index1);

PMX.m


function Chromosome_Children=PMX(Chromosome1,Chromosome2,Crossover_Point)

for i=1:Crossover_Point
    if Chromosome2(i)~=Chromosome1(i)
        ind=find(Chromosome1==Chromosome2(i));
        %swap
        Chromosome1(ind)=Chromosome1(i);
        Chromosome1(i)=Chromosome2(i);
    end
end
Chromosome_Children=Chromosome1;

tsp1.txt


1 2 3 4 5 6 7 8 9 10
10 9 2 3 1 4 5 6 7 8