Practical Applications of Genetic Algorithms for Efficient Reduct Computation

Large collections of data may contain valuable but undiscovered knowledge. The process of making such knowledge explicit is called knowledge discovery. The rough set theory, introduced by Pawlak and his colleagues (see eg [4], [5] or [7]), has been successfully applied to many problems in this area. A real problem when taking rough sets from theory to application is in the analysis of large data sets because the complexity is very high. The essential task of finding reducts is reported NP-hard in [6]. Many other operations related to the rough set theory also have a high complexity, but this paper focuses on computational methods of approximating reducts. In particular, an application of genetic algorithms will be discussed. The use of genetic algorithms for finding reducts was introduced in [8]. We implemented the "Rough Enough" software system which applies genetic algorithms for computing reducts ([1] and [2]). The techniques presented in [8] have been a foundation, but several variations and practical improvements have been implemented. This work led to the discovery of many practical details and possible pitfalls when implementing such techniques, and these discoveries form the focus of this paper. Using the experience from the "Rough Enough" implementation, this paper discusses some rules of thumb for the implementation of reduct computations with genetic algorithms.