2006 IEEE Congress on Evolutionary Computation

Sheraton Vancouver Wall Centre Hotel, Vancouver, BC, Canada

July 16-21, 2006

Local Learning and Search in Memetic Algorithms

Frederico G. Guimarães, Student Member, IEEE, Elizabeth F. Wanner, Student Member, IEEE,
Felipe Campelo, Student Member, IEEE, Ricardo H.C. Takahashi, Member, IEEE,
Hajime Igarashi, Member, IEEE, David A. Lowther, Member, IEEE, Jaime A. Ramı́rez, Member, IEEE

Abstract— The use of local search in evolutionary techniques whose objective function demands much time to evaluate, i.e.
is believed to enhance the performance of the algorithms, giving some seconds to minutes. Optimization problems associated
rise to memetic or hybrid algorithms. However, in many contin- to computer aided design (CAD), in which the designer
uous optimization problems the additional cost required by local
search may be prohibitive. Thus we propose the local learning of needs to model electromagnetic, thermal or fluid phenomena
the objective and constraint functions prior to the local search that lead to the implicit solution of differential or integral
phase of memetic algorithms, based on the samples gathered equations, often fall in this class of problem [10]. When
by the population through the evolutionary process. The local multiplying the time of one single evaluation by thousands
search operator is then applied over this approximated model. of evaluations required for a single run of an evolutionary
We perform some experiments by combining our approach
with a real-coded genetic algorithm. The results demonstrate algorithm, we get a computationally expensive optimization
the benefit of the proposed methodology for costly black-box process. In this context, the use of local search operators
functions. elevates the computational cost in such a way that it makes
the employment of MAs prohibitive.
I. I NTRODUCTION
We provide an alternative methodology for using MAs
Nowadays, the combination of local search operators and with continuous and costly optimization problems. It is based
evolutionary techniques is argued to greatly improve the on the employment of local approximations before the local
performance of the basic evolutionary technique by com- search phase. When an individual is selected for local search,
bining the global search ability of these methods with the it “builds” a local model of the function behavior. After that,
advantages provided by local search techniques. Such class the local search operator uses the estimates provided by the
of hybrid methods is known as memetic algorithms (MAs) local model to enhance the individual. The local model is
[1], [2], [3]. The main idea of memetic evolution is that a generated through the learning of the input-output mapping
given individual in the population may be improved through performed by the black-box function based on current and
individual evolution. the past samples gathered during the evolutionary process.
Initially, MAs were developed for combinatorial optimiza- Evolutionary algorithms can be viewed as adaptive sampling
tion problems [4], [5], [6], by exploring the use of very techniques, in the sense that they sample the search space
specific local search operators for the problem being solved. in seeking for the optimal solution. This adaptive sampling
In this context, MAs have overcome the basic evolutionary process is guided by the heuristic operators of the algorithm,
techniques in many applications. Nonetheless, it did not take which direct the search to the most promising regions.
long for some works to appear in the literature dealing Assuming that we are dealing with an expensive-to-evaluate
with continuous search spaces [7], [8], [9]. However, the function, each sample is very valuable. We may store all
local search phase consumes a great number of function samples in an input-output data set, which represents all the
evaluations. When dealing with optimization problems in knowledge acquired by the algorithm for the problem. Points
which the objective function evaluation is fast, this charac- from this data set in the vicinity of the individual may be
teristic is not critical. In general, combinatorial optimization used to fit a given parameterized model, for instance, a neural
problems and some continuous optimization problems fall network model, that provides a local approximation to the
in this class of problems. Conversely, there are many real- function.
world problems, particularly some engineering problems, The use of approximations to deal with costly functions is
F.G. Guimarães, E.F. Wanner, and J.A. Ramı́rez are with the Depart- not new. A traditional approach is to sample the functions,
ment of Electrical Engineering, Federal University of Minas Gerais, Av. generally in a random manner, prior to the optimization
Antônio Carlos, 6627, Belo Horizonte, MG, 31270-010, Brazil (e-mail: [11], [12], [13]. A global approximation is built and the
fgg@[Link], elizabeth@[Link] and jramirez@[Link]).
R.H.C. Takahashi is with the Department of Mathematics, Federal Uni- optimization is performed over this global model. This global
versity of Minas Gerais, Av. Antônio Carlos, 6627, Belo Horizonte, MG, model can be a static model or a dynamic one, in the sense
Brazil (e-mail: taka@[Link]). that the model is further refined during the optimization
D.A. Lowther is with the Department of Electrical and
Computer Engineering, McGill University, Montreal, Canada (e-mail: process. However, this approach is very limited. For more
[Link]@[Link]). complex functions and for higher dimensions, it is necessary
F. Campelo and H. Igarashi are with the Research Group of Informatics to use many samples to produce a good approximation.
for System Synthesis Graduate School of Information Science and Technol-
ogy, Hokkaido University, Sapporo 060-0814, Japan. (fax: +81 11-706-7670; Additionally, the complexity of the model will increase in
email: pinto@[Link]). order to capture the global behavior of the function.

0-7803-9487-9/06/$20.00/©2006 IEEE 2936

 Local approximations, on the other hand, may be more B. Evolutionary optimization
simple and more efficient, in the sense that only few samples Evolutionary techniques are very flexible and powerful
should be sufficient to capture the local behavior of the optimization tools. They are able to solve the problem
function [14]. Since the local model will be used only for defined previously using only information of the value of
local improvement of the individual, it is not necessary the functions at the point. An evolutionary technique works
to build a global and complex approximate model. Local with a population of candidate solutions distributed over the
approximations have been used for alleviating the computa- search space. The iterative cycle consists in applying heuris-
tional cost of evolutionary optimization by substituting the tic operators that direct the search to the most promising
real function when evaluating fitness of some individuals, regions of the search space, thus giving a chance to achieve
as in [15]. This work exploits the local approximations in the global optimum x∗ . A generic evolutionary algorithm is
a different context, specifically allowing the use of local presented below:
search in memetic algorithms without paying the price of
many function evaluations. Algorithm 1: (Evolutionary Algorithm)
The paper is organized as follows: Section II gives an
1) Define the search space D, population size µ, objective
overview of evolutionary and memetic algorithms, section III
function f (·) and constraint functions,

if any; 
discusses the local learning and search approach proposed,
2) Initialize population P (t = 0) = p(1) , . . . , p(µ) ;
and section IV presents results related to unconstrained and
3) While (¬ stop criterion) do:
constrained problems, demonstrating the gain achieved by
our methodology. a) Φ(t) ← evaluate(P (t), f, g, h);
b) S(t) ← selection(P (t), Φ(t));
II. E VOLUTIONARY AND M EMETIC ALGORITHMS c) C(t) ← variation(S(t));
d) P (t + 1) ← C(t);
A. Problem definition e) t ← t + 1
We first provide a mathematical definition of the optimiza-
tion problem under consideration: where Φ(t) contains the fitness values of the population P (t).
The mechanism of variation (e.g., crossover and mutation)
x∗ = arg minx f (x) ∈ R generates the population for the next generation.
(1)
subject to: x ∈ F = G ∩ H ∩ D ⊂ Rn C. Towards memetic algorithms
A meme [16] represents the unit of cultural evolution, just
where f (x) is the objective function and F is the feasible
like the gene in biological evolution. Moscato [17] utilized
set defined by the constraints. Additionally, we have:
this term to name his genetic algorithm associated with a
local search operator performed by the simulated annealing
G = {x ∈ Rn : gi (x) ≤ 0, i = 1, . . . , p} (2) algorithm. During a given generation, an individual is sub-
mitted to memetic evolution, that is, a local improvement
where gi (x) is an inequality constraint function,
that can be passed to the future offspring. Next, we illustrate
H = {x ∈ Rn : hj (x) = 0, j = 1, . . . , q} (3) a generic diagram of an MA:

where hj (x) is an equality constraint function, and Algorithm 2: (Memetic Algorithm)

1) Define the search space D, population size µ, objective
D = {x ∈ Rn : lk ≤ xk ≤ uk , k = 1, . . . , n} (4)
function f (·) and constraint functions,

if any; 
where lk and uk are respectively the lower and upper limits 2) Initialize population P (t = 0) = p(1) , . . . , p(µ) ;
of the variables. 3) While (¬ stop criterion) do:
In this work we focus on global optimization problems a) Φ(t) ← evaluate(P (t), f, g, h);
where at least one of the functions f (·), gi (·) and hj (·) is b) S(t) ← selection(P (t), Φ(t));
assumed to be an expensive-to-evaluate black-box function. c) C(t) ← variation(S(t));
Optimization of costly black-box functions is frequently d) L(t) ← local search(C(t));
found in engineering design applications, where the compu- e) P (t + 1) ← L(t);
tational models describing systems or devices related to the f) t ← t + 1
problem are expensive to simulate. The optimization problem
may represent the maximization of some performance mea- Observe that a local search phase is introduced within
sure or parameter estimation in inverse problems. The com- the normal cycle of the evolutionary algorithm. The exact
putation of the objective function may involve the solution of position of the local search varies among different MAs [3].
systems of partial differential equations. Nonlinearities and We provide now a more precise definition of the local
accuracy requirements may lead to additional computational search phase. Let x(i) be the solution represented by a
effort. given individual p(i) ∈ P (t). Let V(x(i) ,
) represent a local

2937
vicinity of x(i) . The local search operator aims at obtaining a
solution x ∈ V(x(i) ,
) such that x is a local optimal solution 500
in the local vicinity of x(i) :
Definition 1: Local optimal solution: A solution x∗ ∈ F 400
is said to be a local optimal solution in the vicinity of the 300
point x(i) if there is no x ∈ V(x(i) ,
) such that f (x) <
f (x∗ ). 200
Nonetheless, MAs do not necessarily need to employ
100
local searchers that achieve this goal, since only a local
improvement in the solution may be helpful. Following this 0
definition, the local search problem within an MA can be
−100
posed as the standard form:
−200
Algorithm 3: (Standard local search operator)
−300
1) Given x(i) ,
, f, g, and h;
2) Find an x such that it is better than x(i) in solving: −400

min f (x) −500

(5)
subject to: x ∈ V(x(i) ,
) ∩ F −500 0 500

In this standard local search, there is no specification about

the vicinity V. Here, we adopt a rectangular vicinity centered Fig. 1. Samples produced by the genetic algorithm on the Schwefel
at x(i) : function. The contour plot of the function is also shown.

(i) (i) (i)

V(x(i) ,
) = {x : xk −
(uk −lk ) ≤ xk ≤ xk +
(uk −lk )} • The time required for generating the approximate model
(6) can not be increased;
The parameter
controls the size of the local vicinity as • The total time of the optimization process when using
a fraction of the search space size. the hybrid algorithm (time to evaluate + time to gener-
ate approximations + time to perform local search) has
III. L OCAL LEARNING AND OPTIMIZATION to be smaller than that obtained when using the basic
As already mentioned, the evolutionary technique can be algorithm (time to evaluate only);
viewed as an adaptive sampling process. Consider again • The unit for comparing the original algorithm and its
the generic evolutionary algorithm in Algorithm 1. The hybridized version is the mean number of function
selection operator identifies the most promising regions by evaluations required for achieving a solution of similar
selecting the fittest individuals for variation. The variation quality;
mechanism produces new solutions around the best regions, The first requirement implies that some additional com-
whilst maintaining some level of global exploration. plexity introduced into the evolutionary algorithm is still
As an example, Fig. 1 illustrates the sampling performed justifiable. The third requirement implies that the hybrid
by a genetic algorithm during the evolutionary process for algorithm must achieve a similar solution more rapidly, i.e.,
the 2-dimensional Schwefel function [18]. The GA was set with less evaluations, or, for the same number of evaluations,
up with 30 individuals over 20 generations, giving a total a solution of better quality. Moreover, it also implies that
of 600 function evaluations. Observe how we have more applying local search to many individuals in the population
samples around the best region. The samples obtained by may not be an interesting strategy, because the total time
the algorithm represent valuable information acquired by the may be greatly increased.
sequence of populations. It would be very profitable if we
could use this knowledge to learn the behavior of the function A. Local approximate models
in the vicinity of an individual, in order to enhance the
All evaluations made by the algorithm are stored in an
accuracy and convergence speed of the algorithm.
input-output data of the form:
We have remarked that our approach is suitable for a class
of problems characterized by expensive black-box functions 
of continuous variables. We provide some considerations S(t) = z (i) ; f (z (i) ); g1 (z (i) ); . . . ; gp (z (i) ); . . .
before proceeding. N (t)
• The time required for the execution of the normal h1 (z (i) ); . . . ; hq (z (i) ) (7)
i=1
operators, within an evolutionary cycle, is assumed to
be insignificant when compared to the time spent to where N (t) is the total number of samples collected by the
evaluate the entire population in a generation; algorithm at time t. S(t) is the global data set obtained by

2938
the algorithm. In an unconstrained problem S contains only
Recombination and
the input points and their objective function evaluations. Mutation
Suppose that the individual p(j) ∈ P (t), j ∈ {1, . . . , µ}, Parent pop Offspring Offspring
was selected for local search. We select from the current Size µ Size λ Size λ
data set S all neighbours of p(j) , i.e., those that belong to
V(x(j) ,
), as data points for generating the local approxi-
mation. Using these neighbour points, the individual makes
a local data set named SVj , which contains all points from
S that belong to V(x(j) ,
). The number of data points -
neighbour points - in SVj is given by Nj . Then, we adjust a Parent pop
parameterized model using the local data set. Size µ
Many approximation techniques are available for design- Selection ES(µ,λ) or
ing a memetic algorithm with local approximate models, see Selection ES(µ+λ)
[14] for an overview on the use of approximation techniques
in evolutionary methods. In our experiments, we use the
radial basis function (RBF) network [19], which is capable of
Fig. 2. General diagram of the evolution strategy.
generating a nonlinear input-output mapping and capturing
the local multimodality of the function. The RBF network
is a parameterized model which can be adjusted to the data B. Local optimization
using either the supervised learning paradigm or the direct
solution to a linear system of equations. The next step is to proceed to the optimization of the
The mapping performed by the RBF network is given by: approximate problem, which is described as follows:

m min f˜(x)
 (12)
ψ(x) = wi θi (x) + β (8) subject to: x ∈ V(x(i) ,
) ∩ F̃
i=1
where f˜(·) is the approximation generated by the neural
where we have m neurons in the hidden layer. wi represents network, and F̃ is the approximated feasible set considering
the synaptic connection weight, β is a bias term, and θi is the approximations of the constraints:
the output of the ith nonlinear neuron in the network. We
adopt the multiquadric function as the radial basis function, F̃ = G̃ ∩ H̃ ∩ D (13)
which is given by:
and:

θi (x) = x − ci  + h2i (9) G̃ = {x ∈ Rn : g̃i (x) ≤ 0, i = 1, . . . , p} (14)
where ci is the center of the multiquadric function and hi is  
the shape parameter. H̃ = x ∈ Rn : h̃i (x) = 0, i = 1, . . . , q (15)
Making m = Nj and setting each center equal to one of
the data points in SVj , it is possible to obtain an approxima- In this paper, we employ the evolution strategy (ES) [18],
tion by solving: [20] algorithm as local optimizer. This algorithm is capable
     of dealing with multimodality, hence it can “jump” local
Ψ 1 w f minima captured or modeled by the local approximation
= (10)
1T 0 β 0 technique, which can not be done by gradient-based search
methods.
where:  The evolution strategy works with a population of µ
Ψij = xi − xj  + h2i (11) individuals, which generates an offspring with λ individuals
through the successive application of recombination and
The total number of points in the vicinity should be greater mutation operators. After that, the population of the next
than 0.5(n + 1)(n + 2), which is the minimum number generation is formed by the µ best individuals selected either
required to fit a n-dimensional quadratic function. If this from the offspring population only or from both parent and
condition is not met, the local approximation is not generated offspring population. These two selection schemes give rise
and no local search is made. When it is met, we train the to the nomenclature ES(µ, λ) or ES(µ + λ), respectively.
RBF model using S V as training data. A general diagram of the evolution strategy algorithm is
For constrained problems, the procedure described here is depicted in Fig. 2. This diagram shows the iterative cycle
repeated for each nonlinear constraint function, that is, we of the evolution strategy. The ES performs the local search
obtain an approximation for each function involved in the over the local approximations and within the vicinity of the
original optimization problem. point selected to local search. An improved individual is

2939
returned by the local search and substitutes for the original A. Unconstrained test problems
individual. Finally, since the basic ES does not have any
The test functions used in our experiments are described
explicit mechanism for dealing with constraints, we deal with
next:
constrained problems by using a penalty function. For other
ways to treat constraints in ES, see [21]. 1) Rosenbrock function:

C. Hybridization with genetic algorithms n−1


In this section, we describe how we hybridize the genetic f (x) = 100(x2i − xi+1 )2 + (1 − xi )2 (16)
i=1
algorithm with our local learning and optimization method-
ology. The real-coded genetic algorithm (RGA) used in our with −2.048 ≤ xi ≤ +2.048, i = 1, . . . , n.
experiments employs real representations of the variables 2) Schwefel function:
and the traditional roulette wheel selection mechanism. The
crossover operator is the simulated binary crossover, pro-
f (x) = 418.9829n − xi sin |xi | (17)
posed in [22]. It is described in the following algorithm:

Algorithm 4: (Simulated Binary Crossover) with −500 ≤ xi ≤ +500, i = 1, . . . , n.

1) for k = 1, . . . , n, do: 3) Griewank function:
a) uk = U (0, 1) n n
x2i cos xi
(2uk )1/(η+1) , uk ≤ 0.5 f (x) = − √ (18)
b) βk = 4000 i=1 i
[2(1 − uk )]−1/(η+1) , otherwise i=1
c) c1k = 0.5 [(1 + βk )p1k + (1 − βk )p2k ]
with −600 ≤ xi ≤ +600, i = 1, . . . , n.
d) c2k = 0.5 [(1 − βk )p1k + (1 + βk )p2k ]
The Rosenbrock and Griewank functions should be min-
imized, while the Schwefel function should be maximized.
In this algorithm, p1 and p2 are the parent individuals, c1
All test functions are solved with n = 2 and n = 10.
and c2 are the offspring, η ≥ 0 is a parameter of the crossover
operator, and U (0, 1) represents the realization of a random
variable with uniform distribution in the interval [0, 1]. Here, B. Constrained test problem
we adopt η = 2. The mutation is implemented as a Gaussian
In addition to the unconstrained problems presented be-
disturbance vector added to the original individual.
fore, we also solve the following constrained problem:
Immediately after evaluating the population, we select the
best individual for the local search phase, which includes the 2 × 10−6 3
local approximation generation and the local optimization. min f (x) = 3x1 + 10−6 x31 + 2x2 + x2 (19)
3
The local optimization is performed with the ES(1 + λ)
scheme, where the initial solution is the solution selected subject to:
for local improvement. λ is a parameter of the local search,
which controls the intensity of the local search performed g1 (x) = x3 − x4 − 0.55 ≤ 0
around the vicinity of the individual selected to memetic g2 (x) = −x3 + x4 − 0.55 ≤ 0
evolution.
h1 (x) = 1000 sin(−x3 − 0.25)
In addition, the local search phase is not activated at every
generation, but at an interval of every T generations, with +1000 sin(−x4 − 0.25) + 894.8 − x1 = 0
T ≥ 1 being an integer parameter selected by the user. h2 (x) = 1000 sin(x3 − 0.25)
This is done to avoid a high computational cost of building +1000 sin(x3 − x4 − 0.25) + 894.8 − x2 = 0
and optimizing approximations at every generation. Notice
h3 (x) = 1000 sin(x4 − 0.25)
that applying local learning and search to many individuals
may violate the considerations made before, making the +1000 sin(x4 − x3 − 0.25) + 1294.8 = 0
time to perform local evolution significant compared to the
time to evaluate individuals over the real functions. Besides, with 0 ≤ x1 , x2 ≤ 1200 and −0.55 ≤ x3 , x4 ≤ +0.55. The
performing local learning and search at every generation may best known solution is:
not leave time for global evolution and significant sampling  T
of the search space. x∗ = 679.9453 1026.067 0.1189 −0.3962

IV. E XPERIMENTAL RESULTS where f (x∗ ) = 5126.4981 [21].

As already mentioned, we couple our approach with a real- Only the nonlinear functions involved in this problem are
coded genetic algorithm (RGA). The hybridized version of locally approximated by RBF models. Therefore, only the
the RGA (H-RGA) is compared to its basic version on a objective function and the equality constraint functions are
number of benchmark problems, in order to demonstrate the approximated. The inequality constraints are directly used
benefit of our approach. within the local search phase, since they are linear.

2940
 TABLE I
1.4
S ETTINGS FOR THE UNCONSTRAINED PROBLEMS RGA
H-RGA
1.2
Dimension n=2 n = 10
population size 20 50 1
crossover rate 0.80 0.80
mutation rate 0.05 0.05 0.8
max generations 100 300
0.6

TABLE II 0.4

S ETTINGS FOR THE CONSTRAINED PROBLEM

0.2

Dimension n=4 0
0 200 400 600 800 1000 1200
population size 50
crossover rate 0.80
mutation rate 0.05
max generations 200 Fig. 3. Mean values of the convergence curve with respect to the number
of function calls for the Rosenbrock function with n = 2.
140
RGA
H-RGA
120
C. Results
Both RGA and H-RGA are set up according to Table I for 100

the unconstrained problems and according to Table II for the 80

constrained problem. Regarding the H-RGA, we also have:
60
• Interval of application of the local learning and search:
T = 5; 40

•
= 0.05, i.e., the local vicinity is a hyper rectangle with

sizes of 10% of the global search range and centered at 20

the best individual; 0

ES(1 + 20) as local optimizer;
0 200 400 600 800 1000 1200
•

For each problem analyzed, we performed 20 runs of RGA

and H-RGA in oder to get mean convergence curves of the Fig. 4. Mean values of the convergence curve with respect to the number
of function calls for the Schwefel function with n = 2.
best value with respect to the generation number.
2
Figs. 3-5 show the values of these mean curves with RGA
1.8 H-RGA
respect to the number of calls to the real function for the
unconstrained problems with n = 2. These graphs show an 1.6

evident improvement of the convergence speed of the basic 1.4

RGA when it is associated with the proposed local learning 1.2

and optimization methodology. 1

Figs. 6-8 show the same graphs for the unconstrained 0.8

problem with n = 10. Again, it is evident the improvement 0.6

achieved by the hybridization. With convergence achieved 0.4

earlier, many calls to the real function can be avoided, thus 0.2
speeding up the overall optimization process. 0
0 200 400 600 800 1000 1200
Fig. 9 illustrates the mean convergence for the constrained
problem. A good solution is achieved about 20 generations
earlier, which represents 1, 000 calls of the real functions, Fig. 5. Mean values of the convergence curve with respect to the number
since the population size is 50. If one or more functions of function calls the Griewank function with n = 2.
involved in this problem were time-consuming, the economy
in the total optimization time would be very significant.
The graphs in Figs. 3-9 do not consider the number of calls V. E LECTROMAGNETIC DESIGN APPLICATION
to the approximate function made by the local optimizer, Finally, we analyze an electromagnetic design problem
that is, only calls to the real function are considered as a as an example of an expensive optimization problem. The
significant measure of computational cost. Of course, for problem under consideration is a well-known benchmark
the analytical functions considered here, which are fast to optimization problem in electromagnetic design [23]. It con-
evaluate, the time required by the H-RGA is much greater sists of the design of the dimensions of the outer coil in a
than that required by the RGA without hybridization. The superconducting magnetic energy storage (SMES) assembly.
gain is only noticeable when dealing with costly functions. The problem configuration is shown in Fig. 10. Due to the

2941
 60 12000
RGA RGA
H-RGA 11000
H-RGA
50

10000

40
9000

30 8000

7000
20

6000

10
5000

0 4000
0 2000 4000 6000 8000 10000 12000 14000 16000 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000

Fig. 6. Mean values of the convergence curve with respect to the number Fig. 9. Mean values of the convergence curve at some generation values
of function calls for the Rosenbrock function with n = 10. for the constrained problem.
2500
RGA
H-RGA
2000

1500

1000

500

0
0 0.5 1 1.5 2 2.5 3
4
x 10

Fig. 7. Mean values of the convergence curve with respect to the number
of function calls for the Schwefel function with n = 10.
7 Fig. 10. SMES configuration, showing the two coils, the 21 control points
RGA
H-RGA for evaluating the strayed magnetic field and the 2D planar version of the
6 problem.

4 physical condition that guarantees the superconductivity state

of the coils. All these design goals can be described in the
3
following optimization problem:

2  21
1 
min f (x) = 
2
B(ri ) (20)
21 i=1
1

0
0 2000 4000 6000 8000 10000 12000 14000 16000
subject to:
= Bmax − 4.92T ≤ 0
g(x)
Fig. 8. Mean values of the convergence curve with respect to the number
of function calls for the Griewank function with n = 10. |E − 180M J|
h(x) =
180M J
where ri is one of the 21 control points, Bmax is the
axisymmetric nature of the problem, it is possible to reduce maximum value of the magnitude of the flux density at the
the geometry to a 2D problem, hence saving computation. coils, and E is the stored energy for the given configuration.
The objective of the problem is to find the optimal values The evaluation of these objective and constraint functions
for the radius (x1 ), the height (x2 ) and the width (x3 ) of the involves the solution of an implicit numerical field analysis
coil in its 2D section, which minimize the stray magnetic problem, which demands great computational effort.
field evaluated at the 21 control points shown in Fig. 10. For this problem, we adopt the same configuration used
Additionally, the optimal configuration must provide 180M J for the constrained problem, see Table II, except that the
(30kW h) for the stored energy and must not violate the maximum number of generations is limited to 50, i.e., the

2942
 TABLE III
[2] P. Merz and B. Freisleben, “Fitness landscapes and memetic algorithm
S OLUTIONS FOR THE ELECTROMAGNETIC PROBLEM design,” in New Ideas in Optimization, D. Corne, M. Dorigo, and
F. Glover, Eds. McGraw-Hill, 1999.
RGA strayed field energy Bmax [3] N. Krasnogor, “Studies on the theory and design space of memetic
1.04mT 180.0M J 3.86T algorithms,” Ph.D. dissertation, Faculty of Computing, Engineering
x1 x2 x3 and Mathematical Sciences, University of the West England, Bristol,
3.30 1.06 0.16 UK, June 2002.
H-RGA strayed field energy Bmax [4] P. Merz and B. Freisleben, “Genetic local search for the TSP: New
1.05mT 180.9M J 4.71T results,” in Proc. IEEE International Conference on Evolutionary
x1 x2 x3 Computation. IEEE Press, Apr. 13–16, 1997, pp. 159–164.
3.06 0.52 0.38 [5] ——, “A comparison of memetic algorithms, tabu search, and ant
colonies for the quadratic assignment problem,” in Proc. IEEE
Congress on Evolutionary Computation, vol. 3. IEEE Press, July
6–9, 1999, pp. 2063–2070.
[6] H. Ishibuchi and T. Murata, “Local search procedures in a multi-
number of real function calls is limited to 2, 500. The objective genetic local search algorithm for scheduling problems,” in
electromagnetic analyzer takes about 2.65 seconds to solve Proc. IEEE International Conference on Systems, Man, and Cybernet-
ics, vol. 1. IEEE Press, Oct. 12–15, 1999, pp. 665–670.
the numerical field problem. The time to evaluate the entire [7] X. Hu, Z. Huang, and Z. Wang, “Hybridization of the multi-objective
population within a generation is hence about 2 minutes and evolutionary algorithms and the gradient-based algorithms,” in Proc.
12.5 seconds, thus the computational cost is dominated by IEEE Congress on Evolutionary Computation, vol. 2. IEEE Press,
Dec. 8–12, 2003, pp. 870–877.
the evaluation step. [8] S. Kimura and A. Konagaya, “High dimensional function optimization
Each algorithm is executed 5 times on this problem. The using a new genetic local search suitable for parallel computers,” in
best solutions achieved by both RGA and H-RGA are shown Proc. IEEE International Conference on Systems, Man, and Cybernet-
ics, vol. 1. IEEE Press, Oct. 5–8, 2003, pp. 335–342.
in Table III. On average, a very good solution is achieved by [9] Y. W. Ong and A. J. Keane, “Meta-lamarckian learning in memetic
H-RGA from the 20th generation on, while RGA achieves its algorithms,” IEEE Trans. Evol. Comput., vol. 8, no. 2, pp. 99–110,
solution only 23 generations later. Therefore, H-RGA saves Apr. 2004.
[10] G. Renner and A. Eckart, “Genetic algorithms in computer aided
1, 150 evaluations, which means approximately 50 minutes design,” Computer Aided Design, vol. 35, pp. 709–726, 2003.
in function evaluations. Until the 20th generation, the local [11] T. Ebner, C. Magele, B. R. Brandstatter, and K. R. Richter, “Utilizing
search phase was performed only 4 times, at generations 5, feedforward neural networks for acceleration of global optimization
procedures,” IEEE Trans. Magn., vol. 34, no. 5, pp. 2928–2931, Sept.
10, 15, and 20. The time to generate the local approximations 1998.
and the local search over the approximated functions at these [12] A. Canova, G. Gruosso, and M. Repetto, “Magnetic design opti-
4 times is insignificant compared to 50 minutes. mization and objective function approximation,” IEEE Trans. Magn.,
vol. 39, no. 5, pp. 2154–2162, Sept. 2003.
[13] K. R. Davey, “Examination of various techniques for the acceleration
VI. C ONCLUSIONS of multivariable optimization problems,” IEEE Trans. Magn., vol. 39,
This paper presented the use of local approximations in no. 3, pp. 1293–1296, May 2003.
[14] Y. Jin, “A comprehensive survey of fitness approximation in evo-
the context of local evolution within memetic algorithms for lutionary computation,” Soft Computing - A Fusion of Foundations,
costly optimization problems. The local search operator is Methodologies and Applications, vol. 9, no. 1, pp. 3–12, Jan. 2005.
performed by the evolution strategy restricted to the local [15] R. G. Regis and C. A. Shoemaker, “Local function approximation in
evolutionary algorithms for the optimization of costly functions,” IEEE
vicinity of the individual selected to memetic evolution. The Trans. Evol. Comput., vol. 8, no. 5, pp. 490–505, Oct. 2004.
local evolution is performed over the approximations built for [16] R. Dawkins, “Memes: The new replicators,” in The Selfish Gene.
the objective function and all nonlinear constraints present in Oxford University Press, 1976, ch. 11.
[17] P. Moscato, “On evolution, search, optimization, genetic algorithms
the optimization problem. and martial arts: Towards memetic algorithms,” Caltech Concurrent
The usage of the evolution strategy as local optimizer Computation Program, Tech. Rep., 1989, c3P Report 826.
has the benefit of jumping local minima modeled by the [18] H. P. Schwefel, Evolution and Optimal Seeking. Wiley, 1995.
[19] J. Park and I. W. Sandberg, “Universal approximation using radial-
local approximate models, thus the memetic evolution does basis-function networks,” Neural Computation, vol. 3, no. 2, pp. 246–
not get stuck in local minima within the vicinity. The 257, 1991.
results demonstrate the benefit of the proposed local learning [20] T. Back, Evolutionary Algorithms in Theory and Practice. Oxford
University Press, 1996.
and search for memetic algorithms in unconstrained and [21] E. M. Montes and C. A. C. Coello, “A simple multimembered
constrained optimization problems. evolution strategy to solve constrained optimization problems,” IEEE
The proposed methodology is very promising for tackling Trans. Evol. Comput., vol. 9, no. 1, pp. 1–17, 2005.
[22] K. Deb and R. B. Agrawal, “Simulated binary crossover for continuous
costly optimization problems, as demonstrated in the elec- search space,” Complex Systems, vol. 9, pp. 115–148, 1995.
tromagnetic design problem investigated. [23] B. Brandstaetter. (1996) Team workshop bench-
mark problem 22 definition. [Online]. Available:
ACKNOWLEDGMENT [Link]

This work was supported by CNPq, Brazil, under grants

no. 300353/1997-9 and 141731/2004-4, and CAPES, Brazil.
R EFERENCES
[1] P. Moscato, “Memetic algorithms: A short introduction,” in New Ideas
in Optimization, D. Corne, M. Dorigo, and F. Glover, Eds. McGraw-
Hill, 1999, pp. 219–234.

2943