How to change my matlab code. Is has no error in its present form.
Show older comments
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:');
disp(bestTour);
disp('Best Distance:');
disp(bestDistance);
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
Accepted Answer
Sahaj
on 16 Jul 2023
Edited: Image Analyst
on 17 Jul 2023
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 Comments
Image Analyst
on 17 Jul 2023
@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.
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.
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
on 18 Jul 2023
Amna Habib
on 18 Jul 2023
dpb
on 18 Jul 2023
Excepting the algorithm as written doesn't solve the problem you've asked of it...
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).
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)
for i=2:n-1, for j=i+1:n
candidate=currentTour;
candidate(i)=currentTour(j);
candidate(j)=currentTour(i);
disp(candidate)
end,end
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]
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?
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
on 20 Jul 2023
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
- change the outer loop starting index from 1 to 2 in the function that creates the next set of search paths and
- 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
on 20 Jul 2023
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
on 20 Jul 2023
More Answers (1)
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
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 Comment
Amna Habib
on 17 Jul 2023
Categories
Find more on Creating and Concatenating Matrices in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
