Dr.PandaIn this video, I’m going to show you a Matlab code and demonstrate the performance of an Adaptive Restart Genetic Algorithm for solving travelling salesman problems (Solving a Travelling Salesman Problem (TSP) Using Adaptive Restart Genetic Algorithm).
This Genetic Algorithm can automatically restart its search process if it’s getting stuck in local optima. Thereby, the capability of the Genetic Algorithm for finding the global optimal solution is significantly enhanced. Let’s begin.
For more videos like this, check my YouTube channel here.
population.m
function Y=population(n)
% 10 cities (1-10)
B=zeros(n,10);
for j=1:n
A=1:1:10; % list of 10 cities
[x y]=size(A);
for i = 1:10
r = randi(y);
B(j,i)=A(r);
A(:,r) = [];
[x y]=size(A);
end
end
Y=B;
crossover.m
function YY = crossover(X,n)
% X = population
% n = number of chromosomes to be crossed
%..........................................................................
[x1 y1] = size(X);
Y = zeros(n,y1);
for z = 1:n
B = X(randi(x1),:); % select parent chromosome
r1 = 1 + randi(y1-1);
.
.
.
mutation.m
function Y=mutation(X,n)
% X = population
% n = number of chromosomes to be mutated
%..........................................................................
[x1 y1]=size(X);
Y=zeros(n,y1);
for z=1:n
A=X(randi(x1),:); % select parent chromosome
r1=1+randi(y1-1,1,2);
while r1(1)==r1(2)
r1=1+randi(y1-1,1,2);
.
.
.
evaluation.m
function Y = evaluation(P)
% P = population
% Distances between 10 cities
% city 1 2 3 4 5 6 7 8 9 10
D=[ 0 2.7 4.3 1.3 2.4 4.8 4.9 19 22.3 34.4; %city 1
2.7 0 1.9 4 0.9 2.1 3.6 17.5 21 32.9; %city 2
6.3 1.6 0 6.3 2.2 1.7 2.3 19.8 19.7 35.2; %city 3
1.7 4.5 6.1 0 4.1 5.1 6.5 18.2 24.1 33.5; %city 4
2.5 0.9 2.1 4.1 0 3.7 2.7 18.3 20.1 33.6; %city 5
4.8 1.8 1.7 4.8 2.3 0 3.7 18.3 21.1 33.7; %city 6
5 3.4 2.2 6.5 3 3.7 0 20.7 17.8 36.1; %city 7
19.1 17.8 19.8 18.1 18.1 18.3 20.7 0 38.1 21.3; %city 8
22.4 20.8 19.5 24.2 20.4 21 17.8 38.2 0 53.5; %city 9
34.5 33.2 35.2 33.5 33.5 33.7 36.1 21.4 53.5 0] ; %city 10
[x y] = size(P);
C=0;
for j = 1:x
A=P(j,:);
B=0;
.
.
.
selection.m
function [YY1 YY2] = selection(P1,B,p)
% P1 - population
% B - fitness value [1 x n]
% p - population size
%-------------------------------------------------------------------------
[r1 c1]=find(B==max(B));
Y1(1,:)=P1(max(c1),:); % Keep the best first
P1(max(c1),:) = []; % remove
Fn(1,1)=1/B(1,max(c1)); % best fitness value
B(:,max(c1))=[]; % remove
.
.
.
GA.m
clear all
clc
close all
% Population size
p =50;
% Number of pairs of chromosomes required for crossover
c=25;
% Number of chromosomes required for mutation
m=25;
% Total number of generations
tg=1000;
% Adaptive restart condition
s = 30;
figure
title('Blue - Minimum Red - Average');
xlabel('Generation')
ylabel('Total travel distance')
hold on
w=1;
P0=population(1);
while w <= tg
P=population(p-1);
P(p,:)=P0;
for i=1:tg
P(p+1:p+c,:)=crossover(P,c);
P(p+c+1:p+c+m,:)=mutation(P,m);
.
.
.
Sorry! This is only a half of the code.
Notice: It’s possible to watch the video and re-type the Matlab code yourself – that would take you from 1 to 3 hours; or with just €2.99 (the cost of a cup of coffee), you can download/copy the whole Matlab code within 2 minutes. It’s your choice to make.
Original price is €4.99 but today it’s only €2.99 (save €2 today – available for a limited time only)
Download the whole Matlab code here (Membership Code ID: 009)
No need to build the Matlab code from scratch because it’s very time-consuming. My idol, Jim Rohn, once said: “Time is more value than money. You can get more money, but you cannot get more time”. If you think this code can be used in your research/teaching work, you should download it and then customize/modify/apply it to your work, without any obligation of citing the original source if you don’t want. However, redistribution (i.e., downloading the code/script here and then making it available on another site on the Internet) is strictly prohibited.
If you have any question or problem, please contact Dr. Panda by email: learnwithpanda2018@gmail.com
Thank you very much and good luck with your research!
Hello Dr. Panda,
Thanks for providing such a high level information on GA and useful codes. I have a question if you do not mind. What should be changed in the code to consider an open diagram, i mean starting from one city and ending in a different city of starting point. Thanks for your help.
For that, we need to update the objective function.