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
