Simulated annealing how to solve this error

Dear,

I have a ploblem using Global optimization toolbox with simulannealbnd.

I would be very grateful if anyone knows how to solve it.

the code of my programe is and the matrix of stars is in .txt file:

function prog

clc; close all;

global xc yc zc N

global bestfval_log

% load star positions from 'stars.txt' 

stars = importdata('stars.txt');

N = size(stars.data, 1);

xc = stars.data(:,1); yc = stars.data(:,2); zc = stars.data(:,3); 

names = stars.rowheaders;

plot_stars(xc, yc, zc, names);

bestfval_log = [];

% set up schedule, and plot it

schedule = 1:N;

disp('Initial Schedule:')

disp(schedule);

plot_schedule(schedule);

title(sprintf('Initial Schedule: %s \n Distance = %f light year', ...

      num2str(schedule), cost_function(schedule)))

rotate3d

disp('Initial Total Distance:')

disp(cost_function(schedule));

pause

% set up options and call simulated annealing

rotate3d;

[schedule,fval,exitFlag,output] = ...

      simulannealbnd(@cost_function, schedule, [], []); %#ok<*NASGU>

end

function d = cost_function(schedule)

global xc yc zc N

d = 0;

for i = 1:N-1

      d = d + ( ( xc(schedule(i)) - xc(schedule(i+1)) )^2 ...

          + ( yc(schedule(i)) - yc(schedule(i+1)) )^2 ...

          + ( zc(schedule(i)) - zc(schedule(i+1)) )^2) ^.5 ;

end

i = N;

d = d + ( ( xc(schedule(i)) - xc(schedule(1)) )^2 ...

      + ( yc(schedule(i)) - yc(schedule(1)) )^2 ...

      + ( zc(schedule(i)) - zc(schedule(1)) )^2) ^.5 ;

end

function plot_stars(xc, yc, zc, names)

N = numel(xc);

f = figure('NumberTitle', 'off', ...

      'Name', 'Galactic Traveling Salesman Problem');

ax = axes('Color', [0 0 0]);

hold on;

textargs = {'VerticalAlignment', 'top', ...

      'HorizontalAlignment', 'center', ...

      'FontName', 'Gill Sans MT'};

plot3(xc(1), yc(1), zc(1), 'y*');

text(xc(1), yc(1), zc(1)-.5, names{1}, textargs{:}, 'Color', 'y');

for i = 2:N

      plot3(xc(i), yc(i), zc(i), 'w*');

      text(xc(i), yc(i), zc(i)-.5, names{i}, textargs{:}, 'Color', 'w');

end

view(3); rotate3d;

end

function plot_schedule(schedule)

global xc yc zc

persistent l

if isempty(l) || ~ishghandle(l); l = plot3(0,0,0,'b-'); rotate3d; end

set(l, ...

      'XData', [xc(schedule); xc(schedule(1))], ...

      'YData', [yc(schedule); yc(schedule(1))], ...

      'ZData', [zc(schedule); zc(schedule(1))] );

title(sprintf('Best schedule found so far: %s \n Distance = %f light year', ...

      num2str(schedule), cost_function(schedule)))

end

[Alan Weiss]

What is your question? What is the problem? Please explain, don't just throw up a bunch of uncommented code.

And you would do well to format your code with the {} Code button so that we could read it more easily.

Alan Weiss

MATLAB mathematical toolbox documentation

Answer 1

[Walter Roberson]

Simulated Annealing is going to start with your initial schedule of integral values, and then it is going to take a random point "around" those values and try to evaluate the cost at that point. It is then going to randomly choose whether to accept the new point or not, with a probability that depends on the current Temperature. Then it repeats from the current point. The "temperature" at any one time affects how much random noise to add to the current point. There is also a "temperature schedule" for lowering the temperature.

The question then becomes what these random points to be evaluated at look like. And the answer to that for Simulated Annealing is that the computations are purely done on continuous variables, with non-integral results. Your initial input might be [1 2 3 4] but the very first random location tried might be [.3423 2.141 3 4.17].

Unfortunately in your code you attempt to use these values as array indexes. That is going to fail.

There is no way to restrict S.A. to integers!

Now you could adapt for that by using round() on the values, and by clipping them to the minimum and maximum array index numbers. It might not result in an efficient search, but it would at least not bomb out in the evaluation.

However, Simulated Annealing also assumes that each variable can be altered independently of each other. Even if you get around the continuous vs positive integer problem, S.A. would have no hesitation at all about proposing (for example) [1 2 2 1] to be costed. No attempt at all will be made by S.A. to ensure that the proposed point is a permutation of 1:N.

Now you could attempt to get around that by having your cost function detect that not all of the nodes were being visited, and assigning a Very Big Penalty to such situations. You have to keep in mind, though, that since S.A. does not know that a change in one variable might require a change in another, that very few of the proposed locations will happen to be valid permutations (even after adjusting for integral values.) How bad is it? Well, with only 14 variables, and using the default number of iterations of 3000*(number of variables), the probability would be less than 50% that another permutation would be chosen before the algorithm gave up, even if you restricted the range for the variables to be 1 to 14.

Therefore, you need to redesign your approach. You need to take into account that you are going to be getting floating point values for each coordinate. You need to take into account that S.A. will not make any attempt to keep the coordinates as permutations. And you need to take into account that as the temperature "lowers", that S.A. will be adding less randomness so there has to be a meaningful "nearby" for whatever representation you use.

The meaningful "nearby" rules out strategies such as using a single integral value that represents an index into an ordered list of permutation(see interesting discussions over here) because in such systems, swapping two nodes in the middle of a permutation (a small change that should be considered "nearby") might imply a large change in indexing integer.

The task is not an easy one, so people seldom use simulannealbnd for this purpose, even if they do code the traveling salesman problem as one of Simulated Annealing.