1

I was wondering what the computational complexity of a metaheuristic like tabu search. Why there is not a section to discuss the time and space complexity of the algorithm in the original paper and even on the improvement of the algorithm like iterative tabu search and reactive tabu search?

I want to analyze the algorithm with others on the travelling salesman problem.

begin
 T:= [ ];
 s:=initial solution;
 s*:=s
 repeat
 find the best admissible s’ є N(s);
 if f(s’) > f(s*) then s*:=s’
 s:=s’;
 update tabu list T;
 until stopping criterion:
end;
richard_
  • 45
  • 7
  • 1
    Those are not sound and complete. There is no guarantee to find the optimum and there is also no certificate: they dont know if they found and optimum or.something else. Conceptually those algorithms are very different from others analyzed in this regards. The global analysis is more or less useless then (if analyzed in the same environment as sound and complete algorithms). – sascha Jul 03 '19 at 05:54
  • But the TS has an interaction process for finding solutions within a neighborhood, would not it be possible to calculate his complexity? – richard_ Jul 05 '19 at 01:33
  • The neighbourhood function is problem-dependent. That means, given a problem, more than one neighbourhood can be proposed. Therefore, you could compare the effectiveness/complexity of each neighbourhood. – WillEnsaba Sep 04 '19 at 10:11

1 Answers1

-2

This algorithm is not population-base algorithms. this do is very similar to a typical derivation, so it does not matter how to execute it in finding the very important problem. It is true that in previous scientific discussions there has not been much talk about this issue because several algorithms have been developed to solve a problem that works better than tabu algorithm.

mohamad bagher davoodi
  • 9
  • 2
  • Given an optimization problem X, it is not possible to calculate its complexity? The fact of that method search for a viable solution within a neighborhood (or outside), the iteraction process will not give me his complexity? – richard_ Jul 05 '19 at 01:39