Wróblewski J., 1998.Genetic algorithms in decomposition and classification problem. In: L. Polkowski, A. Skowron (eds.): Rough Sets in Knowledge Discovery. Physica-Verlag, Heidelberg 1998, vol. 2, pp. 471 - 487.
ABSTRACT
Some combinatorical problems concerned with using rough set theory in knowledge discovery (KD) and data analysis can be successfully solved using genetic algorithms (GA) - a sophisticated, adaptive search method based on the Darwinian principle of natural selection. These problems are frequently NP-hard, as in case of reducts or templates finding, and there is no fast and reliable way to solve them in deterministic way.
Genetic algorithms are flexible and universal - they can be used in various situations. On the other hand, approximate but fast heuristics are known for many of considered tasks. They are designed and tuned up especially for a problem, and often are more efficient than simple genetic algorithm. Unfortunately, they are often suboptimal and cannot avoid local optima. Moreover, if they are deterministic, there is no hope for improvement even if one can spend more time on computations.
The advantages of both genetic and heuristic algorithms can be exploited by hybrid algorithms - nondeterministic, problem-oriented heuristics controlled by genetic algorithm. In this work some examples of hybrid systems are presented, as well as the theory of order-based genetic algorithms being used in these systems.
The article involves two examples of application of hybrid algorithms supporting rough set methods in knowledge discovery: a system for short reducts generation and a method of templates finding.