Solving TSP with Genetic Algorithm

Avatar photoDr.Panda

In this post, as requested by one of our readers, I’m going to show you my Matlab code of Genetic Algorithm for solving travelling salesman problem (or TSP), in which the city locations are shown in a Google map.

This is a simple version because the Google map is fixed and static. If you need more advanced version in which the Google map is live and dynamic, please let me know by leaving a comment below.

Here are the locations of 15 major cities in France.

Let’s see how my Genetic Algorithm solves this TSP:

For more videos like this, check my YouTube channel here.

map.png

Matlab Code

population.m

function Y=population(n,nc)
% nc = number of citiest
% n = pop size
B=zeros(n,nc);
for j=1:n
    A=1:1:nc;   
    [x y]=size(A);
    for i = 1:nc
        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);
    C = B(1,1:r1);
    B(:,1:r1) = [];  % cut
    [x3 y3] = size(B);
    B(1,y3+1:y1) = C;
    Y(z,:) = B;
end
YY = Y;

mutation.m

function YY = 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);
    end
    B=A(1,r1(1));
    A(1,r1(1))=A(1,r1(2));
    A(1,r1(2))=B;
    Y(z,:)=A;
end
YY = Y;
.
.
.
Sorry! This is only a part of the Matlab code.

Notice: It would take you from 1 to 3 hours to re-type the Matlab code yourself; or with just €3.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 €6.99 but today it’s only €3.99 (save €3 today – available for a limited time only)

Download the whole Matlab code here (Membership Code ID: 026)

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!

25 Replies to “Solving TSP with Genetic Algorithm”

      1. I tried to input the codes, but the results different from the videos. The line plot from the MatLab didn’t fit with the map.png. any suggestion?

        Reply

        1. Maybe, you can open the map with Paint on Window and then check and update the locations of the cities. Maybe the map has been distorted a little bit, due to uploading and downloading from my web.

          Reply

  3. location points do not match with the image What should the dimensions of the map.png file be? The dots slide on the picture.

    Reply

  7. Respected Sir
    Thank you for your effort .Can you tell me the type of selection, crossover and mutation that you used in the given problem?

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

Related