Digital Signal Processing Reference
In-Depth Information
8.2 Genetic Algorithms
GAs are optimization tools based on the synergy between the idea of nat-
ural selection and the framework established by modern genetics [22]. In
very simple terms, GAs can be considered as a populational optimization
tool founded on three conceptual pillars: existence of a selection mechanism,
possibility of information interchange between solutions, and existence of
spurious changes in their parameters.
∗
The first pillar is the main point of
contact between the GA and the problem to be solved, since it is the cost
function to be optimized that determines the
fitness
of each solution. The sec-
ond pillar is related to the idea of
crossover
. Finally, the third pillar is the
essence of the idea of
mutation
. These concepts are discussed in more detail
in the sequel.
8.2.1 Fundamental Concepts and Terminology
An optimization problem is characterized by the existence of a cost function
and certain number of free parameters with respect to which this function
is to be optimized, in order to provide the best parameter configuration or,
at least, a satisfactory one. The operation of an optimization algorithm can
be understood, in this context, as a continuous process of sampling the cost
function, i.e., generating/evaluating solutions in a search space, which can
be defined as the space generated by all possible instances of the free param-
eters. The modus operandi of an algorithm is thus related to the manner
whereby it performs this sampling [308].
In the case of GAs, the tonic is to conceive the optimization task as being
the results of the operation of evolutionary mechanisms. To allow this, a first
step is to relate the cost function to a fitness function, the role of which is
to create a numerical index to quantify the adequacy of a certain individual,
within the simulated evolution framework, to the environment. As, from
the standpoint of the optimization task, the fittest means simply the best
possible solution, the fitness function can be simply the cost function itself.
However, it can also be, if convenient, a mapping of the cost function. This
can be done, for instance, if we deal with a minimization problem and need
to translate this problem into the evolutionary framework, which typically
assumes higher fitness values to be associated with better solutions.
Each solution to the given problem is assumed to correspond to an indi-
vidual, and the parameters of a given solution must be somehow coded to
correspond to its genotype. Having this in view, we freely interchange the
∗
This description encompasses, in a certain sense, a classical GA, for, modernly, it is acceptable
to describe, in some cases, an evolutionary algorithm without a recombination operator as a
GA. Notice also that it would have been possible to define the threefold foundation of a GA in
terms of selection, reproduction, and variability.
