A New Fitness Function for Solving Minimum Attribute Reduction Problem

The problem of minimum attribute reduction is formally a nonlinearly constrained combinatorial optimization problem and has been proved to be NP-hard. A most commonly used approach for dealing with the problem is to first transform it into a fitness maximization problem over a Boolean space and then to solve the latter via stochastic optimization methods. However, existing fitness functions either fail to assure in theory the optimality equivalence between the original problem and the fitness maximization problem or are not quite adequate in terms of fitness evaluation. In this paper, a new fitness function that overcomes the drawbacks of the existing fitness functions is given. The optimality equivalence using the proposed fitness function is theoretically proved. Comparisons are made experimentally between the proposed fitness function and two other typical fitness functions by using two recent attribute reduction algorithms. Experimental results show that for each algorithm in test, the proposed fitness function outperforms the other two in terms of both the probability of finding a minimum reduct and the average length of the output reducts.