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:

2013 2 25
2 个回答
回答已采纳
5 次查看（30 天）

0 个投票

% 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

2 个评论
显示 无 隐藏 无

Walter Roberson
Walter Roberson 2013-2-25
If you describe some of the errors, people could help you debug it.
Sanuj Shukla
Sanuj Shukla 2013-2-25
??? 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);

请先登录，再进行评论。

请先登录，再回答此问题。

 采纳的回答

Walter Roberson
Walter Roberson 2013-2-25

1 个投票

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.

16 个评论
显示 14更早的评论 隐藏 14更早的评论

Walter Roberson
Walter Roberson 2013-2-26
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
Sanuj Shukla 2013-2-26
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
Walter Roberson 2013-2-26
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
Sanuj Shukla 2013-2-26
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);
Sanuj Shukla
Sanuj Shukla 2013-2-26
编辑：Sanuj Shukla 2013-2-26
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
Walter Roberson 2013-2-26
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
Sanuj Shukla 2013-2-26
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
Walter Roberson 2013-2-26
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
Sanuj Shukla 2013-2-26
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
Walter Roberson 2013-2-26
The code you show above does not have a fixed origin of (0,0), and it does distribute the nodes randomly.
Sanuj Shukla
Sanuj Shukla 2013-2-27
编辑：Walter Roberson 2013-2-27
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
Sanuj Shukla 2013-2-27
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
Walter Roberson 2013-2-27
编辑：Walter Roberson 2013-2-27
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
Sanuj Shukla 2013-2-27
I want to generate a random number between 0 and 1. Which function i can use?

请先登录，再进行评论。

更多回答（1 个）

Sanuj Shukla
Sanuj Shukla 2013-2-26
编辑：Sanuj Shukla 2013-2-26

0 个投票

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.

类别

在 帮助中心 和 File Exchange 中查找有关 Nearest Neighbors 的更多信息

产品

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by