This thesis deals with the subset selection that is a vital combinatorial optimization problem in multivariate statistics. It is the selection of the optimal subset of variables in order to reliably construct a multiple linear regression model. Since this problem has NP-complete nature, the larger the size of the variables, the harder to find the optimal solution. In general, many metaheuristic methods have been developed to tackle the problem. In the subset selection problem, two typical metaheuristics, which are tabu search and hybrid GSA (genetic and simulated annealing algorithm), was proposed. However, they have some shortcomings, that is, the tabu search takes a lot of computing time due to many neighborhood moves and GSA’s solution quality is less accurate. This paper proposes an improved tabu search algorithm to reduce moves of the neighborhood and adopt the appropriate move search strategy. To evaluate the performance of the proposed method, a comparative study is performed on both the literature data sets and simulation data sets. Computational results show that the proposed method outperforms the previous metaheuristics in terms of the computing time and solution quality.