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

Question

Amna Habib 2023-7-16

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1996573-how-to-change-my-matlab-code-is-has-no-error-in-its-present-form

编辑： dpb 2023-7-20

采纳的回答： Sahaj

在 MATLAB Online 中打开

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

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

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

Answer 1

Sahaj 2023-7-16

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1996573-how-to-change-my-matlab-code-is-has-no-error-in-its-present-form#answer_1273873

编辑：Image Analyst 2023-7-17

在 MATLAB Online 中打开

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]

15 个评论
显示 13更早的评论隐藏 13更早的评论

Amna Habib 2023-7-17

在 MATLAB Online 中打开

% 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.

dpb 2023-7-17

编辑：dpb 2023-7-17

在 MATLAB Online 中打开

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 2023-7-18

编辑：dpb 2023-7-18

在 MATLAB Online 中打开

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.

dpb 2023-7-18

编辑：dpb 2023-7-18

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 2023-7-18

编辑：dpb 2023-7-19

在 MATLAB Online 中打开

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 2023-7-20

编辑：dpb 2023-7-20

在 MATLAB Online 中打开

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 2023-7-20

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

请先登录，再进行评论。

Answer 2

dpb 2023-7-16

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1996573-how-to-change-my-matlab-code-is-has-no-error-in-its-present-form#answer_1273878

编辑：dpb 2023-7-16

在 MATLAB Online 中打开

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 = [
10  11  20;
 0  90 25;
90   0  30;
25  30   0
];
n = size(distanceMatrix, 1); % Number of cities
currentTour = perms(1:n)      % all possible tours
currentTour = 24×4
   3     2     1
   3     1     2
   2     3     1
   2     1     3
   1     3     2
   1     2     3
   4     2     1
   4     1     2
   2     4     1
   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... :)

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Amna Habib 2023-7-17

@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.

请先登录，再进行评论。

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

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

15 个评论
显示 13更早的评论隐藏 13更早的评论

更多回答（1 个）

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

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

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

15 个评论 显示 13更早的评论隐藏 13更早的评论

更多回答（1 个）

1 个评论 显示 -1更早的评论隐藏 -1更早的评论

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

15 个评论
显示 13更早的评论隐藏 13更早的评论

1 个评论
显示 -1更早的评论隐藏 -1更早的评论