How to change my matlab code. Is has no error in its present form.

Hi, I want to make a change in the following code. It has been run successfully.

Before starting a loop, this line is written

''currentTour = randperm(n); % Random initial solution''

I need that the algorithm will run on all possible tours and give all possible outputs, except of taking a random tour.

Please note that when we run the current code, every time we obtain equal value (76) of best distance, but different best tours as output.

(Actually the distance matrix represents a network, where the nodes indicates cities. I want to find best possible tour started from each city one by one.)

% Example distance matrix (replace it with your own)
distanceMatrix = [
    0  10  11  20;
   10   0  90 25;
   11  90   0  30;
   20  25  30   0
];
% Set algorithm parameters
maxIterations = 1000;
tabuSize = 10;

% Run Tabu Search
[bestTour, bestDistance] = tabuSearchTSP(distanceMatrix, maxIterations, tabuSize);

% Display the best tour and its distance
disp('Best Tour:');

Best Tour:

disp(bestTour);

     3     1     2     4

disp('Best Distance:');

Best Distance:

disp(bestDistance);

    76

function [bestTour, bestDistance] = tabuSearchTSP(distanceMatrix, maxIterations, tabuSize)
    % Initialize variables
    n = size(distanceMatrix, 1); % Number of cities
    tabuList = zeros(n, tabuSize); % Tabu list to store recently visited solutions
    currentTour = randperm(n); % Random initial solution
    bestTour = currentTour;
    bestDistance = calculateTourDistance(currentTour, distanceMatrix);
    iteration = 1;
    
    while iteration <= maxIterations
        candidateList = generateCandidateList(currentTour, tabuList);
        [bestCandidate, bestCandidateDistance] = evaluateCandidates(candidateList, distanceMatrix);
        if bestCandidateDistance < bestDistance
            bestTour = bestCandidate;
            bestDistance = bestCandidateDistance;
        end
        currentTour = bestCandidate;
        tabuList = updateTabuList(tabuList, currentTour);
        iteration = iteration + 1;
    end
end

function distance = calculateTourDistance(tour, distanceMatrix)
    n = length(tour);
    distance = 0;
    for i = 1:n-1
        distance = distance + distanceMatrix(tour(i), tour(i+1));
    end
    distance = distance + distanceMatrix(tour(n), tour(1)); % Return to the starting city
end

function candidateList = generateCandidateList(currentTour, tabuList)
    candidateList = [];
    n = length(currentTour);
    for i = 1:n-1
        for j = i+1:n
            candidate = currentTour;
            candidate(i) = currentTour(j);
            candidate(j) = currentTour(i);
            if ~isTabu(candidate, tabuList)
                candidateList = [candidateList; candidate];
            end
        end
    end
end

function isTabu = isTabu(candidate, tabuList)
    [n, tabuSize] = size(tabuList);
    isTabu = false;
    for i = 1:tabuSize
        if isequal(candidate, tabuList(:, i))
            isTabu = true;
            break;
        end
    end
end

function [bestCandidate, bestCandidateDistance] = evaluateCandidates(candidateList, distanceMatrix)
    numCandidates = size(candidateList, 1);
    bestCandidateDistance = Inf;
    for i = 1:numCandidates
        candidate = candidateList(i, :);
        candidateDistance = calculateTourDistance(candidate, distanceMatrix);
        if candidateDistance < bestCandidateDistance
            bestCandidate = candidate;
            bestCandidateDistance = candidateDistance;
        end
    end
end

function tabuList = updateTabuList(tabuList, candidate)
    [~, tabuSize] = size(tabuList);
    tabuList = [candidate' tabuList(:, 1:tabuSize-1)];
end

Answer 1

[Sahaj]

Hi Amna Habib.

You can replace the line 'currentTour = randperm(n)' with a loop that iterates over each city as the starting point.

% Example distance matrix (replace it with your own)
distanceMatrix = [
    0  10  11  20;
    10   0  90  25;
    11  90   0  30;
    20  25  30   0
    ];
% Set algorithm parameters
maxIterations = 1000;
tabuSize = 10;

n = size(distanceMatrix, 1); % Number of cities

% Initialize variables for the best tour and distance
bestTour = [];
bestDistance = Inf;

% Iterate over each city as the starting point
for startingCity = 1:n
    currentTour = startingCity:n;
    currentTour = [currentTour, 1:startingCity-1];
    
    % Run Tabu Search
    [tour, distance] = tabuSearchTSP(distanceMatrix, maxIterations, tabuSize, currentTour);
    
    % Update the best tour and distance if necessary
    if distance < bestDistance
        bestTour = tour;
        bestDistance = distance;
    end
end

% Display the best tour and its distance
disp('Best Tour:');
disp(bestTour);
disp('Best Distance:');
disp(bestDistance);

function [bestTour, bestDistance] = tabuSearchTSP(distanceMatrix, maxIterations, tabuSize, currentTour)
% Initialize variables
n = size(distanceMatrix, 1); % Number of cities
tabuList = zeros(n, tabuSize); % Tabu list to store recently visited solutions
bestTour = currentTour;
bestDistance = calculateTourDistance(currentTour, distanceMatrix);
iteration = 1;

while iteration <= maxIterations
    candidateList = generateCandidateList(currentTour, tabuList);
    [bestCandidate, bestCandidateDistance] = evaluateCandidates(candidateList, distanceMatrix);
    if bestCandidateDistance < bestDistance
        bestTour = bestCandidate;
        bestDistance = bestCandidateDistance;
    end
    currentTour = bestCandidate;
    tabuList = updateTabuList(tabuList, currentTour);
    iteration = iteration + 1;
end
end

% The remaining functions remain the same

Hope this helps.

[Edit - formatted the code as code so it can be copied easily]

[Amna Habib]

% Example distance matrix (replace it with your own)
distanceMatrix = [
    0  10  11  20;
   10   0  90  25;
   11  90   0  30;
   20  25  30   0
];
% Set algorithm parameters
maxIterations = 1000;
tabuSize = 10;
n = size(distanceMatrix, 1); % Number of cities
% Initialize variables for the best tour and distance
bestTour = [];
bestDistance = Inf;
% Iterate over each city as the starting point
for startingCity = 1:n
    currentTour = startingCity:n;
    currentTour = [currentTour, 1:startingCity-1];
    % Run Tabu Search
    [tour, distance] = tabuSearchTSP(distanceMatrix, maxIterations, tabuSize, currentTour);
    % Update the best tour and distance if necessary
    if distance < bestDistance
        bestTour = tour;
        bestDistance = distance;
    end
end
% Display the best tour and its distance
disp('Best Tour:');

Best Tour:

disp(bestTour);

     2     1     3     4

disp('Best Distance:');

Best Distance:

disp(bestDistance);

    76

function [bestTour, bestDistance] = tabuSearchTSP(distanceMatrix, maxIterations, tabuSize, currentTour)
    % Initialize variables
    n = size(distanceMatrix, 1); % Number of cities
    tabuList = zeros(n, tabuSize); % Tabu list to store recently visited solutions
    bestTour = currentTour;
    bestDistance = calculateTourDistance(currentTour, distanceMatrix);
    iteration = 1;
    while iteration <= maxIterations
        candidateList = generateCandidateList(currentTour, tabuList);
        [bestCandidate, bestCandidateDistance] = evaluateCandidates(candidateList, distanceMatrix);
        if bestCandidateDistance < bestDistance
            bestTour = bestCandidate;
            bestDistance = bestCandidateDistance;
        end
        currentTour = bestCandidate;
        tabuList = updateTabuList(tabuList, currentTour);
        iteration = iteration + 1;
    end
end
function distance = calculateTourDistance(tour, distanceMatrix)
    n = length(tour);
    distance = 0;
    for i = 1:n-1
        distance = distance + distanceMatrix(tour(i), tour(i+1));
    end
    distance = distance + distanceMatrix(tour(n), tour(1)); % Return to the starting city
end
function candidateList = generateCandidateList(currentTour, tabuList)
    candidateList = [];
    n = length(currentTour);
    for i = 1:n-1
        for j = i+1:n
            candidate = currentTour;
            candidate(i) = currentTour(j);
            candidate(j) = currentTour(i);
            if ~isTabu(candidate, tabuList)
                candidateList = [candidateList; candidate];
            end
        end
    end
end
function isTabu = isTabu(candidate, tabuList)
    [n, tabuSize] = size(tabuList);
    isTabu = false;
    for i = 1:tabuSize
        if isequal(candidate, tabuList(:, i))
            isTabu = true;
            break;
        end
    end
end
function [bestCandidate, bestCandidateDistance] = evaluateCandidates(candidateList, distanceMatrix)
    numCandidates = size(candidateList, 1);
    bestCandidateDistance = Inf;
    for i = 1:numCandidates
        candidate = candidateList(i, :);
        candidateDistance = calculateTourDistance(candidate, distanceMatrix);
        if candidateDistance < bestCandidateDistance
            bestCandidate = candidate;
            bestCandidateDistance = candidateDistance;
        end
    end
end
function tabuList = updateTabuList(tabuList, candidate)
    [~, tabuSize] = size(tabuList);
    tabuList = [candidate' tabuList(:, 1:tabuSize-1)];
end

@Sahaj I have run according to your suggestion, the answer is unique but still it does not provide the result iterates over each city as the starting point.

[Image Analyst]

@Amna Habib Is it working or not??? We're guessing you got it figured out because you accepted the answer but you just didn't update your comment. If that's not correct, then unaccept the answer and let us know it's still not working.

[dpb]

for startingCity = 1:n
    currentTour = startingCity:n;
    currentTour = [currentTour, 1:startingCity-1];
    ...

I dunno how the search logic works to constrain the search (if it it does at all; one would really presume it just uses the initial guess as a starting point but doesn't constrain the result of the shortest distance necessarily to only paths from the first location, but is a global search. (I just looked at the candidate search; looks to me like that is, indeed, what it does; it swaps first and susequent positions right of the bat to generate alternate paths to try so it will probably get the same answer every time, regardless.)

It would it seems require modifying that logic to prevent it; I don't have the time right now to go any further in depth.

Or, if n isn't too large, then the exhaustive search will do it for certain; simply look for the minimum distance result by the starting location; that's an easy use of a grouping variable with the @min function.

[dpb]

I did just verify what the algorithm does to generate new trial paths --

>> currentTour=randperm(4)
currentTour =
          3.00          1.00          2.00          4.00
>> n=4;
>> for i=1:n-1, for j=i+1:n
candidate=currentTour;
candidate(i)=currentTour(j);
candidate(j)=currentTour(i);
disp(candidate)
end,end
          1.00          3.00          2.00          4.00
          2.00          1.00          3.00          4.00
          4.00          1.00          2.00          3.00
          3.00          2.00          1.00          4.00
          3.00          4.00          2.00          1.00
          3.00          1.00          4.00          2.00
>>

You see it does simply reverse the order by pairs starting with the first two, the initial starting location is, in fact, only the initial path tried first will be the only one that starts at that location for a given outer iteration; all the other paths tried begin somewhere else.

If you run a second iteration, then the whichever of those from the first iteration actually turns out to be the best of that bunch will be the starting point for the next set--only if it happens to be the one that was the reverse of the first two elements will that initial starting point again be the new starting point; but that initial swap will be the first element in the taboo list so it won't be tried again.

You would have to modify the generation algorithm to only swap the subsequent locations after the first to force the search to only consider starting from a specific location rather than searching for the best overall path.

[Amna Habib]

@Image Analyst how to update my comment?

I have accepted @Sahaj's answer.

[Amna Habib]

@dpb Thanks a lot for your time. You are right, but I have to follow all steps of my algorithm as written in code.

[dpb]

Excepting the algorithm as written doesn't solve the problem you've asked of it...

[dpb]

I can't and am not speaking for @Image Analyst, but the Q? I believe he's asking is the one above -- did the modification proposed by @Sahaj actually solve the question or not? It doesn't look to me and as I read your answer that it will actually produce a different final result than the original since the search algorithm isn't constrained to keep the initial starting point.

Or, did we misinterpret the question (in which case it isn't clear there actually is a question) that you are looking for the shortest distance solutions given a fixed starting location and hence there need to be n (not necessarily unique numerically depending on the input matrix) solutions, not just one?

The modification proposed by @Sahaj will run the problem n times, it is true, each time starting with a initial guess for a particular one of the n locations as the starting point, but it will still eventually find the same solution (unless the problem size is so large it runs out of allowable outer iterations before exhausting the possibilities).

[dpb]

Try the following modification to the new path generation algorithn -- it will then constrain the solution to only look at paths that begin with the specific starting location instead, thus not producing a global minimum but the minimum for the starting location.

n=4;
currentTour=randperm(n)

currentTour = 1×4

3 1 2 4

for i=2:n-1, for j=i+1:n
  candidate=currentTour;
  candidate(i)=currentTour(j);
  candidate(j)=currentTour(i);
  disp(candidate)
end,end

     3     2     1     4

     3     4     2     1

     3     1     4     2

An alternative way to generate trial paths that would produce the full list would be something like

n=4;
c=candidate(1);
candidate=perms(setdiff(candidate,c));
candidate=[c*ones(size(candidate,1),1) candidate]

candidate = 6×4

3 4 2 1 3 4 1 2 3 2 4 1 3 2 1 4 3 1 4 2 3 1 2 4

where I used the first element of the random permutation as the starting point for the second so the two examples would be commensurate when run. You'll note that the original algorithm only returns one-half of the possible permutations on a given iteration for this number, n, depending upon the size of n, the search as done may never actually find the true minimum before it runs out of iterations; while the second would be guaranteed to find it, the number of possible permutations grows geometrically with n so isn't practical to be implemented in such a brute force manner.

The idea in the original is, of course, that finding the minimal set from the initial ordering will also lead to the global minimum retaining that first case.

Out of curiosity, how big is n in your actual problem set?

[dpb]

Actually, NOTA BENE that @Sahaj's solution will produce the same answer every time it is run because he didn't randomize the remainder of the starting path after the initial starting point -- and since the new path generation algorithm isn't randomized but a specific swapping of elements, it is also deterministic and so the result is deterministic and will be fixed for a givern input array.

The whole point of the initial code using randperm is so that for large problems one has a chance of finding a better solution by multiple runs using a different starting point without running into the issue of the total number of permutations for the exhaustive searching being intractable.

[Amna Habib]

@dpb you are right. Thanks for cooperation. But I am a bit confused. I need the total distance value of paths.

Can you please run the complete code in comment?

[dpb]

You never responded -- how big is n in your real problem? Is the exhaustive search truly out of reach?

It is not at all convenient for me to set aside the project am in midst of at the moment, sorry.

Just

1. change the outer loop starting index from 1 to 2 in the function that creates the next set of search paths and
2. call the routine inside an outer loop as @Sahaj showed with the starting point being the loop index each time. I'd suggest using

    startingTour=[startingCity setdiff(randperm(n),startingCity,'stable');

to generate a randomized starting tour vector instead of a fixed one to retain the variability in potential solutions if n is, as expected, large.

The other thing you need to then do is save the returned best distance from the algorithm in an array of size n so that you have all the results in the end rather than overwriting/just dumping to the screen.

Good luck...

[Amna Habib]

ok, I will try in this manner. I have actually 15 by 15 matrix.

Thank you so much @dpb

[dpb]

Good luck! Sorry can't really divert from what going on; just too complex to get back into the middle of debugging/development of a sticky logic problem...it's really not too hard a nut to crack; @Sahaj did show you the right idea of how to proceed.

Yeah, 15! = ~1.3E12 so that's not feasible, indeed.

Got to thinking which is why I came back just now that probably the way to make the code modifications would be to add an argument (possibly optional) to the function generateCandidateList that is a flag variable for whether to restrict the swap to only use the given starting point (begin outer loop with 2) or leave unconstrained (beginng outer loop with 1)...

function candidateList = generateCandidateList(currentTour, tabuList, fixStartFlag)
    if nargin<3, fixStartFlag=false; end        % keep default behavior
    candidateList = [];
    n = length(currentTour);
    for i = 1+fixStartFlag:n-1
        ...

The above shows the idea; if fixStartFlag is True (1), then it will start the loop at second position leaving first alone; if don't pass anything or it is false, then get same behavior as always. Then, you must fixup the code to set the flag where generateCandidateList is called to use the value desired.

A somewhat more involved way (but far cleaner in the end) would be to set the flag as an optional input at the top level code so there are two possibilites at the beginning to the user to either do the global search or the constrained search.

Depends upon whether this is just a one-time thing to do and will be done or whether is going to be something going on and others may want/need to use the code as well as to how much effort to invest beyond the minimum to get by.

[Amna Habib]

i will surely try in this way too. Thanks again @dpb

Answer 2

[dpb]

To run all possible permuations doesn't need anything but to evaluate the distances for each sequence; there's nothing "best" about any path in that case.

% Example distance matrix (replace it with your own)
distanceMatrix = [
    0  10  11  20;
   10   0  90 25;
   11  90   0  30;
   20  25  30   0
];
n = size(distanceMatrix, 1); % Number of cities
currentTour = perms(1:n)      % all possible tours

currentTour = 24×4

4 3 2 1 4 3 1 2 4 2 3 1 4 2 1 3 4 1 3 2 4 1 2 3 3 4 2 1 3 4 1 2 3 2 4 1 3 2 1 4

Now all you have to do is iterate over the rows in the array and call the tour distance routine for each...

d=arrayfun(@(i)calculateTourDistance(distanceMatrix(i,:)),(1:n).');

However, re-reading the Q? after the other posting, to get the best route for each starting city, just find minimum of d above within each group of the first colum. I dunno how it would compare to the search as far as compute time, but the exhaustive search would definitely find the minimum, IFF the size of the network isn't too large; the total number of possible permutations gets immense pretty quickly...

For that case and for that problem, then do as the other poster says, just start with a given city (1:n) in a loop; you could then start with the random permutation of the subsequent n-1 values; I don't know if it is so that the best choice would start with the shortest first or last difference, maybe? Haven't given the problem any real thought if is better way to get an initial guess or not. @John D'Errico probably knows that otoh... :)

[Amna Habib]

@dpb I have seen your reply. Thanks a lot for this effort.

I need best tour. You have provided all possible permutations. But I need the shortest path starting by all cities one by one.