Can anyone suggest me to write a correct and working code for traveling salesman problem using simulated annealing? I got this but there are so many errors:

% Travellingsalesman problem

% Create random city distribution

n=20;

x=random('unif',-1,1,n,1); 

y=random('unif',-1,1,n,1);

gam=1; mu=sign(x);

% End up where you start. Add starting point to end

x=[x' x(1)]'; 

y=[y' y(1)]'; 

mu=[mu' mu(1)]'; figure(1); hold off; g=plot(x,y,'.r'); 

set(g,'MarkerSize',20);

c0=cost(x,y,mu,gam); k=1; % Boltzmanconstant

nt=50; nr=200; % nt: temp steps. nr: city switches each T cp=zeros(nr,nt);

iran=inline('round(random(d,1.5001,n+0.4999))','d','n');

for i=1:nt

T=1.0 -(i-1)/nt

for j=1:nr

% switch two random cities

ic1=iran('unif',n); ic2=iran('unif',n);

xs=x(ic1); ys=y(ic1); ms=mu(ic1);

x(ic1)=x(ic2); y(ic1)=y(ic2); mu(ic1)=mu(ic2);

x(ic2)=xs; y(ic2)=ys; mu(ic2)=ms;

p=random('unif',0,1); c=cost(x,y,mu,gam);

if (c < c0 | p < exp(-(c-c0)/(k*T))) % accept

c0=c;

else % reject and switch back

xs=x(ic1); ys=y(ic1); ms=mu(ic1);

x(ic1)=x(ic2); y(ic1)=y(ic2); mu(ic1)=mu(ic2);

x(ic2)=xs; y(ic2)=ys; mu(ic2)=ms;

end

cp(j,i)=c0;

end

figure(2); plot(reshape(cp,nt*nr,1)); drawnow;

figure(1); hold off; g=plot(x,y,'.r'); set(g,'MarkerSize',20); hold on; 

plot(x,y,'b'); g=plot(x(1),y(1),'.g'); set(g,'MarkerSize',30);

p=plot([0 0],[-1 1],'r--'); set(g,'LineWidth',2); drawnow;

end

[Walter Roberson]

If you describe some of the errors, people could help you debug it.

[Sanuj Shukla]

??? Undefined function or method 'random'

for input arguments of type 'char'.

Error in ==> salesman at 3

n=20; x=random('unif',-1,1,n,1);

y=random('unif',-1,1,n,1);

Answer 1

[Walter Roberson]

That version of a random number routine is part of the Statistics Toolbox; see http://www.mathworks.com/help/stats/random.html

The Statistics Toolbox is optional extra cost for Academic and Professional licenses. It is, though, included in Student Version licenses, but the toolbox might not be installed by default.

[Walter Roberson]

rand() gives uniform random distribution. The first example in the rand() documentation shows how to generate random numbers in a particular range. In particular, (rand() * 2 - 1) generates values in the range -1 to +1

If you have a new enough MATLAB, randi() can be used to generate random integers.

You should probably be using .' (transpose) instead of ' (complex transpose)

The code

x = [x' x(1)]'

is needlessly complex and can be replaced by

x(end+1) = x(1);

Likewise for the other variables.

[Sanuj Shukla]

Yes. It worked. Thank you so much. But error in using 'cost' function:

??? Undefined function or method 'cost' for input arguments of type 'double'.

Error in ==> salesman at 16 c0=cost(x,y,mu,gam); k=1; % Boltzmanconstant

[Walter Roberson]

cost() is not a function in any Mathworks toolbox that I can think of. Perhaps the function was supplied in the same place you got the code.

[Sanuj Shukla]

Thank you so much for your help.

Please help me by fixing these errors:

??? Error using ==> inlineeval at 15 Error in inline expression ==> round(rand(d,1.5001,n+0.4999)) Unknown command option.

Error in ==> inline.subsref at 27 INLINE_OUT_ = inlineeval(INLINE_INPUTS_, INLINE_OBJ_.inputExpr, INLINE_OBJ_.expr);

Error in ==> salesman at 24 ic1=iran('unif',n); ic2=iran('unif',n);

[Walter Roberson]

I suspect the code should be

ic1 = randi([2,n]);
ic2 = randi([2,n]);

[Sanuj Shukla]

Yes. It worked. Thanks a lot.

There is something wrong in 'reshape' function:

To RESHAPE the number of elements must not change.

??? Error using ==> reshape Error in ==> salesman at 41 figure(2); plot(reshape(cp,nt*nr,1)); drawnow;

[Walter Roberson]

reshape() is operating correctly, but something else in your code is causing the sizes to disagree. You can make the code work anyhow by using

plot(cp(:))

[Sanuj Shukla]

I am getting figure1 correctly But it is not giving the same graph in Figure 2 (probably due to using plot(cp(:))) Is there any other way to plot the same by using some other funcion?

[Walter Roberson]

figure 2 is not intended to be the same graph as figure 1. figure 2 looks to be a cost graph, whereas figure 1 looks to be a route graph.

[Sanuj Shukla]

Sir, My program is not giving the optimum path because there is a fixed node at origin (0,0). The first node(green colored) is always connected to node at origin (0,0) and it doesn't change throughout the program execution. How can I change the code so that all nodes are randomly distributed and there is no fixed path between (0,0) and first node.

Please help me.

[Walter Roberson]

The code you show above does not have a fixed origin of (0,0), and it does distribute the nodes randomly.

[Sanuj Shukla]

But every time I run this code there is a fixed node at (o,o) all other nodes are randomly distributed except this one. There is also an fixed path between first node (denoted in green color)and this is causing un-optimized path.

http://picpaste.com/fig1-sXzlavgM.jpg

http://www.facebook.com/photo.php?fbid=130487983796249&set=a.130488030462911.24642.100005051443114&type=1&theater

[Sanuj Shukla]

I have changed the whole code. Problem of fixed node, fixed path is resolved but path for tsp is not optimum. Please help me.

Cost function:

    function [c] = cost(x,y)
n=length(x);
c=0;
for i=1:n-1
c =c+sqrt((x(i+1)-x(i))^2 +(y(i+1)-y(i))^2)
end

Program:

    n=20;
x=rand(1,n); y=rand(1,n);
x(end+1) = x(1);
y(end+1) = y(1);
figure(1);
hold off;
g=plot(x,y,'.r');
set(g,'MarkerSize',20);
c0=cost(x,y);
k=1;
nt=50; nr=200; 
for i=1:nt
T=1.0 -(i-1)/nt
for j=1:nr 
ic1 = randi([2,n]);
ic2 = randi([2,n]);
xs=x(ic1); ys=y(ic1);
x(ic1)=x(ic2); y(ic1)=y(ic2);
x(ic2)=xs; y(ic2)=ys;
p=rand(0,1); 
c=cost(x,y);
if (c < c0 | p < exp(-(c-c0)/(k*T)))
c0=c;
else
xs=x(ic1); ys=y(ic1);
x(ic1)=x(ic2); y(ic1)=y(ic2);
x(ic2)=xs; y(ic2)=ys;
end
cp(j,i)=c0;
end
figure(2); 
plot(cp(:));
drawnow;
figure(1); hold off;
g=plot(x,y,'.r');
set(g,'MarkerSize',20); hold on;
plot(x,y,'b');
g=plot(x(1),y(1),'.g'); 
set(g,'MarkerSize',30);
drawnow;
end

[Walter Roberson]

What is the purpose of your line

p=rand(0,1);

rand(0,1) creates a 0 x 1 matrix of random numbers -- an empty matrix.

[Sanuj Shukla]

I want to generate a random number between 0 and 1. Which function i can use?

[Walter Roberson]

rand()

Answer 2

[Sanuj Shukla]

Instead of using this routine (ie not using uniform distribution or random function) what else can I change in my code to eliminate errors and make code running. However if I use other function instead of 'random' then I get 'error using ==> ctranspose.. Transpose on ND array is not defined' in following lines:

x=[x' x(1)]';

y=[y' y(1)]';

mu=[mu' mu(1)]';

Thanks for your reply. Please help me because i have my presentation in few days.