Efficiency of Local Search with Multiple Local Optima.
The first contribution of this paper is a theoretical investigation of combinatorial optimization problems. Their landscapes are specified by the set of neighborhoods of all points of the search space. The aim of the paper consists of the estimation of the number N of local optima and the distributions of the sizes $(\alpha_j)$ of their attraction basins. For different types of landscapes we give precise estimates of the size of the random sample that ensures that at least one point lies in each attraction basin.  A practical methodology is then proposed for identifying these quantities ($N$ and $(\alpha_j)$ distributions) for an unknown landscape, given a random sample of starting points and a local steepest ascent search. This methodology can be applied to any landscape specified with a modification operator and provides bounds on search complexity to detect all local optima. Experiments demonstrate the efficiency of this methodology for guiding the choice of modification operators, eventually leading to the design of problem-dependent optimization heuristics.
Introduction
. In the eld of stochastic optimization, two search techniques
have been widely investigated during the last decade: Simulated Annealing [25] and
Evolutionary Algorithms (EAs) [6, 7]. These algorithms are now widely recognized
as methods of order zero for function optimization as they impose no condition on
function regularity. However, the e-ciency of these search algorithms, in terms of
the time they require to reach the solution, is strongly dependent on the choice of
the modication operators used to explore the landscape. These operators in turn
determine the neighborhood relation of the landscape under optimization.
This paper provides a new methodology allowing to estimate the number and the
sizes of the attraction basins of a landscape specied in relation to some modication
operator. This allows one to derive bounds on the probability that one samples a
point in the basin of the global optimum for example. Further, this method could be
used for guiding the choice of e-cient problem-dependent modication operators or
representations.
Formally, a landscape can be denoted by E) where f is the function
to optimize and  the modication operator that is applied to elements of the search
space E. The structure of the landscape, heavily depends on the choice of the modication
operators, which in turn may depend on the choice of the representation (the
coding of the candidate solutions into binary or gray strings for example). Hence,
before the optimization process can be started, there is a number of practical choices
(representation and operators) that determine the landscape structure. Consequently,
these choices are often crucial for the success of stochastic search algorithms.
Some research has studied how the tness landscape structure impacts the potential
search di-culties [13, 21, 22, 26]. It is shown that every complex tness landscape
can be represented as an expansion of elementary landscapes {one term in the Fourier
expansion{ which are easier to search in most cases. This result has been applied to
Centre de Mathematiques Appliquees, Ecole Polytechnique, 91128 Palaiseau Cedex, France
y Corresponding author, Tel: (33).1.69.33.46.30 Fax: (33).1.69.33.30.11, E-mail:
Josselin.Garnier@polytechnique.fr
J. Garnier and L. Kallel
solve a di-cult NP-complete problem [20] (the identication of minimal nite k-state
automaton for a given input-output behavior), using evolutionary algorithms. Other
theoretical studies of search feasibility consider the whole landscape as a tree of local
optima, with a label describing the depth of the attraction basin at each node
[16, 19]. Such a construction naturally describes the inclusion of the local attraction
basins present in the landscape. These studies investigate tree structures that ensure
a minimal correlation between the strength of the local optima and their proximity to
the global optimum, with respect to an ultra-metric distance on the tree. However,
from a practical point of view, the tree describing the repartition of local optima is
unknown and too expensive in terms of computational cost to determine for a given
landscape.
The lack of an e-cient method at reasonable cost that allows one to characterize
a given landscape, motivates the construction of heuristics for extracting a priori
statistical information about landscape di-culty, for example based on random sampling
of the search space. We cite from the eld of evolutionary algorithms: Fitness
Distance relations, rst proposed in [8] and successfully used to choose problem dependent
random initialization procedures [11, 14]; Fitness Improvement of evolution
operators, rst proposed in [5], then extended and successfully used to choose binary
crossover operators [12] and representations [9]. However, even if such heuristics can
guide the a priori choice of some EA parameters, they do not give signicant information
about landscape structure, for instance, recent work suggests that very dierent
landscapes (leading to dierent EA behaviors) can share the same tness distance
relation [18, 10]. Further, the e-ciency of such summary statistics is limited to the
sampled regions of the space, and therefore does not necessarily help the long term
convergence results as implicitly illustrated in [12] for example. This gives strong
motivation for developing tools that allow one to derive a more global (beyond the
sampled regions) information on the landscape at hand, relying on an implicit assumption
of stationarity of the landscape. Along that line, this paper proposes a new
method to identify the number and the repartition of local optima with respect to
a given neighborhood relation of a given landscape. The proposed method applies
to any neighborhood relation specied with a modication operator, and hence provides
a practical tool to compare landscapes obtained with dierent operators and
representations.
The framework is the following. We assume that the search space E can be split
into the partition E 1 ,.,E N of subspaces which are attraction basins of local maxima
of the tness function. We also assume that there exists a local search
algorithm (for example a steepest ascent) which is able to nd from any point of the
search space the corresponding local maximum:
The basic problem consists in detecting all local maxima m j . This is equivalent
to nding a way to put a point in all attraction basins because the local search
algorithm will complete the job. We shall develop the following strategy. First we
shall study the direct problem, which consists in studying the covering of the search
space by a collection of points randomly distributed when the partition
Second we shall deal with the inverse problem which consists in estimating the number
of local maxima from information deduced from the covering.
Direct problem (Section 4): One puts M points randomly in the search space.
The question is the following: Given the statistical distribution of the relative sizes of
E-ciency of local search with multiple local optima 3
Fig. 1. Schematic representations of the search space E with
points have been randomly placed on both pictures. As a result there is at least one point in each
attraction basin in the left picture, but not in the right picture, where E 4 is empty.
the attraction basins and their number N , what is the probability pN;M that at least
one point lies in every attraction basin ? This probability is very important. Indeed,
using the local search algorithm, it is exactly equal to the probability to detect all
local maxima of the function.
Inverse problem (Section 5): The statistical distribution of the relative sizes of
the attraction basins and their number are assumed to be known for computing pN;M
in Section 4. Unfortunately, this is rarely the case in practical situations, and one
wants to estimate both. The strategy is to put randomly M initial points in the search
space and to detect the corresponding local maxima by the local search algorithm.
The data we collect is the set ( j ) j1 of the number of maxima detected with j initial
points. Of course  0 is unknown (number of local maxima of the landscape that have
not been detected). The question is the following: How can the total number of local
e-ciently estimated from the set lower bound
is
but we aim at constructing a better estimator.
The paper is divided into three parts. First, Section 4 addresses the direct problem
of sample sizing in the case of basins of random sizes then in the case of basins of
equal sizes. Second Section 5 is devoted to the estimation of the distribution of
the relative basins sizes for an unknown landscape, using a random sample from the
search space. This is achieved by a two step methodology: Section 5.2 starts by
considering a parametrized family of laws for the relative sizes of basins, for which
it derives the corresponding covering of the search space (law of ( j )). Then Section
5.3 comments on how these results can be practically used for characterizing the
sizes of basins of an unknown landscape. For instance, it proposes to compare the
covering of an unknown landscape (given by the empirically observed ( j ) values) to
the coverings studied in Section 5.2. Finally, the last part of the paper (Section
devoted to some experiments that validate (Section 6.1) and illustrate (Section 6.2)
the methodology: First, a landscape is purposely designed to test the reliability of the
method according to the size of the random sample, and to the number of local optima
(recall the theoretical results are asymptotic with respect to N and M ). Second, the
method is used to investigate some problems, known to be di-cult to optimize for
EAs. For each problem, we also compare the landscapes related to dierent mutation
operators.
2. Notations and Denitions. Consider a tness f R, and a neighborhood
relation induced by a modication operator , such that the number of dierent
-neighbors (neighbors that can be obtained by one application of  to x) of x
is 'bounded'. In the following, we denote by N the number of local optima of L,
4 J. Garnier and L. Kallel
and by ( j ) the random variables describing the sizes of the attraction basins of L
(normalized to the average size). As shown in [23, 24], a local improvement algorithm
is e-cient to nd quickly a local optimum starting from some given point. Among the
possible algorithms we present the Steepest Ascent (SA) also called optimal adjacency
algorithm in [23]:
Steepest Ascent Algorithm (SA).
Input: A tness R, an operator  and a point X 2 E.
Algorithm: Modify X by repeatedly performing the following steps:
- Record, for all -neighbors of X denoted by  i (X): (i; f( i (X)))
chosen such that f( i (X)) reaches the highest
possible value (this is the steepest ascent).
- Stop when no strictly positive improvement in -neighbors tnesses has been
found.
Output: The point X, denoted by  SA (X).
The SA algorithm thus consists in selecting the best neighbors after the entire
neighborhood is examined. An alternative algorithm, the so-called First Improvement
consists in accepting the rst favorable neighbor as soon as it is found, without
further searching. Note that in the FI case there are extra free parameters which are
the order in which the neighborhood is searched. As pointed out in [15, p. 470], the
steepest ascent is often not worth the extra computation time, although it is sometimes
much quicker. Nevertheless our focus in this paper is not a complete optimization of
the computational time, so we let this problem as an open question.
Definition 2.1. Attraction basin: The attraction basin of a local optimum m j is
the set of points of the search space such that a steepest ascent algorithm
starting ends at the local optimum m j . The normalized size of
the attraction basin of the local optimum m j is then equal to k=jEj.
Remarks.
1. This denition of the attraction basins yields a partition of the search space into
dierent attraction basins, as illustrated in Figure 1. The approach proposed in this
paper is based on this representation of the search space into a partition of attraction
basins, and could be generalized to partitions dened with alternative denitions of
attraction basins.
2. In the presence of local constancy in the landscape, the above denition of the
steepest ascent (and hence also the related denition of the attraction basins) is not
rigorous. For instance, if the ttest neighbors of point p have the same tness value,
then the steepest ascent algorithm at point p have to make a -random or user dened-
choice. Nevertheless, even in the presence of local constancy, the comparison of the
results (distribution of ( j obtained with dierent steepest ascent choices, may give
useful information about the landscape and guide the best elitism strategy: 'move' to
tter points, or 'move' to strictly tter points only.
3. Summary of the results. Given a distribution of ( j ), we determine Mmin ,
the minimal size of a random sample of the search space, in order to sample at least one
point in each attraction basin of the landscape. Two particular cases are investigated.
1. Deterministic conguration: all the attraction basins have the same size (( j )
are deterministic).
2. Random conguration: the sizes of the attraction basins are completely random
are uniformly distributed).
In both congurations, we give the value of Mmin as a function of the number of
local optima N . For instance, a random sample of size
E-ciency of local search with multiple local optima 5
*m
*m
*m
*m
Fig. 2. Schematic representation of the search space E with its attraction basins and
the 4 corresponding local maxima m 1 ,.,m 4 . In the left picture we have put randomly
chosen. We apply the search algorithm and detect 3 maxima according to the right picture, so that
we have  5.
the deterministic conguration (resp. for the random conguration),
ensures that a point is sampled in each attraction basin with probability exp( 1=a).
We then address the inverse problem of identifying the distribution of the normalized
of the attraction basins, for an unknown landscape. Some
direct analysis is rst required as discussed below.
Direct analysis. Consider a random sample (X uniformly chosen in the
search space. For each steepest ascent starting from X i (with the
modication operator(s) at hand ) ends at the local optimum  SA (X i ). Dene  j
as the number of local optima (m : ) that are reached by exactly j points from (X i )
(see an example in Figure 2):
Proposition 5.1 gives the distribution of ( j ) for a family of parametrized distributions
for asymptotically with respect to N and M . More precisely, if (Z j ) j=1;:::;N
denotes a family of positive real-valued independent random variables with Gamma
distributions whose densities are:

z
and
, then the expected number  j;
(j
a j

a=M=N
Moreover, the ratio M=N is the unique solution of:
r
(1)
The latter equation is then used to nd a good estimator of N , with observed values
of the variables  j , as explained below.
Inverse problem. Given an unknown landscape, we then propose to characterize
the distribution of ( j ) through the empirical estimation of the distribution of the
random family ( j ). In fact, by construction, the distribution of ( j ) and that of
6 J. Garnier and L. Kallel
are tightly related: We experimentally determine observed values taken by
(random sampling and steepest ascent search). Then, for each
value, we use a  2
test to compare the observed law for to the law  should (theoretically) obey if
the law of ( j ) were Law
. Naturally, we nd a (possible) law for only if
one of the latter tests is positive. Otherwise, we only gain the knowledge that
does not obey the law Law
. Note also that the method can be used to determine
sub-parts of the search space with a given distribution for ( j ). In case the law of
, Eq. (1) is used to nd a good estimator of N .
Last, Section 6 validates the methodology of Section 5, by considering known landscapes
with random and deterministic sizes of basins, showing that the estimations of
the number of local optima N are accurate, even if M is much smaller than N . Fur-
ther, we apply the methodology on unknown landscapes, and show that the Hamming
binary and gray F1 landscapes contain much more local optima than the 3-bits-
ip
landscapes.
4. Direct problem. We assume that the search space E can be split into the
partition of subspaces which are attraction basins of local maxima m 1 ,.,m N
of the tness function. Let us put a sample of M points randomly in the search space.
We aim at computing the probabilities pN;M that at least one point of the random
sample lies in each attraction basin.
Proposition 4.1. If we denote by  j := jE j j=jEj the normalized size of the j-th
attraction basin, then:
(2)
Proof. Let us denote by A j the event:
there is no point in
The probability of the intersection of a collection of events A j is easy to compute. For
any 1  there is one initial point chosen uniformly in E
then we have
If there are M initial points chosen uniformly and independently in E, then:
On the other hand, 1 pN;M is the probability that at least one of the attraction
basin contains no point, which reads as:
The result thus follows from the inclusion-exclusion formula [28, Formula 1.4.1a].
Proposition 4.1 gives an exact expression for pN;M which holds true whatever
but is quite complicated. The following corollaries show that the
expression of pN;M is much simpler in some particular congurations.
Corollary 4.2. 1. If the attraction basins all have the same size  j  1=N (the
so-called D-conguration), then:
E-ciency of local search with multiple local optima 7
2. If moreover the numbers of attractors and initial points are large N  1 and
3. Let us denote by MD the number of points which are necessary to detect all local
maxima. Then in the asymptotic framework N  1, MD obeys the distribution of
where Z is an exponential variable with mean 1.
An exponential variable with mean 1 is a random variable whose density with respect
to the Lebesgue measure over R + is
Proof. The rst point is a straightforward application of Proposition 4.1. It is
actually referenced in the literature as the \coupon-collector" problem. The fact that
MD =(N ln N) converges in probability to 1 is also well-known. The corollary is going
one step further by exhibiting the statistical distribution of M d N ln N . Let us
assume that We begin by establishing an estimate
of
First note C k
Second ln(1 x)  x for any 0  x  1 so that
As a consequence, uniformly with respect to
e:
We thus have
pN;M;k  ea k =k! for all k uniformly with respect to N .
Choosing some K  1, we can write from Eq. (3):
pN;M
eX
a k
It is easy to check that, for any xed k: N k C k
as N !1, so that:
lim sup
pN;M
eX
a k
This holds true for any K, so that we take the limit K ! 1 which gives the result
of the second point. The third point then follows readily from the identity P(M d
stands for the integral part of the real number x.
8 J. Garnier and L. Kallel
Corollary 4.3. 1. If the sizes of the attraction basins are random (the so-called
R-conguration), in the sense that their joint distribution is uniform over the simplex
of
and the numbers of attractors and initial points are large: N  1 and
a > 0, then:
2. Let us denote by MR the number of points which are necessary to detect all local
maxima. Then in the asymptotic framework N  1, MR obeys the distribution of
where Z is an exponential variable with mean 1.
A construction of the R-conguration is the following. Assume that the search
space E is the interval [0; 1). Choose N 1 points (a i uniformly over [0; 1]
and independently. Consider the order statistics (a (i) ) i=;1;:::;N 1 of this sample, that
is to say permute the indices of these points so that a (0) := 0  a (1)  :::
a (N 1)  a (N) := 1. Denote the spacings by  a (j) a (j 1) for
Note that  j is also called the j-th coverage. If the j-th attraction basin E j is the
interval [a (j 1) ; a (j) ), then the sizes of the attraction basins
obey a uniform distribution over the simplex SN .
Proof. From Eq. (2) and the relation
stands for the expectation with respect to ( j ) j=1;:::;N whose distribution is
uniform over SN . As pointed out in Ref. [28, Section 9.6a], the probability distribution
of the sum of any k of the N coverages  j is described by the repartition function
given by Formula 9.6.1-[28], which shows that it admits a density q N;k () with respect
to the Lebesgue measure over [0; 1]:
We can thus write a closed form expression for
E-ciency of local search with multiple local optima 9
We shall rst prove an estimate of pN;M;k .
Step 1. pN;M;k k!
We have N !=(N k)!  N k and (N 1)!=(N k 1)!  (N 1) k  N k . For
any k = 0; :::; N we also have (M +N 1 k)!=(M +N 1)!  M k . Substituting
these inequalities into Eq. (9) establishes the desired estimate.
Step 2. For any xed k, if
On the one hand, C
On the other hand:
is bounded by 1 and converges to exp( as) as N ! 1,
the dominated convergence theorem implies that:
which yields the result by Eq. (8).
Step 3. Convergence of pN;M when
We rst choose some K  1. We have from the result of Step 1:
pN;M
X
Substituting the result of Step 2 into Eq. (10) shows that:
lim sup
pN;M
X
a k
This inequality holds true for any K, so letting K ! 1 completes the proof of the
corollary.
It follows from the corollaries that about N ln N points are needed in the D-
conguration to detect all maxima, while about N 2 points are needed to expect the
same result in the R-conguration. This is due to the fact that there exists very small
attraction basins in the R-conguration. Actually it can be proved that the smallest
attraction basin in the R-conguration has a relative size which obeys an exponential
distribution with mean N 2 (for more detail about the asymptotic distribution concerning
order statistics we refer to [28]). That is why a number of points of the order
of N 2 is required to detect this very small basin.
Mean values. The expected value of MD is:
where C is the Euler's constant whose value is C ' 0:58. The expected value of
MR =N 2 is equal to innity. This is due to the fact that the tail corresponding to
exceptional large values of MR is very important:
P(MR  N 2 a)
J. Garnier and L. Kallel
Standard deviations. The normalized standard deviation, which is equal to the
standard deviation divided by the mean, of the number of points necessary to detect
all local maxima in the D-conguration is equal to:
which goes to 0 as which proves in particular that MD =(N ln N) converges
to 1 in probability. This is of course not surprising. The D-conguration
has a deterministic environment, since all basins have a xed size, so that we can
expect an asymptotic deterministic behavior. The situation is very dierent in the
R-conguration which has a random environment, and it may happen that the smallest
attraction basin be much smaller than its expected size N 2 . That is why the
uctuations of MD , and especially the tail corresponding to exceptional large values,
are very important.
5. Inverse problem.
5.1. Formulation of the problem. We now focus on the inverse problem. We
look for the number N of local maxima of the tness function and also some pieces
of information on the distribution of the sizes of the corresponding attraction basins.
We assume that we can use an algorithm that is able to associate to any point of the
search space the corresponding local maximum. In order to detect all local maxima,
we should apply the algorithm to every point of the search space. Nevertheless this
procedure is far too long since the search space has a large cardinality. Practically
we shall apply the algorithm to M points that will be chosen randomly in the search
space E. The result of the search process can consequently be summed up by the
following set of observed values (j  1):
number of maxima detected with j points:
Our arguments are based upon the following observations. First note that
is the number of detected maxima. It is consequently a lower bound of the
total number of local maxima N , but a very rough estimate in the sense that it may
happen that many maxima are not detected, especially those whose attraction basins
are small. Besides
N represents less information than the complete set ( j ) j1 . By
a clever treatment of this information, we should be able to nd a better estimate of
than
N .
5.2. Analysis. The key point is that the distribution of the set  j is closely
related to the distribution of the sizes of attraction basins. Let us assume that the
relative of the attraction basins can be described by a distribution
parametrized by some positive number
as follows. Let (Z j ) j=1;:::;N be a sequence of
independent random variables whose common distribution has density p
with respect
to the Lebesgue measure over (0; 1): 2

where is the Euler's Gamma function
dt. The density p
is the
so-called Gamma density with parameters (
is a positive integer then p
is a negative-binomial distribution.
E-ciency of local search with multiple local optima 11
z
Fig. 3. Probability density of the sizes of the attraction basins under H
for dierent
the expected value of Z 1 is 1 and its standard deviation is 1= p
. In the following we
shall say that we are under H
if the relative sizes of the attraction basins
can be described as (Z 1
and the distribution
of Z j has density p
. Note that the large deviations principle (Cramer's theorem
[1, Chapter 1]) applied to the sequence (Z j ) yields that for any x > 0 there exists
c
TN
exp( Nc
which shows that, in the asymptotic framework N  1, the ratio Z j =N stands for the
relative size  j up to a negligible correction. The so-called D and R congurations
described in Section 4 are particular cases of this general framework:
- For
so that we get back the deterministic D-
- For
1, the Z j 's obey independent exponential distributions with mean 1, and
the family  obeys the uniform distribution over SN [17].
The important statement is the following one.
Proposition 5.1. Under H
the expected values  j;
of the  j 's can
be computed for any N , M , and
In the asymptotic framework N  1, if
can be expanded as:
(j
a j

Proof. Under H
, the probability that j of the M points lie in the k-th attraction
basin can be computed explicitly:
(j points in E k
3 Applying the procedure described in [1] establishes that c
J. Garnier and L. Kallel
stands for the expectation of Z j with distribution p
.
Accordingly, in terms of the Z i 's this expression reads:
(j points in E k
where
. The random variables Z k and
Z k are independent. The probability
density of Z k is p
given by Eq. (12). The random variable
Z k is the sum of
independent random variables with densities p
, so that its probability density
is [4, p. 47, Formula 2.3]:
z (N 1)
Accordingly:
(j points in E k
Z 1dz
Z 1dzp
(z)p
z
By the change of variables
z) and
z we get:
(j points in E k
Z 1du
Z 1dvv N
The integral with respect to v is straightforward by denition of the Gamma function.
The integral with respect to u can be obtained via tabulated formulae [4, p. 47, formula
2.5]. This gives the explicit formula (14) for  j;
since
(j points in E
If N  1 and then we have N
(N

a) j+
, and N j M !=(M j)! ! a j as
N !1. This proves the asymptotic formula (15).
In particular, the distribution of the  j 's under the D-conguration is Poisson in
the asymptotic framework N  1:
while it is geometric under the R-conguration:
From Eq. (15) we can deduce that the following relation is satised by the ratio
r
E-ciency of local search with multiple local optima 13
5.3. Estimator of the number of local maxima. We have now su-cient
tools to exhibit a good estimator of the number of local maxima. We remind the reader
of the problem at hand. We assume that some algorithm is available to determine from
any given point the corresponding local maximum. We choose randomly M points in
the search space and detect the corresponding local maxima. We thus obtain a set
of values ( j ) j1 as dened by (11). We can then determine from the set of values
0 is the most probable, or at least which H
0 is the
closest conguration of the real underlying distribution of the relative sizes of the
attraction basins. The statistics used to compare observed and expected results is the
so-called  2 goodness of t test [27, Section 8.10], which consists rst in calculating
for each
where
is the set of the indices j for which  j  1. Obviously a
large value for T
indicates that the corresponding  j;
are far from the observed ones,
that is to say H
is unlikely to hold. Conversely, the smaller T
, the more likely H
holds true. In order to determine the signicance of various values of T : , we need the
distribution of the statistics. A general result states that if the hypothesis H
does
hold true, then the distribution of T
0 is approximatively the so-called  2 -distribution
with degrees of freedom equal to the cardinality of the
set
minus 1. Consequently
we can say that the closest conguration of the real underlying distribution of the
relative sizes of the attraction basins is H
0 is given by:
Furthermore, we can estimate the accuracy of the conguration H
0 by referring T to tables of the  2 -distribution
1 degrees of freedom. A value of T much larger than the one indicated in the tables mean that none of the congurations
hold true. Nevertheless, H
0 is the closest distribution of the real one.
Remark. The distribution theory of  2 goodness of t statistic can be found in
[3, Chapter 30]. The result is in any case approximate, and all the poorer as they are
many expected  j;
less than ve. These cases must be avoided by combining cells.
But power in the tail regions is then lost, where dierences are more likely to show up.
Dening
0 as (17), we denote by
the quantity:
From Eq. (16), under H
0 the ratio M=N is the unique solution of:
Consequently, once we have determined
is a good estimator of the
14 J. Garnier and L. Kallel
gc
Simul. 3
Nb.
of
optima
9100Estimated
Visited
Exact
gc
Simul. 3
Nb.
of
optima
91000Estimated
Visited
Exact
Fig. 4. Basins with random uniform sizes: The left gures plot the  2 test results (i.e. the
values of T
comparing the empirically observed  distribution to the family of
-parametrized
distributions. The right gures plot for dierent
values the estimation of the number of local
optima computed by Eq. (18). These estimations are very robust (only one estimation is plotted)
and are accurate for
1. The same gures also show the visited numbers of optima actually
visited by the steepest ascent (
The numerical simulations exhibit unstable results
for the  2 test for small N values and
6. Experiments. Given a landscape L, the following steps are performed in
order to identify a possible law for the number and sizes of the attraction basins of
L, among the family of laws Law
studied above.
1. Choose a random sample (X uniformly in E.
2. Perform a steepest ascent starting from each X i up to  SA (X i ).
3. Compute dened as the number of local optima reached by exactly j initial
points X i .
4. Compare the observed law of  to the laws of (
dierent
values, using
the  2 test.
To visualize the comparison of the last item, we propose to plot the obtained  2
value for dierent
values. We also plot the corresponding  2 value below which the
test is positive with a condence of 95 %.
6.1. Experimental validation. The results obtained in Section 5 are asymptotic
with respect to the number of local optima N and the size of the random sample
M . Hence before the methodology can be applied, some experimental validation is
required in order to determine practical values for M and N for which the method is
reliable. This is achieved by applying the methodology to determine the distribution
of (normalized sizes of the attraction basins) in two known purposely constructed
landscapes: The rst contains basins with random sizes, the second contains basins
with equal sizes.
Results are plotted in Figures 4-5 and 6. Samples with smaller sizes than those
shown in these gures yield  j values which are not rich enough to allow a signicant
E-ciency of local search with multiple local optima 15
gc
Simul. 3
Nb.
of
optima
9100Estimated
Visited
Exact
gc
Simul. 3
Nb.
of
optima
Estimated
Visited
Exact
gc
Simul. 3
Nb.
of
optima
Estimated
Visited
Exact
Fig. 5. The same as in Figure 4 with dierent values for N and M . Stable results are obtained
when N increases and M is bounded (M  min(2000; 3N) here). The estimation of N corresponding
to the smallest  2 value (
very accurate.
test comparison. For instance, the  2 test requires that observed  j are non-null for
some j > 1 at least (some initial points are sampled in the same attraction basin). In
case all initial points are sampled in dierent attraction basins the  2 test comparison
is not signicant.
These experiments give practical bounds on the sample sizes (in relation to the
number of local optima) for which the methodology is reliable: The numerical simulations
exhibit unstable results for the  2 test for
4). When N increases and M is bounded (M  min(2000; 3N) in the experiments),
results become stable and accurate (Figures 5). Further, we demonstrate that the estimation
of number of local optima is accurate, even when initial points visit a small
number of attraction basins of the landscape (Figure 6). This situation is even more
striking in the experiments of the following section on Baluja F1 problems.
6.2. The methodology at work. Having seen that the methodology is a powerful
tool, provided that the information obtained for  is rich enough, we apply it to
investigate the landscape structure of the di-cult gray and binary coded F1 Baluja
problems [2], for a 1-bit-
ip and 3-bit-
ips neighborhood relations.
J. Garnier and L. Kallel
gc
Simul. 3
Nb.
of
optima
Estimated
Visited
Exact
gc
Nb.
of
optima
Estimated
Visited
Exact
2:
log
scale
c
N=10^5, M=500
Nb.
of
optima
3.
Estimation 1
Estimation 2
Visited
Exact
N=10^5, M=500
Fig. 6. Basins with Deterministic equal sizes: The  2 results are stable for smaller sample
sizes than those of the random conguration. The bottom gures correspond to the case
and 500, where the  2 test is not signicant, yet the predicted number of local optima is very
accurate! With 500 initial points, 497 local optima have been visited, while there are actually 10 5
optima. Yet, formula (18) is able to estimate the true number with an error of less than 30% when
the adequate
value is used.
Gray-coded Baluja F1 functions. Consider the function of k variables
It reaches its maximum value among 10 7 at point 0). The Gray-encoded F1g
and binary F1b versions, with respectively 2, 3 and 4 variables encoded on 9 bits are
considered. This encoding consequently corresponds to the binary search space with
Considering the 1-bit-
ip mutation (Hamming landscape), Figure 7 shows that
the distribution of the sizes of the basins is closer to the random conguration than
to the deterministic one, and that the estimated number of local optima is similar for
the binary and gray codings. On the other hand, considering the 3-bit-
ip mutation

Figure

8), the estimated number of local optima drops signicantly for both problems:
less than 250 for both binary and gray landscapes, whereas the Hamming landscape
E-ciency of local search with multiple local optima 17
gc
bits F1g, M=500
Nb.
of
optima
Estimated
Visited
bits F1g, M=500
gc
bits F1b, M=500
Nb.
of
optima
Estimated
Visited
bits F1b, M=500
Fig. 7. The di-cult Baluja 27-bits F1 gray (F1g) and binary (F1b) landscapes with a 1-bit-
ips
mutation. Experiments with samples of sizes show the same results for
the  2 test, and the corresponding estimations of the number of local maxima converge to a stable
value around 4000.
contains thousands of local optima (Figure 7).
Experiments at problem sizes l = carried out in addition
to the plotted ones (l = 27), leading to similar results for both F1g and F1b problems:
The number of local optima of the 3-bit-
ips landscape is signicantly smaller than
that of the Hamming landscape. For example, when there are less than 10
local optima in the 3-bit-
ips landscape versus hundreds in the Hamming landscape.
the estimations for the Hamming landscape show about two times more
local optima for the gray than for the binary encoding (resp. 45 000 and 25 000). Still
but for the 3-bit-
ips landscape, the estimated number of local optima
drops respectively to 1400 and 1000.
A new optimization heuristic. A simple search strategy for solving di-cult problems
naturally follows from the methodology presented in this paper: Once the number
N and distribution of the attraction basins is estimated following the guidelines
summarized in the beginning of Section 6, generate a random sample whose size is set
to if the sizes of the basins are close to the deterministic conguration
if the sizes of the basins are close to random). Then a simple steepest
ascent starting from each point of the sample, ensures that the global optimum is
found with probability exp( 1=a).
In the 27-bits F1 problem, this heuristic demonstrates to be very robust and ecient
in solving the problem with the 3-bits-
ip operator. Using a 3-bits-
ip mutation
steepest ascent, an initial random sample of 5 points (versus 100 with 1-bit-
ip mu-
tation) is enough to ensure that one point at least lies in the global attraction basin
(experiments based on 50 runs)! This is due to the fact that the basin of the global
optimum is larger than the basins of the other local optima. In order to detect all
attraction basins, we can estimate the required sample size to 62500 (250  250 using
Corollary 4.3 and the estimation of in the experiments of Figure 8).
J. Garnier and L. Kallel
gc
Nb.
of
optima
Visited
bits F1g, M=500
gc
bits F1b, M=500
Nb.
of
optima
Exact
bits F1b, M=500
Fig. 8. The di-cult Baluja 27-bits F1 gray (F1g) and binary (F1b) landscapes with a 3-
bit-
ips mutation: the number of local optima drops signicantly compared to the Hamming 1-bit-
ip landscape. These results are conrmed by experiments using samples of sizes 2000 and
which give the same estimation for the number of local optima.
6.3. Discussion. This paper provides a new methodology allowing to estimate
the number and the sizes of the attraction basins of a landscape specied in relation to
some modication operator. This allows one to derive bounds on the probability that
one samples a point in the basin of the global optimum for example. Further, it allows
to compare landscapes related to dierent modication operators or representations,
as illustrated with the Baluja problem.
The e-ciency of the proposed method is certainly dependent on the class of laws
of of the attraction basins) for which the distribution of  is known. We
have chosen a very particular family of distributions p
for representing all possible
distributions for the relative sizes of attraction basins. The constraints for this choice
are twofold and contradictory. On the one hand, a large family of distributions is
required to be sure that at least one of them is su-ciently close of the observed
repartition On the other hand, if we choose an over-large family, then we need a
lot of parameters to characterize the distributions. It is then very di-cult to estimate
all parameters and consequently to decide which distribution is the closest to the
observed one. That is why the choice of the family is very delicate and crucial.
We feel that the particular family p
that has been chosen (12) fullls determinant
conditions. First it contains two very natural distributions, the so-called D and R
congurations that we have studied with great detail. Second it is characterized by
a single parameter easy to estimate. Third it contains distributions with a complete
range of variances, from 0 (the D-conguration) to innity, by going through 1 (the
R-conguration).
However, the experiments with the Baluja problem, appeal for rening the class
of laws of ( j ) around basins with random sizes. We may propose
where Z j are independent and identically distributed with one of the distributions of
E-ciency of local search with multiple local optima 19
the bidimensional family p
;- (:),
The parameter - characterizes the distribution of the sizes of the small basins, since
;- (z)  z - 1 as z ! 0, while
characterizes the distribution of the sizes of the
large basins, since the decay of p
;- (z) as z !1 is essentially governed by e
z . The
density p
;- is the so-called Gamma density with parameters (
2.2]. This family presents more diversity than the family p
(:) we have considered in
Section 5.2. The expected value of  j is under p
(j
a j
a=M=N
The method of estimating the number of local minima described in Section 5.3 could
then be applied with this family.
To apply our method we have also made a crucial choice which consists in executing
the local search algorithm from randomly distributed points. We do so because we
have no a priori information on the landscape at hand. However, assume for a while
that we have some a priori information about the tness function, for instance its
average value. Consequently we could hope that starting with points whose tnesses
are better than average would improve the detection of the local maxima. Nevertheless
extensive computer investigations of some particular problems have shown that
this is not the case [15, p. 456], possibly because a completely random sampling of
starting points allows one to get a wider sample of local optima.
A rst application of the methodology presented in this paper is to compare
landscapes obtained when dierent operators are used (k-bit
ip binary mutations for
dierent k values for example). However, the complexity of this method is directly
related to size of the neighborhood of a given point. Hence, its practical usefulness
to study k-bit-
ip landscapes is limited when k value increases. Hence, it seems
most suited to investigate dierent representations. Its extension to non-binary representations
is straightforward, provided that a search algorithm that leads to the
corresponding local optimum can be provided for each representation. Further, this
methodology can be used to determine sub-parts of the search space, such that
obey a particular law, hence guiding a hierarchical search in dierent subparts of the
space.
Note nally that the distributions of the sizes of basins do not fully characterize
landscape di-culty. Depending on the relative position of the attraction basins, the
search still may range from easy to di-cult. Additional information is necessary
to compare landscapes di-culty. Further work may address such issues to extract
additional signicant information in order to guide the choice or the design of problem
dependent operators and representations.



--R

Grandes d
An empirical comparison of seven iterative and evolutionary function optimization heuristics
Mathematical methods of statistics
An introduction to probability theory and its applications

Genetic algorithms in search
Adaptation in natural and arti
Fitness distance correlation as a measure of problem di-culty for genetic algorithms
Convergence des algorithmes g
On functions with a
Alternative random initialization in genetic algorithms
A priori predictions of operator e-ciency
The genetic algorithm and the structure of the
Memetic algorithms and the
Algorithms and com- plexity
Spin glass theory and beyond


Ultrametricity for Physicists
Genetic algorithms
Complex systems and binary networks
Landscapes and their correlation functions
Local improvement on discrete structures
Hill climbing with multiple local optima
Theory and Applications
Correlated and uncorrelated
Chapman and Hall
Mathematical statistics
--TR

--CTR
Sheldon H. Jacobson , Enver Ycesan, Analyzing the Performance of Generalized Hill Climbing Algorithms, Journal of Heuristics, v.10 n.4, p.387-405, July 2004
combinatorial complexity;neighborhood graph;local search;randomized starting solution