Tabu search with multi-level neighborhood structures for high dimensional problems

Metaheuristics have been successfully applied to solve different types of numerical and combinatorial optimization problems. However, they often lose their effectiveness and advantages when applied to large and complex problems. Moreover, the contributions of metaheuristics that deal with high dimensional problems are still very limited compared with low and middle dimensional problems. In this paper, Tabu Search algorithm based on variable partitioning is proposed for solving high dimensional problems. Specifically, multi-level neighborhood structures are constructed by partitioning the variables into small groups. Some of these groups are selected and the neighborhood of their variables are explored. The computational results shown later indicate that exploring the neighborhood of all variables at the same time, even for structured neighborhood, can badly effect the progress of the search. However, exploring the neighborhood gradually through smaller number of variables can give better results. The variable partitioning mechanism used in the proposed method can allow the search process to explore the region around the current iterate solution more precisely. Actually, this partitioning mechanism works as dimensional reduction mechanism. For high dimensional problems, extensive computational studies are carried out to evaluate the performance of newly proposed algorithm on large number of benchmark functions. The results show that the proposed method is promising and produces high quality solutions within low computational costs.