[ Pobierz całość w formacie PDF ]
A Taxonomy for the Crossover Operator
for Real-Coded Genetic Algorithms: An
Experimental Study
F. Herrera,
1,
*
M. Lozano,
1,†
A. M. S´ nchez
2,‡
1
Department of Computer Science and Artificial Intelligence, University of
Granada, 18071, Granada, Spain
2
Departamento de Inform´ tica, Escuela Superior de Ingenier´a Inform´ tica,
University of Vigo, 32004, Orense, Spain
The main real-coded genetic algorithm (RCGA) research effort has been spent on developing
efficient crossover operators. This study presents a taxonomy for this operator that groups its
instances in different categories according to the way they generate the genes of the offspring
from the genes of the parents. The empirical study of representative crossovers of all the
categories reveals concrete features that allow the crossover operator to have a positive influence
on RCGA performance. They may be useful to design more effective crossover models. © 2003
Wiley Periodicals, Inc.
1. INTRODUCTION
Genetic algorithms (GAs) are adaptive methods based on natural evolution
that may be used for search and optimization problems. They process a population
of search space solutions with three operations: selection, crossover, and mutation.
1–3
Under their initial formulation, the search space solutions are coded using the
binary alphabet; however, other coding types have been taken into account for the
representation issue such as real coding. The real coding approach seems partic-
ularly natural when tackling optimization problems of parameters with variables in
continuous domains. A chromosome is a vector of floating point numbers in which
their size is kept the same as the length of the vector, which is the solution to the
problem. GAs based on real-number representation are called real-coded GAs
(RCGAs).
4,5
*
Author to whom all correspondence should be addressed: e-mail: herrera@decsai.ugr.es.
†
e-mail: lozano@decsai.ugr.es.
‡
e-mail: amlopez@uvigo.es.
INTERNATIONAL JOURNAL OF INTELLIGENT SYSTEMS, VOL. 18, 309 –338 (2003)
© 2003 Wiley Periodicals, Inc. Published online in Wiley InterScience
(www.interscience.wiley.com). • DOI 10.1002/int.10091
310
HERRERA, LOZANO, AND S
´
NCHEZ
Recently, there has been an increasing interest in solving real-world optimi-
zation problems using RCGAs. Some of their applications include chemometric
problems,
6
neural networks,
7,8
aerospace design,
9 –12
biotechnology,
13
con-
trol,
14 –16
economic,
17
signal processing,
18
microware,
19 –21
industrial electron-
ics,
22
industrial engineering,
23,24
tomography,
25
water resources management,
26
and constrained parameter optimization problems.
3
The crossover operator is a method for sharing information between chromo-
somes. Generally, it combines the features of two parent chromosomes to form two
offspring, with the possibility that good chromosomes may generate better ones. It
has always been regarded as the primary search operator in GAs
27–29
because it
exploits the available information from the population about the search space.
Moreover, it is one of the components to consider for improving the behavior of the
GA.
30
The main RCGA research effort has been spent on developing efficient
crossover operators,
4
and as a result, many different instances have been proposed.
At this point, a taxonomy for this operator becomes attractive because it will reveal
and allow us to find properties that are needed in an effective real-parameter
crossover operator. In this study, we propose a taxonomy that groups the models
for this operator in different categories according to the way they generate the
genes of the offspring from the genes of the parents. Furthermore, we perform an
empirical study of representative instances of all the categories, which provides
some clues on the key features that have a positive influence on the crossover
behavior.
Section 2 introduces some issues related to real-parameter crossover opera-
tors. In Section 3, we present the taxonomy for these operators. In Section 4, we
describe an experimental study aimed at determining the goodness associated with
the different groups. Section 5 includes our conclusions and summarizes a few new
promising studies on the topic.
2. CROSSOVER OPERATORS FOR RCGAs
In this section, we deal with the main aspects of the crossover operators for
RCGAs. In Section 2.1, we explain the three mechanisms involved in the appli-
cation of the crossover operator. This is useful to establish the particular features
of the crossover operators analyzed in this study. In Section 2.2, we define different
real-parameter crossover instances that appear in the GA literature. In Section 2.3,
we examine the availability of these operators to adopt different exploration or
exploitation degrees. Finally, in Section 2.4, we review some attempts made for
specifying guidelines for the design of crossover operators for real coding.
2.1. The Crossover Operator
The application of the crossover operator is performed by means of three
different mechanisms:
REAL-CODED GENETIC ALGORITHMS
311
(1) Mating selection mechanism (MSM). The MSM determines the way the chromosomes
are mated for applying the crossover to them. The most common MSM pairs the
parents randomly. However, other approaches have appeared.
31–33
(2) Offspring generation mechanism (OGM). The OGM produces new chromosomes from
each set of parents formed by the MSM. All the OGMs proposed for the binary coding
may be adapted for working under the real coding. However, this coding offers the
possibility of defining a wide variety of special OGMs that take advantage of its
numerical nature. Generally, they calculate the value of the genes corresponding to
each position in the offspring by combing numerically the values of the genes of the
parents in this position.
(3) Offspring selection mechanisms (OSM). Between all the offspring generated for each
set of parents, this mechanism chooses the ones that will be population members. One
of the most used OSMs selects the best offspring as elements for the next popula-
tion.
34 –36
Usually, the crossover operator is applied to pairs of chromosomes, generating
two offspring for each one of them, which are introduced in the population.
1
However, multiparent crossover operators have been proposed, which combine the
features of more than two parents for generating the offspring.
34,37–39
Furthermore,
crossover operators with multiple descendents have been presented,
34 –36,40 – 42
which produce more than two offspring for each group of parents. In this case, the
OSM limits the number of offspring that will be population members. All of the
offspring may be created using the same OGM
34,42
or by means of different
2.2. Crossover Operators for Real Coding
Let us assume that
C
1
(
c
1
, ...,
c
1
) and
C
2
(
c
2
, ...,
c
2
) are two
chromosomes that have been selected to apply the crossover operator to them. In
the following list we describe the operation of different crossover operators for
RCGAs and show their effects:
Simple crossover.
1,2
A position
i
{1, 2, . . . ,
n
1} is chosen randomly and two new
chromosomes are built:
H
1
c
1
,
c
1
,...,
c
i
1
,
c
i
1
,...,
c
2
H
2
c
2
,
c
2
,...,
c
i
2
,
c
i
1
,...,
c
1
Two-point crossover.
43
Two-point crossover is a generalization of the simple crossover.
Two points of crossover are selected randomly (
i
,
j
{1, 2, . . . ,
n
1} with
i
j
),
Figure 1.
Arithmetical crossover with different values for
.
OGMs.
35
We should emphasize that this study relies on crossover operators for real
coding that require only two parents.
2
1
312
HERRERA, LOZANO, AND S
´
NCHEZ
Figure 2.
Geometrical crossover with different values for
.
and the segments of the parent, defined by them, are exchanged for generating two
offspring:
H
1
c
1
,
c
1
,...,
c
i
2
,
c
i
1
2
,...,
c
j
2
,
c
j
1
1
,...,
c
1
H
2
c
2
,
c
2
,...,
c
i
1
,
c
i
1
1
,...,
c
j
1
,
c
j
1
2
,...,
c
2
Uniform crossover.
44
Two offspring are created,
H
k
(
h
k
, ...,
h
i
k
, ...,
h
k
),
k
1, 2.
The value of each gene in the offspring is determined by the random uniform choice of the
values of this gene in the parents:
h
i
k
c
i
1
if
u
0
c
i
2
if
u
1
u
being a random number that can have a value of zero or one.
Arithmetical crossover.
3
Two offspring are produced (Figure 1),
H
k
(
h
k
, ...,
h
i
k
, ...,
h
k
),
k
1, 2, where
h
i
1
c
i
1
(1
)
c
i
2
and
h
i
2
c
i
2
(1
)
c
i
1
,
where
[0, 1].
Geometrical crossover.
45
Two offspring are built (Figure 2),
H
k
(
h
k
, ...,
h
i
k
, ...,
h
k
),
k
1, 2, where
h
i
1
c
i
1
1
, with
[0, 1].
BLX-
(Figure 3).
46,47
Two offspring are generated,
H
k
(
h
k
, ...,
h
i
k
, ...,
h
k
),
k
1, 2, where
h
i
k
is a randomly (uniformly) chosen number from the interval [
C
min
I
,
C
max
I
], where
C
max
max{
c
i
1
,
c
i
2
},
C
min
min{
c
i
1
,
c
i
2
}, and
I
C
max
C
min
.
BLX-
-
(Figure 4).
48
Let’s suppose that
C
1
is the parent with best fitness. Then, two
offspring are produced,
H
k
(
h
k
, ...,
h
i
k
, ...,
h
k
),
k
1, 2, where
h
i
k
c
i
1
c
i
2
l
and
h
i
2
c
i
2
is a randomly
(uniformly) chosen number from the interval [
c
i
1
I
,
c
i
2
I
]if
c
i
1
c
i
2
, or from
I
] otherwise.
Wright’s heuristic crossover (Figure 5).
36
Let’s assume that the fitness of
C
1
is better than
the one of
C
2
. Then, two offspring are generated,
H
k
(
h
k
, ...,
h
i
k
, ...,
h
k
),
k
1,
2, where
h
i
k
I
,
c
i
2
u
(
c
i
1
c
i
2
)
c
i
1
and
u
is a random number belonging to [0, 1].
Linear BGA crossover (Figure 6).
49
Under the same consideration as mentioned previ-
r
i
, where the minus sign is chosen with a probability of 0.9,
r
i
0.5
(
b
i
a
i
),
¥
k
0
c
i
1
15
k
2
k
, where
i
{0, 1} is randomly generated with
p
(
i
c
i
1
)/
C
1
C
2
].
Simulated binary crossover (Figure 7):
4,50
Two offspring are generated,
H
k
(
h
k
, ...,
h
i
k
, ...,
h
k
),
k
1, 2, where
h
i
1
1
2
1
k
c
i
1
1
k
c
i
2
and
h
i
2
1
2
1
k
c
i
1
1
k
c
i
2
,
Figure 3.
BLX-
.
[
c
i
2
ously,
h
i
k
1)
1/16 and
[(
c
i
2
REAL-CODED GENETIC ALGORITHMS
313
Figure 4.
BLX-
-
.
k
(
0) is a sample from a random number generator having the density
1
2
1
,
if 0
1
p
1
2
1
1
2
,
if
1
This distribution can be obtained easily from a uniform
u
(0, 1) random number source by
the transformation
2
u
1/
1
if
u
0, 1
1
2
u
2
1
u
1/
1
if
u
0, 1
1
2
Fuzzy recombination (FR) (Figure 8).
51
Two offspring are produced,
H
k
(
h
k
, ...,
h
i
k
, ...,
h
k
),
k
1, 2. The probability that the
i
th gene in an offspring has the value
i
is given by the distribution
p
(
i
)
{
(
c
i
1
),
(
c
i
2
)} where
(
c
i
1
) and
(
c
i
2
) are triangular
probability distributions having the features shown in Figure 8 (
c
i
1
c
i
2
is assumed).
Linear crossover (LX) (Figure 9):
36
Three offspring,
H
k
(
h
k
, ...,
h
i
k
, ...,
h
k
),
k
1, 2, 3, are calculated:
3
2
c
i
2
With this type of crossover an OSM is applied, which chooses the two most promising
offspring of the three to substitute their parents in the population.
Max-Min-arithmetical crossover (MMAX) (Figure 10).
35
h
i
1
1
2
c
i
1
1
2
c
i
2
,
h
i
2
3
2
c
i
1
1
2
c
i
2
, and
h
i
3
1
2
c
i
1
H
k
(
h
k
, ...,
h
i
k
, ...,
h
k
),
with
k
1, 2, 3, 4, are generated:
h
i
1
c
i
1
1
c
i
2
,
h
i
2
c
i
2
1
c
i
1
,
h
i
3
min
c
i
1
,
c
i
2
, and
h
i
4
max
c
i
1
,
c
i
2
The two best chromosomes are selected as final descendants for the new population.
Dynamic crossover (Figure 11).
52
Four offspring are generated because the Dubois
-crossover,
-crossover,
-crossover, and
-crossover were applied to them (see
Appendix A). An OSM is used, which chooses the two most promising offspring of the
four to substitute their parents in the population.
Figure 5.
Wright’s heuristic crossover.
[ Pobierz całość w formacie PDF ]