A new approach to minimum attribute reduction based on discrete artificial bee colony

The minimum attribute reduction problem in the context of rough set theory is an NP-hard nonlinearly constrained combinatorial optimization problem. In this paper, we propose an efficient and competitive combinatorial artificial bee colony algorithm for solving the minimum attribute reduction problem. In the proposed algorithm, a new multidimensional binary local search scheme for bee colonies based on velocity computation is presented; an employed bee and its recruited onlooker bees use different local search strategies so as to get a possibly more diversified neighboring search around a current food source; the information of the so-far best solution is exploited in various ways by employed bees, onlookers and scouts, respectively; the monotonicity property of classification quality of attribute subsets from the theory of rough sets is employed to avoid possibly invalid local searches. Performance comparisons with some best performing population-based metaheuristic algorithms for the minimum attribute reduction problem were carried out on a number of UCI data sets. The experimental results show that the proposed algorithm overall outperforms all the other algorithms in terms of solution quality and is therefore promising for solving the minimum attribute reduction problem.