Tabu search, designed to escape from local optimum, is a metaheuristic algorithm for solving optimization problems. Motivated by Glover [13] as an optimization tool applicable to nonlinear covering problems, the TS algorithm was originally proposed by Glover [14]. The basic idea of the TS is to expand its search beyond local optimality using adaptive memory. The adaptive memory is a mechanism based on the tabu list of prohibited moves. Use of the tabu list is one way to prevent cycling and guide the search towards unexplored region of the solution space.

The tabu search algorithm has been successfully applied to telecommunications path assignment [15], neural network pattern recognition [16], machine learning [17], just-in-time scheduling [18], and electronic circuit design [19].

Drezner [9] developed a tabu search for the subset selection problem. The TS procedure is described in the following pseudocode.

Drezner [9] generated all neighborhoods by three moves, which are adding a variable, removing a variable, and swapping variables. For example, consider a set of p = 5 independent variables: full-set = {x₁, x₂, x₃, x₄, x₅} and a subset of k= 2 variables: {x₁, x₂}. All neighborhoods of this subset consist of the following moves in Table 1.

Drezner [9] also adapted the stopping criterion as the total number of 30 iterations without improving the best-so-far solution. The size of the tabu list was set to 10.

Lin et. al.[20] suggested the original version of GSA for solving some NP-hard problems such as knapsack problem, travelling salesman problem, and set partitioning problem. Hasan [10] proposed a hybrid GSA for the subset selection problem, in which a genetic algorithm (GA) [21] is combined with a simulated annealing (SA) algorithm [22]. The pseudocode for the hybrid GSA algorithm is as follows.

The SA operator is incorporated into the generation of children produced by the genetic operators. It is applied to decide which two of the parents and children remain. That is, if children are better than parents, then the parents is replaced by the children. If parents are better, they are replaced with the chosen probability as shown in the pseudocode of GSA.

Hasan [10] suggested that the number of the population, crossover rate, mutation rate, maximum number of iteration, the initial temperature and the cooling rate is chosen as 100, 0.8, 0.1, 1000, 100 and 0.9, respectively.

The neighborhood of Drezner [9] was generated by three moves, which are adding a variable, removing a variable, and swapping variables. In Table 1 of the previous section, however, most of neighborhoods of swapping variables can be tentatively explored by the search engine with the neighborhood of only adding and removing a variable. For example, if the subset { x₂, x₃} generated by swapping variables is optimum, it can be also obtained by adding {x₁, x₂} to x₃ variable, and then removing x₁ variable from the resulting subset of {x₁, x₂, x₃} . That is, it can be transitively searched from {x₁, x₂} to {x₁, x₂, x₃} to { x₂, x₃} . This implies that the move of swapping may be replaced by two moves of adding and removing.

As the number of variable increases, the number of the neighborhood of swapping becomes larger. The number of neighborhood of swapping variables is totally k(p-k).

In order to reduce the computing time, we suggest that the neighborhood with swapping should be entirely excluded from the proposed method. Practically, from our computational results, we noticed that our search engine with only two moves, adding or removing a variable, plays a sufficient role in improving the current best solution. Consequently, the neighborhood strategy without swapping variables reduces a considerable amount of computing time.

Widmer & Hertz [23] and Tailard [24] proposed tabu search for the flow shop scheduling problem. They also suggested two specific search strategies: the best move strategy and the first move strategy. The best move strategy examines all neighborhoods and selects the best move that is not on the prohibited tabu list. The first move strategy examines the neighborhoods and selects the first move that improves the current best solution. If there is no first move that improves the current best solution, the first move strategy eventually becomes equivalent to the best move strategy.

As depicted in Figure 1, the procedure of improving the best solution can be divided into two phases: Phase-I and Phase-II. In the Phase-I, the procedure for improving the best solution is rapidly progressed. After the solution reaches a local optimum through the tabu search, it is difficult to improve the local optimum. Accordingly, the procedure of improving the local optimum is slowly processed in the Phase-II

Figure 1: 
The Phase-I and Phase-II

In the improved tabu search, the first move strategy is adopted.

In Phase-I, the first move strategy plays a role in rapidly improving the current best solution.

The pseudocode of the first move strategy is as follows.

In Drezner [9], the tabu list contains a list of moves. In the proposed ITS method, the tabu list contains a list of solutions. In our experiments, we noticed that our tabu list of solutions is more efficient than that of moves for this problem.

In our experiments, stopping criterion is the total number of 30 iterations without improving the best-so-far solution.

In Table 2, p, n, Best, and Freq. are defined as follows.

p : the total number of independent variables.
n : the number of sample data.
Best : the Maximum of Radj2 for 10 trials.
Mean : the Mean of Radj2 for 10 trials.
Freq : the number of Best found by each method for 10 trials.

As the experimental results in Table 2 indicate, all methods find the optimal value of Radj2. In the value of Freq., however, the performance of TS is more or less worse than that of the proposed ITS method.

To further test the performance of the ITS method, the simulation data sets were randomly generated as follows.

i) Independent variables were generated by normal distribution with a mean 0 and a standard deviation 1.

ii) Error terms were generated by normal distribution with a mean 0 and a standard deviation λσ, where σ is standard deviation of actual regression equation, and λ is a constant.

iii) The number of sample data is five times the total number of independent variables.

The value of E is given by the following Equation (3).

where k is the number of sample data and is five times the total number of independent variables, and p is the total number of independent variables.

From the computational results shown in Tables 4 to 7, it is clear that the proposed ITS method outperforms the GSA and TS methods in terms of the computing time and solution quality. As shown in Figure 2, the ITS method is the fastest. Specifically, when the value of p is 100, the GSA and TS methods take a considerable amount of computing time. As seen in Table 3, the computing time (sec.) of GSA, TS, and ITS is 233.8, 267.5 and 8.058, respectively.

Figure 2: 
The Computing Time of GSA, TS and ITS