How to change my matlab code. Is has no error in its present form.
1 visualización (últimos 30 días)
Mostrar comentarios más antiguos
Amna Habib
el 16 de Jul. de 2023
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
0 comentarios
Respuesta aceptada
Sahaj
el 16 de Jul. de 2023
Editada: Image Analyst
el 17 de Jul. de 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 comentarios
dpb
el 20 de Jul. de 2023
Editada: dpb
el 20 de Jul. de 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.
Más respuestas (1)
dpb
el 16 de Jul. de 2023
Editada: dpb
el 16 de Jul. de 2023
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... :)
Ver también
Categorías
Más información sobre Holidays / Seasons en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!