Instance Selection Using Evolutionary Algorithms: An Experimental Study - Advanced Techniques in Knowledge Discovery and Data Mining - page 136

and (sometimes) recombination to evolve toward increasingly better fitness values
of the individuals. The fitness of an individual reflects its objective function value
with respect to a particular objective function to be optimized. The mutation
operator introduces innovation into the population by generating variations of
individuals, and the recombination operator typically performs an information
exchange between different individuals from a population. The selection operator
imposes a driving force on the process of evolution by preferring better
individuals to survive and reproduce when the members of the next generation are
selected.
The reason for a great part of the success of EAs is their ability to exploit the
information accumulated about an initially unknown search space in order to bias
subsequent searches into useful subspaces, i.e., their adaptation. This is their key
feature, particularly in large, complex, and poorly understood search spaces,
where classical search tools (enumerative, heuristic, etc.) are inappropriate. In
such cases, they offer a valid approach to problems requiring efficient and
effective search techniques.
Next, we describe the four EA models that will be used in this chapter as
evolutionary IS algorithms. They are:
z two standard GA models: the generational GA (GGA) and the steady-state
GA (SGA) [36];
z the CHC algorithm [12], which has been tested in many GA works against
other different GA approaches, giving better results, especially on hard
problems [37]; and
z the population based incremental learning (PBIL) algorithm [5], which is an
algorithm that uses a probabilistic model for driving the search toward the
most promising regions. This idea constitutes a profitable research topic in the
EA field by using probabilistic models [29].
5.4.1 Generational Genetic Algorithm (GGA) [18], [16]
GAs are general purpose search algorithms that use principles inspired by natural
genetic populations to evolve solutions to problems. The basic idea is to maintain
a population of chromosomes, which represent candidate solutions to the concrete
problem, that evolves over successive iterations (generations) through a process of
competition and controlled variation. Each chromosome in the population has an
associated fitness to determine which chromosomes are to be used to form new
ones in the competition process. This is called selection. The new ones are created
using genetic operators such as crossover and mutation .
Although there are many possible variants of the basic GA, the classical model
is the GGA, which consists of three operations:
1. Evaluation of individual fitness.
2. Formation of an intermediate population through a selection mechanism.
3. Recombination through crossover and mutation operators.