Abstract
Genetic algorithms (GAs) are a class of problem solving techniques which have been successfully applied to a wide variety of hard problems (Goldberg, 1989). In spite of conventional GAs are interesting approaches to several problems, in which they are able to obtain very good solutions, there exist cases in which the application of a conventional GA has shown poor results. Poor performance of GAs completely depends on the problem. In general, problems severely constrained or problems with difficult objective functions are hard to be optimized using GAs. Regarding the difficulty of a problem for a GA there is a well established theory. Traditionally, this has been studied for binary encoded problems using the so called Walsh Transform (Liepins & Vose, 1991), and its associated spectrum (Hordijk & Stadler, 1998), which provides an idea of the distribution of the important schemas (building blocks) in the search space. Several methods to enhance the performance of GAs in difficult applications have been developed. Firstly, the encoding of a problem determines the search space where the GA must work. Therefore, given a problem, the selection of the best encoding is an important pre-processing step. Operators which reduce the search space are then interesting in some applications. Secondly, variable length or transformed encodings are schemes, which can be successfully applied to some difficult problems. The hybridization of a GA with local search algorithms can also improve the performance of the GA in concrete applications. There are two types of hybridization: • If the GA is hybridized with a local search heuristic in order to tackle the problem constraints, it is usually known as a hybrid genetic algorithm. • If the GA is hybridized with a local search heuristic in order to improve its performance, then it is known as a memetic algorithm. In this chapter we revise several hybrid methods involving GAs that have been applied to data mining problems. First, we provide a brief background with several important definitions on genetic algorithms, hybrid algorithms and operators for improving its performance. In the Main Trust section, we present a survey of several hybrid algorithms, which use GAs as search heuristic, and their main applications in data mining. Finally, we finish the chapter giving some conclusions and future trends.
TopIntroduction
Genetic algorithms (GAs) are a class of problem solving techniques which have been successfully applied to a wide variety of hard problems (Goldberg, 1989). In spite of conventional GAs are interesting approaches to several problems, in which they are able to obtain very good solutions, there exist cases in which the application of a conventional GA has shown poor results. Poor performance of GAs completely depends on the problem. In general, problems severely constrained or problems with difficult objective functions are hard to be optimized using GAs. Regarding the difficulty of a problem for a GA there is a well established theory. Traditionally, this has been studied for binary encoded problems using the so called Walsh Transform (Liepins & Vose, 1991), and its associated spectrum (Hordijk & Stadler, 1998), which provides an idea of the distribution of the important schemas (building blocks) in the search space.
Several methods to enhance the performance of GAs in difficult applications have been developed. Firstly, the encoding of a problem determines the search space where the GA must work. Therefore, given a problem, the selection of the best encoding is an important pre-processing step. Operators which reduce the search space are then interesting in some applications. Secondly, variable length or transformed encodings are schemes, which can be successfully applied to some difficult problems. The hybridization of a GA with local search algorithms can also improve the performance of the GA in concrete applications. There are two types of hybridization:
- •
If the GA is hybridized with a local search heuristic in order to tackle the problem constraints, it is usually known as a hybrid genetic algorithm.
- •
If the GA is hybridized with a local search heuristic in order to improve its performance, then it is known as a memetic algorithm.
In this chapter we revise several hybrid methods involving GAs that have been applied to data mining problems. First, we provide a brief background with several important definitions on genetic algorithms, hybrid algorithms and operators for improving its performance. In the Main Trust section, we present a survey of several hybrid algorithms, which use GAs as search heuristic, and their main applications in data mining. Finally, we finish the chapter giving some conclusions and future trends.
TopBackground
Genetic Algorithms
Genetic algorithms are robust problems’ solving techniques based on natural evolution processes. They are population-based algorithms, which encode a set of possible solutions to the problem, and evolve it through the application of the so called genetic operators (Goldberg, 1989). The standard genetic operators in a GA are:
- •
Selection, where the individuals of a new population are selected from the old one. In the standard implementation of the Selection operator, each individual has a probability of surviving for the next generation proportional to its associated fitness (objective function) value. This procedure of selection is usually called roulette wheel selection mechanism.
- •
Crossover, where new individuals are searched starting from couples of individuals in the population. Once the couples are randomly selected, the individuals have the possibility of swapping parts of themselves with its couple, the probability of this happens is usually called crossover probability, P_c.
- •
Mutation, where new individuals are searched by randomly changing bits of current individuals with a low probability P_m (probability of mutation).