Tabu search is a metaheuristic algorithm, related to simulated annealing, which it depends on neighbourhood search with different acceptance criteria. Tabu search firstly proposed by Fred Glover (1986).The Basic idea of tabu search algorithm is to explore the neighbourhoods, selecting the best moves that improve the solution found so far during the search. The idea of tabu search procedure is to prevent the search from getting stuck in local optima solutions. Preventing the search from getting stuck in local optima, a tabu list is constructed of the pre-visited solutions which are forbidden to be revisited within a certain number of iterations (called the tabu tenure). The tabu tenure determines how long a given solution or move remains tabu. Study the main features and more details of the different variations of tabu search tabu search can be found in (Rego and Alidaee 2005; Glover and Laguna 1998) where it shows the capability of dealing with various difficult problems by using different memory structures and stopping criteria.
A. Hader et al (2006) proposed a tabu search method called Tabu Search for Attribute Reduction (TSAR), to solve Attribute reduction problem. It used High-level tabu search with long-term memory. This algorithm applied diversification and intensification search criteria based on Neighbourhood search methodology. A rough set dependency degree method used to evaluate the solution quality. Two main concepts considered during local search; avoiding return to a recently visited solution, and accepting downhill moves to escape from local maximum information. Diversification and intensification in TSAR invokes into three stages; diverse solution generation, best reduct shaking which attempts to reduce its cardinality, and elite reducts inspiration. Examine the performance of TSAR on 13 well-known datasets and compared with three other rough set attribute reduction methods show that the TSAR with High-level tabu search with long-term memory competitive with some other algorithms used for the same problem in terms of reduct qualities. Moreover, the author claimed that TSAR shows a superior performance in saving the computational costs of the dependency degree function.
Oduntan O. el at (2008) proposed a new feature selection technique (multilevel feature selection) that combines a tabu search method with a hierarchical search framework. Use a multilevel search in biomedical data. The framework consists of increasingly coarse forms (i.e., search subspaces) of the original feature space that is strategically and progressively explored by the tabu search method. The proposed method consists of three phases namely: coarsening phase, search phase, and refinement phase. The result of the search at any given coarse subspace is used to initialize the search at the previous less coarse subspace. Evaluate the performance of the proposed technique on biomedical dataset origin from the National Research Councils Institute for Biodiagnostics (NRC-IBD) in terms of the solution quality, shows that multilevel and tabu search-based feature selection techniques outperforms other compared feature selection techniques, Furthermore the multilevel technique demonstrates better performance than the tabu search-based technique in terms of the three evaluation parameters (i.e., classification accuracy on training set, and classification accuracy on independent test set and stability).
Scatter search
Another metahuristic search method applied to solve Attribute reduction problem,
One of the cheapest techniques in saving computational cost is Scatter Search for Attribute Reduction algorithm developed by Wang j. et al (2009). It was first introduced for solving linear programming problems by Glover (1977), it is considered as an evolutionary strategy using population base to generate best trial solution, which has proved useful for solving discrete and non-linear optimization problems. Scatter search initiate a reference set (RefSet) generated from the population of initial solutions. The use of (RefSet) is to construct a good solution from combining its solutions from the list. The original scatter search divided into two phases: an initial phase and an evolutionary phase. As in the evolutionary methods, the highest evaluated solutions found by the local search phase are used to update the set of solutions. Five sub-routines are called in the Evolutionary Phase with diverse solutions. Scatter search algorithm applied in various fields such as job shop scheduling, neural network, Graph drawing, Liner ordering, and many others.
Wang j. et al (2009) method uses memory based heuristic with population generation to the initial solution. The SSAR start with two procedures. The first procedure called Diversification Generation to generate population which follows Glover's systematic basis (Glover 1998) , second Improvement procedure attempts to refine the selected solutions from the first one to produce better quality reducts set called (RedSet).The Improvement procedure base on removing or adding attributes that has the minimum and maximum frequencies. The initial solutions (RedSet) get filtered and changed during four procedures as follows:
Subset Generation Procedure generates all pairs of solutions in RefSet. In this procedure discard all those pairs of reference solutions which have already been combined in previous iterations.
Solution Combination Procedure, generate one random child solution for each subset generated by Subset Generation Procedure,
Improvement Procedure tries to refine the computed children by applying the second procedure.
Reference Set Update Procedure, Update RefSet to have the best μ1 solutions from the old RefSet and the improved generated children, and μ2 diverse solutions chosen randomly from population.
Finally, an Intensification procedure is applied to refine the best obtained solutions. Specifically, Best Reduct Shaking and Elite Reducts Inspiration mechanisms are used. Computational experiments state that SSAR technique give a promising and competitive performance compared with some other heuristic approaches in term of solution quality.
Ant Colony
Ant colony optimisation (ACO) is a metaheuristic algorithm using population base. The main idea of ACO based on the behaviour of ants in their life and how they search for the shortest path to food sources and back to their nest. The ability of finding the shortest route between a food source and their nest by chemical materials called pheromone that they leave when moving. First Implementation for ACO was to solve traveling salesman problem (TSP) by Dorigo et al. (1996). ACO has been successfully applied to a large number of NP-Hard problems like the quadratic assignment problem, feature selection, Networks routing, graph colouring problems, scheduling, etc.
Jensen and Shen (2003), developed a method called AntRSAR to the attribute reduction problem. The number of simulated ants was set equally to the number of features within the data; the initial population consists of 100 randomly generated feature subsets, the probability of mutation and crossover set to 0.4 and 0.6 respectively, and the number of generations is set to 100. An entropy based feature selector EBR is presented also in the work, aiming to show the difference between dependency degree and entropy feature selection techniques. The proposed work was tested on well-known datasets, the initial results were superior comparing to other methods at that time, and on the other hand associated parameters require more investigation and further experiments. Moreover the results using entropy measure indicates that it is a costly operation compared with dependency evaluation which it should take on consideration as an important factor when processing large datasets.
Chen Y. et al. (2010) made some modifications about Ant colony optimisation algorithms based on (Jensen and Shen 2003) method for a rough set approach to feature selection. They suggest that rather than using Jensen and Shen's method by randomly start features to select the ants, it possibly better to start the algorithm by selecting the feature core based on rough set theory, calling the method (RSFSACO). Entropy method used as an information measure of information table for feature selection. In RSFSACO the heuristic information is dynamically calculated during the construction process of solutions. The significance of features is adopted as heuristic information for RSFSACO. The significance of features is defined by information entropy and mutual information. The suggested method always accepts the improved solution. Experimental test applied to demonstrate the performance RSFSACO algorithm, the initial pheromone was set to 0.5 with a small random perturbation added, the number of ants was half the number of features and the maximum number of cycles equals 100. From the results, from the results, Comparing the algorithm with other methods shows that RSFSACO is able to find different reducts with various lengths, unlike RST-based method where it produce the same reducts every time. It is obvious that in some situations hill-climbing methods can locate the optimal feature reduct. On the other hand the proposed algorithm could not outperforms Jensen and Shen's ACO-based algorithm in all problems in term of quality measurement except for run time where it gives a good results, Furthermore the number of chosen dataset to be tested on , is not enough to show the real significant between tested methods.
Liangjun Ke et al. (2008) Introduce a new Ant Colony technique for attribute reduction called ACOAR, the algorithm extends the basic idea of max-min ant system (MMAS) (Stu¨ tzle and Hoos 2000) which is one of the most successful ACO variants (Dorigo and Blum 2005). The objective of this work is to study the proposed algorithm in terms of solution quality and computational effort. One of the key aims of their work is to speed up the calculation of dependency degree to reduce to computational time. ACOAR used same Jensen and Shen's ACO method to construct the solutions, by select attribute at random for every generated ant, then it probabilistically selects next attribute from those unselected attributes. Pheromone trails are updated mainly according to MMAS. In ACOAR, pheromone trails update controlled by two parameters. If one of the parameters far larger than the other then ants will consider one of two decisions, ether mainly based on pheromone trails or select those edges with higher heuristic information in a greedy manner. Liangjun Ke et al. used two strategies to update the Pheromones called Pheromone_Update_Rule_1 and Pheromone_Update_Rule_2; this rule can make the probability of searching around the best-so-far solution higher. ACOAR-1 which uses Pheromone_Update_Rule_1 to update pheromone trails. Iinitial pheromone value was set to 0.5 with a small random perturbation added, the number of ants was 10 and the maximum number of cycles was 100. These parameters were determined based on a small number of preliminary runs. Rresults for small or medium-sized datasets and for high-dimensional datasets has been presented to evaluate the capability of ACOAR. Experimental results showed that the new method has a significant different comparing to other heuristics algorithms; moreover ACOAR capable of finding solutions rapidly with very small cardinality. When ACOAR is applied to a high-dimensional problem, the ants use a candidate list of length 100 which contains the best unselected attributes ordered according to decreasing dependency degrees. Comparing ACOAR with other well-known approaches in attribute reduction field, we can consider it as one of the best performing approaches and very promising method to solve the problem.
Simulated Annealing
Temperature effect on solid annealing through increase the size of the crystals and reduce defects for material by increasing the level of heat, causes the atoms to become unstuck from their initial positions. This idea was an inspiration to develop an effective meta-heuristic algorithm to solve optimisation problems called simulated annealing, it was proposed by Kirkpatrick et al. (1983). Simulated annealing controlled by three main parameters; initial temperature, cooling schedule and finishing temperature which they control the performance of the algorithm. Initial solution usually generated randomly. Accepting or rejecting the solutions based on the the temperature, which it determines how likely the moves from the neighbourhood structures been accepted, high temperature giving a high probability of acceptance and a low temperature causing most worsening moves to be rejected. Probability criteria, P, calculated by formula P = e -α/ t where α is the difference of the objective function evaluation between the current and the candidate solutions and t is a parameter (called the temperature) which periodically decreases during the search process according to some cooling schedule. Improving moves will always be accepted, whilst the current temperature determines the probabilistic acceptance of worsening moves. The algorithm begins with a high temperature, which means a high probability of accepting worse solutions. Continuance sequential iterations, the temperature is gradually decreased, as such reducing the probability of accepting non-improving solutions. At temperature zero, the algorithm only accepts improving solutions. The algorithm ends when a stopping condition is met. Simulated annealing has been applied successfully to a variety of optimisation problems, including flow-shop scheduling (Osman and Potts 1989) ,stock cutting (Lutfiyya et al. 1992)and vehicle routing (Czech and Czarnas 2002).
The Simulated annealing algorithm was applied to attribute reduction problem in Jensen and Shen (2004). The proposed method called SimRSAR employs a simulated annealing-based feature selection mechanism as presented in (Jensen and Shen 2003).The used neighbourhood structures ether add or remove to change the statues of subsets. The cost function attempts to maximize the rough set dependency (ï§) is used while minimizing the subset cardinality. The algorithm parameters as the initial temperature of the system is estimated as 2 * |C| and the cooling schedule is T(t+1) = 0.93* T(t). SimRSAR has been tested on diffrend datasets that represent a real-life data and compared to other methods. Results prove that SimRSAR often found different size of reduct and sometimes different subset cardinalities in most of the cases. On the whole, it appears to be the case that SimRSAR outperform the other compared methods in some of the cases at that time. SimRSAR might give good result by fine-tuning the parameters to each individual data set.
Guanyu P. and Hui Y. (2009) proposed a reduction methods using binary particle swam optimization method based on simulated annealing (BPSOwSA). The use of simulated annealing was to particles updated their position in particle swam algorithm during the search. The algorithm convergence was controlled by adjusting the speed of annealing. The particles would not easily jump out of the "expected" search area when the fall of temperature was slow enough, that leads to enhance the efficiency of the algorithm and which improved the particles' local search capability. Initialize the particle swarm, by determining the scale and iteration depth of the particle swarm, in addition to the initial temperature T of simulated annealing and the scale of weak population, the same random legitimate solution vector is assigned to the optimum solution. The experiments carried out show that this hybridisation approach (BPSOwSA) was able to produce better results when compared to basic particle swam optimization method when applied on in the oil field casing damage datasets.
Genetic Algorithm
Genetic Algorithm were inspired by principles of natural evolution that works with population-based method, quality of the solution is measured by a fitness function, this algorithm invented by Holland (1975) and become more popular by John R. Koza (). The initial chromosomes represented in a form of array where each cell in that array called a gene and contains a unit of solution information. As other population algorithms, genetic algorithm is iterative, and it base on three main procedures to produce the solution; Evaluation of current population, selection of chromosomes for reproduction and apply genetic operators such as crossover to produce new population. The evolution stage usually starts from randomly generating a population. In each generation, the fitness of every individual in the population is evaluated, multiple individuals are stochastically selected from the current population (based on their fitness), and modified (recombined and possibly randomly mutated) to produce a new population to be used in the followed iteration. Fitness function in a genetic algorithm, labels the chromosomes that have higher probability to produce optimal solutions. Highly ranked chromosomes are allowed to breed and mix their datasets by any of several techniques (e.g. roulette wheel), producing a new generation that might give better solutions. Genetic algorithm iterated until the termination condition is met (e.g. Maximum number of generations or a satisfactory fitness level has been reached for the population). Genetic Algorithms has been successfully applied to a large number of Real-World applications such as Engineering, Robotics, Evolvable Hardware, Telecommunications Routing and Computer-Aided Molecular Design, etc.
In Jensen and Shen (Jensen and Shen 2004; ), Genetic algorithm is used as attribute reduction procedure called (GenRSAR) . The aim of the approach is to use genetic algorithms to discover optimal or close-to-optimal reducts. Dependency degree tool based of Rough set theory used to evaluate the quality of the solutions. GenRSAR employs a genetic search strategy in order to determine rough set reducts. As a parameter setting, the initial population consists of 100 randomly generated feature subsets, the probability of mutation and crossover set to 0.4 and 0.6 respectively, and the number of generations is set to 100. The fitness function considers both the size of subset and its evaluated suitability. The algorithm is tested on standard benchmark from UCI machine learning repository, A comparison between a genetic algorithm, ant colony and simulated annealing in (Jensen and Shen 2004) shows that GenRSAR technique often fail to find good or even the known minimal data reduct . Furthermore it gets surpassed from most of other heuristics compared to the number of minimal reducts.
Zhangyan et al. (2009) presented a modified genetic algorithm to solve attribute reduction problem. Trying to cover-up of standard genetic algorithm shortage, where the objective function or fitness function on the chromosome is not efficient to calculate the minimal reducts, assuming that the chosen candidate attribute which it should be optimal might not be an attribute reduction. Moreover during the crossover and mutation process in the existing genetic algorithm it could not delete the candidate attribute reduction which is not the minimal attribute reduction. The chosen objective was to introduce new fitness function, and make sure to provide an optimize candidate attribute reduction. It also can handle the problem of crossover and mutation process by making it able to delete the contained attributes in the chromosome which is not representing the minimal attribute reduction. In order to improve the convergence speed and find a fast solution for the problem they used one-point crossover method and make sure to delete the candidate which is not the attribute reduction. In selection method they consider the larger fitness function of chromosome is, the better the corresponding individual. In order to test the effectiveness of the new genetic algorithm, two real datasets were used from UCI repository. The parameters used for Initialization population size is 18, Crossover rate is 0.8, Mutation rate is 0.03. The authors claimed that, results from the new algorithm may find the minimal attribute reduction and has quick convergence speed. But the experiment does not show enough details due to the small number of tested benchmarks.
Zhi, Liu, and Wang (2009) proposed a kind of rough set attribute reduction algorithm based on immune genetic algorithm. The algorithm introduce core into the initial antibody population to improve the performance. The use of immune genetic algorithm is to increase the convergence to reach the global optimum. Chromosome generation represented using the traditional binary scale code, considering each chromosome from the initial population contain the relative attribute core. Fitness function used to appraise the chromosome, treating the less the number of condition attributes adopted by the chromosome is, the higher the fitness function value is. In order to achieve the objective of reaching higher convergent speed separately in different evolution periods of the algorithm and find minimal reducts, they select a self-adaptation crossover and mutation probability. Furthermore they adopt different fitness functions at different stages. The stop criterion for this method based on kind of shrinking precision. The investigation conducted on data of weapons which participating in the calculation of the destruction effect assessment, and the results represents the destruction assessment decision information. From the given results we can conclude that during the evolution process of the algorithm, it goes through continues generation changes. It proves that the algorithm has realized effective search for the solution space during all stages of the work, on the other hand compared with traditional algorithm, it does not appear the phenomenon of being convergent too early. The results prove that the proposed algorithm can carry on reduction to the decision table effectively and can be convergent to global optimum quickly.
