Variable Neighbourhood Iterated Improvement Search Algorithm for Attribute Reduction Problems

Attribute reduction is one of the main contributions in Rough Set Theory (RST) that tries to find all possible reducts by eliminating redundant attributes while maintaining the information of the problem in hand. In this paper, we propose a meta-heuristic approach called a Variable Neighbourhood Iterated Improvement Search (VNS-IIS) algorithm for attribute reduction. It is a combination of the variable neighbourhood search with the iterated search algorithm where two local search algorithms i.e. a random iterated local search and a sequential iterated local search algorithm are employed in a parallel strategy. In VNS-IIS, an improved solution will always be accepted. The proposed method has been tested on the 13 well-known datasets that are available in the UCI machine learning repository. Experimental results show that the VNS-IIS is able to obtain competitive results when compared with other approaches mentioned in the literature in terms of minimal reducts.