Yanushkevich S.N., Wang P.S.P., Gavrilova M.L., Srihari S.N. (eds.) Image Pattern Recognition. Synthesis and Analysis in Biometrics
Подождите немного. Документ загружается.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
298 Carlos A. Coello Coello
Table 12.3. The basic selection schemes of genetic algorithms.
Scheme Definition
Proportionate
Selection
This term is used generically to describe several selection schemes that
choose individuals for birth according to their objective function values
f. In these schemes, the probability of selection p of an individual from
the ith class in the tth generation is calculated as
p
i,t
=
f
i
k
j=1
m
j,t
f
j
(12.1)
where k classes exist and the total number of individuals sums
to n. Several methods have been suggested for sampling this
probability distribution, including Monte Carlo or roulette wheel
selection
[
60
]
, stochastic remainder selection
[
11,12
]
,andstochastic
universal selection
[
8,49
]
.
Ranking
Selection
In this scheme, proposed by Baker
[
7
]
the population is sorted from
best to worst, and each individual is copied as many times as it
can, according to a non-increasing assignment function, and then
proportionate selection is performed according to that assignment.
Tournament
Selection
The population is shuffled and then is divided into groups of k elements
from which the best individual (i.e. the fittest) will be chosen. This
process has to be repeated k times because on each iteration only m
parents are selected, where
m =
population size
k
For example, if we use binary tournament selection (k = 2), then
we have to shuffle the population twice, since at each stage half of
the parents required will be selected. The interesting property of this
selection scheme is that we can guarantee multiple copies of the fittest
individual among the parents of the next generation.
Steady State
Selection
This is the technique used in Genitor
[
92
]
, which works individual
by individual, choosing an offspring for birth according to linear
ranking, and choosing the currently worst individual for replacement.
In steady-state selection only a few individuals are replaced in each
generation: usually a small number of the least fit individuals are
replaced by offspring resulting from crossover and mutation of the
fittest individuals. This selection scheme is normally used in evolving
rule-based systems in which incremental learning (and remembering
what has already been learned) is important and in which members
of the population collectively (rather than individually) solve the
problem at hand
[
71
]
.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Evolutionary Algorithms: Basic Concepts and Applications in Biometrics 299
10101101 11101110
10101110
11101101
Cross-point Cross-point
Descendants
Fig. 12.2. Use of a single-point crossover between two chromosomes. Notice that each
pair of chromosomes produces two descendants for the next generation. The cross-point
may be located at the string boundaries, in which case the crossover has no effect and
the parents remain intact for the next generation.
Once an appropriate encoding has been chosen, we apply a fitness
function to each one of these chromosomes in order to measure the
quality of the solution encoded by the chromosome. Knowing each
chromosome’s fitness, a selection process takes place to choose the
individuals (presumably, the fittest) that will be the parents of the following
generation. The most commonly used selection schemes are described in
Table 12.3
[
46
]
.
After being selected, crossover takes place. During this stage, the
genetic material of a pair of individuals is exchanged in order to create the
population of the next generation. There are three main ways of performing
crossover:
(1) Single-point crossover. A position of the chromosome is randomly
selected as the crossover point as indicated in Fig. 12.2.
(2) Two-point crossover. Two positions of the chromosome are randomly
selected as to exchange chromosomic material, as indicated in Fig. 12.3.
(3) Uniform crossover. This operator was proposed by Syswerda
[
87
]
and
can be seen as a generalization of the two previous crossover techniques.
In this case, for each bit in the first offspring it decides (with some
probability p) which parent will contribute its value in that position.
The second offspring would receive the bit from the other parent.
See an example of 0.5-uniform crossover in Fig. 12.4. Although for
some problems uniform crossover presents several advantages over other
crossover techniques
[
87
]
, in general, one-point crossover seems to be a
bad choice, but there is no clear winner between two-point and uniform
crossover
[
71,69
]
.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
300 Carlos A. Coello Coello
101 101 11101110
101011
111 1
Descendants
01
0110
Cross-points Cross-points
10
Fig. 12.3. Use of a two-point crossover between two chromosomes. In this case the
genes at the extremes are kept, and those in the middle part are exchanged. If one of
the two cross-points happens to be at the string boundaries, a single-point crossover will
be performed, and if both are at the string boundaries, the parents remain intact for the
next generation.
101011 10
10101100
1
1101110
10101101
11
101110
11101111
P a r e n t 2P a r e n t 1
P a r e n t 2P a r e n t 1
C h i l d 1
C h i l d 2
Fig. 12.4. Use of 0.5-uniform crossover (i.e. adopting a 50% probability of crossover)
between two chromosomes. Notice how half of the genes of each parent go to each of the
two children. First, the bits to be copied from each parent are selected randomly using
the probability desired, and after the first child is generated, the same values are used
to generate the second child, but inverting the source of procedence of the genes.
Mutation is another important genetic operator that randomly changes
a gene of a chromosome. If we use a binary representation, a mutation
changes a 0 to 1 and viceversa. An example of how mutation works
is displayed in Fig. 12.5. This operator allows the introduction of
new chromosomic material to the population and, from the theoretical
perspective, it assures that — given any population — the entire search
space is connected
[
13
]
.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Evolutionary Algorithms: Basic Concepts and Applications in Biometrics 301
Mutation points
Original string
String after mutation
10
1
10
01
1
1
0
01
1
01
1
Fig. 12.5. An example of mutation using binary representation.
If we knew in advance the final solution, it would be trivial to determine
how to stop a genetic algorithm. However, as this is not normally the case,
we have to use one of the two following criteria to stop the GA: either give
a fixed number of generations in advance, or verify when the population
has become homogeneous (i.e. all or most of the individuals have the same
fitness). Traditionally,
Genetic algorithms do not have a self-adaptation mechanism. Therefore,
one of their main drawbacks is that their parameters tend to be fine-tuned
in an empirical manner (i.e., by trial-and-error).
Some representative applications of genetic algorithms are the following
[
45,32,5
]
: data mining, optimization (structural, combinatorial, etc.),
pattern recognition, and robot motion planning.
12.2.4. Genetic Programming
One of the original goals of artificial intelligence (AI) was the automatic
generation of computer programs that could produce a desired task given
a certain input. During several years, such a goal seemed too ambitious
since the size of the search space increases exponentially as we extend the
domain of a certain program and, consequently, any technique will tend to
produce programs that are either invalid or highly inefficient.
Some early evolutionary algorithms were attempted in automatic
programming tasks, but they were unsuccessful and were severely criticized
by some AI researchers
[
35
]
. Over the years, researchers realized that the
key issue for using evolutionary algorithms in automatic programming tasks
was the encoding adopted. In this regard, John Koza
[
66
]
suggested the
use of a genetic algorithm with a tree-based encoding. In order to simplify
the implementation of such an approach, the original implementation of
this sort of approach (which was called “genetic programming”) was done
under LISP, taking advantage of the fact that such programming language
has a built-in parser.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
302 Carlos A. Coello Coello
The tree-encoding adopted by Koza obviously requires of
different alphabets and specialized operators for evolving
randomly generated programs until they become 100%
valid. Note however, that the basic principles of this
technique may be generalized to any other domain and,
in fact, genetic programming has been used in a wide
variety of applications
[
66
]
. The trees used in genetic
programming consist of both functions and terminals.
The functions normally adopted are the following
[
66
]
:
Arithmetic operations (e.g., +, -, ×, ÷ )
Mathematical functions (e.g., sine, cosine, logarithms, etc.)
Boolean Operations (e.g., AND, OR, NOT)
Conditionals (IF-THEN-ELSE)
Loops (DO-UNTIL)
Recursive Functions
Any other domain-specific function
Terminals are typically variables or constants, and can be seen as
functions that take no arguments. An example of a chromosome that uses
the functions F = {AND, OR, NOT} and the terminals T = {A0, A1} is
shown in Fig. 12.6.
NOT
NOT
A1
A0
A0
A1
AND
OR
AND
Fig. 12.6. An example of a chromosome used in genetic programming.
OR
NOT
AND
A1 A0 A1 A1
OR
NOT
A0
A0
NOT NOT
A1
AND
OR
1
2
3
5
4
6
3
2
1
6
9
4
5
8
10
7
Fig. 12.7. The tree nodes are numbered before applying the crossover operator.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Evolutionary Algorithms: Basic Concepts and Applications in Biometrics 303
OR
A1
OR
NOT
A0
OR
NOT
A1
NOT
A1NOT
AND
AND
A0
A1
A0
Fig. 12.8. The two offspring generated after applying the crossover operator.
Crossover can be applied by numbering the tree nodes corresponding to
the two parents chosen (see Fig. 12.7) and (randomly) selecting a point in
each of them such that the subtrees below such point are exchanged (see
Fig. 12.8, where we assume that the crossover point for the first parent is
2 and for the second is 6). Typically, the sizes of the two parent trees will
be different as in the example previously shown. It is also worth noticing
that if the crossover point is the root of one of the parent trees, then the
whole chromosome will become a subtree of the other parent. This allows
the incorporation of subroutines in a program. It is also possible that the
roots of both parents are selected as crossover points. Should that be the
case, the crossover operator will have no effect and the offspring will be
identical to their parents.
Normally, genetic programming implementations impose a limit on the
maximum depth that a tree can reach, as to avoid the generation (as a
byproduct of crossover and mutation) of trees of very large size that could
produce a memory overflow
[
9
]
.
A0
A1
AND
OR
A0
AND A0
OR
A1NOT
A1
1
2
34
5
AfterBefore
+
+
AA
B
C
(E0)
*
Before After
(a) (b)
Fig. 12.9. An example of mutation in genetic programming (a) and of encapsulation in
genetic programming (b).
Mutation in genetic programming takes place through a (random)
selection of a certain node tree. The subtree below the chosen node is
replaced by another tree which is randomly generated. Fig. 12.9(a) shows
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
304 Carlos A. Coello Coello
an example of the use of this operator (the mutation point in this example
is node 3).
In genetic programming is also possible to protect or “encapsulate” a
certain subtree which we know to contain a good building block, as to
avoid that it is destroyed by the genetic operators. The selected subtree
is replaced by a symbolic name that points to the real location of the
subtree. Such subtree is separately compiled and linked to the rest of the
tree in an analogous way to the external classes of object oriented languages.
Figure 12.9(b) shows an example of encapsulation in which the right subtree
isreplacedbythename(E0).
Finally, genetic programming also provides mechanisms to destroy
a certain percentage of the population such that we can renovate the
chromosomic material after a certain number of generations. This
mechanism, called execution, is very useful in highly complex domains
in which our population may not contain a single feasible individual even
after a considerably large number of generations.
12.3. A More General View of Evolutionary Algorithms
Despite the obvious differences and motivations of each of the aforemen-
tioned paradigms, the trend in the last few years has been to decrease the
differences among the paradigms and refer (in generic terms) simply to
evolutionary algorithms when talking about any of them.
In Table 12.4, the basic components to implement an EA in order to
solve a problem
[
69,32
]
are given. Also, it is shown that EAs differ from
traditional search techniques in several ways
[
13
]
.
It is worth indicating that the ever-growing popularity of evolutionary
algorithms in a variety of application domains tends to be related to
their good reputation as “optimizers” (either for single-objective or for
multi-objective problems
[
75,16
]
). This is remarkable if we consider
that some of them (namely, genetic algorithms) were not originally
proposed for that type of application and that their use in optimization
tasks has been questioned by some well-established researchers in the
evolutionary computation community
[
61
]
. Apparently, the reported
success of evolutionary algorithms has resulted sufficiently convincing for
practitioners and therefore their popularity
[
6
]
.
12.4. Some Applications in Biometrics
Since their very inception, several researchers have attempted to use
evolutionary algorithms for tasks related to pattern recognition, image
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Evolutionary Algorithms: Basic Concepts and Applications in Biometrics 305
Table 12.4. Basic components to implement an EA and particular features of an EA.
Requirements of an EA Particular features of an EA
(1) A representation of the potential
solutions to the problem. The
selection of an appropriate encoding
scheme tends to be crucial for the
good performance of an EA
[
81
]
.
(2) A way to create an initial population
of potential solutions
(this is normally done randomly, but
deterministic approaches can also be
used).
(3) An evaluation function that plays
the role of the environment, rating
solutions in terms of their “fitness”.
The definition of a good fitness
function is also vital for having a
good performance.
(4) A selection procedure that chooses
the parents that will reproduce.
(5) Evolutionary operators that alter the
composition of children (normally,
crossover and mutation).
(6) Values for various parameters that
the evolutionary algorithm
uses (population size, probabilities
of applying evolutionary operators,
etc.).
• EAs do not require problem specific
knowledge
to carry out a search. However, if
such knowledge is available, it can
be easily incorporated as to make the
search more efficient.
• EAs use stochastic instead
of deterministic operators and appear
to be robust in noisy environments.
• EAs are conceptually simple and easy
to implement.
• EAs have a wide applicability.
• EAs are relatively simple to
parallelize.
• EAs operate on a population of
potential solutions at a time. Thus,
they are less susceptible to false
attractors (i.e. local optima).
processing, classification and machine learning
[
15,19,91,34,85,93,33,94
]
.
However, most of this early work was mainly focused on the algorithmic
development aspect rather than on an specific application. Thus, for some
time, there was relatively little research on the development of evolutionary
algorithms for specific biometric applications. This situation has changed in
the last few years
[
84
]
, although the use of other soft computing techniques
such as neural networks is still more common than the use of evolutionary
algorithms
[
58
]
.
Next, we will review a few case studies in this area which aim to provide
a general picture of the type of research being conducted nowadays. A
summary of these case studies is provided in Table 12.5.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
306 Carlos A. Coello Coello
Table 12.5. Applications of evolutionary algorithms in biometrics.
Physiological biometrics
Biometric Technique of EA
Fingerprints
In
[
48
]
, a coevolutionary genetic algorithm is proposed based
on an Enforced Sub-Populations technique
[
47
]
andona
mathematical technique called Lifting to find wavelets that are
specially adapted to a particular class of images.
Other researchers have also worked on the use of evolutionary
algorithms for solving other related problems such as optimizing
the alignment of a pair of fingerprint images
[
3
]
, estimation of the
ridges in fingerprints
[
1
]
and fingerprint classification
[
77
]
.
Face
In
[
53
]
, a genetic algorithm-based approach has been proposed for
facial modeling from an uncalibrated face image using a flexible
generic parameterized facial model.
Other researchers have also used evolutionary algorithms for
related problems, such as human face detection
[
95
]
, automated
face recognition
[
89,59
]
, and human posture estimation
[
80
]
,
among others.
Palmprints
In
[
65
]
, a cooperative coevolutionary genetic algorithm is used for
hand-based feature selection. The outcome of the approach is a
number of good (i.e. tight and well-separated) clusters which exist
in the smallest possible feature space.
Behavioral biometrics
Signature
In
[
90
]
, genetic programming has been adopted for handwritten
character recognition. Fitness function consists of the weighted
sum of errors produced by each of the programs generated (zero-
argument functions, which consists of the features to be extracted
from the images that are presented as test cases). Each program
also receives a penalty when there is a lack of diversity.
Other researchers have also used evolutionary algorithms for
related problems, such as unsupervised learning in handwritten
character recognition tasks
[
72
]
, design of a voting system to select
from among multiple classifiers adopted for cursive handwritten
text recognition
[
50
]
, and interpretation of characters for ebooks
[
68
]
.
Keystroke
dynamics
In
[
96
]
, a combination of a support vector machine and a genetic
algorithm is used for keystroke dynamics identity verification.
The authors also propose the use of an ensemble model based on
feature selection to alleviate the defficiencies of a small training
data set.
Voice
In
[
43
]
a locally recurrent probabilistic neural network was
adopted for speaker verification. The approach is based on a
three-step training procedure, from which the third step was
done with differential evolution (an evolutionary algorithm that
is highly competitive for numerical optimization tasks in which
the decision variables are real numbers).
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Evolutionary Algorithms: Basic Concepts and Applications in Biometrics 307
12.4.1. Fingerprint Compression
Grasemann and Miikulainen
[
48
]
proposed a coevolutionary genetic
algorithm based on a technique known as Enforced Sub-Populations
[
47
]
and on a mathematical technique called Lifting to find wavelets that are
specially adapted to a particular class of images. This approach was tested
in the fingerprint domain against standard wavelets (including a winner
of a competition held by the FBI in the early 1990s) to find the best
wavelet fingerprint compression. The evolutionary algorithm outperformed
the algorithm used by the FBI, which attracted a lot of attention from
the media and from the evolutionary computation community, because this
was a clear example of how an evolutionary design can outperform a human
design.
Enforced sub-populations refers to an approach in which a number of
populations of individual neurons (from a neural network) are evolved in
parallel. In the evaluation phase, this approach repeatedly selects one
neuron from each subpopulation to form candidate neural networks. The
fitness of a particular neuron is the average fitness of all the neural networks
in which it participated. This same idea was used in this work, but evolving
different wavelets instead. These wavelets are constructed using the so-
called lifting step
[
86
]
, which is a finite filter that can generate new filter
pairs from existing pairs.
To validate the approach, the authors used 80 available images. The
size of each image was 300 by 300 pixels, at 500 dpi resolution. Each of
them was used once as a test image and 79 times as part of the training
set. In the experiments performed, the best wavelet found after each
generation was used to compress the test image. It turns out that after
only 50 generations, the evolutionary algorithm was able to produce results
that outperformed the wavelets used by the FBI. Overall, the evolutionary
algorithm introduced between a 15% and a 20% decrease in the space
requirements for the same image quality. This is very significant if we
consider that the FBI has over 50 million fingerprint cards on file and has
recently started to store them electronically (the FBI is currently digitizing
and compressing between 30,000 and 50,000 new cards every day).
12.4.2. Facial Modeling
Ho and Huang
[
53
]
proposed a genetic algorithm-based approach for
facial modeling from an uncalibrated face image using a flexible generic
parameterized facial model (FGPFM). The authors adopted the so-called
“Intelligent Genetic Algorithm” IGA
[
54
]
(which they had previously
proposed) to tackle this problem. The approach of the authors consists