Heuristic Method Using Soft Tabu Search for Quadratic Assignment Problems

摘要

The tabu search is one of the metaheuristics to avoid local minima of combinatorial optimization problems. Although the tabu search shows good performances for the traveling salesman problem and the quadratic assignment problem, the tabu search is not effective for the motif extraction problem because the tabu effect of the tabu search is too strong. We have already proposed a soft tabu search to resolve this problem. Most different point between the soft tabu search and the tabu search is that the tabu effect in the tabu search prohibits to select the same solutions for a while. On the other hand, in the soft tabu search, the same solutions are hard to be selected for a while. Due to such weak tabu effect, the soft tabu search shows better performances than the tabu search for the motif extraction problems and the traveling salesman problems. In this report, to investigate searching ability of the soft tabu search, we apply the soft tabu search to the quadratic assignment problem. As a result, the soft tabu search shows also higher performance than the tabu search for the quadratic assignment problem.