Two-Loop Real-Coded Genetic Algorithms with Adaptive Control of Mutation Step Sizes.
Genetic algorithms 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. 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 particularly natural when tackling optimization problems of parameters with variables in continuous domains.A problem in the use of genetic algorithms is premature convergence, a premature stagnation of the search caused by the lack of population diversity. The mutation operator is the one responsible for the generation of diversity and therefore may be considered to be an important element in solving this problem. For the case of working under real coding, a solution involves the control, throughout the run, of the strength in which real genes are mutated, i.e., the step size.This paper presents TRAMSS, a Two-loop Real-coded genetic algorithm with Adaptive control of Mutation Step Sizes. It adjusts the step size of a mutation operator applied during the inner loop, for producing efficient local tuning. It also controls the step size of a mutation operator used by a restart operator performed in the outer loop, for reinitializing the population in order to ensure that different promising search zones are focused by the inner loop throughout the run. Experimental results show that the proposal consistently outperforms other mechanisms presented for controlling mutation step sizes, offering two main advantages simultaneously, better reliability and accuracy.
INTRODUCTION
.
Genetic algorithms (GAs) are general purpose search algorithms which use principles inspired by
natural genetic populations to evolve solutions for problems ([Goldberg (1989a), Holland (1992)]).
The basic idea is to maintain a population of chromosomes, which represent candidate solutions
for the specific problem, that evolves over time through a process of competition and controlled
variation. The following bibliography may be examined for a more detailed discussion about GAs:
[B-ack (1996), B-ack et al. (1997), Goldberg (1989a), Holland (1992), Michalewicz (1992)].
Under their initial formulation, the search space solutions are coded using the binary alpha-
bet. However, other coding types have been considered for the representation issue, such as real
coding, which would seem particularly natural when tackling optimization problems of parameters
with variables on continuous domains. Then a chromosome is a vector of floating point numbers,
the size of which is kept the same as the length of the vector, which is the solution to the prob-
lem. GAs with this type of coding are called real-coded GAs (RCGAs) (see [Herrera et al. (1998),
Surry et al. (1996)]). There are other types of Evolutionary Algorithms (EAs), i.e., implementing
the idea of evolution ([B-ack (1996)]), which are based on real coding as well. These are Evolution
Strategies ([Schwefel (1995)]) and Evolutionary Programming ([Fogel (1995)]). This paper deals with
RCGAs.
Population diversity is crucial to a GA's ability to continue the fruitful exploration of the search
space ([Li et al. (1992)]). If the lack of population diversity takes place too early, a premature
stagnation of the search is caused. Under these circumstances, the search is likely to be trapped in
a local optimum before the global optimum is found. This problem, called premature convergence,
has long been recognized as a serious failure mode for GAs ([Eshelman et al. (1991)]).
The mutation operator may be considered to be an important element for solving the premature
convergence problem, since it serves to create random diversity in the population ([Spears (1993)]).
Different techniques have been suggested for the control, during the GA's run, of parameters associated
with this operator, depending on either the current state of the search or other GA related
parameters ([Angeline (1995), Herrera et al. (1996b), Hinterding et al. (1997)]). They try to offer
suitable diversity levels for avoiding premature convergence and improving the results. In the case
of working with real coding, a topic of major importance involves the control of the proportion or
strength in which real-coded genes are mutated, i.e., the step size ([B-ack et al. (1996a)]).
The objective of this paper is to formulate a mechanism for the control of mutation step sizes for
RCGAs, which should handle and maintain population diversity that in some way helps produce good
chromosomes, i.e., useful diversity ([Mahfoud (1995)]). We present TRAMSS, a Two-loop RCGA
model with Adaptive control of Mutation Step Sizes that attempts to do this. It is made up by two
loops, an inner loop and an outer one:
Inner loop. It is designed for processing useful diversity in order to lead the population toward
the most promising search areas, producing an effective refinement on them. So, its principal
mission is to obtain the best possible accuracy levels.
The inner loop performs the selection process and fires the crossover and mutation operators.
Furthermore, for achieving its objective, it controls the step size of the mutation operator.
ffl Outer loop. It introduces new population diversity, after the inner loop reaches a stationary
point where there are no improvements, that helps the next one to reach better solutions.
Therefore, it attempts to induce reliability in the search process.
The outer loop iteratively performs the inner one, and later, it applies a restart operator that
reinitializes the population by mutating all genes, using a step size that is adapted as well,
throughout the runs for this loop.
For doing this, the paper is set up as follows: in Section 2, we analyze two mutation issues, the
ways in which the control of mutation step sizes may be made and the idea of the restart operator; in
Section 3, we present TRAMSS, in Section 4, we describe the experiments carried out for determining
the efficacy of the proposal; and finally, some conclusions are dealt with in Section 5.
In this Section, we explain two issues that will be included as important components in the conceptual
foundation of TRAMSS, mutation step size control (Subsection 2.1) and the restart operator
(Subsection 2.2).
2.1 Mutation Step Size Control
In general, the mechanisms presented for controlling parameters associated with EAs may be
assigned to the following three categories ([Hinterding et al. (1997)]):
ffl Deterministic Control. It takes place if the values of the parameters to be controlled are
altered by some deterministic rule, without using any feedback from the GA. Usually, a time-varying
schedule is used.
Adaptive Control. It takes place if there is some form of feedback from the GA that is used
to determine the direction and/or magnitude of the change to the parameters to be controlled.
The rules for updating parameters that are used by this type of control and, by the previous
one, are termed absolute adaptive heuristics ([Angeline (1995)]) and, ideally, capture some
lawful operation of the dynamics of the EA over a broad range of problems.
ffl Self-adaptive Control. The parameters to be controlled are encoded onto the chromosomes
of the individual and undergo mutation and recombination.
Next, we describe mechanisms for the control of mutation step sizes that belong to each one of
these categories.
2.1.1 Deterministic Step Size Control
In [Michalewicz (1992)], a mutation operator for RCGAs, called non-uniform mutation, was pre-
sented, which is based on the absolute adaptive heuristic "to protect the exploration in the initial
stages and the exploitation later". It implements this idea by decreasing the step size as the GA's
execution advances. Let us suppose that this operator is applied on a real-coded gene, x 2 [a; b]
(a; b 2 !), at generation t, and that T is the maximum number of generations, then it generates a
gene, x 0 , as follows:
ae
with - being a random number that may have a value of zero or one, and
where r is a random number from the interval [0; 1] and b is a parameter chosen by the user. This
function gives a value in the range [0; y] such that the probability of returning a number close to
zero increases as the algorithm advances. The size of the gene generation interval shall be smaller
with the passing of generations. This property causes this operator to make an uniform search in
the initial space when t is small, and very locally at a later stage, favoring local tuning.
The non-uniform mutation operator has been widely used, reporting good results ([Herrera et
al. (1996a), P'eriaux et al. (1995), Sefrioui et al. (1996)]). It is considered to be one of the most
suitable mutation operators for RCGAs ([Herrera et al. (1998)]).
2.1.2 Adaptive Step Size Control
The (1+1)-Evolution Strategy ((1+1)-ES) ([Schwefel (1995)]) is an EA that uses adaptive step
size control. It attempts to adapt its mutation step size to the problem according to the absolute
adaptive heuristic: "expand the step size when making progress, shrink it when stuck". This heuristic
will be denoted as E/S heuristic.
(1+1)-ES works using a continuous representation and a mutation operator based on normally
distributed modifications with expectation zero and given variance, oe, as the step size. It operates
on a vector of variables by applying mutation with identical oe to each variable, so generating a
descendant. The better of ancestor and descendant is considered as the new starting point. (1+1)-
ES applies the E/S heuristic for adapting oe by means of the 1/5 success rule. This rule uses the
results obtained by mutation in the last few generations: if more than one fifth of the mutation have
been successful, the step size is increased, otherwise it is decreased.
In [De La Maza et al. (1994)], a dynamic hill climbing algorithm is presented, which uses the
E/S heuristic as well. We would like to point out that the model proposed in this paper, TRAMSS,
uses important ideas that are present in this algorithm.
2.1.3 Self-Adaptive Step Size Control
In [Schwefel (1995)], an EA model, called (-Evolution Strategy ((-ES), is developed that
uses a mechanism for the self-adaptive step size control.
In (-ES, - parents create - offspring by means of recombination and mutation, and the best
offspring individuals are deterministically selected to replace the parents. Therefore, - should
be greater than -. The main quality of the algorithm is its ability to incorporate the standard
deviations (step sizes) and the correlation coefficients of normally distributed mutations into the
search process, such that adaptation not only takes place in the object variables, but also in these
parameters according to the current local topology of the search space. This property is called
self-adaptation ([B-ack (1996), Schwefel (1995)]). Self-adaptation exploits the indirect link between
favorable parameter values and fitness function values, being capable of adapting the parameters
implicitly, according to the topology of the objective function ([B-ack et al. (1996b)]).
Therefore, each population individual consists of three vectors, representing the
object variable, the standard deviation and the rotation angle values, respectively. The vector ~x has
dimensions, equal to the number of problem variables. The n oe dimensions of a vector ~oe can be
up to n (in this case, each object variable x different step size oe i associated to
it), and n ff can be up to (2\Deltan\Gamman oe )\Delta(n oe \Gamma1). n ff may be set to zero, indicating that the rotation angles
are not considered, as is assumed in this paper.
For more information about (-ES refer to [B-ack (1996), Schwefel (1995)]. Other mechanisms
for the self-adaptive step size control are to be found in [Fogel (1995), Hinterding (1995),
Ostermeier et al. (1994)].
2.2 Restart Operator
Premature convergence causes a drop in the GA's efficiency; the genetic operators do not produce
the feasible diversity to tackle new search space zones and thus the algorithm reiterates over the
known zones producing a slowing-down in the search process. Under these circumstances, resources
may be wasted by the GA searching an area not containing a solution of sufficient quality, where
any possible improvement in the solution quality is not justified by the resources used. Therefore,
resources would be better utilized in restarting the search in a new area, with a new population
et al. (1995)]). This is carried out by means of a restart operator. Next, we review some
different approaches to this operator.
ffl In [Goldberg (1989b)], it was suggested restarting GAs that have substantially converged, by
reinitializing the population using both randomly generated individuals and the best individual
from the converged population.
ffl In [Eshelman (1991)], upon convergence, the population is reinitialized by using the best individual
found so far as a template for creating a new population. Each individual is created
by flipping a fixed proportion (35%) of the bits of the template chosen at random without
replacement. If several successive reinitializations fail to yield an improvement, the population
is completely (100%) randomly reinitialized.
ffl In [Maresky et al. (1995)], a selectively destructive restart is proposed that does not completely
destroy the converged population; a percentage of the converged genes will survive untouched
to begin the next convergence stage. A probability of gene reinitialization, p r , is used: the
higher the rate, the more genes are initialized. Experiments carried out with some p r values
showed that different problems have different optimal reinitialization probabilities. This model
seems to provide an improved method for renewing genetic diversity in GA search. Intuitively,
the complete reinitialization of the population forgets the previous solutions, therefore it cannot
make use of previously discovered building blocks.
ffl In [Grefenstette (1992)], a similar mechanism, called partial hypermutation model, was in-
troduced, which replaces, at each generation, a percentage of the population by randomly
generated individuals. The percentage is called replacement rate. The intended effect is similar
to the one of the previous approach: to maintain a continuous level of exploration of the
search space, while trying to minimize disruption for the ongoing search.
Other important GA models based on the restart operator are ARGOT ([Shaefer (1987)]), Dynamic
parameter encoding ([Schraudolph et al. (1992)]) and Delta coding ([Whitley et al. (1991)]).
OF STEP SIZES.
In this Section, we present TRAMSS. It uses:
ffl An instance of the absolute adaptive E/S heuristic, presented in Subsection 2.1.2, for the
adaptive step size control of the mutation operator applied in the inner loop, and
ffl An instance of its opposite version, denoted here as S/E heuristic, for the adaptive step size
control of the mutation operator used by the restart operator that is executed by the outer
loop.
Next, in Subsection 3.1, we examine the application of the E/S and S/E heuristics for step size
control in RCGAs, and, in Subsections 3.2 and 3.3, we present the TRAMSS inner and outer loops,
respectively.
3.1 The E/S and S/E Heuristics
Let's suppose that an RCGA is applying a mutation operator with ffi being its step size. If a
stationary state is detected (the fitness of the best individual or the average fitness have not been
improved during the previous generations), there are two possible causes concerning ffi:
1. It is too high, which does not allow the convergence to be produced for obtaining better
individuals, or
2. It is too low, which induces a premature convergence, with the search process being trapped
in a local optimum.
On the one hand, if we decided to include an adaptive control of ffi based on the instance of the
E/S heuristic "increase ffi when making progress, decrease it when stuck", a stationary state caused
by (1) would be suitably tackled, since ffi would become lower, so introducing more convergence.
However, this heuristic would not be adequate if the stationary state is caused by (2), because it
would complicate the problem even more.
Precisely, this last circumstance will occur as the number of iterations increases. Since the RCGA
will find more difficulties for making progress, the natural trend of the instance of the E/S heuristic
will be to lead ffi to lower values, so producing more convergence. The possibility of this problem has
been claimed by some authors. For example, in [B-ack et al. (1995)], the following was stated about
the 1/5 success rule:
". the 1/5 success rule may cause premature stagnation of the search due to the deterministic
decrease of the step size whenever the topological situation does not lead to a
sufficiently large success rate".
For complex problems, this effect will probably become a premature convergence. This explains
the following claim, again about the 1/5 success rule ([Angeline (1995)]):
". this heuristic is especially useful in smooth multimodal environments of the type well
studied by the ES community but would be less applicable in discontinuous or extremely
rough environments".
On the other hand, if we are inclined to use the instance of the S/E heuristic "decrease ffi when
progress is made, increase it when there are no improvements", a stationary state produced by (2)
will be adequately attacked, since ffi would be greater and so, more diversity is introduced with the
possibility of escaping from the local optimum. However, an important problem may occur: as no
improvements are made by the RCGA, higher ffi values are tried, so introducing too much diversity
and not considering the possibility that convergence may be suffice for improving results.
So, all these facts show that serious problems may arise when the E/S and S/E heuristics are
applied separately. However, we think that a mechanism applying both of these heuristics would
handle the population diversity suitably to avoid the premature convergence problem and improve
the behavior of the search process.
The adaptive RCGA model proposed, TRAMSS, includes this idea: it uses the E/S heuristic for
adapting the step size of a mutation operator applied in the inner loop and the S/E heuristic for
adapting the step size of a mutation operator used by a restart operator performed in the outer loop.
3.2 TRAMSS Inner Loop
The inner loop performs the usual process (selection, crossover and mutation) over a number of
G, called time-interval between observations. Then, depending on the progress of the
population mean fitness found throughout these generations, it adjusts the step size of the mutation
operator, and calculates a new value for G. Next, we fully describe these steps where a minimization
problem is assumed.
Selection, Crossover and Mutation (Step 2.2). Over the time-interval between observations, G,
the following selection mechanism and crossover and mutation operators are applied.
ffl The selection probability calculation follows linear ranking ([Baker (1985)]), with
and the sampling algorithm is the stochastic universal sampling ([Baker (1987)]).
The elitist strategy ([De Jong (1975)]) is considered as well. It involves making sure that the
best performing chromosome always survives intact from one generation to the next. This
is necessary since it is possible that the best chromosome disappears, due to crossover or
mutation.
ffl We have tried different crossover operators, which are presented in Subsection 4.2.
ffl The mutation operator used is denoted as Mutation(ffi), where ffi is the step size (0 - ffi - 1).
This operator is defined as follows: If x 2 [a; b] is a gene to be mutated, then the gene resulting
from the application of this operator, x 0 , will be a random (uniform) number chosen from
Clearly, the higher ffi is, the greater changes on x are produced.
Adaptive Control of ffi (Step 2.3). After G generations, the ffi parameter used by the mutation
operator is adapted following a particular instance of the E/S heuristic: "increase ffi when observing
progress on -
f (population mean fitness), decrease it when stuck". ffi is kept in the interval [ffi min ; \Delta],
where \Delta is a parameter calculated by the outer loop, as described in Subsection 3.3, and ffi min
is the minimum threshold defined by the user (in experiments we assume a value of
1.0e-100).
The inner loop ends when ffi reaches the ffi min value. By finishing with a fine grained search
with small step sizes, we are sure that a local optimum, or the global one, will be located precisely
([De La Maza et al. (1994)]). It will stop as well, when a maximum number of generations is reached.
The update rates for ffi depend on the number of previous successive observations that were
successful or not successful. Two variables, yes and no, are used for recording these occurrences,
respectively. If progress is made during many successive previous observations
fOld -
fOld being
the population mean fitness of the previous iteration), then the increasing rate for ffi is very high
(in particular, ffi is multiplied by 2 yes ), whereas if these observations were not successful, then the
decreasing rate is high (ffi is divided by 2 no ). In this way, when the search process is located in a
local optimum and improvements are still not surely expected by reducing ffi, the inner loop duration
will not be too long.
Time-interval Calculation (Step 2.4). The time-interval between observations, G, is calculated
depending on the current values of ffi with regard to \Delta. If ffi is similar to \Delta, then the time-interval
is high (G 0
100 in the experiments), and if it is lower, the time-interval will become like Gmin
in the experiments). This allows ffi values similar to \Delta to be used for a long time (\Delta is
considered a good starting point for ffi, because it is adapted in the outer loop on the basis thereof,
as we will explain in Subsection 3.3). Furthermore, we need to point out that the initial \Delta, \Delta 0
, was
assigned to 1 in the experiments, in order to favor exploration during the initial stages of the first
inner loop's run.

Figure

1 shows the pseudocode algorithm for the whole TRAMSS inner loop. In short, the
objective of this loop is to find and refine local optima (or the global one), in an efficient way.
TRAMSS INNER LOOP
1.
2. while (ffi - ffi min ) and (not termination-condition) do
2.1. -
fOld := -
2.2. perform Selection, Crossover and Mutation(ffi) over G generations;
2.3. if ( -
fOld -
f) then
else
2.4. G := G0 \Delta ffi=\Delta; if
Fig. 1. TRAMSS Inner Loop Structure
3.3 TRAMSS Outer Loop
The outer loop randomly initializes the population that will be handled throughout the TRAMSS
run. It fires the inner loop, and when this one returns, it applies a restart operator based on a step
size that is adaptatively controlled throughout its execution. Now, we explain, in depth, the main
issues related to this loop.
Restart Operator Application (Step 3.4). The outer loop applies a restart operator, called
applies Mutation(\Delta) to all the genes in the chromosomes stored
in the population. The objective of this operator is similar to the one of the partial restart operators
for binary-coded GAs, described in Section 2.2, i.e., to maintain a continuous level of exploration of
the search space, while trying to use the promising zones located as a kind of sketch. It attempts
to ensure that new and promising genetic material is available in the population for being handled
and treated by the next inner loop.
Adaptive Control of \Delta (Step 3.3). The outer loop adapts the \Delta parameter, using information
obtained after each inner loop run, by means of an instance of the S/E heuristic: "decrease \Delta when
observing progress on fBest (fitness of the best element found so far), otherwise increase it. This is
implemented by dividing the previous \Delta value by 2 or multiplying it by 2, respectively. The new \Delta
value will be the first value for the ffi parameter used in the next inner loop.
The pseudocode algorithm for the outer loop is depicted in Figure 2. To sum up, the outer loop
attempts to introduce adequate diversity levels for allowing the subsequent inner loop processing to
be capable of finding, better local optima, or the global one, every time. For this reason, it uses
the f best for the adaptive step size control. When no better local optima are found after the last
inner loop runs, the outer loop produces more diversity in order to increase the probability of having
access to a better one, which will be refined by the next inner loop. On the other hand, if better
solutions are being found by previous inner loop's runs, \Delta becomes low, so avoiding, for the moment,
great destructive effects of the restart operator.
TRAMSS OUTNER LOOP
1.
2. run Initialize;
3. while (not Termination-condition) do
3.1. fOldBest := fBest ;
3.2. run Inner Loop;
3.3. if (fOldBest - fBest ) then
else
3.4. run Restart(\Delta);
Fig. 2. TRAMSS Outer Loop Structure
Minimization experiments on the test suite, described in Subsection 4.1, were carried out in order
to study the behavior of the TRAMSS model. In Subsection 4.2, we describe the algorithms built
in order to do this and, in Subsection 4.3, we show the results and discuss some conclusions about
them.
fSph fRos
fSph
fSch fGri
fSch
d
fSch
fRas ef10
Fig. 3. Test functions
4.1 Test Suite
For the experiments, we have considered six test functions used in the GA literature: Sphere
model (f Sph ) ([De Jong (1975), Schwefel (1981)]), Generalized Rosenbrock's function (f Ros ) ([De
Jong (1975)]), Schwefel's Problem 1.2 (f Sch ) ([Schwefel (1981)]), Griewangk's function ([Griewangk
(1981)]), Generalized Rastringin's function (f Ras ) ([B-ack (1992), T-orn et al. (1989)]), and Expansion
([Whitley et al. (1995)]). Figure 3 shows their formulation. The dimension of the
search space is 25.
fSph is a continuous, strictly convex and unimodal function.
fRos is a continuous and unimodal function, with the optimum located in a steep parabolic
valley with a flat bottom. This feature will probably cause slow progress in many algorithms since
they must permanently change their search direction to reach the optimum. This function has been
considered by some authors to be a real challenge for any continuous function optimization program
([Schlierkamp-Voosen et al. (1994)]). A great part of its difficulty lies in the fact that there are
nonlinear interactions between the variables, i.e., it is nonseparable ([Whitley et al. (1996)]).
fSch is a continuous and unimodal function. Its difficulty lies in the fact that searching along
the coordinate axes only gives a poor rate of convergence, since the gradient of fSch is not oriented
along the axes. It presents similar difficulties to f Ros , but its valley is much narrower.
fRas is a scalable, continuous, separable and multimodal function which is produced from fSph
by modulating it with a
fGri is a continuous and multimodal function. This function is difficult to optimize because it
is nonseparable ([M-uhlenbein et al. (1991)]) and the search algorithm has to climb a hill to reach
the next valley. Nevertheless, one undesirable property exhibited is that it becomes easier as the
dimensionality is increased ([Whitley et al. (1996)]).
is a function that has nonlinear interactions between two variables. Its expanded version,
built in such a way that it induces nonlinear interaction across multiple variables. It is
nonseparable as well.
4.2 Algorithms
We have built five different TRAMSS versions that apply the following crossover operators: Arithmetical
([Michalewicz (1992), Wright (1991)]), Max-min-arithmetical ([Herrera et al. (1997)]), Discrete
([M-uhlenbein et al. (1993)]), Fuzzy recombination ([Voigt et al. (1995)]), and BLX-ff ([Eshel-
man et al. (1993)]). The TRAMSS versions are called TRAMSS-AR, TRAMSS-MMA, TRAMSS-DI,
TRAMSS-FR and TRAMSS-BLX, respectively.
We have implemented five classical RCGAs based on these crossover operators that apply the
non-uniform mutation operator (Subsection 2.1.1.) and, the same selection strategy as the one used
by the TRAMSS inner loop. They are called RCGA-AR, RCGA-MMA, RCGA-DI, RCGA-FR and
RCGA-BLX, respectively.
The crossover probability in these RCGAs and in the TRAMSS versions is 0:6, the mutation
probability 0:005, and the population size 60 chromosomes.
Now, we present the definition of the crossover operators. Let us assume that
are two real-code chromosomes that have been selected to apply the crossover
operator to them. Below, the effects of the five crossover operators are shown.
Arithmetical crossover. An offspring,
We have considered
Max-min-arithmetical crossover. It generates the following four offspring:
In particular, we have considered 0:25. The resulting descendents are the two
best of the four aforesaid offspring.
Discrete crossover. z i is a randomly (uniformly) chosen value from the set fx g.
Fuzzy recombination. The probability that the i-th gene in the offspring has the value z i is given
by the distribution p(z i
g, where OE x i
and OE y i
are triangular probability distributions with
the following features (d - 0:5):
Triangular Prob. Dist. Minimum Value Modal Value Maximum Value
d have been set to 0.5 in the experiments.
BLX-ff crossover. z i is a randomly (uniformly) chosen number from the interval [Min \Gamma I \Delta
We have
assumed
All these crossover operators may be ordered with regard to the way randomness is used for
generating the genes of the offspring: 1) Arithmetical and Max-min-arithmetical crossovers do not
use it, 2) Discrete crossover considers discrete probability distributions, where there are only two
possibilities introduces uniform continuous probability distributions, and
Fuzzy recombination applies triangular continuous probability distributions, and therefore, it may
be considered as a hybrid between discrete crossover and BLX-ff.
Probability distributions used by BLX-ff and Fuzzy recombination are calculated according to
the distance between the genes in the parents (x i and y i ), and the ff and d values, respectively. So,
they fit their action range depending on the diversity of the population using specific information
held by the parents ([Eshelman et al. (1993)]).
We have also implemented two (-ESs, with 100. The first one is denoted as
(15; 100)-ES1 and uses n the other, denoted as (15; 100)-ESn, uses n i.e., the number
of variables. n for both of them. They apply discrete recombination (random exchanges
between parents) on object variables and local intermediate recombination (arithmetic averaging)
on standard deviations (see [B-ack (1996)] for a more detailed description of these operators). The
number of potential parents involved in the recombination of the object variable is 15, and that for
the standard deviations is 15, as well. The standard deviations are initialized to value of 3.0. This
parameterization is very usual for (-ES ([B-ack et al. (1995)]).
All TRAMSS versions and RCGAs were executed 15 times, each one with 10,000 generations,
except TRAMSS-MMA and RCGA-MMA, that performed 5,000 generations, since each Max-min-
arithmetical crossover application needs four evaluations. (15; 100)-ES1 and (15; 100)-ESn were executed
times, each one with 4,000 generations. In this way, the number of fitness function
evaluations required by all algorithms are similar.
4.3 Results
For each function, we introduce the average of the best fitness function found at the end of each
run (A), the best of these values (B), and the percentage of success with respect to the thresholds
shown in Table 1 (S). Table 2 shows the results obtained.
Test Thresholds
fSph 1.0e-150
fRos 1.0
fSch 1.0e-3
fRas

Table

1. Thresholds for the test functions
First, we consider the behavior of the TRAMSS algorithms compared with their corresponding
RCGAs. Then, we comment on the results obtained by (-ES1 and (-ESn.
4.3.1 RCGAs vs. TRAMSS
In general, TRAMSS-AR, -MMA, -DI, -FR and -BLX outperform their corresponding RCGAs,
RCGA-AR, -MMA, -DI, -FR and -BLX, respectively, for all functions, with regard to all performance
measures. To explain this ability, first we focus on the study of the results on the unimodal functions,
fSph , f Ros and fSch , and then, on the multimodal ones, f Ras , fGri and f ef10 .
Analysis for unimodal functions.
ffl We have observed that during runs of the TRAMSS instances on all unimodal functions, the
outer loop performed the inner loop only once. This means that the inner loop has been
controlling ffi to properly suit the local nature of the landscape in these functions. In this way,
improvements on -
f (population mean fitness) predominated, so obtaining very accurate results.
Thus, we may say that the implementation of the E/S heuristic used for controlling ffi is highly
suitable for dealing with unimodal functions. In fact, we should point out that this heuristic has
already been used for designing efficient local search procedures ([De La Maza et al. (1994)]).
fSph fRos fSch
Algorithms A B S A B S A B S
TRAMSS-FR 4.5e-153 2.1e-163 100.0 1.6e+01 2.7e-03 20.0 2.7e-04 2.7e-05 100. 0
TRAMSS-BLX 2.2e-176 2.7e-188 100.0 1.3e+01 4.9e-01 13.3 7.4e-08 2.2e-09 100 .0
(15, 100)-ESn 0.0e+00 0.0e+00 100.0 3.4e+00 7.9e-03 13.3 7.8e+03 3.4e+03 0.0
fRas fGri ef10
Algorithms A B S A B S A B S
TRAMSS-MMA 2.3e-14 0.0e+00 33.3 2.7e-02 0.0e+00 13.3 6.9e-01 0.0e+00 66.7

Table

2. Results of experiments
ffl For fSph , the A and B measures of the TRAMSS algorithms are very accurate to a higher
degree than the ones for the respective RCGAs based on non-uniform mutation (see the very
good results of TRAMSS-FR and TRAMSS-BLX for this function).
ffl For f Ros and fSch , more complex functions, these measures are better as well. The joint effects
of the E/S heuristic and the application of high ffi values during many initial generations allow
the inner loop to be capable of tackling the difficulties associated with the localization of the
optimum in these functions. For example, we may highlight the good B results obtained by
TRAMSS-FR for f Ros , 2.7e-03, and TRAMSS-BLX for fSch , 2.2e-9.
These results indicate that the inner loop has been generating useful diversity throughout the
runs for the unimodal functions. On the other hand, the non-uniform mutation does not take
into account whether the diversity being generated is useful or not. It only decreases the step size
depending on the time without observing if improvements are made, or not. For the case of f Ros ,
this fact does not allow a good search direction to be established for reaching the optimum, and so,
no good final results are obtained (see the results of RCGA-AR, RCGA-FR and RCGA-BLX for this
Analysis for multimodal functions.
ffl The participation of the restart operator in the outer loop allowed reliability to be improved
on the multimodal functions, with regard to the RCGAs based on non-uniform mutation. For
f Ras and fGri , all TRAMSS implementations reached the global optimum, at least once (see B
measure).
ffl Other examples of improvements on reliability, for the case of fGri , involve increasing in the
S measure (expressed with regard to the fitness of the global optimum) of TRAMSS-AR (60%)
in front of RCGA-AR (0%), and TRAMSS-BLX (80%) as contrasted with RCGA-BLX (26.7%).
ffl For the case of
, the union of the effective local tuning of the inner loop and the introduction
of a spread search by means of the restart operator allows very good results to be obtained.
For example, the A measure of TRAMSS-FR for this function is the best of all the algorithms
executed, 1.4e-14, and the B measure of TRAMSS-BLX is very exact, 1.5e-44.
On the other hand, the decreasing of the step size performed by the non-uniform mutation does
not allow the search direction to escape from a possible stagnation in a local optimum, when working
on multimodal functions. In particular, for the case of using arithmetical and discrete operators, we
may observe how this disadvantage induced very poor performance measure values for this type of
functions.
TRAMSS and Crossover Operators.
ffl An important issue that should be highlighted is that the improvements of the TRAMSS
implementations on their corresponding RCGAs based on non-uniform mutation operator are
more notable for most test functions when using Fuzzy recombination and BLX-ff.
The adaptive ffi control performed in the inner loop depends on the changes produced on
f , which are determined by the joint effects of the selection process, and the mutation and
crossover operators. Let us consider only the interactions between the last ones. The mutation
operator generates diversity and the crossover operator would have to use it for creating better
individuals. If the crossover operator achieves this task, then the mutation operator would be
generating "useful diversity", and so evolution is introduced. Therefore, only if the mutation
and the crossover operators are being suitably coupled, the success of the inner loop may be
accomplished. Results have shown that in the case of using Fuzzy recombination and BLX-ff,
this circumstance is held. In particular, we highlight the very good A, B and S measures of
TRAMSS-FR and TRAMSS-BLX for all functions.
These facts lead us to think that the associated property of these crossover operators (to fit
their action range depending on the diversity of the population) is the main one responsible
for making this union so profitable. It would allow these operators to exploit the diversity
generated by the mutation operator.
ffl We should underline the good results of the TRAMSS version based on the Max-min-arithme-
tical crossover as well, TRAMSS-MMA, for the unimodal fSph and the multimodal
. It
reached the global optimum of the first one for 100% of the runs (see A measure) and was the
only algorithm that found the global optimum of the second one (see B measure). The process
of selecting the two best offspring from a set of four ones with different properties along with
the effects of the TRAMSS model allow the best search regions to be located and refined.
4.3.2 (-ESs vs. TRAMSS
performance measures for (15, 100)-ES1 show good behavior. The adaptation mechanism
concerning this algorithm is similar to the one in the TRAMSS model to the fact that all genes
belonging to the same chromosome are mutated using the same step size. However, all TRAMSS
implementations have outperformed this algorithm.
On the other hand, (15, 100)-ESn shows a similar behavior for fSch and f Ras than (15, 100)-ES1.
Furthermore, it is outperformed by TRAMSS-FR and TRAMSS-BLX in the complex f ef10 . However,
its performance for the unimodal functions fSph and f Ros and for the multimodal one fGri was very
good. For these functions, (15, 100)-ESn certainly benefited from the greater degree of freedom by
working with n different self-adaptive step sizes per individual in contrast to a single one in the case
of the TRAMSS algorithms.
5 CONCLUDING REMARKS.
In this paper, we have presented TRAMSS, a two-loop RCGA model that adjusts the step size
of a mutation operator applied during the inner loop, for producing an efficient local tuning, and
controls the step size of a mutation operator used by the outer loop, for reinitializing the population
in order to ensure that different promising search zones are focused by the inner loop throughout
the run. An instance of the E/S heuristic was used for implementing the adaptive mechanism in the
inner loop whereas an instance of its opposite, the S/E heuristic, was considered for the outer loop.
Five TRAMSS algorithms were built using five crossover operators for RCGAs, Arithmetical,
Max-min-arithmetical, Discrete, Fuzzy recombination and BLX-ff, which represent different ways in
which randomness may be used for generating real-coded genes. The principal conclusions derived
from the results of experiments carried out are the following:
ffl The TRAMSS model allows the control of useful population diversity to be accomplished for
improving accuracy in the case of unimodal functions, and, both reliability and accuracy for
the multimodal ones, with regard to RCGAs based on the non-uniform mutation operator.
ffl The adaptive control of step size performed by TRAMSS couples suitably with Fuzzy recombination
and BLX-ff. Their interactions allow TRAMSS to manage useful diversity, so inducing
an effective behavior on all test functions. We suggested that this occurs thanks to the fact
that these crossovers adjust the intervals for the generation of genes depending on the current
population diversity.
ffl With the TRAMSS model, the performance of the strategy of selecting the two best offspring
from a set of four with different properties (Max-min-arithmetical crossover) is enhanced.
Finally, we should point out that TRAMSS extensions may be followed in two ways: 1) control the
parameter associated with the Fuzzy recombination and BLX-ff, respectively, in order to exploit,
even more, the profitable combination between TRAMSS and these crossover operators, and 2)
study the possible application of dynamic crossover operators, such as the Dynamic FCB-crossovers
([Herrera et al. (1996a)]) and Dynamic Heuristic FCB-crossovers ([Herrera et al. (1996c)]), which
are based on the same absolute adaptive heuristics as the non-uniform mutation operator.



--R

Adaptive and self-adaptive evolutionary computations

Evolution strategies I: variants and their computational implementation.
Genetic Algorithms in Engineering and Computer Science (New York: John Wiley
Evolutionary Algorithms in Theory and Practice (Oxford).

Artificial Evolution (Berlin: Springer)


Handbook of Evolutionary Computation (Oxford University Press).
Adaptive selection methods for genetic algorithms.
Reducing bias and inefficiency in the selection algorithm.
An Analysis of the Behavior of a Class of Genetic Adaptive Systems
Dynamic hillclimbing.
The CHC adaptive search algorithm: how to have safe search when engaging in nontraditional genetic recombination.
Preventing premature convergence in genetic algorithms by preventing incest.


Evolutionary Computation: Toward a New Philosophy of Machine Intelligence (Piscataway: IEEE Press).


Genetic algorithms for changing environments.
Generalized descent of global optimization


Genetic Algorithms and Soft Computing (Heidelberg: Physica-Verlag)

In 4th International Conference on Parallel Problem Solving from Nature (Berlin: Springer)
Fuzzy connectives based crossover operators to model genetic algorithms population diversity.
Tackling real-coded genetic algorithms: operators and tools for the behavioural analysis
Representation and self-adaption in genetic algorithms
Adaptation in evolutionary computation: a survey.
Adaptation in Natural and Artificial Systems (London: The MIT Press).
Optimization of calibration data with the dynamic genetic algorithm.

Niching methods for genetic algorithms.
Selectively destructive re-start
Genetic Algorithms
The parallel genetic algorithm as function optimizer.
Predictive models for the breeder genetic algorithm I.
A derandomized approach to self-adaptation of evolution strate- gies

The ARGOT strategy: adaptive representation genetic optimizer Technique.
Numerical Optimization of Computer Models (Chichester: Wiley).
Evolution and Optimum Seeking.
Dynamic parameter encoding for genetic algorithms.
Strategy adaptation by competing subpopulations.
Fast convergence thanks to diversity.
Crossover or mutation?
Real representations.



coding: an iterative search strategy for genetic algorithms.
Test driving three

Genetic algorithms for real parameter optimization.
--TR

--CTR
Manuel Lozano , Francisco Herrera , Natalio Krasnogor , Daniel Molina, Real-coded memetic algorithms with crossover hill-climbing, Evolutionary Computation, v.12 n.3, p.273-302, September 2004
mutation operator;premature convergence;real-coded genetic algorithms