Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Sancho Salcedo-Sanz (Universidad de Alcalá, Spain), Gustavo Camps-Valls (Universitat de València, Spain) and Carlos Bousoño-Calzón (Universidad Carlos III de Madrid, Spain)

Copyright: © 2009
|Pages: 6

DOI: 10.4018/978-1-60566-010-3.ch154

Chapter Preview

TopG**enetic 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.

TopGenetic 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*).

Search this Book:

Reset